Random sampling algorithm was proposed firstly by Schnorr in 2003 to find short lattice vectors, as an alternative to enumeration. The follow-up developments in random sampling were mainly proposed by Fukase and Kashiwabara in 2015 and Aono and Nguyen in 2017. Although they extended the sampling space compared to Schnorr's work through the natural number representation, they did not show how to sample specifically in practice and what vectors should be sampled, in order to find short enough lattice vectors. In this paper, the authors firstly introduce a practical random sampling algorithm under some reasonable assumptions which can find short enough lattice vectors efficiently. Then, as an application of this new random sampling algorithm, the authors show that it can improve the performance of progressive BKZ algorithm in practice. Finally, the authors solve the Darmstadt's Lattice Challenge and get a series of new records in the dimension from 500 to 825, using the improved progressive BKZ algorithm.
Abstract
Random sampling algorithm was proposed firstly by Schnorr in 2003 to find short lattice vectors, as an alternative to enumeration. The follow-up developments in random sampling were mainly proposed by Fukase and Kashiwabara in 2015 and Aono and Nguyen in 2017. Although they extended the sampling space compared to Schnorr's work through the natural number representation, they did not show how to sample specifically in practice and what vectors should be sampled, in order to find short enough lattice vectors. In this paper, the authors firstly introduce a practical random sampling algorithm under some reasonable assumptions which can find short enough lattice vectors efficiently. Then, as an application of this new random sampling algorithm, the authors show that it can improve the performance of progressive BKZ algorithm in practice. Finally, the authors solve the Darmstadt's Lattice Challenge and get a series of new records in the dimension from 500 to 825, using the improved progressive BKZ algorithm.
关键词
Darmstadt's lattice challenge /
lattice /
lattice reduction algorithm /
post-quantum cryptography /
random sampling
{{custom_keyword}} /
Key words
Darmstadt's lattice challenge /
lattice /
lattice reduction algorithm /
post-quantum cryptography /
random sampling
{{custom_keyword}} /
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] Fischlin R and Seifert J P, Tensor-based trapdoors for CVP and their application to public key cryptography, IMA International Conference on Cryptography and Coding, 1999, 1746: 244-257.
[2] Hoffstein J, Pipher J, Silverman J H, et al., An Introduction to Mathematical Cryptography, 2nd Edition, Springer, New York, 2014.
[3] Regev O, On lattices, learning with errors, random linear codes, and cryptography, Journal of the ACM, 2009, 56(6): 1-40.
[4] Brakerski Z and Vaikuntanathan V, Fully homomorphic encryption from ring-lwe and security for key dependent messages, CRYPTO 2011, 2011, 6841: 505-524.
[5] Gentry C, Fully homomorphic encryption using ideal lattices, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, New York, 2009.
[6] Howe J, Pöppelmann T, O'neill M, et al., Practical lattice-based digital signature schemes, ACM Transactions on Embedded Computing Systems (TECS), 2015, 14(3): 1-24.
[7] Pan Y and Zhang F, Solving low-density multiple subset sum problems with SVP oracle, Journal of Systems Science & Complexity, 2016, 29(1): 228-242.
[8] Deng Y, Luo L, Pan Y, et al., On some computational problems in local fields, Journal of Systems Science & Complexity, 2022, 35(3): 1191-1200.
[9] Lenstra A K, Lenstra H W, and Lovász L, Factoring polynomials with rational coefficients, Math. Ann., 1982, 261: 513-534.
[10] Schnorr C P and Euchner M, Lattice basis reduction: Improved practical algorithms and solving subset sum problems, Math. Program., 1994, 66: 181-199.
[11] Chen Y and Nguyen P Q, BKZ 2.0: Better lattice security estimates, ASIACRYPT 2011, 2011, 7073: 1-20.
[12] Aono Y, Wang Y, Hayashi T, et al., Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator, EUROCRYPT 2016, 2016, 9665: 789-819.
[13] Bai S, Stehlé D, and Wen W, Measuring, simulating and exploiting the head concavity phenomenon in BKZ, Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, 2018.
[14] Gama N, Nguyen P Q, and Regev O, Lattice enumeration using extreme pruning, EUROCRYPT 2010, 2010, 6110: 257-278.
[15] Schnorr C P, Lattice reduction by random sampling and birthday methods, STACS 2003, 2003, 2607: 145-156.
[16] Fukase M and Kashiwabara K, An accelerated algorithm for solving SVP based on statistical analysis, JIP, 2015, 23(1): 67-80.
[17] Darmstadt's SVP Challenge, https://www.latticechallenge.org/svp-challenge/index.php.
[18] Aono Y and Nguyen P Q, Random sampling revisited: Lattice enumeration with discrete pruning, EUROCRYPT 2017, 2017, 10211: 65-102.
[19] Darmstadt's Lattice Challenge, http://www.latticechallenge.org/.
[20] Micciancio D and Regev O, Lattice-based cryptography, PQC 2009, Springer, Berlin/Heidelberg, 2009.
[21] Gama N and Nguyen P Q, Predicting lattice reduction, EUROCRYPT 2008, 2008, 4965: 31-51.
[22] Chen Y, Réduction de réseau et sécurité concréte du chiffrement complétement homomorphe, Doctor Degree Thesis, 2013.
[23] Rogers C A, The number of lattice points in a set, Proc. London Math. Soc., 1956, 6(3): 305-320.
[24] Yu Y and Ducas L, Second order statistical behavior of LLL and BKZ, SAC 2017, 2017, 10719: 3-22.
[25] NTL Library Homepage, http://shoup.net/ntl/.
[26] Progressive BKZ Library Homepage, https://www2.nict.go.jp/security/pbkzcode/.
[27] Buchmann J, Lindner R, and Rückert M, Explicit hard instances of the shortest vector problem, PQC 2008, 2008, 5299: 79-94.
[28] Ajtai M, Generating hard instances of lattice problems, STOC 1996, 1996, 1644: 1-9.
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
This research was supported by the National Natural Science Foundation of China under Grant Nos. 62032009 and 62102440.
{{custom_fund}}
PDF(1708 KB)
