Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

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 $a \in \mathbb{F}_p$ such that for many known random $t \in \mathbb{F}_p$ approximations to the values of $\left\lfloor{a t}\right\rfloor_p$ are known. Here we study a version of the problem where the ``multipliers'' $t$ 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.


References [Enhancements On Off] (What's this?)

  • 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 (88a:68049), http://dx.doi.org/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 (99b:11104)
  • 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 (89d:11115), http://dx.doi.org/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 (2002j:11153), http://dx.doi.org/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 (2002h:94080), http://dx.doi.org/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 (89a:11131)
  • 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 (92f:11109)
  • 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 (84a:12002), http://dx.doi.org/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 (2002h:94064), http://dx.doi.org/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 (89h:11085), http://dx.doi.org/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 $g^{x^2}$, 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 (15,933e)

Similar Articles

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
PII: S 0025-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