[liberationtech] Quantum computation & communication

[Matt Mackall]

On Wed, 2012-12-19 at 00:38 -0600, Gregory Foster wrote:
> After reading Assange, et. al.'s "Cypherpunks: Freedom and the Future of 
> the Internet", wherein classical encryption is presented as a panacea 
> for ensuring privacy in an age of mass surveillance, I found the 
> following article succinct in questioning the long-term viability of 
> that narrative (or at least insisting on some qualifications).  Quantum 
> computation and communication is still a long distance away, but this 
> article provides the outlines of how that technology will be used (and 
> abused) by the institutions that will be able to afford it.

Don't believe the hype.

Shor's algorithm for quantum factoring is a special case. With it,
future large quantum computers may some day be able to break today's RSA
and ECC, the two most popular schemes for public key encryption.

However, most other cryptographic schemes (including several other
public-key schemes) will NOT be rendered broken. Instead, they will
become as strong as ciphers with half the key length. For instance,
today's AES-256 will become as strong as today's AES-128. It is
considered very unlikely that there will be significant breakthroughs in
quantum computing theory to improve on that.

In short, given everything known today about the possible potential of
quantum computers, it is already possible to do all the sorts of things
we do with cryptography today in a way that is secure against future
adversaries with quantum computers. Unfortunately, "Quantum Computing
Not Really A Big Deal For Security" doesn't make for a very good
magazine article.

To give you a sense of how far there is to go for quantum computers to
be practical at breaking SSL, the largest number factored by researchers
with a "quantum computer" is the number 143 (ie 11x13), though there's
much debate about whether the approach used is actually "quantum". The
largest undisputed result is for the number 21, also this year, besting
the factoring of the number 15 in 2001. Needless to say, you don't even
need pencil and paper, let alone a quantum computer, to factor these
sorts of numbers. By comparison, today's typical SSL keys have hundreds
of digits.

The biggest risk is that the secrets you encrypt today with SSL or GPG
might be decrypted by a very rich, patient adversary 20 to 50 years from
now. That risk exists with or without quantum computers and I very much
doubt the NSA and friends see enough code-breaking potential in quantum
computing to be putting serious effort into it.

-- 
Mathematics is the supreme nostalgia of our time.


--
Unsubscribe, change to digest, or change password at: https://mailman.stanford.edu/mailman/listinfo/liberationtech

----- End forwarded message -----
-- 
Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org
______________________________________________________________
ICBM: 48.07100, 11.36820 http://www.ativel.com http://postbiota.org
8B29F6BE: 099D 78BA 2FD3 B014 B08A  7779 75B0 2443 8B29 F6BE