[Cryptography] NSA looking for quantum-computing resistant encryption. How will encryption be affected by quantum computing

[Jerry Leichter]

> On Aug 31, 2015, at 10:41 AM, Erik Granger <erikgranger at gmail.com> wrote:
> 
> www.engadget.com/2015/08/30/nsa-quantum-resistant-encryption/ <http://www.engadget.com/2015/08/30/nsa-quantum-resistant-encryption/>
> I read this article and as a non-expert in quantum computing, I'm wondering what sort of impact quantum computing will have on our encryption. Will it just make brute forcing easier, thus requiring certificates to have a shorter shelf life? Or is it something more worrying? Less worrying?
> 
There are generic attacks, and there are attacks on specific techniques.

The best general attack known is Grover's algorithm, which allows you to search through N elements to find the one for which some predicate is true (e.g., the one encryption key that produces a known decrypted result) in O(sqrt(N)) time (as opposed to O(N) classical time).  There are some restrictions on the predicate, but it gets really complicated to determine with certainty what can and can't be computed this way (assuming, of course, you have a quantum computer!).  So it's probably safer to just assume that "brute force search on a quantum computer is O(sqrt(N))".  The net effect is that to retain the same level of security against brute force search that you had on a classical machine, you have to double the number of bits in your key.  This isn't all that big a deal:  No (classical) technology we can conceive of today could brute force an AES-128 key, so simply going to AES-256 gives you the same safety in a quantum world.

The specific attacks depend on the details of the cryptographic algorithm.  What got this whole field started is Shor's algorithm, which allows factoring on a quantum computer in polynomial time.  (The best known classical technique has exponential time complexity, though it's not actually known whether factoring can be done in classical polynomial time.)  The detailed numbers, again if one could build an appropriate quantum machine, would require that secure RSA keys be large enough to be impractical.  Related algorithms are effective against the Discrete Logarithm problem for integers mod N (used in Diffie-Hellman key exchange) and the related algorithms that use elliptic curves rather then integers mod N.  So most currently-used public key algorithms are attackable if quantum computers are practical.  (Just for comparison:  The current record for factoring an integer using a quantum computer is 56153, which you could factor by hand.  Then again, 20-odd years ago, we didn't know that quantum factoring algorithms existed, much less that they could be implemented at all, so we can't be smug about this - the field is evolving *very* rapidly.)

We have no idea whether there are specific quantum attacks against, say, AES.  It seems highly unlikely.  (The same is, in some sense, true of classical specific attacks against AES.  But the theory and experience in support of the claim that such a classical attack is highly unlikely is much better developed, and has been around a lot longer.)  If you're being paranoid, all you can really say is "we don't know"; but that doesn't give you much in the way of alternatives.
                                                        -- Jerry

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150831/78126ea7/attachment.html>