Page 426 - 《软件学报》2026年第1期

曹金政 等: 格上困难问题量子求解算法综述 423

[74] Zhang F, Pan YB, Hu GR. A three-level sieve algorithm for the shortest vector problem. In: Proc. of the 20th Int’l Conf. on Selected
Areas in Cryptography. Burnaby: Springer, 2014. 29–47. [doi: 10.1007/978-3-662-43414-7_2]
[75] Bai S, Laarhoven T, Stehlè D. Tuple lattice sieving. LMS Journal of Computation and Mathematics, 2016, 19(Special Issue A):
146–162. [doi: 10.1112/S1461157016000292]
[76] Herold G, Kirshanova E, Laarhoven T. Speed-ups and time-memory trade-offs for tuple lattice sieving. In: Proc. of the 21st IACR Int’l
Conf. on Public-key Cryptography. Rio de Janeiro: Springer, 2018. 407–436. [doi: 10.1007/978-3-319-76578-5_14]
[77] Doulgerakis E, Laarhoven T, de Weger B. Sieve, enumerate, slice, and lift: Hybrid lattice algorithms for SVP via CVPP. In: Proc. of the
12th Int’l Conf. on Cryptology in Africa. Cairo: Springer, 2020. 301–320. [doi: 10.1007/978-3-030-51938-4_15]
[78] Montanaro A. Quantum-walk speedup of backtracking algorithms. Theory of Computing, 2018, 14: 15. [doi: 10.4086/toc.2018.v014a015]
[79] Cerezo M, Arrasmith A, Babbush R, Benjamin SC, Endo S, Fujii K, McClean JR, Mitarai K, Yuan X, Cincio L, Coles PJ. Variational
quantum algorithms. Nature Reviews Physics, 2021, 3(9): 625–644. [doi: 10.1038/s42254-021-00348-9]
[80] Joseph D, Ghionis A, Ling C, Mintert F. Not-so-adiabatic quantum computation for the shortest vector problem. Physical Review
Research, 2020, 2(1): 013361. [doi: 10.1103/PhysRevResearch.2.013361]
[81] Joseph D, Callison A, Ling C, Mintert F. Two quantum ising algorithms for the shortest-vector problem. Physical Review A, 2021,
103(3): 032433. [doi: 10.1103/PhysRevA.103.032433]
[82] Chen YM, Nguyen PQ. BKZ 2.0: Better lattice security estimates. In: Proc. of the 17th Int’l Conf. on the Theory and Application of
Cryptology and Information Security. Seoul: Springer, 2011. 1–20. [doi: 10.1007/978-3-642-25385-0_1]
[83] Schnorr CP. A more efficient algorithm for lattice basis reduction. Journal of Algorithms, 1988, 9(1): 47–62. [doi: 10.1016/0196-6774
(88)90004-1]
[84] Nguên PQ, Stehlè D. Floating-point LLL revisited. In: Proc. of the 24th Annual Int’l Conf. on the Theory and Applications of
Cryptographic Techniques. Aarhus: Springer, 2005. 215–233. [doi: 10.1007/11426639_13]
[85] Ryan K, Heninger N. Fast practical lattice reduction through iterated compression. In: Proc. of the 43rd Annual Int’l Cryptology Conf.
Santa Bar: Springer, 2023. 3–36. [doi: 10.1007/978-3-031-38548-3_1]
[86] Lin D, Xiang ZJ, Xu RQ, Zhang SS, Zeng XY. Optimized quantum implementation of AES. Quantum Information Processing, 2023,
22(9): 352. [doi: 10.1007/s11128-023-04043-9]
[87] Bhattacherjee S, Hernandez-Castro JC, Moyler J. A greedy global framework for lattice reduction using deep insertions. IACR
Communications in Cryptology, 2025, 2(1): 1–46. [doi: 10.62056/aevuommol]
[88] Albrecht M, Bai S, Fouque PA, Kirchner P, Stehlé D, Wen W. Faster enumeration-based lattice reduction: Root Hermite factor k 1/(2k)
k/8+o(k)
time k . In: Proc. of the 40th Annual Int’l Cryptology Conf. Santa Barbara: Springer, 2023. 186–212. [doi: 10.1007/978-3-030-
56880-1_7]
[89] Albrecht MR, Cid C, Faugère JC, Fitzpatrick R, Perret L. On the complexity of the BKW algorithm on LWE. Designs, Codes and
Cryptography, 2015, 74(2): 325–354. [doi: 10.1007/s10623-013-9864-x]
[90] Wei Y, Bi L, Lu XH, Wang KP. Security estimation of LWE via BKW algorithms. Cybersecurity, 2023, 6(1): 24. [doi: 10.1186/s42400-
023-00158-9]
[91] Guo Q, Johansson T, Mårtensson E, et al. Coded-BKW with sieving. In: Proc. of the 23rd Int’l Conf. on the Theory and Applications of
Cryptology and Information Security (ASIACRYPT 2017). Hong Kong: Springer, 2017. 323–346. [doi: 10.1007/978-3-319-70694-
8_12]
[92] Chang WL, Vasilakos AV. Fundamentals of Quantum Programming in IBM’s Quantum Computers. Cham: Springer, 2021. [doi: 10.
1007/978-3-030-63583-1]
[93] Schrottenloher A. Quantum linear key-recovery attacks using the QFT. In: Proc. of the 43rd Annual Int’l Cryptology Conf. Santa
Barbara: Springer, 2023. 258–291. [doi: 10.1007/978-3-031-38554-4_9]
[94] Dachman-Soled D, Gong HJ, Kippen H, Shahverdi A. BKW meets Fourier new algorithms for LPN with sparse parities. In: Proc. of the
19th Theory of Cryptography Conf. Raleigh: Springer, 2021. 658–688. [doi: 10.1007/978-3-030-90453-1_23]
[95] Pouly A, Shen YX. Provable dual attacks on learning with errors. In: Proc. of the 43rd Annual Int’l Conf. on the Theory and
Applications of Cryptographic Techniques. Zurich: Springer, 2024. 256–285. [doi: 10.1007/978-3-031-58754-2_10]
[96] Guo Q, Johansson T. Faster dual lattice attacks for solving LWE with applications to CRYSTALS. In: Proc. of the 27th Int’l Conf. on
the Theory and Application of Cryptology and Information Security. Singapore: Springer, 2021. 33–62. [doi: 10.1007/978-3-030-92068-
5_2]
[97] Lv LH, Yan B, Wang H, Ma Z, Fei YY, Meng XD, Duan QH. Using variational quantum algorithm to solve the LWE problem. Entropy,
2022, 24(10): 1428. [doi: 10.3390/e24101428]