Experimenting with Post-Quantum Cryptography | Hacker News Reader

Experimenting with Post-Quantum Cryptography

security.googleblog.com

163 pointscramforce39 comments

As I understand it that the picture for symmetric encryption in a quantum computer world is still relatively rosy. The key strength of something like AES is halved, but with the important caveat that the difficulty is with respect to quantum operations rather than classical operations and there's no guarantee quantum computers will be able to scale as well over time as silicon has. The situation for asymmetric encryption is where the real potential trouble lies. Please correct me if I misunderstand the situation.

You are mostly correct. In fact the key strength of something like AES is realistically not even going to be reduced by half. In terms of the query complexity (the number of calls to AES that are needed) using Grover's algorithm the key strength is half what it would be with classical brute force. In practice though these queries must be implemented as quantum circuits and run a on quantum computer which adds a pretty large overhead.

This article is about the implementation of an asymmetric protocol based on the RLWE (https://en.wikipedia.org/wiki/Ring_Learning_with_Errors) problem.

That's right, symmetric encryption is fine. You're also right that protocols that rely on factoring or discrete log (more generally, any hidden subgroup problem) will be broken by quantum computers. However, this still means symmetric encryption is in trouble; namely in that we still need a post-quantum method for exchanging keys, otherwise symmetric ciphers will be virtually useless.

How about hashing - in particular wrt key derivation? Does anyone have some insight there? Is it likely passphrase+salt+stretching might be in danger from quantum attacks? (I also wonder if DNA/RNA based biologic computing (or computing inspired by biology) might somehow change things around in terms of guessing passwords or look for hash collision...)

Hashing is in a similar position in that we just need to increase the size. Biological computing is (AFAIK) irrelevant to the speedups provided by quantum mechanics.

> Hashing is in a similar position in that we just need to increase the size.

Size of hash, or number of iterations? Or either? And will it still be "convenient security" available for those that "only" have classical computers? (ie: is will be get away with "small" increases in size, and get to keep (some of) our current speed)?

> Biological computing is (AFAIK) irrelevant to the speedups provided by quantum mechanics.

I didn't think otherwise. But they might be relevant to combinatorial problems, and so relevant to security?

There are some quantum key distribution protocols[1], though they still have their faults.

[1](https://en.wikipedia.org/wiki/Quantum_key_distribution)

Based on what I've read, QKD requires a out of band shared secret to authenticate and rule out an active man in the middle. Given that I don't see the point at all.

I discovered NTRU while searching for a fast alternative to RSA for asymmetric encryption. It's said to be quantum resistant as well but I can only vouch for its speed (it is very fast and served my purpose perfectly).

https://github.com/NTRUOpenSourceProject/ntru-crypto

NTRU is patented though and requires you to use their GPL library for patent exemption, or have a paid license (as said in the project README). However, given that, there's also http://tbuktu.github.io/ntru/ as BSD, so I'm not sure how to square that with what the owners of NTRU publicly stated. Apparently the EU is also considering it for some sort of standardization?

Bernstein also recently released a paper on NTRU Prime which I just became aware of, although it makes no mention of the patent issue. https://ntruprime.cr.yp.to/ntruprime-20160511.pdf

In any case, it'd be interesting to get an answer on this, since NTRU has looked interesting for a long time, but the patents were pretty unfortunate.

It is lattice based so the state of the art to attack it uses LLL lattice reduction, I believe. I wrote a python implementation of both and, with pypy, it is quite fast at encrypting and decrypting. The LLL reduction was rather slow, but impressive that it could be done within a few minutes for some low-rank lattices.

Alternating between tours of BKZ(50) and y-sparse enumeration is much stronger. I have some BSD-d C++ implementations here: https://github.com/elemental/Elemental/tree/master/include/E...

Are the TLS constructions they're using documented anywhere? Is this a combination of Ring-LWE and, say, ECC, in case there are as-yet-unknown implementation faults in Ring-LWE?

We haven't written a spec because we don't intend for this to be widespread. However, the spec would basically be: run both X25519 and NewHope concurrently, concatenate their outputs and feed that into the TLS KDF as normal.

It is indeed a combination of R-LWE and ECC because it doesn't yet seem reasonable to depend on R-LWE alone. Not only because of the possibility of implementation faults in NewHope, but also because of the possibility of significant crypto-analytic advances against R-LWE, even with classical computers.

Maybe this is a naive question, not knowing chrome well, but is the source available? Would love to play around with this..

https://github.com/google/boringssl/blob/master/include/open...

and also https://github.com/google/boringssl/blob/master/crypto/newho...

cool, thanks

https://github.com/google/boringssl/commit/e25775bcacb120f7f... seems to be the code, as agl described.

a hypothetical, future quantum computer would be able to retrospectively decrypt any internet communication that was recorded today, and many types of information need to remain confidential for decades. Thus even the possibility of a future quantum computer is something that we should be thinking about today.

Uh-oh.

Apparently not even Perfect Forward Secrecy can protect against this: https://en.wikipedia.org/wiki/Forward_secrecy#Attacks

Are any of these algorithms suited for PGP signing replacements?

I'm interested in being able to make long term claims based on web-of-trust models, and I've been nervous about basing it around RSA/DSA key pairs.

In that sort of world, what do the keys actually look like? Is it comparable to being able to distribute a single public root key?

you may want to have a look at sphincs. its security is based on hash-functions, therefore unlike most other postquantum schemes it can be considered very reliable (good hash functions are a solved problem these days). Downside: signatures are big (~40k). For TLS this is unworkable, for a PGP-like system this is doable. https://sphincs.cr.yp.to/

We do not currently have good options for small Post Quantum signatures.

Hash Based signatures in a web of trust would result in enormous amounts of signature data for each public key.

A stateful hash based signing protocol like XMSS might be more suitable.

Hopefully a Post Quantum small signature alternative appears.

very good talk by Daniel J Bernstein on PQC Hacks at the last 32C3 (certainly separating reality/fiction and one of the best talks I have seen on the subject):

- https://www.youtube.com/watch?v=6XeBvdm8vao

We need a lot more money being poured into PQC. The key sizes are enormous: ECC requires 256 bits and these new schemes range up to 10KB. Say goodbye to single packet key exchanges.

[weekend-senility.Modus:On] anectodical ?

um... when actual information must be _matched_

via "0" and "1" harrumph's principles... eerie ahem...

and the lever is relativeness... zzz... eh... using

stochastical methods to...zzzz ...strategy... zzz

[slept away]

> We explicitly do not wish to make our selected post-quantum algorithm a de-facto standard

Like so many other things in computer science history, that seems like a great way to make it the de-facto standard.

If Google manages to prove it works and there are no better alternatives later on, then it will probably become the de-facto standard.

However, the second condition seems to not be met if Google is right, because they mention there are promising papers published.

>Since we selected New Hope, we've noted two promising papers in this space, which are welcome.

There is also the fact that "as of now" efficient quantum computers capable to break our crypto is fiction.

Yes, but if you want your sessions that are captured today to remain confidential when quantum computers do become reality then you need to use post-quantum key exchange methods today.

Could someone replace the link with the non-mobile version?

https://security.googleblog.com/2016/07/experimenting-with-p...

just remove ?m=1 from the end of the url

If 1000 people need to do that, the few seconds it takes quickly adds up.

It would be much easier if the original link was changed.

Thanks! We've updated the link.

Upvote for hearing "post-quantum" for the first time in my life.

I suspect Deepak Chopra is going to appropriate it soon enough.

When you realize that your soul is already entangled with existence on a quantum level, your consciousness can achieve post-quantum awareness...

I would have lent a pithy rejoinder, but the I don't want to incur further wrath of the down-voters.

Tanja Lange [0] did a talk om post-quantumcrypto @ 32c3 https://media.ccc.de/v/32c3-7210-pqchacks. Last week she organised a 1 day workshop in Utrecht [1]

[0] http://www.hyperelliptic.org/tanja/ [1] https://pqcrypto.eu.org/mini.html

Reply on news.ycombinator.com