Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
L. Babai. On Lovasz lattice reduction and the nearest lattice point problem. Cornbinatorica, 6:1–13, 1986.
D. Bleichenbacher, 1999. Private communication.
M. Bellare, S. Goldwasser, and D. Micciancio. “Pseudo-random” number generation within cryptographic algorithms: The DSS case. In Proc. of Crypto ‘87, volume 1294 of LNCS. IACR, Springer-Verlag, 1997.
D. Boneh and R. Venkatesan. Hardness of computing the most significant bits of secret keys in diffie-hellman and related schemes. In Proc. of Crypto ‘86. IACR, Springer-Verlag, 1996.
M.J. Coster, A. Joux, B.A. LaMacchia, A.M. Odlyzko, C.-P. Schnorr, and J. Stern. Improved low-density subset sum algorithms. Comput. Complexity, 2:111–128, 1992.
N.A. Howgrave-Graham and N.P. Smart. Lattice attacks on digital signature schemes. Technical report, HP Labs, 1999. Report HPL-1999–90. To appear in Designs, Codes and Cryptography.
A.K. Lenstra, H.W. Lenstra Jr., and L. Lovész. Factoring polynomials with rational coefficients. Mathematische Ann., 261:513–534, 1982.
A. Menezes, P. Van Oorschot, and S. Vanstone. Handbook of Applied Cryptography. CRC Press, 1997.
P. Nguyen. Cryptanalysis of the Goldreich-Goldwasser-Halevi cryptosystem from Crypto ‘87. In Proc. of Crypto ‘89, volume 1666 of LNCS, pages 288–304. IACR, Springer-Verlag, 1999.
P.Q. Nguyen and I.E. Shparlinski. The insecurity of the Digital Signature Algorithm with partially known nonces. Manuscript in preparation, 2000.
P.Q. Nguyen and J. Stern. Lattice reduction in cryptology: An update. In Algorithmic Number Theory - Proc. of ANTS-IV, LNCS. Springer-Verlag, 2000.
H. Ritter. Breaking knapsack cryptosystems by max-norm enumeration. In Proc. of Pragocrypt ‘86, pages 480–492. CTU Publishing House, 1996.
C.P. Schnorr. A hierarchy of polynomial lattice basis reduction algorithms. Theoretical Computer Science, 53:201–224, 1987.
C.P. Schnorr and M. Euchner. Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Programming, 66:181–199, 1994.
V. Shoup. Number Theory C++ Library (NTL) version 3.7. Available at http://www.shoup.net/nt1/.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer Basel AG
About this paper
Cite this paper
Nguyen, P.Q. (2001). The Dark Side of the Hidden Number Problem: Lattice Attacks on DSA. In: Lam, KY., Shparlinski, I., Wang, H., Xing, C. (eds) Cryptography and Computational Number Theory. Progress in Computer Science and Applied Logic, vol 20. Birkhäuser, Basel. https://doi.org/10.1007/978-3-0348-8295-8_23
Download citation
DOI: https://doi.org/10.1007/978-3-0348-8295-8_23
Publisher Name: Birkhäuser, Basel
Print ISBN: 978-3-0348-9507-1
Online ISBN: 978-3-0348-8295-8
eBook Packages: Springer Book Archive