Solving HNP with One Bit Leakage: An Asymmetric Lattice Sieving Algorithm.

Area of Science:

• Cryptography and Information Security
• Computational Number Theory
• Lattice-based Cryptanalysis

Background:

• The Hidden Number Problem (HNP) is crucial for analyzing the security of cryptographic schemes, notably the Diffie-Hellman key exchange and (EC)DSA.
• Lattice reduction algorithms have expanded the scope of cryptanalytic attacks on HNP, but 1-bit nonce leakage remains a significant challenge.
• Previous lattice attacks struggled with minimal nonce leakage due to the inherent difficulty of solving HNP under such constraints.

Purpose of the Study:

• To propose a novel asymmetric lattice sieving algorithm capable of solving the Hidden Number Problem (HNP) with only 1-bit nonce leakage.
• To extend the practical vulnerability of cryptographic parameters against lattice-based side-channel attacks.
• To demonstrate the effectiveness of the proposed algorithm on a concrete instance of HNP.

Main Methods:

• Development of an asymmetric lattice sieving algorithm combining Block Korkin-Ziv (BKZ) pre-processing and a lattice sieving step.
• Utilizing lattices of different dimensions in the BKZ and sieving phases: higher dimensions for basis derivation and truncated dimensions for sieving.
• Application of the algorithm to solve HNP with 1-bit nonce leakage and a 116-bit modulus.

Main Results:

• Successfully solved the Hidden Number Problem (HNP) with 1-bit nonce leakage using the proposed asymmetric lattice sieving algorithm.
• Demonstrated that the novel approach, employing different lattice dimensions for BKZ and sieving, effectively tackles the 1-bit leakage challenge.
• Verified the algorithm's capability on a 116-bit modulus, confirming its practical applicability.

Conclusions:

• The proposed asymmetric lattice sieving algorithm significantly advances the cryptanalysis of HNP, particularly in scenarios with minimal nonce leakage.
• This work challenges the assumption that 1-bit leakage is intractable for lattice attacks, broadening the understanding of cryptographic vulnerabilities.
• The findings have implications for the security analysis of widely used cryptographic protocols like Diffie-Hellman and (EC)DSA.