Concrete Analysis of Quantum Lattice Enumeration

Shi Bai; Maya Iggy van Hoof; Floyd B. Johnson; Tanja Lange; Tran Ngo

doi:10.1007/978-981-99-8727-6_5

Concrete Analysis of Quantum Lattice Enumeration

Shi Bai
, Maya Iggy van Hoof
, Floyd B. Johnson
, Tanja Lange
, Tran Ngo

Coding Theory and Cryptology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

4 Citations (Scopus)

Abstract

Lattice reduction algorithms such as BKZ (Block-Korkine-Zolotarev) play a central role in estimating the security of lattice-based cryptography. The subroutine in BKZ which finds the shortest vector in a projected sublattice can be instantiated with enumeration algorithms. The enumeration procedure can be seen as a depth-first search on some “enumeration tree” whose nodes denote a partial assignment of the coefficients, corresponding to lattice points as a linear combination of the lattice basis with the coefficients. This work provides a concrete analysis for the cost of quantum lattice enumeration based on Montanaro’s quantum tree backtracking algorithm. More precisely, we give a concrete implementation in the quantum circuit model. We also show how to optimize the circuit depth by parallelizing the components. Based on the circuit designed, we discuss the concrete quantum resource estimates required for lattice enumeration.

Original language	English
Title of host publication	Advances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
Editors	Jian Guo, Ron Steinfeld
Publisher	Springer
Pages	131-166
Number of pages	36
ISBN (Print)	9789819987269
DOIs	https://doi.org/10.1007/978-981-99-8727-6_5
Publication status	Published - 2023
Event	29th Annual International Conference on the Theory and Application of Cryptology and Information Security, Asiacrypt 2023 - Guangzhou, China Duration: 4 Dec 2023 → 8 Dec 2023

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	14440 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	29th Annual International Conference on the Theory and Application of Cryptology and Information Security, Asiacrypt 2023
Country/Territory	China
City	Guangzhou
Period	4/12/23 → 8/12/23

Bibliographical note

Publisher Copyright:
© International Association for Cryptologic Research 2023.

Funding

Author list in alphabetical order; see https://ams.org/profession/leaders/ CultureStatement04.pdf. This research was funded in part by the U.S. National Science Foundation under Grant No. 2044855 & 2122229, the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy–EXC 2092 CASA–390781972 “Cyber Security in the Age of Large-Scale Adversaries”, and the Taiwan’s Executive Yuan Data Safety and Talent Cultivation Project (AS-KPQ-109-DSTCP). This work was done in part while Tanja Lange was visiting the Simons Institute for the Theory of Computing and in part when she was with Academia Sinica, Taiwan. c○ International Association for Cryptologic Research 2023

Funders	Funder number
National Science Foundation	2122229, 2044855
University of California at Berkeley
Deutsche Forschungsgemeinschaft	EXC 2092 CASA–390781972
Academia Sinica Taiwan

Keywords

Enumeration
Lattices
Quantum algorithms
Quantum backtracking

Access to Document

10.1007/978-981-99-8727-6_5

https://eprint.iacr.org/2023/1623Licence: CC BY

Cite this

Bai, S., van Hoof, M. I., Johnson, F. B., Lange, T., & Ngo, T. (2023). Concrete Analysis of Quantum Lattice Enumeration. In J. Guo, & R. Steinfeld (Eds.), Advances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings (pp. 131-166). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14440 LNCS). Springer. https://doi.org/10.1007/978-981-99-8727-6_5

Bai, Shi ; van Hoof, Maya Iggy ; Johnson, Floyd B. et al. / Concrete Analysis of Quantum Lattice Enumeration. Advances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. editor / Jian Guo ; Ron Steinfeld. Springer, 2023. pp. 131-166 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{eaf04bb1dbd846518ce20c37a48a0a7d,

title = "Concrete Analysis of Quantum Lattice Enumeration",

abstract = "Lattice reduction algorithms such as BKZ (Block-Korkine-Zolotarev) play a central role in estimating the security of lattice-based cryptography. The subroutine in BKZ which finds the shortest vector in a projected sublattice can be instantiated with enumeration algorithms. The enumeration procedure can be seen as a depth-first search on some “enumeration tree” whose nodes denote a partial assignment of the coefficients, corresponding to lattice points as a linear combination of the lattice basis with the coefficients. This work provides a concrete analysis for the cost of quantum lattice enumeration based on Montanaro{\textquoteright}s quantum tree backtracking algorithm. More precisely, we give a concrete implementation in the quantum circuit model. We also show how to optimize the circuit depth by parallelizing the components. Based on the circuit designed, we discuss the concrete quantum resource estimates required for lattice enumeration.",

keywords = "Enumeration, Lattices, Quantum algorithms, Quantum backtracking",

author = "Shi Bai and \{van Hoof\}, \{Maya Iggy\} and Johnson, \{Floyd B.\} and Tanja Lange and Tran Ngo",

note = "Publisher Copyright: {\textcopyright} International Association for Cryptologic Research 2023.; 29th Annual International Conference on the Theory and Application of Cryptology and Information Security, Asiacrypt 2023 ; Conference date: 04-12-2023 Through 08-12-2023",

year = "2023",

doi = "10.1007/978-981-99-8727-6\_5",

language = "English",

isbn = "9789819987269",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "131--166",

editor = "Jian Guo and Ron Steinfeld",

booktitle = "Advances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings",

address = "Germany",

}

Bai, S, van Hoof, MI, Johnson, FB, Lange, T & Ngo, T 2023, Concrete Analysis of Quantum Lattice Enumeration. in J Guo & R Steinfeld (eds), Advances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14440 LNCS, Springer, pp. 131-166, 29th Annual International Conference on the Theory and Application of Cryptology and Information Security, Asiacrypt 2023, Guangzhou, China, 4/12/23. https://doi.org/10.1007/978-981-99-8727-6_5

Concrete Analysis of Quantum Lattice Enumeration. / Bai, Shi; van Hoof, Maya Iggy; Johnson, Floyd B. et al.
Advances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. ed. / Jian Guo; Ron Steinfeld. Springer, 2023. p. 131-166 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14440 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Concrete Analysis of Quantum Lattice Enumeration

AU - Bai, Shi

AU - van Hoof, Maya Iggy

AU - Johnson, Floyd B.

AU - Lange, Tanja

AU - Ngo, Tran

N1 - Publisher Copyright: © International Association for Cryptologic Research 2023.

PY - 2023

Y1 - 2023

N2 - Lattice reduction algorithms such as BKZ (Block-Korkine-Zolotarev) play a central role in estimating the security of lattice-based cryptography. The subroutine in BKZ which finds the shortest vector in a projected sublattice can be instantiated with enumeration algorithms. The enumeration procedure can be seen as a depth-first search on some “enumeration tree” whose nodes denote a partial assignment of the coefficients, corresponding to lattice points as a linear combination of the lattice basis with the coefficients. This work provides a concrete analysis for the cost of quantum lattice enumeration based on Montanaro’s quantum tree backtracking algorithm. More precisely, we give a concrete implementation in the quantum circuit model. We also show how to optimize the circuit depth by parallelizing the components. Based on the circuit designed, we discuss the concrete quantum resource estimates required for lattice enumeration.

AB - Lattice reduction algorithms such as BKZ (Block-Korkine-Zolotarev) play a central role in estimating the security of lattice-based cryptography. The subroutine in BKZ which finds the shortest vector in a projected sublattice can be instantiated with enumeration algorithms. The enumeration procedure can be seen as a depth-first search on some “enumeration tree” whose nodes denote a partial assignment of the coefficients, corresponding to lattice points as a linear combination of the lattice basis with the coefficients. This work provides a concrete analysis for the cost of quantum lattice enumeration based on Montanaro’s quantum tree backtracking algorithm. More precisely, we give a concrete implementation in the quantum circuit model. We also show how to optimize the circuit depth by parallelizing the components. Based on the circuit designed, we discuss the concrete quantum resource estimates required for lattice enumeration.

KW - Enumeration

KW - Lattices

KW - Quantum algorithms

KW - Quantum backtracking

UR - https://www.scopus.com/pages/publications/85184111586

U2 - 10.1007/978-981-99-8727-6_5

DO - 10.1007/978-981-99-8727-6_5

M3 - Conference contribution

AN - SCOPUS:85184111586

SN - 9789819987269

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 131

EP - 166

BT - Advances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings

A2 - Guo, Jian

A2 - Steinfeld, Ron

PB - Springer

T2 - 29th Annual International Conference on the Theory and Application of Cryptology and Information Security, Asiacrypt 2023

Y2 - 4 December 2023 through 8 December 2023

ER -

Bai S, van Hoof MI, Johnson FB, Lange T, Ngo T. Concrete Analysis of Quantum Lattice Enumeration. In Guo J, Steinfeld R, editors, Advances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Springer. 2023. p. 131-166. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-981-99-8727-6_5