Quantum Algorithms for Lattice Problems

Re:Quantum Algorithms for Lattice Problems by ghostway on Wednesday April 10, 2024 @03:32PM (#39994846)

From the paper: > Let us remark that the modulus-noise ratio achieved by our quantum algorithm is still too large to break the public-key encryption schemes based on (Ring)LWE used in practice. In particular, we have not broken the NIST PQC standardization candidates. For example, for CRYSTALS-Kyber [BDK+18], the error term is chosen from a small constant range, the modulus is q = 3329, the dimension is n = 256 · k where k ∈ {3, 4, 5}, so we can think of q as being almost linear in n. For our algorithm, if we set αq ∈ O(1), then our algorithm applies when q ∈ Ω^~(n^2), so we are not able to break CRYSTALS-Kyber yet. We leave the task of improving the approximation factor of our quantum algorithm to future work.

[ Parent | on HN ]

Re:Quantum Algorithms for Lattice Problems by ghostway on Wednesday April 10, 2024 @04:04PM (#39995144)

(of course, this doesn't mean we are in the clear -- a polynomial-time algorithm is alarming)

[ Parent | on HN ]

Re:Quantum Algorithms for Lattice Problems by rhaps0dy on Thursday April 11, 2024 @05:26PM (#40006996)

I don't understand your comment in the context of the previous comment you posted. AIUI, the excerpt says "our algorithm only applies when the modulus q is larger than n^2" where n is 2563 or 2566 (I guess?). So the excerpt would be saying that the algorithm does not apply in this case, because 3000 << (256*3)^2. Right?

[ Parent | on HN ]

Re:Quantum Algorithms for Lattice Problems by abdullahkhalids on Thursday April 11, 2024 @06:28PM (#40007475)

If the history of cryptography is any guide, even though this result doesn't break LWE crypto-protocols, it's much more likely now that someone will come up an improvement that will break LWE crypto-protocols. First constructions of algorithms are rarely optimal.

Even though the opposite is possible as well, now that a concrete algorithm has been made. Someone could very well prove that LWE crypto-protocols are secure against some class of algorithms this algorithm belongs to.

Of course, right now, we should just wait for the experts to read the paper and check if there are any problems.

[ Parent | on HN ]

Re:Quantum Algorithms for Lattice Problems by Ar-Curunir on Friday April 12, 2024 @12:39PM (#40014872)

The algorithm is only quantum-polynomial time for a parameter regime not applicable to the PQC candidates.

[ Parent | on HN ]

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 ]