[liberationtech] Quantum computation & communication

[Gregory Foster]

Thanks for the engagement and informative responses on this thread. I'd 
like to help it remain constructive and informative.

My goal in surfacing this subject is to determine whether or not steps 
should be taken to change the algorithms in use in popular cryptographic 
products to avoid future compromise.  In the course of this message, it 
will become clear that I have no qualms with promotion of the practice 
of encryption - it's a matter of whether we're promoting use of the 
"right" encryption.

Language is important, and I've used the term "classical encryption" 
incorrectly and imprecisely.  As Maxim pointed out, venerable symmetric 
key algorithms (one-time pads, shared secrets) deserve that attribution; 
and as Matt Mackall pointed out, it's only crypto algorithms that rely 
on integer factorization or discrete logarithms that are theoretically 
known to be solvable in polynomial time by a sufficiently "large" 
quantum computer (one with enough qubits to model the problem).
http://en.wikipedia.org/wiki/Symmetric-key_algorithm
http://en.wikipedia.org/wiki/Integer_factorization

So I'm just going to abandon that term altogether because it isn't 
helpful :)

Implicit in this discussion is an assumption that quantum computers of 
sufficient capability can be built, and as Maxim points out that's a big 
assumption.  Let's avoid getting bogged down here by acknowledging that 
the challenges are, well, challenging - but progress has been made on 
expanding the number of qubits, extending the distance over which 
photons can be entangled, etc.  To adapt a turn of phrase by Mr. 
Assange, the physics and engineering seem to be smiling on the emergence 
of quantum computation.

To further the conversation...

Matt stated:

> 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.


This is true, and outlines the concern it's my intent to document. We've 
clarified that quantum computers won't be able to break all encryption.  
But it will be able to break the most widely used public-key 
algorithms.  Here's some context from RSA's website:
http://www.rsa.com/rsalabs/node.asp?id=2222

> The RSA system is currently used in a wide variety of products, 
> platforms, and industries around the world. It is found in many 
> commercial software products and is planned to be in many more. The 
> RSA algorithm is built into current operating systems by Microsoft, 
> Apple, Sun, and Novell. In hardware, the RSA algorithm can be found in 
> secure telephones, on Ethernet network cards, and on smart cards. In 
> addition, the algorithm is incorporated into all of the major 
> protocols for secure Internet communications, including S/MIME (see 
> Question 5.1.1), SSL (see Question 5.1.2), and S/WAN (see Question 
> 5.1.3). It is also used internally in many institutions, including 
> branches of the U.S. government, major corporations, national 
> laboratories, and universities.
>
> At the time of this publication, technology using the RSA algorithm is 
> licensed by over 700 companies. The estimated installed base of RSA 
> BSAFE encryption technologies is around 500 million. The majority of 
> these implementations include use of the RSA algorithm, making it by 
> far the most widely used public-key cryptosystem in the world.


Matt stated:

> 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.


By no means am I a dedicated researcher into this field, but a search on 
"quantum computing NSA" turned up an article from October 2010:
http://www.afcea.org/content/?q=node/2407

> ...a host of U.S. government agencies is teamed with universities 
> across the country and internationally to crack the science code that 
> will make quantum computers viable. Participating federal 
> organizations include the National Security Agency (NSA), U.S. Army 
> Research Office (ARO), Defense Advanced Research Projects Agency, 
> Intelligence Advanced Research Projects Activity, Air Force Office of 
> Scientific Research, Office of Naval Research, Sandia National 
> Laboratories, the Department of Energy’s Los Alamos National 
> Laboratory and the National Institute of Standards and Technology (NIST).
> ...
> [NSA technical director for quantum computing Barry] Barker echoes 
> that sentiment: “We started working in this field in the mid-1990s. 
> This was then a purely mathematical conception, and it’s now 
> progressed to a much more elaborate field of science. We aren’t the 
> only group to play a role in that, but we’re one of the groups, both 
> in funding research with universities over the years and doing some of 
> the research ourselves. We’ve played a substantial role in advancing 
> this field,” Barker says.


It's worth noting that Shor's Algorithm was first published in 1994.
http://arxiv.org/abs/quant-ph/9508027


Jacob stated:

> If you have a specific passage where you feel that we state that 
> classical encryption is a panacea to the problem of mass surveillance, 
> I'd hope it is considered in the context of all the social discussion 
> that has almost nothing to do with cryptography per se.
>
> (In any case, thanks for reading the book, I hope you enjoyed it!)


I very much enjoyed reading the book.  It's a timely document, a 
snapshot of the zeitgeist, a wide-ranging conversation amongst four 
admirable, courageous souls from our time.  I learned quite a bit and 
have plenty of placemarks for further research, especially to expand my 
understanding of the international dimensions of the challenges we 
face.  I wished I was there drinking whiskey with you, and who knows 
maybe we'll get a chance to someday.

Nowhere in the text did any of the participants use the terms "panacea" 
or the dreaded "classical encryption" - those are my literary 
indiscretions.  But the book title wouldn't be admirably resurrecting 
the signifier "Cypherpunks" (again, with the literary indiscretions!) if 
encryption weren't a primary theme.

So, here's an important quotation, one which I present while emphasizing 
that the book is not in the least summarized by it:

> ...the universe, our physical universe, has that property that makes 
> it possible for an individual or a group of individuals to reliably, 
> automatically, even without knowing, encipher something, so that all 
> the resources and all the political will of the strongest superpower 
> on earth may not decipher it.  And the paths of encipherment between 
> people can mesh together to create regions free from the coercive 
> force of the outer state.  Free from mass interception.  Free from 
> state control.
>
> In this way, people can oppose their will to that of a fully mobilized 
> superpower and win.  Encryption is an embodiment of the laws of 
> physics, and it does not listen to the bluster of states, even 
> transnational surveillance dystopias.
>
> It isn't obvious that the world had to work this way.  But somehow the 
> universe smiles on encryption.
>
> Cryptography is the ultimate form of non-violent direct action.
>
> While nuclear weapons states can exert unlimited violence over even 
> millions of individuals, strong cryptography means that a state, even 
> by exercising unlimited violence, cannot violate the intent of 
> individuals to keep secrets from them.
>
> Strong cryptography can resist an unlimited application of violence.  
> No amount of coercive force will ever solve a math problem.
>
> But could we take this strange fact about the world and build it up to 
> be a basic emancipatory building block for the independence of mankind 
> in the platonic realm of the internet?  And as societies merged with 
> the internet could that liberty then be reflected back into physical 
> reality to redefine the state?

-- Julian Assange, from the introduction to _Cypherpunks: Freedom and 
the Future of the Internet_, p. 5-6.


I think that's some great stuff, some crucial insights from hard-earned 
experience - experience which we all must admit is rather unique in this 
world.  It's important.  It's so important, that I'm going to insist 
that we get it right.

So, to return to my concern - which I'll narrow even further: if we know 
RSA is "the most widely used public-key cryptosystem in the world," and 
we know RSA can be broken by a sufficiently large quantum computer using 
Shor's Algorithm, and we know there is significant research and 
development into building a sufficiently large quantum computer - 
shouldn't we help shift dependence upon RSA through our advocacy for 
popular encryption?

And if not now, when?  Especially when one considers that every stored 
RSA-encrypted ciphertext---and we have plenty of reasons to believe that 
everything is being stored somewhere---becomes effectively transparent 
when that last qubit hovers into place. Well, as soon as the quantum 
priests translate the ciphertext onto quantum punch cards...

Let's advocate encryption---for all the reasons well stated by Assange 
and company---but let's recommend the "right" encryption.

Now, WTF is "right"?  Linguistic indiscretions are even worse :)
gf

-- 
Gregory Foster || gfoster at entersection.org
@gregoryfoster <> http://entersection.com/