Google's Post-Quantum Cryptography

News has been bubbling about an announcement by Google that it’s starting to experiment with public-key cryptography that’s resistant to cryptanalysis by a quantum computer. Specifically, it’s experimenting with the New Hope algorithm.

It’s certainly interesting that Google is thinking about this, and probably okay that it’s available in the Canary version of Chrome, but this algorithm is by no means ready for operational use. Secure public-key algorithms are very hard to create, and this one has not had nearly enough analysis to be trusted. Lattice-based public-key cryptosystems such as New Hope are particularly subtle—and we cryptographers are still learning a lot about how they can be broken.

Targets are important in cryptography, and Google has turned New Hope into a good one. Consider this an opportunity to advance our cryptographic knowledge, not an offer of a more-secure encryption option. And this is the right time for this area of research, before quantum computers make discrete-logarithm and factoring algorithms obsolete.

Tags: , , , ,

Posted on July 12, 2016 at 12:53 PM • 34 Comments

Comments

Nelson Elhage • July 12, 2016 2:31 PM

It’s worth noting that Google is combining New Hope with a more traditional ECDHE negotiation explicitly with the goal of being at least as secure as the most secure of the two — even if New Hope is completely broken, this will just degrade to the same security level users were getting anyways.

Joshua Bowman • July 12, 2016 2:39 PM

What are the chances that a strict chain encryption — in this case using RLWE KX to communicate a secret used only to encipher the TLS DH/ECDH KX, which then communicates the actual secret used to encipher the content — would lead to an all-new vulnerability? That kind of onion ring composition is, if not stronger, generally at least not weaker than its strongest component.

Louis • July 12, 2016 3:30 PM

The math is incredible, and honestly beyond me. Very fascinating.

What about also including survival strategies that mimic those of living things (math + self-defense type behavioral characteristics)?

Anti-predator adaptation
https://en.wikipedia.org/wiki/Anti-predator_adaptation

“Anti-predator adaptations are mechanisms developed through evolution that assist prey organisms in their constant struggle against predators. Throughout the animal kingdom, adaptations have evolved for every stage of this struggle…”

blake • July 12, 2016 5:07 PM

With a name like that, I’d expect New Hope to be highly resistant to direct attacks, but have an exposed thermal exhaust over a pipe leading directly from the main generator.

And yes, I expect this joke has been made many times before.

MrC • July 12, 2016 7:03 PM

On the topic of post-quantum key exchange algorithms, can anyone explain how a DH-style exchange would work with McEliece — or can it even be done?

jfgunter • July 12, 2016 8:12 PM

The company I call Ooogle seems more interested in protecting vs. (maybe someday) quantum attacks than in getting my MotoG3 the last 7 monthly android security updates. My phone is very vulnerable RIGHT NOW, Ooogle. Please re-think your priorities.

Jim Van Zandt • July 12, 2016 9:46 PM

jfgunter: I’d blame the update delay on Motorola. I have a similar complaint about my Samsung Galaxy S4, which is still running Android 4.4.4. Hmm. Almost seems like another man-in-the-middle attack. Maybe we’ll have to buy Ooogle phones to be assured of timely updates.

Regardless, I’m glad someone’s looking into this.

Bumble Bee • July 12, 2016 9:59 PM

@Louis

The math is incredible, and honestly beyond me. Very fascinating.

Please, let’s not adulate math that is beyond us. In law, you would have to prove something to a jury of 12 humans of average IQ somewhere around 100. This kind of math tends to be all but incomprehensible to the author and a very few close colleagues. The paper is probably missing (or assuming) some significant pieces of important background information or references that would be helpful to others who are not necessarily experts in that particular field or familiar with the unspoken assumptions of those particular researchers.

Albert Einstein, for instance, was a lot more expository in what he wrote and a lot less interested in obfuscating his knowledge and restricting it to a rarefied circle.

In other words, the math needs to be more broadly explained and understood by outsiders before I trust it.

Louis • July 12, 2016 11:04 PM

@Bumble Bee

Can you please explain to me what opportunities and savings exist in ‘de-escalating’ security and how you would achieve that?

Bumble Bee • July 12, 2016 11:24 PM

@Louis

Re “de-escalating security”

I’m not advocating anything of the sort. The math simply needs to be discussed and gone over very thoroughly by outsiders before it will be trusted. I believe that will happen, now that it has publicity, but papers of a more expository nature will inevitably have to be written…

If you can’t explain it clearly to a wider audience, I still have reasonable doubts that you understand it clearly enough yourselves for the rest of us to base the security of our private information on it.

In yet other words it simply hasn’t undergone sufficient peer review. If it’s legit, rest assured that will happen in time. Meanwhile I’m still skeptical of snake oil, and the more esoteric the math is, the more skeptical I am.

Mobius • July 13, 2016 1:10 AM

@ blake

the double-doublespeak name is indeed the giveaway

it’s like the bush administrationn calling something the freedom act,
and the fine print of the act all being about oppressing anyone whose not rich, white, male and in congress

Louis • July 13, 2016 1:32 AM

@Bumble Bee

I apologize. I do not even a beginner’s understanding of cryptography or the logic behind it. The articles seem to suggest that the ‘locks’ fail at some point in time. I do not know the cost of development for encryption technologies, or how a failure would impact the information owner. I was curious if cryptography behaved in only one ‘restructuring’ manner to make the data ‘unconsumable’. Are there already community programs that promote the responsible stewardship of information and information laws? Yes I agree with you. A peer review and a simplified explanation are great ideas. I think, personally, I will have to read the articles a few more times before I can begin to work through and grasp all of the subtle details and complexity. A truly worthy challenge 🙂

Perhaps we can work through explaining the math and the underlying organization communally. We’d find ourselves on the fingers and toes list of those who understand New Hope

Who? • July 13, 2016 2:27 AM

@ jfgunter

Google is a joke in the security field. Not only your Moto G3 lacks security updates, the Nexus 7 (2012) is even worse. Even if you have an up to date device (let us say, one of its new and expensive tablets) you will find a lot of “critical” and “high” vulnerabilities on each monthly update. Take a look at july’s Android security bulletin:

http://source.android.com/security/bulletin/2016-07-01.html

Seriously, Google is not working on post-quantum cryptography to improve security. Google is working on post-quantum cryptography to get some buzz in the press.

That’s all.

Curious • July 13, 2016 3:32 AM

Anyone that has seen what I write on this blog probably by know that I don’t know much about crypto, and I am instead a language guy. I do like to read about things I don’t understand, and every now and again I find some things fascinating. So please take the following with a grain of salt.

I wonder if the following illustration is sort of indicative of what I thought of could be multi dimensional math, for creating backdoors in crypto.

In the illustration below, I sort of imagine that there could be hidden symmetries with anything plotted on a cartesian coordinate system, something that I guess lattice based crypto would rely on:
https://en.wikipedia.org/wiki/File:Quaternion2.png

From the article: https://en.wikipedia.org/wiki/Quaternion

The way I imagine it, is that there could perhaps be an infinite way of plotting any single point in such a coordinate system, by simply having “jumps” between points, that eventually lead to an end and a starting point, as if a vector line, was composed of any number of other vectors, short and/or long. Notice in the illustration that there are two “jumps” drawn with the red color and one “jump” with the blue. Ofc, whether or not this illustration are meaningful symmetries I have no idea to be honest, or just how to make something like this into backdoored math of sorts.

Thoth • July 13, 2016 5:05 AM

Good old way of using symmetric secrets and splitting the secrets into shares and delivering them via mulitple trusted courier held in tamper evident wrappings would be the most preferred choice.

If you look at the diplomatic and government encryptors offerings, most of them are still using symmetric secrets. One good example of symmettic secrets is the IFF mechanism for fighter planes or the manpack set using a KYK keyfill that holds a protectee secret.

Symmetric secrets with key sizes beyond 128 bit strength would be able to withstand QC attacks.

Bumble Bee • July 13, 2016 5:20 AM

@Louis

Perhaps we can work through explaining the math and the underlying organization communally.

Exactly! If you are interested in that sort of thing, take some courses, (even free ones online,) read some books, educate yourself in the necessary background, and never lose your skepticism or critical thinking skills.

I know a little number theory, but the elliptic curves and lattice theory are a bit beyond me, too. I definitely wish more people would study this stuff because each person who does so explains the material in a unique way that is communally helpful. Definitely necessary if we are to trust such advanced math for our security.

Thoth • July 13, 2016 8:28 AM

@Curious

OFF TOPIC

re: IFF Transponder

It is more than just the IFF stuff. Crypto loading is also used for one-time programming of weapon systems (e.g. missiles) The link is very generic but yea, you got the idea, it uses a offline EKMS system to provision keymats and critical security and comms stuff into a loading device which you carry it to your aircraft and load the parameters into your flight system.

rabinabo • July 13, 2016 9:41 AM

@Bumble Bee

The math behind New Hope is not really advanced. Any undergrad math major that has taken abstract algebra should be able to understand the entire key exchange process. The supersingular isogeny crypto would take someone with a background in algebraic geometry, probably at least grad level, but there are plenty of people who can understand what’s going on there.

hawk • July 13, 2016 1:45 PM

@rabinabo
Lots of people understand the math behind a block cipher, say AES. But no one can prove or disprove the security. That’s the worst thing about cryptography that depends upon computational hardness. That’s why no one wants or needs a new cipher because you can’t prove anything. All you can do is push it out then wait 10 years to see if anyone finds a break. And here’s a dirty little secret -> everyone thinks the other guy is testing it. If it isn’t heavily used and tested intensely you can wait 100 years and it won’t matter.

Spoiler alert!
1) QC will be commonplace before solid practical QC resistant algorithms are ready, if ever.
2) No matter how much you know about crypto, it doesn’t mean you understand QC.
3) No! You can’t just use a bigger key.
4) Once QC is available to researchers there is no predicting what will emerge. Don’t believe assertions that are contingent upon what we know now.

Bumble Bee • July 13, 2016 2:42 PM

@rabinabo

… should be able to understand the entire key exchange process.

#1. TMI.

#2. Oh, yeah, we can exchange keys, encrypt, decrypt, it works! Just implement it; don’t question it.

I still want to know, “Is the problem of cracking this crypto provably reducible to a well studied purely mathematical problem that is known to be very difficult?”

If it isn’t, I don’t buy it.

MarkH • July 13, 2016 3:45 PM

@hawk, who wrote:

3) No! You can’t just use a bigger key.

Well, of course you can. Who’s going to stop you?

Perhaps what hawk meant, is that using a bigger key won’t help.

It’s quite likely that using a bigger key will help a lot, although large keys have a substantial cost in time and energy consumption.

The problem of scaling in quantum computers appears (so far) to be a very difficult one. To break 1024-bit RSA or DH will need about 2000 qubits, and roughly 1000 seconds. Yes, this means that the entire 2000-qubit assemblage must maintain coherence for about one billion microseconds. And of course, 1024 bits was recommended for deprecation years ago.

Even if a QC capable of breaking 1024-bit RSA or DH is eventually developed, it is likely to take years longer — perhaps quite a few years — to attain the capability of cracking 4096 bit keys.

So, using long keys is a practical defense that can be adopted today, and does not depend on a new PK system whose weaknesses have not yet been adequately probed.

Notar • July 13, 2016 9:18 PM

The question is when will Bruce Schneier come with his Post-Quantum Cryptography algorithm…

Bumble Bee • July 14, 2016 9:46 PM

@MarkH, Notar

I share some concerns that quantum computing will (ever) scale to more than a few bits and remain coherent for more than a few processor cycles. It has never been clear to me how they prevent wave function collapse for sufficient time and space to, say, factor an RSA semiprime larger than 15, or if they are still chasing Schrödinger’s cat.

The physics is completely beyond me, but #1 the physicists fail to convince me they understand it themselves, and #2 I feel that quantum physics would be better off without the needless and irrelevant touchy-feely philosophizing that the perceptions and “observations” of sentient beings somehow operate psychologically to bring about this collapse of the wave function.

Technically, a dead-cat bounce means it’s time to sell your stock.

Dan3264 • July 16, 2016 3:45 PM

@Louis, @Bumble Bee,
I feel your pain. I usually cannot understand scientific papers, especially ones on post-quantum cryptography. Once, I found a paper that explained a Ring-LWE scheme in a way I could understand. It felt really good. I am totally capable of understanding these things, but I don’t have enough background knowledge and experience to visualize complex equations. I wish that I could find the paper I mentioned. Also, I know this topic is several days old. I just got back from a family vacation and am catching up on what happened(I don’t care about any security vulnerabilities coming from the disclosure of my family vacation, in case you were wondering)

Louis • July 16, 2016 10:11 PM

@Dan3264

“Once, I found a paper that explained a Ring-LWE scheme in a way I could understand.”

Was this the Ring-LwE research paper you read before?
https://www.douglas.stebila.ca/research/papers/SP-BCNS15/

Here are some additional materials that may help provide context to Stebila’s work above. I am still in the beginning stages of unraveling the technical craft of the Ring-LwE design itself 🙂

Article
Cryptographers aim to future-proof protocol</a href>
“The need to secure today’s communications from the powerful quantum computers of the future has propelled new research aimed at upgrading the internet’s core encryption protocol… Internet communication presently is protected by encryption using the Transport Layer Security protocol, which uses mathematical techniques to protect information… The team, which has released the software for their new protocol under an open source license for further research and development at https://github.com/dstebila/rlwekex</a href>, wants to make it faster and with less overhead.”

Paper published in 2015 IEEE Symposium on Security and Privacy
Post-Quantum Key Exchange for the TLS Protocol from the Ring Learning with Errors Problem</a href>

Authors

Joppe W. Bos
http://www.joppebos.com/
”I am a cryptographic researcher in the innovation center crypto & security at NXP Semiconductors, Leuven, Belgium. Previously, I was a post-doctoral researcher in the Cryptography Research Group at Microsoft Research, Redmond, USA.”

Craig Costello
http://www.craigcostello.com.au/
“I am a researcher in the Security and Cryptography group at Microsoft Research in Redmond, USA. I am primarily interested in the cryptographic applications of computational number theory; in particular, curve-, pairing-, and lattice-based cryptography.”

Michael Naehrig
http://cryptosith.org/michael/index.shtml
“I am a researcher in the Security and Cryptography team at Microsoft Research in Redmond.”

Douglas Stebila
https://www.douglas.stebila.ca/
“I’m an Assistant Professor in cryptography at McMaster University in Hamilton, Ontario, Canada. My research focuses on improving the security of Internet cryptography protocols such as SSL/TLS and SSH.”

Louis • July 17, 2016 5:47 PM

@Dan3264, @r

Ring Learning with Errors (RLWE)</a href>
[…] is a computational problem which serves as the foundation of new cryptographic algorithms designed to protect against cryptanalysis by quantum computers and also to provide the basis for homomorphic encryption.”

Learning with errors (LWE)</a href>
[…] is a problem in machine learning that is conjectured to be hard to solve.”

Machine learning</a href>
[…] is a subfield of computer science (more particularly soft computing) that evolved from the study of pattern recognition and computational learning theory in artificial intelligence. In 1959, Arthur Samuel defined machine learning as a “Field of study that gives computers the ability to learn without being explicitly programmed”.”

If I was contemplating the creation and streamlining of a highly-secure cryptographic solution, I would probably start by defining what I wanted to keep safe and why. I would then begin researching related materials. For example, because I believe that stories preserve generational and humanitarian value, I might start with movies I’ve enjoyed. Let’s say Science fiction films, to lay a technical and philosophical groundwork. Wikipedia lists 27 subcategories</a href> of science fiction films 🙂 This includes subcategories for Comedy science fiction films and for Soft science fiction films as well… (This does not even get into short stories and novels yet.).

Hard sciences: chemistry, physics, astronomy, technology, etc.
Soft sciences: psychology, biology, anthropology, sociology, linguistics, etc.

Additionally, with regards to researchers who are exploring Ring-LwE, look into the work accomplished by Chris Piekert –

http://web.eecs.umich.edu/~cpeikert/

“In 2006 I received my Ph.D. from the MIT Computer Science and Artificial Intelligence Laboratory. My advisor was the incomparable Silvio Micali. My research interests include cryptography, lattices, coding theory, algorithms, and computational complexity… “

“Postdoc available:: For Fall 2016 I am seeking a postdoc, preferably (but not exclusively) one working in lattice crypto or closely related areas. Please email me if you are interested!”

Dan3264 • July 17, 2016 6:26 PM

@Louis,
I found the paper I was talking about. It is here. The concepts described in it apply to pretty much all variants of R-LWE(at least key-agreement and public-key protocols. R-LWE signatures are still beyond me). While I was reading the paper, I suddenly understood R-LWE. R-LWE schemes are essentially noisy multiplication(and other simple arithmetic operations). The ciphertext is arranged in a way that the parts of it that conceal the key/data_encrypted can be approximately removed with knowledge of S(Refer to the paper to figure out what S is). If the parameters are chosen correctly, the key/data_encrypted can be recovered with a very low probability of failure. I like that paper because its high ratio of english text to formal notation makes it much easier to understand than most papers.

Dan3264 • July 17, 2016 6:50 PM

@Louis,
The paper you showed me(the first one) is almost easy for me to understand. I know most of the terminology(vaguely), but I have a hard time fitting all the information in my head at once. My brain page-faults(meaning that I have to go back to review something) to much for it to be interesting to me. I liken it to Shakespeare Plays: I understand most of the words that are used, but the translation isn’t automatic and I have to think about what I am reading for it to make sense to me. I still think that paper is better than most other papers I have come across. Some papers I have come across have very dense use of complex notations. A compilation of math humor (available here) shows this method of proof:

Proof by cumbersome notation:
Best done with access to at least four alphabets and special symbols.

I believe that this method of proof is rather prevalent in real life. I hope that that will change. (I suggest you check the math humor compilation after you do anything else you want to do. The part of it I am refrencing is not at the front. You might have to do a little searching)

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.