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

[Benjamin Kreuter]

On Mon, 2015-08-31 at 10:41 -0400, Erik Granger wrote:
> 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?

More worrying.  A scalable quantum computer would mean that
cryptosystems based on RSA and discrete logarithms (and related
assumptions), including elliptic curves, could not be considered secure.
It would mean almost all of the public-key crypto in use today would
need to be replaced.

The good news is that we have candidate cryptosystems that are secure
against quantum computers.  The bad news is that in many cases it is
unclear what the real security level of those systems is and performance
is a possible concern (huge public keys and sometimes lots of
computation).  We also do not have much real-world experience with those
cryptosystems.

Also, remember that the key word is *scalable*.  There are tons of
quantum computers out there, but none of them scale to arbitrarily large
problem sizes (not counting limited computers like D-wave, since that is
irrelevant to crypto).  We know how to increase key sizes arbitrarily,
so a quantum computer that does not scale is not hard to defeat.

-- Ben

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: This is a digitally signed message part
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150831/34a6efa3/attachment.sig>