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.
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.
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?
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).
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?
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.
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.
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.
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):
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 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.
40 comments
[ 4.8 ms ] story [ 28.8 ms ] threadLike so many other things in computer science history, that seems like a great way to make it 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.
This article is about the implementation of an asymmetric protocol based on the RLWE (https://en.wikipedia.org/wiki/Ring_Learning_with_Errors) problem.
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?
[1](https://en.wikipedia.org/wiki/Quantum_key_distribution)
https://github.com/NTRUOpenSourceProject/ntru-crypto
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.
https://security.googleblog.com/2016/07/experimenting-with-p...
It would be much easier if the original link was changed.
I suspect Deepak Chopra is going to appropriate it soon enough.
[0] http://www.hyperelliptic.org/tanja/ [1] https://pqcrypto.eu.org/mini.html
Uh-oh.
Apparently not even Perfect Forward Secrecy can protect against this: https://en.wikipedia.org/wiki/Forward_secrecy#Attacks
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.
- https://www.youtube.com/watch?v=6XeBvdm8vao
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?
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.
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]