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

[Steve Weis]

On Mon, Aug 31, 2015 at 7:41 AM, Erik Granger <erikgranger at gmail.com> 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?

Here's a good summary on post-quantum crypto:
http://cr.yp.to/talks/2008.10.18/slides.pdf

I am not losing sleep over quantum computing, but it's prudent to have
some standards to fall back on. Academia has been having conferences
on post-quantum crypto (http://pqcrypto.org/) for 10 years, so the NSA
is not saying anything new or scary.

In terms of impact, large quantum computers will break public key
factoring-based cryptography (e.g. RSA), discrete logarithm-based
crypto (e.g. DSA), and elliptic curve crypto. Symmetric key algorithms
aren't directly broken, but may require doubling the key length to
maintain the same level of security.

Cryptosystems based on lattices, codes, hash functions, and
multivariate quadratic equations are not expected to be impacted. The
PQ Crypto conference is talking about defining standards for
cryptosystems based on these primitives.

As far as I know, the record for factoring with Shor's algorithm is
the number 21. Larger numbers have been factored (like 143 or 56,153),
but they are special forms and not relevant to RSA keys.

As a side note, D-Wave is talking about 1000-qubit adiabatic quantum
computers. I don't think that is at all relevant to running Shor's
algorithm or crypto.