Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Experimenting with Post-Quantum Cryptography

security.googleblog.com

Post reply on HN
Print view View original

31–40 of 41 posts

Re: Experimenting with Post-Quantum Cryptography

#31

Post by zmanian »

epaulson wrote: post #28

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?

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.

Re: Experimenting with Post-Quantum Cryptography

#33

Post by mkj »

tptacek wrote: post #13

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?

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

Re: Experimenting with Post-Quantum Cryptography

#34

Post by math_and_stuff »

eximius wrote: post #22
gfody wrote: post #5

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

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

Re: Experimenting with Post-Quantum Cryptography

#35

Post by e12e »

aruss wrote: post #11
bradleyjg wrote: post #4

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 encryp…

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

Re: Experimenting with Post-Quantum Cryptography

#36

Post by naibafo »

aruss wrote: post #11
bradleyjg wrote: post #4

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 encryp…

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.

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

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

Re: Experimenting with Post-Quantum Cryptography

#37

Post by serendipitous »

baby wrote: post #20
Frank2312 wrote: post #6

Earlier quoted context omitted.

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.

Re: Experimenting with Post-Quantum Cryptography

#38

Post by bradleyjg »

naibafo wrote: post #36
aruss wrote: post #11

Earlier quoted context omitted.

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.

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.

Re: Experimenting with Post-Quantum Cryptography

#39

Post by indolering »

e12e wrote: post #35
aruss wrote: post #11

Earlier quoted context omitted.

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.

Re: Experimenting with Post-Quantum Cryptography

#40

Post by e12e »

indolering wrote: post #39
e12e wrote: post #35

Earlier quoted context omitted.

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?

Post reply on HN