# Tag Info

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 ... 21 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 ... 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 ... 18 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 ... 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 A proof of P = NP would prove that one-way functions do not exist. That in turn would imply, that almost no secure cryptographic primitives can exist according to the accepted definitions of security. (No symmetric encryption, no MACs, no pseudorandom generators, no signature schemes, ...) However, it would just mean that no scheme can be provably secure. ... 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 There are techniques for doing online surveys on sensitive subjects. They don't follow the approach you outlined, but here's a sketch of how they work. Suppose we want to survey people to determine how many people have ever seriously considered suicide (say), but we suspect many people might be unwilling to answer honestly because of the stigma associated ... 13 Perfect secrecy is achievable in a few cases, such as one-time pads, and, well, that's pretty much it. Most cryptographic protocols are vulnerable to an all-powerful, all-knowing attacker. If you do not put any restriction on what the attacker can do, then Guess the key. Profit. breaks almost any cryptography, as does Wave a magic wand. Profit. So at the ... 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 ... 10 As you probably know$f(\lambda)=O(\lambda^4)$means that$|f|$asymptotically upper bounded by some constant times$\lambda^4$. The notation$f(\lambda)=\Omega(\lambda^4)$corresponds to an asymptotic lower-bound. Now, the$\tilde O$and$\tilde \Omega$are closely related notations, where we not only ignore constants but also values which are polynomial ... 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 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 Presumably, it's because they rounded it down to a nice round number of bits. Nobody's going to use an 86.76611925028119 bit key in practice, but an 80-bit key is plausible. Besides, the 86.whatever bit symmetric key length is only approximate, anyway: even using the GNFS, implementation details could easily swing it several bits either way, and of course, ... 9 What Dan Boneh says is not a formal definition as you want it. Let me quote Rogaway on this: In cryptographic practice, a collision-resistant hash-function (also called a collision-free or collision-intractable hash-function) maps arbitrary-length strings to fixed-length ones; it’s an algorithm$H:\{0,1\}^*\rightarrow \{0,1\}^n$for some fixed$n$... 9 Well, one assumption you appear to be making is that, with 2DES, there will be approximately$2^{56}$possible key matches. Actually, there are an expected$2^{48}$possible key matches; here's why: Let us assume we're running the meet-in-the-middle attack on 2DES, and consider an arbitrary incorrect encryption trial (that is, we try an encryption key that ... 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 ... 9 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 ... 8 I've previously answered this question over at How will security need to be changed if P=NP? (on our sister site, the IT Security Stack Exchange). In addition, see the answers to What would be the scenario if P = NP for RSA algorithm? for still more on the subject. The short answer is that a proof that P=NP doesn't necessarily mean that all cryptography is ... 8 I'll expand on the comment I left on my answer. The purpose of Part 2 of NIST SP 800-57 is to "[provide] guidance on policy and security planning requirements for U.S. government agencies". Keeping that in mind, the table on page 64, i.e. the table from whence the numbers in that question came, includes more than just RSA key sizes. Namely, it includes some ... 8 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 ... 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 ...