Awesome Machine Learning for Crypto(Lattice Problem)

We would like to maintain a list of resources that focus on solving lattice problems, particularly the Shortest Vector Problem (SVP) and related tasks like lattice basis reduction, utilizing classical algorithms, heuristic methods, and modern machine learning technologies.

Maintained by Jinchen Yu, Wenzheng Pan, Xinhao Zheng, Yuhao Zhang, Junchi Yan. We thank all the researchers who have contributed to this field.

Content

1. Survey & Foundations
2. Problems
2.1 Lattice Reduction (LLL, BKZ, etc.)	2.2 Shortest Vector Problem (SVP)
2.3 Closest Vector Problem (CVP)	2.4 Machine Learning for Lattice Problems
2.5 Quantum Method

Survey Papers & Foundations

This section includes foundational papers that define the problems and survey classical solution methods.

1. Factoring polynomials with rational coefficients. Mathematische Annalen, 1982. journal Lenstra, A. K. and Lenstra, H. W. and Lovász, L.

2. Improved algorithms for integer programming and related lattice problems. STOC, 1983. paper Kannan, Ravi.

3. Minkowski's convex body theorem and integer programming. Mathematics of operations research, 1987. journal Kannan, Ravi.

4. Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Mathematics of computation, 1985. journal Fincke, Ulrich and Pohst, Michael.

5. On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications. ACM Sigsam Bulletin, 1981. journal Pohst, Michael.

6. Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Mathematical programming, 1994. journal Schnorr, Claus-Peter and Euchner, Martin.

7. Closest vector problem. In Complexity of lattice problems: a cryptographic perspective, 2002. journal Micciancio, Daniele and Goldwasser, Shafi.

8. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM (JACM), 2009. journal Regev, Oded.

Problems

Lattice Reduction

1. Factoring polynomials with rational coefficients. Mathematische Annalen, 1982. journal Lenstra, A. K. and Lenstra, H. W. and Lovász, L.

2. Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Mathematical programming, 1994. journal Schnorr, Claus-Peter and Euchner, Martin.

3. Attacking the Chor-Rivest cryptosystem by improved lattice reduction. EUROCRYPT, 1995. paper Schnorr, Claus-Peter and Hörner, Horst Helmut.

4. BKZ 2.0: Better lattice security estimates. ASIACRYPT, 2011. paper Chen, Yuanmi and Nguyen, Phong Q.

5. PotLLL: a polynomial time version of LLL with deep insertions. Designs, codes and cryptography, 2014. journal Fontein, Felix and Schneider, Michael and Wagner, Urs.

6. Practical, predictable lattice basis reduction. EUROCRYPT, 2016. paper Micciancio, Daniele and Walter, Michael.

7. Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator. EUROCRYPT, 2016. paper Aono, Yoshinori and Wang, Yuntao and Hayashi, Takuya and Takagi, Tsuyoshi.

8. Explicit formula for Gram-Schmidt vectors in LLL with deep insertions and its applications. International Conference on Number-Theoretic Methods in Cryptology, 2017. paper Yamaguchi, Junpei and Yasuda, Masaya.

9. A new polynomial-time variant of LLL with deep insertions for decreasing the squared-sum of Gram–Schmidt lengths. Designs, Codes and Cryptography, 2019. journal Yasuda, Masaya and Yamaguchi, Junpei.

10. Self-dual DeepBKZ for finding short lattice vectors. Journal of Mathematical Cryptology, 2020. journal Yasuda, Masaya.

11. Development of a dual version of DeepBKZ and its application to solving the LWE challenge. AFRICACRYPT, 2018. paper Yasuda, Masaya and Yamaguchi, Junpei and Ooka, Michiko and Nakamura, Satoshi.

Shortest Vector Problem (SVP)

1. The shortest vector problem in L2 is NP-hard for randomized reductions. STOC, 1998. paper Ajtai, Miklós.

2. A sieve algorithm for the shortest lattice vector problem. STOC, 2001. paper Ajtai, Miklós and Kumar, Ravi and Sivakumar, Dandapani.

3. Parallel enumeration of shortest lattice vectors. Euro-Par, 2010. paper Dagdelen, Özgür and Schneider, Michael.

4. Lattice enumeration using extreme pruning. EUROCRYPT, 2010. paper Gama, Nicolas and Nguyen, Phong Q. and Regev, Oded.

5. Faster exponential time algorithms for the shortest vector problem. SODA, 2010. paper Micciancio, Daniele and Voulgaris, Panagiotis.

6. Sieve algorithms for the shortest vector problem are practical. Journal of Mathematical Cryptology, 2008. journal Nguyen, Phong Q. and Vidick, Thomas.

7. Improved Nguyen-Vidick heuristic sieve algorithm for shortest vector problem. ASIACCS, 2011. paper Wang, Xiaoyun and Liu, Mingjie and Tian, Chengliang and Bi, Jingguo.

8. Solving shortest and closest vector problems: The decomposition approach. IACR Cryptology ePrint Archive, 2013. paper Becker, Anja and Gama, Nicolas and Joux, Antoine.

9. Speeding-up lattice sieving without increasing the memory, using sub-quadratic nearest neighbor search. IACR Cryptology ePrint Archive, 2015. paper Becker, Anja and Gama, Nicolas and Joux, Antoine.

10. Sieving for shortest vectors in lattices using angular locality-sensitive hashing. CRYPTO, 2015. paper Laarhoven, Thijs.

11. New directions in nearest neighbor searching with applications to lattice sieving. SODA, 2016. paper Becker, Anja and Ducas, Léo and Gama, Nicolas and Laarhoven, Thijs.

12. Shortest vector from lattice sieving: a few dimensions for free. EUROCRYPT, 2018. paper Ducas, Léo.

13. The general sieve kernel and new records in lattice reduction. EUROCRYPT, 2019. paper Albrecht, Martin R. and Ducas, Léo and Herold, Gottfried and Kirshanova, Elena and Postlethwaite, Eamonn W. and Stevens, Marc.

14. Darmstadt SVP challenges. website Schneider, Michael and Gama, Nicolas.

Closest Vector Problem (CVP)

1. Bounded-distance decoding: algorithms, decision regions, and pseudo nearest neighbors. IEEE Transactions on Information Theory, 2002. journal Amrani, Ofer and Be'ery, Yair.

2. On bounded distance decoding, unique shortest vectors, and the minimum distance problem. CRYPTO, 2009. paper Lyubashevsky, Vadim and Micciancio, Daniele.

3. Closest vector problem. In Complexity of lattice problems: a cryptographic perspective, 2002. journal Micciancio, Daniele and Goldwasser, Shafi.

4. Lattice reduction. IEEE Signal Processing Magazine, 2011. journal Wübben, Dirk and Seethaler, Dominik and Jalden, Joakim and Matz, Gerald.

Machine Learning for Lattice Problems

1. Neural Lattice Reduction: A Self-Supervised Geometric Deep Learning Approach. arXiv, 2023. paper Marchetti, Giovanni Luca and Cesa, Gabriele and Kumar, Pratik and Behboodi, Arash.

2. Salsa: Attacking lattice cryptography with transformers. NeurIPS, 2022. paper Wenger, Emily and Chen, Mingjie and Charton, Francois and Lauter, Kristin E.

3. Attack on Shortest Vector Problem of Lattice Using Machine Learning. International Conference on Trends in Computational and Cognitive Engineering, 2023. paper Singh, Shaurya Pratap and Chaurasia, Brijesh Kumar and Tripathi, Tanmay and Gupta, Siddharth and Pal, Ayush.

4. Heuristic time complexity of nisq shortest-vector-problem solvers. arXiv, 2025. paper Prokop, Miloš and Wallden, Petros.

5. RL4CO: a Unified Reinforcement Learning for Combinatorial Optimization Library. NeurIPS Workshop, 2023. paper code Berto, Federico and Hua, Chuanbo and Park, Junyoung and Kim, Minsu and Kim, Hyeonah and Son, Jiwoo and Kim, Haeyeon and Kim, Joungho and Park, Jinkyoo.

6. DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization. NeurIPS, 2023. paper code Sun, Zhiqing and Yang, Yiming.

7. Fast T2T: Optimization consistency speeds up diffusion-based training-to-testing solving for combinatorial optimization. NeurIPS, 2024. paper code Li, Yang and Guo, Jinpei and Wang, Runzhong and Zha, Hongyuan and Yan, Junchi.

8. COExpander: Adaptive Solution Expansion for Combinatorial Optimization. ICML, 2025. paper code Ma, Jiale and Pan, Wenzheng and Li, Yang and Yan, Junchi.

9. ML4CO-Bench-101: Benchmark Machine Learning for Classic Combinatorial Problems on Graphs. NeurIPS, 2025. paper code Ma, Jiale and Pan, Wenzheng and Li, Yang and Yan, Junchi.

10. UniCO: On Unified Combinatorial Optimization via Problem Reduction to Matrix-Encoded General TSP. ICLR, 2025. paper code Pan, Wenzheng and Xiong, Hao and Ma, Jiale and Zhao, Wentao and Li, Yang and Yan, Junchi.

11. A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization. ICML, 2024. paper code Sanokowski, Sebastian and Hochreiter, Sepp and Lehner, Sebastian.

12. Unsupervised Learning for Combinatorial Optimization Needs Meta Learning. ICLR, 2023. paper code Wang, Haoyu Peter and Li, Pan.

Quantum Method

1. Quantum enumeration approaches to solving the shortest vector problem. PhD Thesis, The University of Edinburgh, 2025. paper arXiv Prokop, Miloš.

2. Quantum-classical hybrid algorithm for solving the learning-with-errors problem on NISQ devices. Communications Physics, 2025. journal doi Zheng, Muxi and Zeng, Jinfeng and Yang, Wentao and Chang, Pei-Jie and Lu, Quanfeng and Yan, Bao and Zhang, Haoran and Wang, Min and Wei, ShiJie and Long, Gui-Lu.

3. Iterative Partition Search Variational Quantum Algorithm for Solving Shortest Vector Problem. arXiv, 2025. paper Huang, Zi-Wen and Ni, Xiao-Hui and Fan, Jia-Cheng and Qin, Su-Juan and Huang, Wei and Xu, Bing-Jie and Gao, Fei.

4. Quantum algorithmic solutions to the shortest vector problem on simulated coherent Ising machines. arXiv, 2025. paper Dable-Heath, Edmund and Casas, L. and Porter, C. and Mintert, F. and Ling, C.

5. An efficient variational quantum Korkin-Zolotarev algorithm for solving shortest vector problems. arXiv, 2025. paper Authors from the Institute of Southwestern Communication and Beijing University of Posts and Telecommunications.

6. Quantum enumeration approaches to solving the shortest vector problem. INSPIRE HEP, 2025. record Prokop, Miloš.

7. Iterative Partition Search Variational Quantum Algorithm for Solving Shortest Vector Problem. arXiv, 2025. paper Huang, Zi-Wen and Ni, Xiao-Hui and Fan, Jia-Cheng and Qin, Su-Juan and Huang, Wei and Xu, Bing-Jie and Gao, Fei.

Related Algorithms & Tools

1. Numerical aspects of Gram-Schmidt orthogonalization of vectors. Linear algebra and its applications, 1983. journal Ruhe, Axel.

2. Learning representations by back-propagating errors. Nature, 1986. journal Rumelhart, David E. and Hinton, Geoffrey E. and Williams, Ronald J.

3. A quantum approximate optimization algorithm. arXiv, 2014. paper Farhi, Edward and Goldstone, Jeffrey and Gutmann, Sam.

4. Report on post-quantum cryptography. National Institute of Standards and Technology, 2016. journal Chen, Lily and Jordan, Stephen and Liu, Yi-Kai and Moody, Dustin and Peralta, Rene and Perlner, Ray A. and Smith-Tone, Daniel.

5. Proximal policy optimization algorithms. arXiv, 2017. paper Schulman, John and Wolski, Filip and Dhariwal, Prafulla and Radford, Alec and Klimov, Oleg.

6. Proximal policy optimization and its dynamic version for sequence generation. arXiv, 2018. paper Tuan, Yi-Lin and Zhang, Jinzhi and Li, Yujia and Lee, Hung-yi.

7. HEBO: Pushing The Limits of Sample-Efficient Hyperparameter Optimisation. Journal of Artificial Intelligence Research, 2022. journal code Cowen-Rivers, Alexander and Lyu, Wenlong and Tutunov, Rasul and Wang, Zhi and Grosnit, Antoine and Griffiths, Ryan-Rhys and Maravel, Alexandre and Hao, Jianye and Wang, Jun and Peters, Jan and Ammar, Haitham Bou.