Quantum Algorithms for Lattice Problems eprint.iacr.org/2024/555

[D P]

Dear PQC Forum,

We came across this today, Is this algorithm valid and if so, how much of a risk is it to current lattice algorithms?

https://eprint.iacr.org/2024/555

Yilei Chen, Tsinghua University, Shanghai Artificial Intelligence Laboratory, Shanghai Qi Zhi Institute

Abstract

We show a polynomial time quantum algorithm for solving the learning with errors problem (LWE) with certain polynomial modulus-noise ratios. Combining with the reductions from lattice problems to LWE shown by Regev [J.ACM 2009], we obtain polynomial time quantum algorithms for solving the decisional shortest vector problem (GapSVP) and the shortest independent vector problem (SIVP) for all -dimensional lattices within approximation factors of . Previously, no polynomial or even subexponential time quantum algorithms were known for solving GapSVP or SIVP for all lattices within any polynomial approximation factors.

[Danilo Gligoroski]

Hmmm,

Two initial comments regarding the remarks on page 3 of the paper (given below as an image):

1. For Kyber (NIST FIPS 203), the paper says k \in {3, 4, 5}, while the correct values should be {2, 3, 4}. Still, the claims are correct: q = 3329 is not bigger than n^2, where n = 256 k, and k in {2, 3, 4}.

2. However, for Dilithium (NIST FIPS 204), q = 8380417, k \in {4, 6, 8}, and for all values n = 256 k, actually q > n^2. Is this a serious threat?

Regards,

Danilo!

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/d70007b7-22bf-441e-b8ff-15fdf9ddf01bn%40list.nist.gov.

[赵运磊]

Hi, Chen's result requires q=\tilde{\Omega}(m^2),where m=\Omega{n*log q}, where tilde{\Omega}(m^2) means c*m^2*(logm)^d，for some constants c and d. So, for Dilithium, q is still less than \tilde{\Omega}(m^2).

For NTRU, Chen's result does not go beyond the fatigue point q=2^{2.484+o(1)} of [1], so as far as I see, the result does not bring new security threats to NTRU. 

[1]  Ducas L, Woerden W. NTRU Fatigue: How Stretched is Overstretched? // Proceedings of the 27th International Conference on the Theory and Application of Cryptology and Information Security. Singapore: Springer, 2021: 3–32

Regards

Yunlei

-----原始邮件-----
发件人: "Danilo Gligoroski" <dan...@ntnu.no>
发送时间: 2024-04-11 15:14:24 (星期四)
收件人: pqc-...@list.nist.gov
主题: Re: [pqc-forum] Quantum Algorithms for Lattice Problems eprint.iacr.org/2024/555

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/43acd2d9-5e3e-4589-a6ba-7c545d25d14b%40ntnu.no.

[赵运磊]

For Dilithium, with Dilithim65 as an example, m=256*6,n=256*5, m is much smaller than n*log q, in this case  Chen's result may need further larger q. But I suggest better to use smaller q indeed, at least for the recommended parameter set of Dilithium6*5. In the same way, when applying Chen's result on RLWE or NTRU,  applying Chen's result (if applicable) may also need further larger q. 

 

 

-----原始邮件-----
发件人: "Danilo Gligoroski" <dan...@ntnu.no>
发送时间: 2024-04-11 15:14:24 (星期四)
收件人: pqc-...@list.nist.gov
主题: Re: [pqc-forum] Quantum Algorithms for Lattice Problems eprint.iacr.org/2024/555

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/43acd2d9-5e3e-4589-a6ba-7c545d25d14b%40ntnu.no.

[赵运磊]

If the ground-breaking result is correct, most PQ-KEMs should have to analyze case by case with concrete parameters. No one can assume quantum-secure in theory :-) FHE may face more serious problems... 

-----原始邮件-----
发件人: "Divesh Aggarwal" <divesh....@gmail.com>
发送时间: 2024-04-11 18:32:12 (星期四)
收件人: 赵运磊 <ylz...@fudan.edu.cn>
抄送: "Danilo Gligoroski" <dan...@ntnu.no>, pqc-...@list.nist.gov

主题: Re: [pqc-forum] Quantum Algorithms for Lattice Problems eprint.iacr.org/2024/555

Isn’t it really premature to worry about what it implies for NIST submissions. If the result is correct, there will be follow-ups and most lattice based schemes will be broken.

For now the most important thing is to check for correctness, and not to plug in the value of q and n and m, and get overjoyed with the resulting inequalities :)

Best regards

Divesh 

On 11 Apr 2024, at 6:21 PM, '赵运磊' via pqc-forum <pqc-...@list.nist.gov> wrote:

Hi, Chen's result requires q=\tilde{\Omega}(m^2),where m=\Omega{n*log q}, where tilde{\Omega}(m^2) means c*m^2*(logm)^d，for some constants c and d. So, for Dilithium, q is still less than \tilde{\Omega}(m^2).

For NTRU, Chen's result does not go beyond the fatigue point q=2^{2.484+o(1)} of [1], so as far as I see, the result does not bring new security threats to NTRU. 

[1]  Ducas L, Woerden W. NTRU Fatigue: How Stretched is Overstretched? // Proceedings of the 27th International Conference on the Theory and Application of Cryptology and Information Security. Singapore: Springer, 2021: 3–32

Regards

Yunlei

-----原始邮件-----
发件人: "Danilo Gligoroski" <dan...@ntnu.no>
发送时间: 2024-04-11 15:14:24 (星期四)
收件人: pqc-...@list.nist.gov
主题: Re: [pqc-forum] Quantum Algorithms for Lattice Problems eprint.iacr.org/2024/555

Hmmm,

Two initial comments regarding the remarks on page 3 of the paper (given below as an image):

1. For Kyber (NIST FIPS 203), the paper says k \in {3, 4, 5}, while the correct values should be {2, 3, 4}. Still, the claims are correct: q = 3329 is not bigger than n^2, where n = 256 k, and k in {2, 3, 4}.

2. However, for Dilithium (NIST FIPS 204), q = 8380417, k \in {4, 6, 8}, and for all values n = 256 k, actually q > n^2. Is this a serious threat?

Regards,

Danilo!

<saj6UrBAeUiOV00p.png>

On 10/04/2024 22:19, D P wrote:

Dear PQC Forum,

We came across this today, Is this algorithm valid and if so, how much of a risk is it to current lattice algorithms?

https://eprint.iacr.org/2024/555

Yilei Chen, Tsinghua University, Shanghai Artificial Intelligence Laboratory, Shanghai Qi Zhi Institute

Abstract

We show a polynomial time quantum algorithm for solving the learning with errors problem (LWE) with certain polynomial modulus-noise ratios. Combining with the reductions from lattice problems to LWE shown by Regev [J.ACM 2009], we obtain polynomial time quantum algorithms for solving the decisional shortest vector problem (GapSVP) and the shortest independent vector problem (SIVP) for all -dimensional lattices within approximation factors of . Previously, no polynomial or even subexponential time quantum algorithms were known for solving GapSVP or SIVP for all lattices within any polynomial approximation factors.

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/d70007b7-22bf-441e-b8ff-15fdf9ddf01bn%40list.nist.gov.

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/43acd2d9-5e3e-4589-a6ba-7c545d25d14b%40ntnu.no.

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/2d55b2b6.31ee1.18eccacd098.Coremail.ylzhao%40fudan.edu.cn.

[Divesh Aggarwal]

Isn’t it really premature to worry about what it implies for NIST submissions. If the result is correct, there will be follow-ups and most lattice based schemes will be broken.

For now the most important thing is to check for correctness, and not to plug in the value of q and n and m, and get overjoyed with the resulting inequalities :)

Best regards

Divesh 

On 11 Apr 2024, at 6:21 PM, '赵运磊' via pqc-forum <pqc-...@list.nist.gov> wrote:



Hi, Chen's result requires q=\tilde{\Omega}(m^2),where m=\Omega{n*log q}, where tilde{\Omega}(m^2) means c*m^2*(logm)^d，for some constants c and d. So, for Dilithium, q is still less than \tilde{\Omega}(m^2).

For NTRU, Chen's result does not go beyond the fatigue point q=2^{2.484+o(1)} of [1], so as far as I see, the result does not bring new security threats to NTRU. 

[1]  Ducas L, Woerden W. NTRU Fatigue: How Stretched is Overstretched? // Proceedings of the 27th International Conference on the Theory and Application of Cryptology and Information Security. Singapore: Springer, 2021: 3–32

Regards

Yunlei

-----原始邮件-----
发件人: "Danilo Gligoroski" <dan...@ntnu.no>
发送时间: 2024-04-11 15:14:24 (星期四)
收件人: pqc-...@list.nist.gov
主题: Re: [pqc-forum] Quantum Algorithms for Lattice Problems eprint.iacr.org/2024/555

Hmmm,

Two initial comments regarding the remarks on page 3 of the paper (given below as an image):

1. For Kyber (NIST FIPS 203), the paper says k \in {3, 4, 5}, while the correct values should be {2, 3, 4}. Still, the claims are correct: q = 3329 is not bigger than n^2, where n = 256 k, and k in {2, 3, 4}.

2. However, for Dilithium (NIST FIPS 204), q = 8380417, k \in {4, 6, 8}, and for all values n = 256 k, actually q > n^2. Is this a serious threat?

Regards,

Danilo!

<saj6UrBAeUiOV00p.png>

On 10/04/2024 22:19, D P wrote:

Dear PQC Forum,

We came across this today, Is this algorithm valid and if so, how much of a risk is it to current lattice algorithms?

https://eprint.iacr.org/2024/555

Yilei Chen, Tsinghua University, Shanghai Artificial Intelligence Laboratory, Shanghai Qi Zhi Institute

Abstract

We show a polynomial time quantum algorithm for solving the learning with errors problem (LWE) with certain polynomial modulus-noise ratios. Combining with the reductions from lattice problems to LWE shown by Regev [J.ACM 2009], we obtain polynomial time quantum algorithms for solving the decisional shortest vector problem (GapSVP) and the shortest independent vector problem (SIVP) for all -dimensional lattices within approximation factors of . Previously, no polynomial or even subexponential time quantum algorithms were known for solving GapSVP or SIVP for all lattices within any polynomial approximation factors.

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/d70007b7-22bf-441e-b8ff-15fdf9ddf01bn%40list.nist.gov.

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/43acd2d9-5e3e-4589-a6ba-7c545d25d14b%40ntnu.no.

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/2d55b2b6.31ee1.18eccacd098.Coremail.ylzhao%40fudan.edu.cn.