5 ms·

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 ba

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.

ghostway 2y ago
(of course, this doesn't mean we are in the clear -- a polynomial-time algorithm is alarming)
- rhaps0dy 2y ago
  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?
  - abdullahkhalids 2y ago
    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.
- Ar-Curunir 2y ago
  The algorithm is only quantum-polynomial time for a parameter regime not applicable to the PQC candidates.
deleted 2y ago
[deleted]
pclmulqdq 2y ago
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.
- pseudo0 2y ago
  > 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.
- cryptonik 2y ago
  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 ?
  - pclmulqdq 2y ago
    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.
  - kamilner 2y ago
    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.

ghostway 2y ago

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

rhaps0dy 2y ago
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?
- abdullahkhalids 2y ago
  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.
Ar-Curunir 2y ago
The algorithm is only quantum-polynomial time for a parameter regime not applicable to the PQC candidates.

deleted 2y ago

[deleted]

pclmulqdq 2y ago

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.

pseudo0 2y ago
> 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.
cryptonik 2y ago
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 ?
- pclmulqdq 2y ago
  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.
- kamilner 2y ago
  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.