Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



A hidden number problem in small subgroups

Authors: Igor Shparlinski and Arne Winterhof
Journal: Math. Comp. 74 (2005), 2073-2080
MSC (2000): Primary 11T23, 11T71, 11Y16, 94A60
Published electronically: April 5, 2005
MathSciNet review: 2164114
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Boneh and Venkatesan have proposed a polynomial time algorithm for recovering a hidden element $\alpha \in \mathbb{F}_p$, where $p$ is prime, from rather short strings of the most significant bits of the residue of $\alpha t$ modulo $p$ for several randomly chosen $t\in \mathbb{F}_p$. González Vasco and the first author have recently extended this result to subgroups of $\mathbb{F}_p^*$ of order at least $p^{1/3+\varepsilon}$ for all $p$ and to subgroups of order at least $p^\varepsilon$ for almost all $p$. Here we introduce a new modification in the scheme which amplifies the uniformity of distribution of the multipliers $t$ and thus extend this result to subgroups of order at least $(\log p)/(\log \log p)^{1-\varepsilon}$ for all primes $p$. As in the above works, we give applications of our result to the bit security of the Diffie-Hellman secret key starting with subgroups of very small size, thus including all cryptographically interesting subgroups.

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

  • 1. 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.
  • 2. D. Boneh and R. Venkatesan, ``Rounding in lattices and its cryptographic applications'', Proc. 8th Annual ACM-SIAM Symp. on Discr. Algorithms, SIAM, 1997, 675-681. MR 1447716
  • 3. J. Bourgain and S. V. Konyagin, ``Estimates for the number of sums and products and for exponential sums over subgroups in fields of prime order'', Comptes Rendus Mathematique, 337 (2003), 75-80. MR 1998834 (2004g:11067)
  • 4. T. Cochrane, C. Pinner and J. Rosenhouse, ``Bounds on exponential sums and the polynomial Waring's problem$\mod p$'', Proc. Lond. Math. Soc., 67 (2003), 319-336. MR 1956138 (2003m:11129)
  • 5. B. Codenotti, I. E. Shparlinski and A. Winterhof, ``Non-approximability of the permanent of structured matrices over finite fields'', Comp. Compl., 11 (2002), 158-170. MR 2022046 (2004m:15010)
  • 6. R. Crandall and C. Pomerance, Prime numbers: A Computational perspective, Springer-Verlag, Berlin, 2001. MR 1821158 (2002a:11007)
  • 7. S. D. Galbraith, H. J. Hopkins and I. E. Shparlinski, ``Secure bilinear Diffie-Hellman bits'', Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 3108 (2004), 370-378. Archive,
  • 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. MR 1944731 (2004a:94043)
  • 9. D. R. Heath-Brown and S. V. Konyagin, ``New bounds for Gauss sums derived from $k$th powers, and for Heilbronn's exponential sum'', Quart. J. Math., 51 (2000), 221-235. MR 1765792 (2001h:11106)
  • 10. S. V. Konyagin, ``On estimates of Gaussian sums and the Waring problem modulo a prime'', Trudy Matem. Inst. Acad. Nauk USSR, Moscow, 198 (1992), 111-124 (in Russian); translation in Proc. Steklov Inst. Math., 1 (1994), 105-117. MR 1289921 (96e:11122)
  • 11. S. V. Konyagin, ``Bounds of exponential sums over subgroups and Gauss sums'', Proc 4th Intern. Conf. Modern Problems of Number Theory and Its Applications, Moscow Lomonosov State Univ., Moscow, 2002, 86-114 (in Russian).
  • 12. S. V. Konyagin and I. Shparlinski, Character sums with exponential functions and their applications, Cambridge Univ. Press, Cambridge, (1999). MR 1725241 (2000h:11089)
  • 13. W.-C. W. Li, M. Näslund and I. E. Shparlinski, ``The hidden number problem with the trace and bit security of XTR and LUC'', Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 2442 (2002), 433-448. MR 2055076 (2005a:94062)
  • 14. R. Lidl and H. Niederreiter, Finite fields, Cambridge University Press, Cambridge, 1997. MR 1429394 (97i:11115)
  • 15. A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of applied cryptography, CRC Press, Boca Raton, FL, 1996. MR 1412797 (99g:94015)
  • 16. P. Q. Nguyen and I. E. Shparlinski, ``The insecurity of the digital signature algorithm with partially known nonces'', J. Cryptology, 15 (2002), 151-176. MR 2007211 (2004h:94047)
  • 17. K. Prachar, Primzahlverteilung, Springer-Verlag, Berlin, 1957. MR 0087685 (19,393b)
  • 18. O. Schirokauer, ``Discrete logarithms and local units'', Philos. Trans. Roy. Soc. London, Ser. A, 345 (1993), 409-423. MR 1253502 (95c:11156)
  • 19. O. Schirokauer, D. Weber and T. Denny, ``Discrete logarithms: The effectiveness of the index calculus method'', Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 1122 (1996), 337-362. MR 1446523 (98i:11109)
  • 20. I. E. Shparlinski, ``On exponential sums with sparse polynomials'', J. Number Theory, 60 (1996), 233-244. MR 1412961 (97g:11089)
  • 21. I. E. Shparlinski, ``On the generalised hidden number problem and bit security of XTR'', Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 2227 (2001), 268-277. MR 1913473 (2003d:94088)
  • 22. I. E. Shparlinski, ``Playing `Hide-and-Seek' in finite fields: Hidden number problem and its applications'', Proc. 7th Spanish Meeting on Cryptology and Information Security, Vol.1, Univ. of Oviedo, 2002, 49-72.
  • 23. I. E. Shparlinski, ``Exponential sums and lattice reduction: Applications to cryptography'', Finite Fields with Applications to Coding Theory, Cryptography and Related Areas, Springer-Verlag, Berlin, 2002, 286-298. MR 1995344 (2004h:94048)
  • 24. I. E. Shparlinski, Cryptographic applications of analytic number theory, Birkhäuser, 2003. MR 1954519 (2004h:94049)
  • 25. I. E. Shparlinski and A. Winterhof, ``A nonuniform algorithm for the hidden number problem in subgroups'', Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 2947 (2004), 416-424. MR 2095823
  • 26. I. E. Shparlinski and A. Winterhof, ``Noisy interpolation of sparse polynomials in finite fields'', Appl. Algebra in Engin., Commun. and Computing, (to appear).
  • 27. D. R. Stinson, Cryptography: Theory and practice, CRC Press, Boca Raton, FL, 2002. MR 1911330 (2003c:94035)
  • 28. A. Winterhof, ``On Waring's problem in finite fields'', Acta Arith., 87 (1998), 171-177. MR 1811878 (2001m:11164)

Similar Articles

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

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

Additional Information

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

Arne Winterhof
Affiliation: RICAM, Austrian Academy of Sciences, Altenbergerstrasse 69, 4040 Linz, Austria

Keywords: Hidden number problem, Diffie--Hellman key exchange, lattice reduction, exponential sums, Waring problem in finite fields
Received by editor(s): March 3, 2003
Published electronically: April 5, 2005
Article copyright: © Copyright 2005 American Mathematical Society

American Mathematical Society