A New Sieving Approach for Solving the HNP with One Bit of Nonce by Using Built-in Modulo Arithmetic

Yao Sun; Shuai Chang

Paper 2023/1137

A New Sieving Approach for Solving the HNP with One Bit of Nonce by Using Built-in Modulo Arithmetic

Yao Sun, State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China.

Shuai Chang, State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China.

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.

Note: This manuscript was once submitted in February, 2023, and it will be improved sooner.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: Hidden Number Problem (HNP)lattice sieving algorithm modulo arithmetic
Contact author(s): sunyao @ iie ac cn
changshuai751x @ iie ac cn
History: 2023-07-24: approved; 2023-07-22: received; See all versions
Short URL: https://ia.cr/2023/1137
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1137,
      author = {Yao Sun and Shuai Chang},
      title = {A New Sieving Approach for Solving the {HNP} with One Bit of Nonce by Using Built-in Modulo Arithmetic},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1137},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1137}
}