1
$\begingroup$

I have heard that public key cryptography may be “totally broken” by Quantum computers running Shor’s algorithm, whils symmetric key ciphers are safe, but Grover’s algorithm may require twice as many bits in the keys.

Can someone please elaborate on what exactly is going on underneath, to say these things? What exactly does Shor’s algorithm do and how bad is it? How exactly are symmetric key ciphers not susceptible to this? How do we know we can’t do better than Grover’s algorithm later, making ALL ciphers susceptible? And finally, if you can fit it into your answer, what are the measures taken by the latest public key ciphers submitted to NIST that purport to overcome these problems?

$\endgroup$

migrated from security.stackexchange.com Apr 3 '18 at 8:17

This question came from our site for information security professionals.

  • 1
    $\begingroup$ This question may better belong in cryptography stackexchange so admins can migrate it. $\endgroup$ – Gregory Magarshak Apr 2 '18 at 15:31
  • 2
    $\begingroup$ This is also an extremely broad question, far beyond the normal scope of stackexchange questions. $\endgroup$ – Gordon Davisson Apr 2 '18 at 17:08
  • 1
    $\begingroup$ Shor's algorithm solves certain mathematical problems more efficiently than classical algorithms. Specifically, it solves integer factorization and the discrete log problem, which breaks RSA and DSA/DHE, respectively. Symmetric ciphers are not vulnerable to this because they do not rely on mathematical "hardness problems". We know for a fact that nothing can do better than grover's algorithm because all it does is allow searching a keyspace faster. The new NIST public key crypto simply uses hardness problems that cannot be cracked by a quantum computer (e.g. R-LWE). $\endgroup$ – forest Apr 3 '18 at 0:24
  • $\begingroup$ No worries here. I use fractal encryption with 2MB key. Shor's algorithm is about efficiency in solving various algorithms. $\endgroup$ – Overmind Apr 3 '18 at 5:11
  • 1
    $\begingroup$ @Overmind What in the world is fractal encryption? $\endgroup$ – forest Apr 3 '18 at 6:11
6
$\begingroup$

I have heard that public key cryptography may be “totally broken” by Quantum computers running Shor’s algorithm

Cryptosystems based on discrete logarithms and factoring are vulnerable to Shor's algorithm.

These cryptosystems do not comprise the entirety of "public-key cryptography", because "public-key cryptography" includes digital signatures, not just public-key encryption and key agreement.

The following types of cryptosystems are not completely broken by quantum algorithms:

So "public key cryptography is totally broken by quantum computers" is too broad of a conclusion.

It is more accurate to say "The most common schemes such as RSA, DH, and ECC are broken again quantum computers, but there are more schemes in existence then just those three."

...while symmetric key ciphers are safe, but Grover’s algorithm may require twice as many bits in the keys.

This is more or less accurate. There is some debate whether or not an actual doubling of key sizes is strictly necessary. And it should be noted that Grover's algorithm also influences hash functions.

Can someone please elaborate on what exactly is going on underneath, to say these things? What exactly does Shor’s algorithm do and how bad is it?

What does it do

Shor's algorithm uses a combination of a classical computation algorithm and the quantum fourier transform to factor numbers.

The problem of integer factorization is hard when the product to be factored consists of large prime numbers. A typical RSA modulus consists of two large prime numbers multiplied together $N = p * q$.

Shor's algorithm uses the quantum fourier transform to find how long it takes $f(x) = a^x \bmod N$ to cycle through all the possible outputs back to the beginning. So it looks for an $r$ such that $a^{x + r} \bmod N \equiv a^x \bmod N$, with the additional condition that $r$ is even so that $r/2$ can be obtained. The rest of the algorithm actually uses classical computation, finding the value of $r$ is the hard problem that the quantum algorithm solves. Finally, $gcd(a^{r/2} + 1, N)$ and $gcd(a^{r/2} - 1, N)$ are both nontrivial factors of $N$. (Where "nontrivial" means "not counting $1, N, -1, -N$", because those aren't helpful). The complete algorithm can be found in the wikipedia article about Shor's algorithm.

You can also use Shor's algorithm to compute discrete logarithms, which breaks Diffie-Hellman type cryptosystems. I don't understand the details of how to do so, so I will refrain from going into details.

How bad is it?

On a quantum computer, to factor an integer $N$, Shor's algorithm runs in polynomial time (the time taken is polynomial in $log\ N$, which is the size of the input)

It's bad. We really need the best attack to take exponential or at least sub-exponential time in order to have security with reasonable and practical sized values. A polynomial time algorithm for solving a problem basically makes that problem not useful for cryptography. Of course, you can technically try to use (much) larger parameters to make up for the difference... but that's not nearly as practical or graceful as we would like.

How exactly are symmetric key ciphers not susceptible to this?

The ability to find the period of a function is not necessarily useful for breaking a symmetric cipher. In order to do anything, you would need access to (at least) an encryption oracle. There is a paper about using Simon's algorithm to break symmetric modes of operation, but the attack model they use is pretty powerful: The adversary must prepare a superposition of all possible plaintext-ciphertext pairs, which is not trivial.

Basically, symmetric block ciphers and stream ciphers tend to use highly non-linear components which destroy any useful relations between inputs/outputs. Asymmetric designs tend to rely on such relations in order to achieve their goals. This means that asymmetric designs tend to incorporate more structure, and the structure can be exploited as a weakness.

How do we know we can’t do better than Grover’s algorithm later, making ALL ciphers susceptible?

Because it has been proven that:

...any quantum solution to the problem needs to evaluate the function $Ω(\sqrt{N})$ times, so Grover's algorithm is asymptotically optimal.

What are the measures taken by the latest public key ciphers submitted to NIST that purport to overcome these problems?

They are built on problems that are not known to be vulnerable to quantum algorithms. Using non-abelian groups seems to be helpful in regards to resisting quantum algorithms.

Note that "not known to be vulnerable" does not mean "It is proven that there cannot exist a quantum algorithm that solves the problem", it just means that there is no publicly known quantum algorithm for solving these types of problems.

$\endgroup$
  • 3
    $\begingroup$ Nit: while we know that Grover's algorithm is essentially optimal for solving the problem 'searching an oracle for a specific value', what is unproven is whether there's a more efficient attack against any specific primitive (which, of course, is not actually a random oracle). It is possible (i.e. not proven otherwise) that any efficiently computable algorithm can be attacked in more efficient ways. Such an eventuality would appear to be unlikely; however (with the current state of knowledge), it is not impossible. Of course, P=NP is not impossible either... $\endgroup$ – poncho Apr 3 '18 at 20:01
  • 1
    $\begingroup$ Regarding Simon's algorithm on symmetric constructions, it's not merely ‘not trivial’ for an adversary to learn a quantum superposition of secret function evaluations. Only an unbelievably deranged engineer would evaluate the secret function on a quantum computer in the first place. If they evaluate it only on a classical computer, as is the only sane thing to do, the attack model evaporates. It doesn't matter if the adversary has a quantum computer: it's the legitimate user who won't, barring spontaneous combustion of sanity, reveal quantum superpositions of secret function evaluations. $\endgroup$ – Squeamish Ossifrage Jun 8 '18 at 17:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.