Welcome to the resource topic for 2023/1137
Title:
A New Sieving Approach for Solving the HNP with One Bit of Nonce by Using Built-in Modulo Arithmetic
Authors: Yao Sun, Shuai Chang
Abstract:The Hidden Number Problem (HNP) has been extensively used in the side-channel attacks against (EC)DSA and Diffie-Hellman. The lattice approach is a primary method of solving the HNP. In EUROCRYPT 2021, Albrecht and Heninger constructed a new lattice to solve the HNP, which converts the HNP to the SVP. After that, their approach became the state-of-the-art lattice method of solving the HNP. But Albrecht and Heninger’s approach has a high failure rate for solving the HNP with one bit of nonce (1-bit HNP) because there are enormous vectors related to the modulus q shorter than the target vector in Albrecht and Heninger’s Lattice.
To decrease the number of vectors that are shorter than the target vector and avoid the duplicated reduction, we introduce the modulo-q lattice, a residue class ring of the general lattice modulo q, where q is the modulus of the HNP. We present a new sieving algorithm to search for the shortest vectors in the modulo-q lattice. Our algorithm uses built-in modulo q arithmetic and many optimization techniques. As a result, we can solve a general 1-bit HNP (q=2^{120}) within 5 days and solve a general 1-bit HNP (q=2^{128}) within 17 days.
ePrint: https://eprint.iacr.org/2023/1137
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .