The Dark Side of the Hidden Number Problem: Lattice Attacks on DSA
Phong Q. Nguyễn · Birkhäuser Basel eBooks · 2001
At Crypto ‘86, Boneh and Venkatesan introduced the so-called hidden number problem: in a prime field ℤ q , recover a number α such that for many known random t, the most significant bits of tα are known. They showed that Babai’s LLL-based polynomial-time nearest plane algorithm for approximating the lattice closest vector problem solves the problem with probability at least $$\frac{1}{2}$$ , provided that the number of bits known (for each tα) is greater than $$\sqrt {\log q} + \log \log q$$ . That result is often cited as the only positive application known in cryptology of the LLL algorithm, because it enables to prove the hardness of the most significant bits of secret keys in Diffie-Hellman and related schemes. The purpose of this short and elementary note is to highlight the fact that the result also has a dark side. Indeed, we remark that the hidden number problem is an idealized version of the problem which HowgraveGraham and Smart recently tried to solve heuristically in their (lattice-based) attacks on DSA and related signature schemes: given a few bits of the random nonces k used in sufficiently many DSA signatures, recover the secret key. This suggests to determine what can be achieved in practice, rather than in theory. Since lattice reduction algorithms are known to behave much more nicely than their proved worst-case bounds, we give the number of bits that enables the Boneh-Venkatesan technique to succeed, provided an oracle for the lattice closest vector problem in the Euclidean norm or the infinity norm. An analogous assumption is used in the well-known lattice-based attacks against low-density subset sums. Interestingly, our experiments support our theoretical bounds and improve the experimental bounds of Howgrave-Graham and Smart.