4 ms·

How does this affect these statements on Wikipedia [1] > some lattice-based constructions appear to be resistant to attack by both classical and quantum comput

by tromp 3y ago

How does this affect these statements on Wikipedia [1] > some lattice-based constructions appear to be resistant to attack by both classical and quantum computers. Furthermore, many lattice-based constructions are considered to be secure under the assumption that certain well-studied computational lattice problems cannot be solved efficiently. and [2] ? > One class of quantum resistant cryptographic algorithms is based on a concept called "learning with errors" introduced by Oded Regev in 2005. [1] https://en.wikipedia.org/wiki/Lattice-based_cryptography https://en.wikipedia.org/wiki/Lattice-based_cryptography [2] https://en.wikipedia.org/wiki/Ring_learning_with_errors_key_exchange https://en.wikipedia.org/wiki/Ring_learning_with_errors_key_...

doomrobo 3y ago
The idea of "appear to be resistant to attack" is an empirical one. When someone says that, they are saying that we simply have not found a good attack against this problem. That can change any day, in principle. Unfortunately, "we don't know of an attack" is about as strong a statement you can make in cryptography, when talking about a fundamental hardness assumption. More verbosely, you'd say "the best known attacks take 2^whatever operations on a computer (classical or quantum), and that's expensive, so we're probably fine unless someone makes a significant leap tomorrow"
- adgjlsfhk1 3y ago
  imo, this isn't quite true. there are a lot of areas where we can say "this looks sufficiently secure for now, but given the rate of advancement in this area in the last decade, we expect it will probably lose a few bits of security in the next decade"
wbl 3y ago
Do you know how little we know? We don't even know P isn't PSPACE!
westurner 3y ago
CRYSTALS-Kyber, NTRU, SABER, CRYSTALS-Dilithium, and FALCON are lattice-based method finalists in NIST PQC Round 3. [1] NIST Post-Quantum Cryptography Standardization: https://en.wikipedia.org/wiki/NIST_Post-Quantum_Cryptography_Standardization#Finalists https://en.wikipedia.org/wiki/NIST_Post-Quantum_Cryptography... The NTRU article mentions PQ resistance to Shor's only, other evaluations, and that IEEE Std 1363.1 (2008) and the X9 financial industry spec already specify NTRU, which is a Round 3 Finalist lattice-based method. In [1] Under "Selected Algorithms 2022", the article lists "Lattice: CRYSTALS-Kyber, CRYSTALS-Dilithium, FALCON; Hash-based: SPHINCS+". Round 4 includes Code-based and Supersingular elliptic curve isogeny algos. FWIU There's not yet a TLS 1.4/2.0 that specifies which [lattice-based] PQ algos webservers would need to implement to support a new PQ TLS spec.

by tromp 3y ago

doomrobo 3y ago

The idea of "appear to be resistant to attack" is an empirical one. When someone says that, they are saying that we simply have not found a good attack against this problem. That can change any day, in principle. Unfortunately, "we don't know of an attack" is about as strong a statement you can make in cryptography, when talking about a fundamental hardness assumption. More verbosely, you'd say "the best known attacks take 2^whatever operations on a computer (classical or quantum), and that's expensive, so we're probably fine unless someone makes a significant leap tomorrow"

adgjlsfhk1 3y ago
imo, this isn't quite true. there are a lot of areas where we can say "this looks sufficiently secure for now, but given the rate of advancement in this area in the last decade, we expect it will probably lose a few bits of security in the next decade"

wbl 3y ago

Do you know how little we know? We don't even know P isn't PSPACE!

westurner 3y ago

CRYSTALS-Kyber, NTRU, SABER, CRYSTALS-Dilithium, and FALCON are lattice-based method finalists in NIST PQC Round 3. [1] NIST Post-Quantum Cryptography Standardization: https://en.wikipedia.org/wiki/NIST_Post-Quantum_Cryptography_Standardization#Finalists https://en.wikipedia.org/wiki/NIST_Post-Quantum_Cryptography... The NTRU article mentions PQ resistance to Shor's only, other evaluations, and that IEEE Std 1363.1 (2008) and the X9 financial industry spec already specify NTRU, which is a Round 3 Finalist lattice-based method. In [1] Under "Selected Algorithms 2022", the article lists "Lattice: CRYSTALS-Kyber, CRYSTALS-Dilithium, FALCON; Hash-based: SPHINCS+". Round 4 includes Code-based and Supersingular elliptic curve isogeny algos. FWIU There's not yet a TLS 1.4/2.0 that specifies which [lattice-based] PQ algos webservers would need to implement to support a new PQ TLS spec.