We’re rewarding the question askers & reputations are being recalculated! Read more.
29

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 $...


20

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

TL;DR; Just give me the numbers; Summit can reach $\approx 2^{63}$ SHA-1 hashes around one hour, $\approx 2^{72}$ hashes in one year. Titan can reach $\approx 2^{63}$ SHA-1 hashes around two hours, $\approx 2^{71}$ hashes in one year. Bitcoin miners reached $\approx 2^{92}$ SHA-256 hashes per year in 06 Agust 2019. Performance Results of some GPU's On ...


17

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 ...


16

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

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

Most of these algorithms (i.e. the block ciphers DES, Triple DES, AES, Blowfish) are normally only working on a fixed block size, and take approximately the same time independently of input, thus they are $O(1)$. If you put them into a mode of operation to encrypt longer messages, you usually get an $O(m)$ complexity, where $m$ is the message size, as you ...


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

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. ...


12

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 ...


12

Let $n = \lceil \log q \rceil$ (with "$\log$" being the base-2 logarithm, so $n$ is the size, in bits, of $q$). If $q$ is a prime integer (i.e. $\mathbb{F}_q$ is the field of integers modulo $q$), then classical implementations will have cost $O(n)$ for addition and subtraction, $O(n^2)$ for multiplications and divisions. The cost of multiplications can be ...


12

Do the post-quantum ciphers also automag/tically address the 1st problem? Not really, however to explore that in any detail, we need to explore what the 1st problem is. If $P=NP$ is proven true, what does that practically mean? Well, it might have absolutely no practical ramifications, or it might mean that virtually all known cryptographical systems can ...


12

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 ...


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

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

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

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 ...


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

Well, if $q$ is a prime (and not $p^n$ with $n>1$), then addition, subtraction and multiplication can be performed by doing the traditional operations modulo $q$, that is: $a +_{\mathbb{F}_q}b \equiv (a+b) \bmod q$ $a -_{\mathbb{F}_q}b \equiv (a-b) \bmod q$ $a \times_{\mathbb{F}_q}b \equiv (a\times b) \bmod q$ As such, addition and subtraction can be ...


9

The last major effort I know of for cracking keys was the Distributed.net effort. You can find the project page at http://www.distributed.net/RC5/en. In 2002, they cracked a 64-bit RC5 key using at total of 331,252 computers over 1,757 days. Their maximum throughput was "equivalent to 32,504 800MHz Apple PowerBook G4 laptops or 45,998 2GHz AMD Athlon XP ...


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

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$ ...


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 ...


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