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

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

[27] Ramos-Calderer S, Bellini E, Latorre JI, Manzano M, Mateu V. Quantum search for scaled hash function preimages. Quantum
Information Processing, 2021, 20(5): 180. [doi: 10.1007/s11128-021-03118-9]
[28] Baek S, Kim J. Quantum rebound attacks on reduced-round aria-based hash functions. ETRI Journal, 2023, 45(3): 365–378. [doi: 10.
4218/etrij.2022-0032]
[29] Hoffstein J, Pipher J, Silverman JH. NTRU: A ring-based public key cryptosystem. In: Proc. of the 3rd Int’l Algorithmic Number
Theory Symp. Portland: Springer, 1998. 267–288. [doi: 10.1007/BFb0054868]
[30] Gentry C, Sahai A, Waters B. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-
based. In: Proc. of the 33rd Annual Int’l Cryptology Conf. Santa Barbara: Springer, 2013. 75–92. [doi: 10.1007/978-3-642-40041-4_5]
[31] Regev O. Quantum computation and lattice problems. SIAM Journal on Computing, 2004, 33(3): 738–760. [doi: 10.1137/
S0097539703440678]
[32] Aono Y, Nguyen PQ, Seito T, Shikata J. Lower bounds on lattice enumeration with extreme pruning. In: Proc. of the 38th Annual Int’l
Cryptology Conf. Santa Barbara: Springer, 2018. 608–637. [doi: 10.1007/978-3-319-96881-0_21]
[33] May A, Nowakowski J. Too many hints—When LLL breaks LWE. In: Proc. of the 29th Int’l Conf. on the Theory and Application of
Cryptology and Information Security. Guangzhou: Springer, 2023. 106–137. [doi: 10.1007/978-981-99-8730-6_4]
[34] Ajtai M, Kumar R, Sivakumar D. A sieve algorithm for the shortest lattice vector problem. In: Proc. of the 33rd Annual ACM Symp. on
Theory of Computing. Hersonissos: ACM, 2001. 601–610. [doi: 10.1145/380752.380857]
[35] Micciancio D, Voulgaris P. Faster exponential time algorithms for the shortest vector problem. In: Proc. of the 21st Annual ACM-SIAM
Symp. on Discrete Algorithms. Austin: SIAM, 2010. 1468–1480. [doi: 10.1137/1.9781611973075.119]
[36] Bi L, Lu XH, Wang KP. Research status and development trend of lattice sieving. Journal of Cryptologic Research, 2021, 8(5): 735–757
(in Chinese with English abstract). [doi: 10.13868/j.cnki.jcr.000474]
[37] Pohst M. On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications. ACM
SIGSAM Bulletin, 1981, 15(1): 37–44. [doi: 10.1145/1089242.1089247]
[38] Nguyen PQ, Vallèe B. The LLL Algorithm: Survey and Applications. Berlin: Springer, 2010. [doi: 10.1007/978-3-642-02295-1]
[39] Lenstra AK, Lenstra Jr HW, Lovász L. Factoring polynomials with rational coefficients. Mathematische Annalen, 1982, 261(4):
515–534. [doi: 10.1007/BF01457454]
[40] Schnorr CP, Euchner M. Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Mathematical
Programming, 1994, 66(1–3): 181–199. [doi: 10.1007/BF01581144]
[41] Esser A, Heuer F, Kübler R, May A, Sohler C. Dissection-BKW. In: Proc. of the 38th Annual Int’l Cryptology Conf. Santa Barbara:
Springer, 2018. 638–666. [doi: 10.1007/978-3-319-96881-0_22]
[42] Albrecht MR, Shen YX. Quantum augmented dual attack. IACR Cryptology ePrint Archive, 2022.656.
[43] Liu HL, Yu Y. A non-heuristic approach to time-space tradeoffs and optimizations for BKW. In: Proc. of the 28th Int’l Conf. on the
Theory and Application of Cryptology and Information Security. Taipei: Springer, 2022. 741–770. [doi: 10.1007/978-3-031-22969-
5_25]
[44] Chen YL. Quantum algorithms for lattice problems. IACR Cryptology ePrint Archive, 2024.555.
[45] Fluhrer SR. Quantum cryptanalysis of NTRU. IACR Cryptology ePrint Archive, 2015.676.
[46] Laaji EH, Azizi A, Ezzouak S. Two quantum attack algorithms against NTRU when the private key and plaintext are codified in ternary
polynomials. In: Serrhini M, Silva C, Aljahdali S, eds. Innovation in Information Systems and Technologies to Support Learning
Research. Cham: Springer, 2019. 551–562. [doi: 10.1007/978-3-030-36778-7_61]
[47] Dong J. The quantum algorithm analysis of NTRU cryptography and the research of quantum lattice sieving algorithm [MS. Thesis].
Beijing: Beijing University of Posts and Telecommunications, 2021 (in Chinese with English abstract). [doi: 10.26969/d.cnki.gbydu.
2021.001999]
[48] Laarhoven T, Mosca M, van de Pol J. Solving the shortest vector problem in lattices faster using quantum search. In: Proc. of the 5th Int’l
Conf. on Post-quantum Cryptography. Limoges: Springer, 2013. 83–101. [doi: 10.1007/978-3-642-38616-9_6]
[49] Laarhoven T, Mosca M, van de Pol J. Finding shortest lattice vectors faster using quantum search. Designs, Codes and Cryptography,
2015, 77(2): 375–400. [doi: 10.1007/s10623-015-0067-5]
[50] Becker A, Laarhoven T. Efficient (ideal) lattice sieving using cross-polytope LSH. In: Proc. of the 8th Int’l Conf. on Cryptology in
Africa. Fes: Springer, 2016. 3–23. [doi: 10.1007/978-3-319-31517-1_1]
[51] Becker A, Ducas L, Gama N, Laarhoven T. New directions in nearest neighbor searching with applications to lattice sieving. In: Proc. of
the 27th Annual ACM-SIAM Symp. on Discrete Algorithms. Arlington: Society for Industrial and Applied Mathematics, 2016. 10–24.
[doi: 10.5555/2884435.2884437]