33

I am struggling to understand what is meant by "standard cryptographic assumption". ‘Standard assumption’ broadly means an assumption that has withstood the scrutiny of many smart cryptanalysts for a long time. Examples: We think that, for uniform random 1024-bit primes $p$ and $q$, solving $y = x^3 \bmod pq$ for uniform random $x$ is hard given $pq$ and $...


26

TL;DR; Just give me the numbers; \begin{array} {|l|c|c|c|c|}\hline & \text{in a second} & \text{in an hour} & \text{in a day} & \text{in a year} \\ \hline \text{Summit on SHA-1} & \approx 2^{49.7} & \approx 2^{61.5} & \approx 2^{66.1} & \approx 2^{74.6} \\ \hline \text{Titan on SHA-1} & \approx 2^{49.1}& \approx ...


22

What makes a problem suitable for cryptography is slightly different than what makes a problem NP-hard. What is required for cryptography is average-case hardness --- i.e., a randomly selected instance of a problem should be "hard" for an adversary to solve. However, random instances of some NP-hard problems (3SAT, e.g.) turn out to be easy with high ...


21

Definitions: An algorithm is said to run in logarithmic time if $T(n) = O(log(n))$ polylogarithmic time if $T(n) = O(log(n)^k)$ (also written as $T(n) = O(log^k(n))$) That means they are the same for $k=1$. Otherwise they are different and your other examples are all polylogarithmic. I'm not sure how exactly to explain what the difference is but maybe a ...


19

There is a huge difference between $2^{-64}$ probability of failure, which is indeed very small, and having to run $2^{64}$ in order to carry out the attack. The latter is much too small to be considered reasonable. Of course, one could argue about protecting secrets that are not very significant and you only need weak protection. However, it is usually very ...


15

Proving P=NP would not necessarily give you an algorithm, because there are many different methods to prove something (i.e. Direct proof, Proof by contradiction, etc.). But it is shown that if you were to find a polynomial time algorithm to solve a NP-complete problem that you could modify that algorithm to solve all NP-problems, including the Integer ...


14

Decrypt the ciphertext with every possible key and store the result: $2^{56}$ decryptions. Now encrypt the (known) plaintext of the ciphertext with every possible key: $2^{56}$ encryptions. Now you have to check every entry, which is in both lists and try it with another plaintext-ciphertext pair. If you can successfully decrypt that, you are very likely to ...


14

Suppose you have an $n$-bit key. Suppose further you have some reliable predicate $P(k,m)$ which decides whether a key $k$ is the key you are looking for given the reference $m$. Furthermore, suppose you have a "successor" function $F$, that takes a key and returns you the "next" key so that eventually all keys are traversed. Now what a brute-force attack ...


13

It mostly has to do with the real world influence of memory caches. A cache is a small amount of fast memory; when you read from memory, the contents are placed in this fast memory (possibly along with adjacent locations); if you read from the location again, you read it from the fast memory (which, of course, proceeds much faster). Hence, if you read a ...


12

Your observations are basically correct. Informally it is as follows: For a uniform PPT algorithm think of a fixed Turing machine that has access to some random tape and the output of the algorithm is a random variable. For non-uniform algorithms it is best to think of a family of circuits indexed by the length of the input (so for every input length the ...


11

There is no direct inference from $P = NP$ or $P \neq NP$ to security or insecurity of any particular encryption algorithm. As far as practical consequences are concerned, the "$P = NP$" problem is severely overhyped. If $P = NP$ then any problem for which a solution can be verified in polynomial time can also be solved in polynomial time. "Polynomial time" ...


11

Just looking for a Turing machine vs circuit is a bit misleading. The important distinction is uniform (complexity class BPP) vs non-uniform (complexity class P/poly) adversaries. You can characterize P/poly in terms of circuit families, but also in terms of Turing machines with arbitrary "advice strings." In fact, the latter is the more traditional ...


11

The Merkle–Hellman knapsack cryptosystem (Wikipedia article) is the canonical example of this. It was designed to rely on the difficulty of the subset sum problem, which is NP-complete. However, while NP-complete means, under the P ≠ NP hypothesis, that there is no polynomial-time algorithm to guarantee a solution for every input, that doesn't mean the ...


11

Bill Garsarch just posted about this the other day. The short answer is that there is an explicit algorithm, which is known today, such that if P = NP (or even just FACTORING ∈ P) then the algorithm solves factoring in polynomial time on all instances. However, this algorithm is utterly infeasible for real-world computation because it works by iterating ...


11

The reason is that essentially, the class of languages in $\mathcal IP$ that are not in $\mathcal NP$ cannot be proven with an efficient prover. Since we are typically interested in the cryptographic context with efficient provers, the study of ZK typically focuses on $\mathcal NP$. (Note that when studying complexity and often in foundations of cryptography,...


10

NP is about worst case hardness. An NP-hard problem can in fact be very easy to solve for the majority of cases. This would obviously be a poor cryptographic system. Further, some NP-hard problems may even be quite easy to approximate. This could also be bad for cryptography.


10

Whether P = NP is a question about the asymptotic growth of computational costs of algorithms as functions of input sizes. It may provide hints about concrete computational cost estimates of algorithms for specific input sizes, but doesn't provide answers. In the eyes of the asymptotic setting, an $O(n^{10000})$ cost is ‘smaller’ than an $O(1.0001^n)$ cost ...


10

The concept of language has been systematized. For example here you can become familiar with this in an accessible way. In the article you are reading the language has such meaning: Wikipedia BQP: A language L is in BQP if and only if and only if and only if there exists a polynomial-time uniform family of quantum circuits $\{Q_n:n \in \mathbb{N}\}$, ...


9

An algorithm being probabilistic means that it is allowed to "throw coins", and use the results of the coin throws in its computations. This is reasonable because a realistic adversary has access to certain pseudo-randomness sources (such as the C rand() function). Of course, a probabilistic algorithm is not required to use its randomness source (i.e., throw ...


9

First, it's not said that AES is unbreakable, merely that none of the currently known attacks reduce the computational cost to a point where it's feasible. The current best attack on AES-128 takes 2^126.1 operations, if we had a computer (or cluster) several million times more efficient than any current computer and could operate at the thermodynamic ...


8

I know an algorithm that runs in polynomial time would be able to break an RSA key pair "quickly". But how quickly is "quickly"? No way to say, it might be microseconds, and it might be large multiplies of the age of the universe. When we say that an algorithm runs in polynomial time, we're not saying anything about how fast the algorithm runs given any ...


8

Is the running times of corresponding steps true? No. Step 3 of the dealer has to be executed $n$ times (once for each party) with each execution taking $O(t)$ time. So it must be $O(t\cdot n)$. Step 4 of the dealer needs $O(n)$ to distribute each share to every party. I count $O(t\cdot n)$ as the overall time complexity for the dealer. Of course, you ...


8

Is AES solvable in this way? In other words, will the algorithm eventually complete, producing the correct key? Almost yes. It will produce some correct key — there might be more than one. (It should quite plausibly be unique given "enough" plaintext-ciphertext samples, but this need not be the case in general.) Generally, computing the key in a known-...


8

As @sejpm already hinted in his comment: both scale the same when it comes to the parameters. You might still want to read the RFC to get the complete picture, but the general differences can be quickly summarized: Argon2i Argon2i is invulnerable to side-channel timing attacks, but is weaker against time-memory trade-off (TMTO) attacks. Argon2i uses data-...


8

Maybe there is an encryption scheme out there that can be 'broken' in polynomial time, but only with super-polynomial space. That possibility can be excluded; if an algorithm uses $F(x)$ time (for any $F$), then that algorithm can be implemented using $O(F(x))$ space. The reason is fairly obvious; in $F(x)$ steps, the algorithm can access at most $\ell F(x)...


8

The focus on polynomial time comes from cryptography's historical origin as a branch of computational complexity. It makes sense for a theoretical field to develop technology-independent ways of measuring efficiency. Actual clock time or number of clock cycles are technology-dependent. Talking about running time in an asymptotic sense is convenient because ...


8

Yes, you are looking for the notion of a universal one-way function. Rafael Pass/abhi shelat's notes contain a construction on page 49. The construction is "unnatural" in the sense that it involves parsing the input to the OWF $y$ as a pair $\langle M\rangle || x$, where $\langle M\rangle$ is interpreted as the description of a Turing machine. Then ...


8

First, the wikipedia article stated that the assumption required a PRG with an exponential stretch. This is not correct, and I have edited the article. Rather, the requirement is for a PRG in $NC_0$ with super-linear stretch (i.e., stretching from $n$ to $n^{1+\tau}$ for any $\tau>0$). This is indeed not known, as far as I could ascertain from a brief ...


7

Actually, it's not true that public key encryption is based on Discrete Log; the ones in common use (DH, ECDH, ECDSA) are (and even RSA can be viewed as "based on Discrete Log", at least from the standpoint of "if you can solve the Discrete Log modulo a composite, you can break RSA"). However, we do have a number of public key systems (NTRU, McEliece) which ...


7

When $n$ is prime, solving for $e$-th roots modulo $n$ is easy, since it suffices to compute $d = e^{-1} \pmod {n-1}$ and then $s = m^d \pmod n$. If $n$ is not prime, but is instead a RSA modulus (a composite integer that is the product of two big primes), then the problem becomes apparently hard (in the sense that we don't have a clue how to do it ...


Only top voted, non community-wiki answers of a minimum length are eligible