Optimizing $c$-sum BKW and Faster Quantum Variant for LWE

Jinzheng Cao; Qingfeng Cheng; Jian Weng

doi:10.62056/a6qj5w7sf

Optimizing $c$-sum BKW and Faster Quantum Variant for LWE

Authors

Jinzheng Cao, Qingfeng Cheng, Jian Weng

Jinzheng Cao

Information Engineering University, Zhengzhou, China
caojinzheng at 126 dot com

Qingfeng Cheng

Information Engineering University, Zhengzhou, China
qingfengc2008 at sina dot com

Jian Weng

Jinan University, Guangzhou, China
cryptjweng at gmail dot com

Keywords: LWE BKW algorithm Quantum algorithm Time/memory tradeoff

Abstract

The Learning with Errors (LWE) problem has become one of the most prominent candidates of post-quantum cryptography, offering promising potential to meet the challenge of quantum computing. From a theoretical perspective, optimizing algorithms to solve LWE is a vital task for the analysis of this cryptographic primitive. In this paper, we propose a fine-grained time/memory trade-off method to analyze c-sum BKW variants for LWE in both classical and quantum models, then offer new complexity bounds for multiple BKW variants determined by modulus q, dimension k, error rate alpha, and stripe size b. Through our analysis, optimal parameters can be efficiently found for different settings, and the minimized complexities are lower than existing results. Furthermore, we enhance the performance of c-sum BKW in the quantum computing model by adopting the quantum Meet-in-the-Middle technique as c-sum solver instead of the naive c-sum technique. Our complexity trade-off formula also applies to the quantum version of BKW, and optimizes the theoretical quantum time and memory costs, which are exponentially lower than existing quantum c-sum BKW variants.

References

[ACF⁺15]

Martin Albrecht, Carlos Cid, Jean-Charles Faugere, Robert Fitzpatrick, and Ludovic Perret. On the complexity of the BKW algorithm on LWE. Designs, Codes and Cryptography, 74, February 2015. DOI: 10.1007/s10623-013-9864-x

Google Scholar ePrint

[AFFP14]

Martin R. Albrecht, Jean-Charles Faugère, Robert Fitzpatrick, and Ludovic Perret. Lazy modulus switching for the BKW algorithm on LWE. In Hugo Krawczyk, editor, Public-Key Cryptography – PKC 2014, pages 429–445, Berlin, Heidelberg. 2014. Springer Berlin Heidelberg. DOI: 10.1007/978-3-642-54631-0_25

Google Scholar ePrint

[BCSS23]

Xavier Bonnetain, André Chailloux, André Schrottenloher, and Yixin Shen. Finding Many Collisions via Reusable Quantum Walks. In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology – EUROCRYPT 2023, pages 221–251, Cham. 2023. Springer Nature Switzerland. DOI: 10.1007/978-3-031-30589-4_8

Google Scholar ePrint

[BGJ⁺21]

Alessandro Budroni, Qian Guo, Thomas Johansson, Erik Mårtensson, and Paul Stankovski Wagner. Improvements on Making BKW Practical for Solving LWE. Cryptography, 5(4), 2021. DOI: 10.3390/cryptography5040031

Google Scholar ePrint

[BHMT02]

Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplication and estimation. Contemporary Mathematics, 305:53-74, 2002. DOI: 10.1090/conm/305

Google Scholar ePrint

[BHT98]

Gilles Brassard, Peter Høyer, and Alain Tapp. Quantum cryptanalysis of hash and claw-free functions. In Cláudio L. Lucchesi and Arnaldo V. Moura, editors, LATIN'98: Theoretical Informatics, pages 163–169, Berlin, Heidelberg. 1998. Springer Berlin Heidelberg. DOI: 10.1007/BFb0054319

Google Scholar ePrint

[BKW03]

Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. Journal of ACM, 50(4):506-519, July 2003. DOI: 10.1145/792538.792543

Google Scholar ePrint

[BTV16]

Sonia Bogos, Florian Tramér, and Serge Vaudenay. On solving LPN using BKW and variants. Cryptography and Communications, 8:331-369, 2016. DOI: 10.1007/s12095-015-0149-2

Google Scholar ePrint

[Cry06]

Mary Cryan. Probability and computing: Randomized algorithms and probabilistic analysis. Bulletin of Symbolic Logic, 12(2):304-308, 2006. DOI: 10.1017/S107989860000278X

Google Scholar ePrint

[DTV15]

Alexandre Duc, Florian Tramèr, and Serge Vaudenay. Better algorithms for LWE and LWR. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology – EUROCRYPT 2015, pages 173–202, Berlin, Heidelberg. 2015. Springer Berlin Heidelberg. DOI: 10.1007/978-3-662-46800-5_8

Google Scholar ePrint

[EHK⁺18]

Andre Esser, Felix Heuer, Robert Kübler, Alexander May, and Christian Sohler. Dissection-BKW. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology – CRYPTO 2018, pages 638–666, Cham. 2018. Springer International Publishing. DOI: 10.1007/978-3-319-96881-0_22

Google Scholar ePrint

[GJL14]

Qian Guo, Thomas Johansson, and Carl Löndahl. Solving LPN using covering codes. In Tetsu Iwata and Palash Sarkar, editors, Advances in Cryptology - ASIACRYPT 2014, volume 8873, pages 1–20, Germany. 2014. Springer. DOI: 10.1007/s00145-019-09338-8

Google Scholar ePrint

[GJMS17]

Qian Guo, Thomas Johansson, Erik Mårtensson, and Paul Stankovski. Coded-BKW with sieving. In Tsuyoshi Takagi and Thomas Peyrin, editors, Advances in Cryptology – ASIACRYPT 2017, pages 323–346, Cham. 2017. Springer International Publishing. DOI: 10.1007/978-3-319-70694-8_12

Google Scholar ePrint

[GJS15]

Qian Guo, Thomas Johansson, and Paul Stankovski. Coded-BKW: Solving LWE using lattice codes. In Rosario Gennaro and Matthew Robshaw, editors, Advances in Cryptology – CRYPTO 2015, pages 23–42, Berlin, Heidelberg. 2015. Springer Berlin Heidelberg. DOI: 10.1007/978-3-662-47989-6_2

Google Scholar ePrint

[GvVW17]

Florian Göpfert, Christine van Vredendaal, and Thomas Wunderer. A Hybrid Lattice Basis Reduction and Quantum Search Attack on LWE. In Tanja Lange and Tsuyoshi Takagi, editors, Post-Quantum Cryptography, pages 184–202, Cham. 2017. Springer International Publishing. DOI: 10.1007/978-3-319-59879-6_11

Google Scholar ePrint

[HGJ10]

Nick Howgrave-Graham and Antoine Joux. New Generic Algorithms for Hard Knapsacks. In Henri Gilbert, editor, Advances in Cryptology – EUROCRYPT 2010, pages 235–256, Berlin, Heidelberg. 2010. Springer Berlin Heidelberg. DOI: 10.1007/978-3-642-13190-5_12

Google Scholar ePrint

[KF15]

Paul Kirchner and Pierre-Alain Fouque. An improved BKW algorithm for LWE with applications to cryptography and lattices. In Rosario Gennaro and Matthew Robshaw, editors, Advances in Cryptology – CRYPTO 2015, pages 43–62, Berlin, Heidelberg. 2015. Springer Berlin Heidelberg. DOI: 10.1007/978-3-662-47989-6_3

Google Scholar ePrint

[KP20]

Iordanis Kerenidis and Anupam Prakash. Quantum gradient descent for linear systems and least squares. Phys. Rev. A, 101:022316, February 2020. DOI: 10.1103/PhysRevA.101.022316

Google Scholar ePrint

[Kup13]

Greg Kuperberg. Another subexponential-time quantum algorithm for the dihedral Hidden Subgroup Problem. In Simone Severini and Fernando Brandao, editors, 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013), volume 22 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20–34, Dagstuhl, Germany. 2013. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. DOI: 10.4230/LIPIcs.TQC.2013.20

Google Scholar ePrint

[LF06]

Éric Levieil and Pierre-Alain Fouque. An improved LPN algorithm. In Roberto De Prisco and Moti Yung, editors, Security and Cryptography for Networks, pages 348–359, Berlin, Heidelberg. 2006. Springer Berlin Heidelberg. DOI: 10.1007/11832072_24

Google Scholar ePrint

[LP11]

Richard Lindner and Chris Peikert. Better Key Sizes (and Attacks) for LWE-Based Encryption. In Topics in Cryptology – CT-RSA 2011, pages 319–339, Berlin, Heidelberg. 2011. Springer. DOI: 10.1007/978-3-642-19074-2_21

Google Scholar ePrint

[LY22]

Hanlin Liu and Yu Yu. A Non-heuristic Approach to Time-Space Tradeoffs and Optimizations for BKW. In Shweta Agrawal and Dongdai Lin, editors, Advances in Cryptology – ASIACRYPT 2022, pages 741–770, Cham. 2022. Springer Nature Switzerland. DOI: 10.1007/978-3-031-22969-5_25

Google Scholar ePrint

[LZ19]

Qipeng Liu and Mark Zhandry. On Finding Quantum Multi-collisions. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2019, pages 189–218, Cham. 2019. Springer International Publishing. DOI: 10.1007/978-3-030-17659-4_7

Google Scholar ePrint

[NPS20]

María Naya-Plasencia and André Schrottenloher. Optimal Merging in Quantum k-xor and k-sum Algorithms. In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology – EUROCRYPT 2020, pages 311–340, Cham. 2020. Springer International Publishing. DOI: 10.1007/978-3-030-45724-2_11

Google Scholar ePrint

[Reg05]

Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, pages 84-93, New York, NY, USA. 2005. Association for Computing Machinery. DOI: 10.1145/1060590.1060603

Google Scholar ePrint

[Sag]

SageMath. Accessed on June 10, 2024.

Google Scholar ePrint

[ZJW16]

Bin Zhang, Lin Jiao, and Mingsheng Wang. Faster algorithms for solving LPN. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology – EUROCRYPT 2016, pages 168–195, Berlin, Heidelberg. 2016. Springer Berlin Heidelberg. DOI: 10.1007/978-3-662-49890-3_7

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/a6qj5w7sf

History

Submitted: 2024-06-26
Accepted: 2024-09-02
Published: 2024-10-07

How to cite

Jinzheng Cao, Qingfeng Cheng, and Jian Weng, Optimizing $c$-sum BKW and Faster Quantum Variant for LWE. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/a6qj5w7sf.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{CiC-1-3-7,
    author = "Cao, Jinzheng and Cheng, Qingfeng and Weng, Jian",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "Optimizing $c$-sum {BKW} and Faster Quantum Variant for {LWE}",
    volume = "1",
    number = "3",
    date = "2024-10-07",
    year = "2024",
    issn = "3006-5496",
    doi = "10.62056/a6qj5w7sf"
}

TY - JOUR
AU - Cao, Jinzheng
AU - Cheng, Qingfeng
AU - Weng, Jian
PY  - 2024
TI  - Optimizing $c$-sum BKW and Faster Quantum Variant for LWE
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 3
DO  - 10.62056/a6qj5w7sf
UR  - https://doi.org/10.62056/a6qj5w7sf
AB  - <p>  The Learning with Errors (LWE) problem has  become one of the most prominent  candidates of post-quantum cryptography, offering promising potential to meet the challenge of quantum computing. From a theoretical perspective, optimizing algorithms to solve LWE is a vital task for the analysis of this cryptographic primitive. In this paper, we propose a fine-grained time/memory trade-off method to analyze c-sum BKW variants for LWE in both classical and quantum models, then offer new complexity bounds for multiple BKW variants determined by modulus q, dimension k, error rate alpha, and stripe size b. Through our analysis, optimal parameters can be efficiently found for different settings, and the minimized complexities are lower than existing results. Furthermore, we enhance the performance of c-sum BKW in the quantum computing model by adopting the quantum Meet-in-the-Middle technique as c-sum solver instead of the naive c-sum technique. Our complexity trade-off formula also applies to the quantum version of BKW, and optimizes the theoretical quantum time and memory costs, which are exponentially lower than  existing quantum c-sum BKW variants. </p>
ER  -

Jinzheng Cao, Qingfeng Cheng, and Jian Weng, Optimizing $c$-sum BKW and Faster Quantum Variant for LWE. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/a6qj5w7sf.