Hidden number problem with hidden multipliers, timed-release crypto, and noisy exponentiation

Authors:
Nick A. Howgrave-Graham, Phong Q. Nguyen and Igor E. Shparlinski

Journal:
Math. Comp. **72** (2003), 1473-1485

MSC (2000):
Primary 11Y16, 94A60; Secondary 11T71, 11T23

Published electronically:
February 3, 2003

MathSciNet review:
1972747

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We consider a generalisation of the *hidden number problem* recently introduced by Boneh and Venkatesan. The initial problem can be stated as follows: recover a number such that for many known random approximations to the values of are known. Here we study a version of the problem where the ``multipliers'' are not known but rather certain approximations to them are given. We present a probabilistic polynomial time solution when the error is small enough, and we show that the problem cannot be solved if the error is sufficiently large. We apply the result to the bit security of ``timed-release crypto'' introduced by Rivest, Shamir and Wagner, to noisy exponentiation black-boxes and to the bit security of the ``inverse'' exponentiation. We also show that it implies a certain bit security result for Weil pairing on elliptic curves.

**1.**M. Ajtai, R. Kumar and D. Sivakumar,*A sieve algorithm for the shortest lattice vector problem,*Proc. 33rd ACM Symp. on Theory of Comput., Crete, Greece, July 6-8, 2001, 601-610.**2.**L. Babai,*On Lovász’ lattice reduction and the nearest lattice point problem*, Combinatorica**6**(1986), no. 1, 1–13. MR**856638**, 10.1007/BF02579403**3.**R. C. Baker and G. Harman,*Shifted primes without large prime factors*, Acta Arith.**83**(1998), no. 4, 331–361. MR**1610553****4.**D. Boneh and R. Venkatesan,*Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes,*Lect. Notes in Comp. Sci., Springer-Verlag, Berlin,**1109**(1996), 129-142.**5.**D. Boneh and R. Venkatesan,*Rounding in lattices and its cryptographic applications,*Proc. 8th Annual ACM-SIAM Symp. on Discr. Algorithms, ACM, NY, 1997, 675-681.**6.**E. El Mahassni, P. Q. Nguyen and I. E. Shparlinski,*The insecurity of some DSA-like signature schemes with partially known nonces,*Lect. Notes in Comp. Sci., Springer-Verlag, Berlin,**2146**(2001), 97-109.**7.**Alan M. Frieze, Johan Håstad, Ravi Kannan, Jeffrey C. Lagarias, and Adi Shamir,*Reconstructing truncated integer variables satisfying linear congruences*, SIAM J. Comput.**17**(1988), no. 2, 262–280. Special issue on cryptography. MR**935340**, 10.1137/0217016**8.**M. I. González Vasco and I. E. Shparlinski,*On the security of Diffie-Hellman bits,*Proc. Workshop on Cryptography and Computational Number Theory, Singapore 1999, Birkhäuser, 2001, 257-268.**9.**Maria Isabel González Vasco and Igor E. Shparlinski,*Security of the most significant bits of the Shamir message passing scheme*, Math. Comp.**71**(2002), no. 237, 333–342. MR**1863004**, 10.1090/S0025-5718-01-01358-8**10.**N. A. Howgrave-Graham and N. P. Smart,*Lattice attacks on digital signature schemes*, Des. Codes Cryptogr.**23**(2001), no. 3, 283–290. MR**1840910**, 10.1023/A:1011214926272**11.**R. Kannan,*Improved algorithms for integer programming and related lattice problems,*Proc. 15th ACM Symp. on Theory of Comput., Boston, MA, May 25-27, 1983, 193-206.**12.**Ravi Kannan,*Algorithmic geometry of numbers*, Annual review of computer science, Vol. 2, Annual Reviews, Palo Alto, CA, 1987, pp. 231–267. MR**921497****13.**M. Kiwi, F. Magniez and M. Santha,*Exact and approximate testing/coorecting of algebraic functions: A survey,*Electronic Colloq. on Comp. Compl., Univ. of Trier,**TR2001-014**(2001), 1-49.**14.**S. V. Konyagin and I. E. Shparlinski,*Character sums with exponential functions and their applications*, Cambridge Univ. Press, Cambridge, 1999.**15.**J. C. Lagarias,*Pseudorandom number generators in cryptography and number theory*, Cryptology and computational number theory (Boulder, CO, 1989) Proc. Sympos. Appl. Math., vol. 42, Amer. Math. Soc., Providence, RI, 1990, pp. 115–143. MR**1095554**, 10.1090/psapm/042/1095554**16.**A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász,*Factoring polynomials with rational coefficients*, Math. Ann.**261**(1982), no. 4, 515–534. MR**682664**, 10.1007/BF01457454**17.**P. MacKenzie,*On the security of the SPEKE Password-authenticated key exchange protocol,**Cryptology ePrint Archive, Report 2001/57*, 2001, 1-19.**18.**D. Micciancio,*On the hardness of the shortest vector problem,*PhD Thesis, MIT, 1998.**19.**P. Q. Nguyen,*The dark side of the Hidden Number Problem: Lattice attacks on DSA,*Proc. Workshop on Cryptography and Computational Number Theory, Singapore 1999, Birkhäuser, 2001, 321-330.**20.**P. Q. Nguyen and I. E. Shparlinski,*The insecurity of the Digital Signature Algorithm with partially known nonces,*J. Cryptology,**15**(2002), 152-176.**21.**P. Q. Nguyen and I. E. Shparlinski,*The insecurity of the elliptic curve Digital Signature Algorithm with partially known nonces,*Designs, Codes and Cryptography, (to appear).**22.**Phong Q. Nguyen and Jacques Stern,*Lattice reduction in cryptology: an update*, Algorithmic number theory (Leiden, 2000) Lecture Notes in Comput. Sci., vol. 1838, Springer, Berlin, 2000, pp. 85–112. MR**1850600**, 10.1007/10722028_4**23.**P. Q. Nguyen and J. Stern,*The two faces of lattices in cryptology,*Cryptology and Lattices (Providence, RI, 2001), Lecture Notes in Computer Sci., vol. 2146, Springer-Verlag, Berlin, 2001, pp. 146-180.**24.**R. L. Rivest, A. Shamir and D. A. Wagner,*Time-lock puzzles and timed-release crypto,*Preprint, 1996, 1-9.**25.**A.-R. Sadeghi and M. Steiner,*Assumptions related to discrete logarithms: Why subtleties make a real difference,*Lect. Notes in Comp. Sci., Springer-Verlag, Berlin,**2045**(2001), 243-260.**26.**C.-P. Schnorr,*A hierarchy of polynomial time lattice basis reduction algorithms*, Theoret. Comput. Sci.**53**(1987), no. 2-3, 201–224. MR**918090**, 10.1016/0304-3975(87)90064-8**27.**I. E. Shparlinski,*Sparse polynomial approximation in finite fields,*Proc. 33rd ACM Symp. on Theory of Comput., Crete, Greece, July 6-8, 2001, 209-215.**28.**I. E. Shparlinski,*Security of most significant bits of**,*Inform. Proc. Letters,**83**(2002), 109-113. CMP**2002:12****29.**J. H. Silverman.*The Arithmetic of Elliptic Curves*. Springer-Verlag, Berlin, 1995. MR**95:11054****30.**I. M. Vinogradov,*Elements of number theory*, Dover Publications, Inc., New York, 1954. Translated by S. Kravetz. MR**0062138**

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
11Y16,
94A60,
11T71,
11T23

Retrieve articles in all journals with MSC (2000): 11Y16, 94A60, 11T71, 11T23

Additional Information

**Nick A. Howgrave-Graham**

Affiliation:
IBM T. J. Watson Research Center, Hawthorne, NY 10532, USA

Email:
nahg@watson.ibm.com

**Phong Q. Nguyen**

Affiliation:
Département d’Informatique, École Normale Supérieure, 45, rue d’Ulm, 75230 Paris Cedex 05, France

Email:
pnguyen@ens.fr

**Igor E. Shparlinski**

Affiliation:
Department of Computing, Macquarie University, New South Wales 2109, Australia

Email:
igor@ics.mq.edu.au

DOI:
http://dx.doi.org/10.1090/S0025-5718-03-01495-9

Keywords:
Hidden number problem,
lattice reduction,
timed-release crypto,
noisy exponentiation,
exponential sums

Received by editor(s):
July 31, 2001

Published electronically:
February 3, 2003

Article copyright:
© Copyright 2003
American Mathematical Society