News for hackers. Stuff that matters.

A comment on Quantum Algorithms for Lattice Problems. Parent comment

Re:Quantum Algorithms for Lattice Problems by pclmulqdq on Thursday April 11, 2024 @07:53PM (#40008037)
Factorization and discrete log are also polynomial on a quantum computer, and we are very good at just increasing bit widths. If CRYSTALS is also polynomial in BQP, there is very little reason to invest so much into it.

I am still of the (very controversial) opinion that the only PQC algorithm worth investing in at the expense of classical algorithms is Classic McEliece. This is a code that has stood up to classical and quantum cracking attempts for a very long time - cracking these codes is equivalent to creating a very valuable algorithm in error correcting codes.

The NIST also is dead set on people using only PQC or classical crypto, not a wrapper with both. That is stupid IMO.

[ Parent | on HN ]
Re:Quantum Algorithms for Lattice Problems by pseudo0 on Thursday April 11, 2024 @08:12PM (#40008143)
> The NIST also is dead set on people using only PQC or classical crypto, not a wrapper with both. That is stupid IMO.

Yeah, this is rather baffling. After SIKE got broken, you'd think they would have realized the importance of combining these new cutting-edge candidates with something reliable.

[ Parent | on HN ]
Re:Quantum Algorithms for Lattice Problems by cryptonik on Friday April 12, 2024 @12:14PM (#40014547)
Thanks for your comment, very interesting. About your last paragraph : Do you know why NIST refuses hybridization, when European agencies imposes it ? What is the political behind it ?
[ Parent | on HN ]
Re:Quantum Algorithms for Lattice Problems by pclmulqdq on Friday April 12, 2024 @12:31PM (#40014761)
The charitable interpretation I would give the NIST - and a very real concern - is that they are not sure that one form of cryptography doesn't weaken the other, without proofs. Since these cryptosystems also tend to work in different number fields, it's very hard to prove anything about their interactions at all.

We all know the uncharitable interpretation, that the PQC algorithms may be backdoored.

[ Parent | on HN ]
Re:Quantum Algorithms for Lattice Problems by kamilner on Friday April 12, 2024 @01:09PM (#40015210)
NIST does not refuse hybridization, they will be publishing guidance on hybrid schemes in the draft of SP 800-227 at the same time as the final standards. They don't impose it though, because at a large scale it's more efficient to run just (fast) ML-KEM instead of (fast) ML-KEM + (slower) ECDH, which more than doubles your computation time for what they see as no benefit.
[ Parent | on HN ]
Re:Quantum Algorithms for Lattice Problems by Ar-Curunir on Friday April 12, 2024 @12:40PM (#40014879)
The remark clearly states that CRYSTALs is not affected by this attack.
[ Parent | on HN ]
Re:Quantum Algorithms for Lattice Problems by less_less on Friday April 12, 2024 @04:43PM (#40017442)
It's NSA who wants only PQC and not hybrid. NIST is fine with hybrid. They don't plan to standardize hybrids as entire units, but they said they plan to standardize the KDF modes you'd need to build them.
[ Parent | on HN ]