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)latticesieving algorithmmodulo 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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.