{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:48:09Z","timestamp":1760244489393,"version":"build-2065373602"},"reference-count":21,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2022,12,27]],"date-time":"2022-12-27T00:00:00Z","timestamp":1672099200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Key R &amp;D Program of China","award":["2021YFB3100100","62002385","61972413"],"award-info":[{"award-number":["2021YFB3100100","62002385","61972413"]}]},{"DOI":"10.13039\/501100001809","name":"National Nature Science Foundation of China","doi-asserted-by":"publisher","award":["2021YFB3100100","62002385","61972413"],"award-info":[{"award-number":["2021YFB3100100","62002385","61972413"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>The Hidden Number Problem (HNP) was introduced by Boneh and Venkastesan to analyze the bit-security of the Diffie\u2013Hellman key exchange scheme. It is often used to mount a side-channel attack on (EC)DSA. The hardness of HNP is mainly determined by the number of nonce leakage bits and the size of the modulus. With the development of lattice reduction algorithms and lattice sieving, the range of practically vulnerable parameters are extended further. However, 1-bit leakage is still believed to be challenging for lattice attacks. In this paper, we proposed an asymmetric lattice sieving algorithm that can solve HNP with 1-bit leakage. The algorithm is composed of a BKZ pre-processing and a sieving step. The novel part of our lattice sieving algorithm is that the lattice used in these two steps have different dimensions. In particular, in the BKZ step we use more samples to derive a better lattice basis, while we just use truncated lattice basis for the lattice sieving step. To verify our algorithm, we use it to solve HNP with 1-bit leakage and 116-bit modulus.<\/jats:p>","DOI":"10.3390\/e25010049","type":"journal-article","created":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T05:42:48Z","timestamp":1672206168000},"page":"49","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Solving HNP with One Bit Leakage: An Asymmetric Lattice Sieving Algorithm"],"prefix":"10.3390","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0978-5222","authenticated-orcid":false,"given":"Wenhao","family":"Shi","sequence":"first","affiliation":[{"name":"State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China"},{"name":"Henan Key Laboratory of Network Cryptography Technology, Zhengzhou 450001, China"}]},{"given":"Haodong","family":"Jiang","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China"},{"name":"Henan Key Laboratory of Network Cryptography Technology, Zhengzhou 450001, China"}]},{"given":"Zhi","family":"Ma","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China"},{"name":"Henan Key Laboratory of Network Cryptography Technology, Zhengzhou 450001, China"}]}],"member":"1968","published-online":{"date-parts":[[2022,12,27]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Albrecht, M.R., Bai, S., Fouque, P.A., Kirchner, P., Stehl\u00e9, D., and Wen, W. (2020, August 10). Faster Enumeration-Based Lattice Reduction: Root Hermite Factor k(1\/(2k)) in Time k(k\/8+o(k)). Cryptology ePrint Archive, Paper 2020\/707. Available online: https:\/\/eprint.iacr.org\/2020\/707.","key":"ref_1","DOI":"10.1007\/978-3-030-56880-1_7"},{"doi-asserted-by":"crossref","unstructured":"Micciancio, D., and Walter, M. (2015, January 4\u20136). Fast Lattice Point Enumeration with Minimal Overhead. Proceedings of the 2015 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), San Diego, CA, USA.","key":"ref_2","DOI":"10.1137\/1.9781611973730.21"},{"unstructured":"Gilbert, H. (2010, January 15\u201319). Lattice Enumeration Using Extreme Pruning. Proceedings of the Advances in Cryptology\u2014EUROCRYPT 2010, Santa Barbara, CA, USA.","key":"ref_3"},{"doi-asserted-by":"crossref","unstructured":"Ajtai, M., Kumar, R., and Sivakumar, D. (2001, January 6). A Sieve Algorithm for the Shortest Lattice Vector Problem. Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, Hersonissos, Greece.","key":"ref_4","DOI":"10.1145\/380752.380857"},{"doi-asserted-by":"crossref","unstructured":"Becker, A., Ducas, L., Gama, N., and Laarhoven, T. (2016, January 01). New Directions in Nearest Neighbor Searching with Applications to Lattice Sieving. Cryptology ePrint Archive, Paper 2015\/1128. Available online: https:\/\/eprint.iacr.org\/2015\/1128.","key":"ref_5","DOI":"10.1137\/1.9781611974331.ch2"},{"unstructured":"Becker, A., Gama, N., and Joux, A. (2015, August 24). Speeding-up Lattice Sieving without Increasing the Memory, Using Sub-Quadratic Nearest Neighbor Search. Cryptology ePrint Archive, Paper 2015\/522. Available online: https:\/\/eprint.iacr.org\/2015\/522.","key":"ref_6"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1515\/JMC.2008.009","article-title":"Sieve algorithms for the shortest vector problem are practical","volume":"2","author":"Nguyen","year":"2008","journal-title":"J. Math. Cryptol."},{"doi-asserted-by":"crossref","unstructured":"Gennaro, R., and Robshaw, M. (2015, January 16\u201320). Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing. Proceedings of the Advances in Cryptology\u2014CRYPTO 2015, Santa Barbara, CA, USA.","key":"ref_8","DOI":"10.1007\/978-3-662-48000-7"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1364","DOI":"10.1137\/100811970","article-title":"A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations","volume":"42","author":"Micciancio","year":"2013","journal-title":"SIAM J. Comput."},{"unstructured":"Aggarwal, D., Dadush, D., Regev, O., and Stephens-Davidowitz, N. (2015, January 14\u201317). Solving the shortest vector problem in 2n time via discrete Gaussian sampling. Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, Portland, OR, USA.","key":"ref_10"},{"unstructured":"Koblitz, N. (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.","key":"ref_11"},{"doi-asserted-by":"crossref","unstructured":"Bertoni, G., and Coron, J.S. (2013, January 20\u201323). Using Bleichenbacher\u201ds Solution to the Hidden Number Problem to Attack Nonce Leaks in 384-Bit ECDSA. Proceedings of the Cryptographic Hardware and Embedded Systems\u2014CHES 2013, Santa Barbara, CA, USA.","key":"ref_12","DOI":"10.1007\/978-3-642-40349-1"},{"unstructured":"Mehlhorn, K. (1985, January 3\u20135). On Lov\u00e1sz\u2019 lattice reduction and the nearest lattice point problem. Proceedings of the STACS\u201985, Saarbr\u00fccken, Germany.","key":"ref_13"},{"unstructured":"Sarkar, P., and Iwata, T. (2014, January 7\u201311). GLV\/GLS Decomposition, Power Analysis, and Attacks on ECDSA Signatures with Single-Bit Nonce Bias. Proceedings of the Advances in Cryptology\u2014ASIACRYPT 2014, Kaoshiung, Taiwan.","key":"ref_14"},{"unstructured":"Lee, D.H., and Wang, X. (2011, January 4\u20138). BKZ 2.0: Better Lattice Security Estimates. Proceedings of the Advances in Cryptology\u2014ASIACRYPT 2011, Seoul, Republic of Korea.","key":"ref_15"},{"unstructured":"Albrecht, M.R., and Heninger, N. (2021, June 16). On Bounded Distance Decoding with Predicate: Breaking the \u201cLattice Barrier\u201d for the Hidden Number Problem. Cryptology ePrint Archive, Paper 2020\/1540. Available online: https:\/\/eprint.iacr.org\/2020\/1540.","key":"ref_16"},{"unstructured":"Albrecht, M.R., Ducas, L., Herold, G., Kirshanova, E., Postlethwaite, E.W., and Stevens, M. (2019, April 24). The General Sieve Kernel and New Records in Lattice Reduction. Cryptology ePrint Archive, Paper 2019\/089. Available online: https:\/\/eprint.iacr.org\/2019\/089.","key":"ref_17"},{"doi-asserted-by":"crossref","unstructured":"Sun, C., Espitau, T., Tibouchi, M., and Abe, M. (2021, October 14). Guessing Bits: Improved Lattice Attacks on (EC)DSA with Nonce Leakage. Cryptology ePrint Archive, Paper 2021\/455. Available online: https:\/\/eprint.iacr.org\/2021\/455.","key":"ref_18","DOI":"10.46586\/tches.v2022.i1.391-413"},{"unstructured":"Budach, L. (1991, January 9\u201313). Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Proceedings of the Fundamentals of Computation Theory, Gosen, Germany.","key":"ref_19"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/0304-3975(87)90064-8","article-title":"A hierarchy of polynomial time lattice basis reduction algorithms","volume":"53","author":"Schnorr","year":"1987","journal-title":"Theor. Comput. Sci."},{"key":"ref_21","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":"2000","journal-title":"J. Cryptol."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/25\/1\/49\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:53:02Z","timestamp":1760147582000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/25\/1\/49"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,27]]},"references-count":21,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,1]]}},"alternative-id":["e25010049"],"URL":"https:\/\/doi.org\/10.3390\/e25010049","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2022,12,27]]}}}