{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:49:43Z","timestamp":1760147383017,"version":"build-2065373602"},"reference-count":36,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2023,1,28]],"date-time":"2023-01-28T00:00:00Z","timestamp":1674864000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>The bounded distance decoding (BDD) is a fundamental problem in lattice-based cryptography which is derived from the closest vector problem (CVP). In this paper, we adapt the lattice enumeration with discrete pruning, a burgeoning method for the shortest lattice vector problem (SVP), to solve BDD in various cryptanalysis scenarios using direct method. We first transfer the basic definition involved in discrete pruning technique from SVP to CVP, prove corresponding properties and give the specific procedures of the algorithm. Additionally, we use the discrete pruning technique to interpret the classical CVP algorithms, including Babai\u2019s nearest plane and Lindner\u2013Peikert nearest planes, which can be regarded as discrete pruned enumeration on some special pruning sets. We propose three probability models in the runtime analysis to accurately estimate the cost of our algorithm in different application scenarios. We study the application of discrete pruned enumeration for BDD mainly on LWE-based cryptosystem and DSA with partially known nonces. The experimental results show that our new algorithm has higher efficiency than the previous algorithms which directly solve BDD, including the nearest plane(s) algorithms and the lattice enumeration with classical pruning strategies, and we are able to recover the DSA secret with less leaked information than the previous works.<\/jats:p>","DOI":"10.3390\/sym15020355","type":"journal-article","created":{"date-parts":[[2023,1,30]],"date-time":"2023-01-30T07:34:41Z","timestamp":1675064081000},"page":"355","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Application of Discrete Pruned Enumeration in Solving BDD"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5459-9520","authenticated-orcid":false,"given":"Luan","family":"Luan","sequence":"first","affiliation":[{"name":"Henan Key Laboratory of Network Cryptography Technology, Zhengzhou 450001, China"},{"name":"PLA Information Engineering University, Zhengzhou 450001, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yanan","family":"Shi","sequence":"additional","affiliation":[{"name":"Henan Key Laboratory of Network Cryptography Technology, Zhengzhou 450001, China"},{"name":"PLA Information Engineering University, Zhengzhou 450001, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chunxiang","family":"Gu","sequence":"additional","affiliation":[{"name":"Henan Key Laboratory of Network Cryptography Technology, Zhengzhou 450001, China"},{"name":"PLA Information Engineering University, Zhengzhou 450001, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yonghui","family":"Zheng","sequence":"additional","affiliation":[{"name":"Henan Key Laboratory of Network Cryptography Technology, Zhengzhou 450001, China"},{"name":"PLA Information Engineering University, Zhengzhou 450001, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2023,1,28]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Kiayias, A. (2011, January 14\u201318). Better Key Sizes (and Attacks) for LWE-Based Encryption. Proceedings of the Topics in Cryptology\u2014CT-RSA, San Francisco, CA, USA.","DOI":"10.1007\/978-3-642-19074-2"},{"key":"ref_2","unstructured":"Dawson, E. (March, January 25). Solving BDD by Enumeration: An Update. Proceedings of the Topics in Cryptology\u2014CT-RSA, San Francisco, CA, USA."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Albrecht, M.R., Fitzpatrick, R., and G\u00f6pfert, F. (2014, January 5\u20138). On the Efficacy of Solving LWE by Reduction to Unique-SVP. Proceedings of the International Conference on Information Security and Cryptology, Fuzhou, China.","DOI":"10.1007\/978-3-319-12160-4_18"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/s10623-016-0326-0","article-title":"On the asymptotic complexity of solving LWE","volume":"86","author":"Herold","year":"2015","journal-title":"Des. Codes Cryptogr."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1515\/jmc-2015-0016","article-title":"On the concrete hardness of Learning with Errors","volume":"9","author":"Albrecht","year":"2015","journal-title":"J. Math. Cryptol."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Albrecht, M.R., G\u00f6pfert, F., Virdia, F., and Wunderer, T. (2017, January 3\u20137). Revisiting the Expected Cost of Solving uSVP and Applications to LWE. Proceedings of the Advances in Cryptology\u2014ASIACRYPT, Hong Kong, China.","DOI":"10.1007\/978-3-319-70694-8_11"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Bai, S., Miller, S., and Wen, W. (2019, January 9\u201311). A Refined Analysis of the Cost for Solving LWE via uSVP. Proceedings of the Progress in Cryptology\u2014AFRICACRYPT, Rabat, Morocco.","DOI":"10.1007\/978-3-030-23696-0_10"},{"key":"ref_8","unstructured":"Chen, H., Chua, L., Lauter, K., and Song, Y. (2022, December 26). On the Concrete Security of LWE with Small Secret. Cryptology ePrint Archive, Paper 2020\/539. Available online: https:\/\/eprint.iacr.org\/2020\/539."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Boneh, D., and Venkatesan, R. (1996, January 18\u201322). Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes. Proceedings of the Advances in Cryptology\u2014CRYPTO \u201996, Santa Barbara, CA, USA.","DOI":"10.1007\/3-540-68697-5_11"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/s00145-002-0021-3","article-title":"The Insecurity of the Digital Signature Algorithm with Partially Known Nonces","volume":"15","author":"Nguyen","year":"2002","journal-title":"J. Cryptol."},{"key":"ref_11","unstructured":"Nguyen, P.Q., and Tibouchi, M. (2012). Fault Analysis in Cryptography, Springer."},{"key":"ref_12","unstructured":"Mulder, E., Hutter, M., Marson, M., and Pearson, P. (2013). Cryptographic Hardware and Embedded Systems-CHES 2013: 15th International Workshop, Santa Barbara, CA, USA, 20\u201323 August 2013, Springer."},{"key":"ref_13","unstructured":"Li, S., Fan, S., and Lu, X. (2021). International Conference on Information Security and Cryptology, Springer."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Albrecht, M.R., and Heninger, N. (2021, January 17\u201321). On Bounded Distance Decoding with Predicate: Breaking the \u201cLattice Barrier\u201d for the Hidden Number Problem. Proceedings of the Advances in Cryptology\u2014EUROCRYPT, Zagreb, Croatia.","DOI":"10.1007\/978-3-030-77870-5_19"},{"key":"ref_15","unstructured":"(1986). On Lov\u00e1sz\u2019 lattice reduction and the nearest lattice point problem. Combinatorica, 6, 1\u201313."},{"key":"ref_16","unstructured":"Gilbert, H. (June, January 30). Lattice Enumeration Using Extreme Pruning. Proceedings of the Advances in Cryptology\u2014EUROCRYPT, French Riviera, France."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1287\/moor.12.3.415","article-title":"Minkowski\u2019s Convex Body Theorem and Integer Programming","volume":"12","author":"Kannan","year":"1987","journal-title":"Math. Oper. Res."},{"key":"ref_18","first-page":"1","article-title":"BKZ 2.0: Better Lattice Security Estimates","volume":"Volume 7073","author":"Chen","year":"2011","journal-title":"International Conference on the Theory and Application of Cryptology and Information Security"},{"key":"ref_19","first-page":"198","article-title":"Terminating BKZ","volume":"2011","author":"Hanrot","year":"2011","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Aono, Y., Wang, Y., Hayashi, T., and Takagi, T. (2016, January 8\u201312). Improved Progressive BKZ Algorithms and Their Precise Cost Estimation by Sharp Simulator. Proceedings of the Advances in Cryptology\u2014EUROCRYPT, Vienna, Austria.","DOI":"10.1007\/978-3-662-49890-3_30"},{"key":"ref_21","unstructured":"Peyrin, T., and Galbraith, S. (2018, January 2\u20136). Measuring, Simulating and Exploiting the Head Concavity Phenomenon in BKZ. Proceedings of the Advances in Cryptology\u2014ASIACRYPT, Brisbane, QLD, Australia."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Alt, H., and Habib, M. (March, January 27). Lattice Reduction by Random Sampling and Birthday Methods. Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science (STACS 2003), Berlin, Germany.","DOI":"10.1007\/3-540-36494-3"},{"key":"ref_23","first-page":"67","article-title":"An accelerated algorithm for solving SVP based on statistical analysis","volume":"23","author":"Fukase","year":"2015","journal-title":"J. Inf. Process."},{"key":"ref_24","unstructured":"Abdalla, M., and Dahab, R. (2018, January 25\u201329). Fast Lattice Basis Reduction Suitable for Massive Parallelization and Its Application to the Shortest Vector Problem. Proceedings of the Public-Key Cryptography\u2014PKC, Rio de Janeiro, Brazil."},{"key":"ref_25","unstructured":"Coron, J.S., and Nielsen, J.B. (May, January 30). Random Sampling Revisited: Lattice Enumeration with Discrete Pruning. Proceedings of the Advances in Cryptology\u2014EUROCRYPT, Paris, France."},{"key":"ref_26","unstructured":"Luan, L., Gu, C., Zheng, Y., and Shi, Y. (2022, December 20). Lattice Enumeration with Discrete Pruning: Improvement, Cost Estimation and Optimal Parameters. Cryptology ePrint Archive, Paper 2022\/1067. Available online: https:\/\/eprint.iacr.org\/2022\/1067."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Kannan, R. (1983, January 25\u201327). Improved Algorithms for Integer Programming and Related Lattice Problems. Proceedings of the Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, Boston, MA, USA.","DOI":"10.1145\/800061.808749"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/BF01581144","article-title":"Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems","volume":"66","author":"Schnorr","year":"1994","journal-title":"Math. Program."},{"key":"ref_29","unstructured":"Micciancio, D., and Ristenpart, T. (2020, January 17\u201321). Faster Enumeration-Based Lattice Reduction: Root Hermite Factor k1\/(2k) Time kk\/8+o(k). Proceedings of the Advances in Cryptology\u2014CRYPTO, Santa Barbara, CA, USA."},{"key":"ref_30","unstructured":"Ducas, L. (May, January 29). Shortest Vector from Lattice Sieving: A Few Dimensions for Free. Proceedings of the Advances in Cryptology\u2014EUROCRYPT, Tel Aviv, Israel."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Albrecht, M.R., Ducas, L., Herold, G., Kirshanova, E., Postlethwaite, E.W., and Stevens, M. (2019, January 19\u201323). The General Sieve Kernel and New Records in Lattice Reduction. Proceedings of the Advances in Cryptology\u2014EUROCRYPT, Darmstadt, Germany.","DOI":"10.1007\/978-3-030-17656-3_25"},{"key":"ref_32","unstructured":"Alkim, E., Ducas, L., P\u00f6ppelmann, T., and Schwabe, P. (2016, January 10\u201312). Post-Quantum Key Exchange: A New Hope. Proceedings of the 25th USENIX Conference on Security Symposium, Austin, TX, USA."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1090\/S0025-5718-1985-0777278-8","article-title":"Improved methods for calculating vectors of short length in a lattice","volume":"44","author":"Fincke","year":"1985","journal-title":"Math. Comput."},{"key":"ref_34","unstructured":"(2022, December 18). TU Darmstadt, Lattice Challenge. Available online: https:\/\/www.latticechallenge.org\/lwe_challenge\/challenge.php\/."},{"key":"ref_35","unstructured":"(2022, December 26). Lattice Algorithms Using Floating-Point Arithmetic(fplll). Available online: https:\/\/github.com\/fplll\/fplll."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"De Micheli, G., Piau, R., and Pierrot, C. (2020, January 20\u201322). A Tale of Three Signatures: Practical Attack of ECDSA with wNAF. Proceedings of the Progress in Cryptology\u2014AFRICACRYPT 2020, Cairo, Egypt.","DOI":"10.1007\/978-3-030-51938-4_18"}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/15\/2\/355\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T18:18:02Z","timestamp":1760120282000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/15\/2\/355"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,28]]},"references-count":36,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2023,2]]}},"alternative-id":["sym15020355"],"URL":"https:\/\/doi.org\/10.3390\/sym15020355","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2023,1,28]]}}}