Hidden number problem with hidden multipliers, timedrelease crypto, and noisy exponentiation
Authors:
Nick A. HowgraveGraham, Phong Q. Nguyen and Igor E. Shparlinski
Journal:
Math. Comp. 72 (2003), 14731485
MSC (2000):
Primary 11Y16, 94A60; Secondary 11T71, 11T23
Published electronically:
February 3, 2003
MathSciNet review:
1972747
Fulltext 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 ``timedrelease crypto'' introduced by Rivest, Shamir and Wagner, to noisy exponentiation blackboxes 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 68, 2001, 601610.
 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 DiffieHellman and related schemes, Lect. Notes in Comp. Sci., SpringerVerlag, Berlin, 1109 (1996), 129142.
 5.
D. Boneh and R. Venkatesan, Rounding in lattices and its cryptographic applications, Proc. 8th Annual ACMSIAM Symp. on Discr. Algorithms, ACM, NY, 1997, 675681.
 6.
E. El Mahassni, P. Q. Nguyen and I. E. Shparlinski, The insecurity of some DSAlike signature schemes with partially known nonces, Lect. Notes in Comp. Sci., SpringerVerlag, Berlin, 2146 (2001), 97109.
 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 DiffieHellman bits, Proc. Workshop on Cryptography and Computational Number Theory, Singapore 1999, Birkhäuser, 2001, 257268.
 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/S0025571801013588
 10.
N.
A. HowgraveGraham 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 2527, 1983, 193206.
 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, TR2001014 (2001), 149.
 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), http://dx.doi.org/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 (84a:12002), http://dx.doi.org/10.1007/BF01457454
 17.
P. MacKenzie, On the security of the SPEKE Passwordauthenticated key exchange protocol, Cryptology ePrint Archive, Report 2001/57, 2001, 119.
 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, 321330.
 20.
P. Q. Nguyen and I. E. Shparlinski, The insecurity of the Digital Signature Algorithm with partially known nonces, J. Cryptology, 15 (2002), 152176.
 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, SpringerVerlag, Berlin, 2001, pp. 146180.
 24.
R. L. Rivest, A. Shamir and D. A. Wagner, Timelock puzzles and timedrelease crypto, Preprint, 1996, 19.
 25.
A.R. Sadeghi and M. Steiner, Assumptions related to discrete logarithms: Why subtleties make a real difference, Lect. Notes in Comp. Sci., SpringerVerlag, Berlin, 2045 (2001), 243260.
 26.
C.P.
Schnorr, A hierarchy of polynomial time lattice basis reduction
algorithms, Theoret. Comput. Sci. 53 (1987),
no. 23, 201–224. MR 918090
(89h:11085), http://dx.doi.org/10.1016/03043975(87)900648
 27.
I. E. Shparlinski, Sparse polynomial approximation in finite fields, Proc. 33rd ACM Symp. on Theory of Comput., Crete, Greece, July 68, 2001, 209215.
 28.
I. E. Shparlinski, Security of most significant bits of , Inform. Proc. Letters, 83 (2002), 109113. CMP 2002:12
 29.
J. H. Silverman. The Arithmetic of Elliptic Curves. SpringerVerlag, 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)
 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 68, 2001, 601610.
 2.
 L. Babai, On Lovász lattice reduction and the nearest lattice point problem, Combinatorica, 6 (1986), 113. MR 88a:68049
 3.
 R. C. Baker and G. Harman, Shifted primes without large prime factors, Acta Arithm., 83 (1998), 331361. MR 99b:11104
 4.
 D. Boneh and R. Venkatesan, Hardness of computing the most significant bits of secret keys in DiffieHellman and related schemes, Lect. Notes in Comp. Sci., SpringerVerlag, Berlin, 1109 (1996), 129142.
 5.
 D. Boneh and R. Venkatesan, Rounding in lattices and its cryptographic applications, Proc. 8th Annual ACMSIAM Symp. on Discr. Algorithms, ACM, NY, 1997, 675681.
 6.
 E. El Mahassni, P. Q. Nguyen and I. E. Shparlinski, The insecurity of some DSAlike signature schemes with partially known nonces, Lect. Notes in Comp. Sci., SpringerVerlag, Berlin, 2146 (2001), 97109.
 7.
 A. M. Frieze, J. Håstad, R. Kannan, J. C. Lagarias, and A. Shamir, Reconstructing truncated integer variables satisfying linear congruence, SIAM J. Comp., 17 (1988), 262280. MR 89d:11115
 8.
 M. I. González Vasco and I. E. Shparlinski, On the security of DiffieHellman bits, Proc. Workshop on Cryptography and Computational Number Theory, Singapore 1999, Birkhäuser, 2001, 257268.
 9.
 M. I. González Vasco and I. E. Shparlinski, Security of the most significant bits of the Shamir message passing scheme, Math. Comp., 71 (2002), 333342. MR 2002j:11153
 10.
 N. A. HowgraveGraham and N. P. Smart, Lattice attacks on digital signature schemes, Designs, Codes and Cryptography, 23 (2001), 283290. MR 2002h:94080
 11.
 R. Kannan, Improved algorithms for integer programming and related lattice problems, Proc. 15th ACM Symp. on Theory of Comput., Boston, MA, May 2527, 1983, 193206.
 12.
 R. Kannan, Algorithmic geometry of numbers, Annual Review of Comp. Sci., 2 (1987), 231267. MR 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, TR2001014 (2001), 149.
 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, Proc. Symp. in Appl. Math., Amer. Math. Soc., Providence, RI, 42 (1990), 115143. MR 92f:11109
 16.
 A. K. Lenstra, H. W. Lenstra and L. Lovász, Factoring polynomials with rational coefficients, Mathematische Annalen, 261 (1982), 515534. MR 84a:12002
 17.
 P. MacKenzie, On the security of the SPEKE Passwordauthenticated key exchange protocol, Cryptology ePrint Archive, Report 2001/57, 2001, 119.
 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, 321330.
 20.
 P. Q. Nguyen and I. E. Shparlinski, The insecurity of the Digital Signature Algorithm with partially known nonces, J. Cryptology, 15 (2002), 152176.
 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.
 P. Q. Nguyen and J. Stern, Lattice reduction in cryptology: An update, Lect. Notes in Comp. Sci., SpringerVerlag, Berlin, 1838 (2000), 85112. MR 2002h:94064
 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, SpringerVerlag, Berlin, 2001, pp. 146180.
 24.
 R. L. Rivest, A. Shamir and D. A. Wagner, Timelock puzzles and timedrelease crypto, Preprint, 1996, 19.
 25.
 A.R. Sadeghi and M. Steiner, Assumptions related to discrete logarithms: Why subtleties make a real difference, Lect. Notes in Comp. Sci., SpringerVerlag, Berlin, 2045 (2001), 243260.
 26.
 C. P. Schnorr, A hierarchy of polynomial time basis reduction algorithms, Theor. Comp. Sci., 53 (1987), 201224. MR 89h:11085
 27.
 I. E. Shparlinski, Sparse polynomial approximation in finite fields, Proc. 33rd ACM Symp. on Theory of Comput., Crete, Greece, July 68, 2001, 209215.
 28.
 I. E. Shparlinski, Security of most significant bits of , Inform. Proc. Letters, 83 (2002), 109113. CMP 2002:12
 29.
 J. H. Silverman. The Arithmetic of Elliptic Curves. SpringerVerlag, Berlin, 1995. MR 95:11054
 30.
 I. M. Vinogradov, Elements of number theory, Dover Publ., New York, 1954. MR 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. HowgraveGraham
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/S0025571803014959
PII:
S 00255718(03)014959
Keywords:
Hidden number problem,
lattice reduction,
timedrelease crypto,
noisy exponentiation,
exponential sums
Received by editor(s):
July 31, 2001
Published electronically:
February 3, 2003
Article copyright:
© Copyright 2003
American Mathematical Society
