Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[liberationtech] Quantum computation & communication

Matt Mackall mpm at
Wed Dec 19 07:38:02 PST 2012

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.

More information about the liberationtech mailing list