## A hidden number problem in small subgroups

HTML articles powered by AMS MathViewer

- by Igor Shparlinski and Arne Winterhof PDF
- Math. Comp.
**74**(2005), 2073-2080 Request permission

## 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

- 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. - Dan Boneh and Ramarathnam Venkatesan,
*Rounding in lattices and its cryptographic applications*, Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans, LA, 1997) ACM, New York, 1997, pp. 675–681. MR**1447716** - Jean Bourgain and S. V. Konyagin,
*Estimates for the number of sums and products and for exponential sums over subgroups in fields of prime order*, C. R. Math. Acad. Sci. Paris**337**(2003), no. 2, 75–80 (English, with English and French summaries). MR**1998834**, DOI 10.1016/S1631-073X(03)00281-4 - Todd Cochrane, Christopher Pinner, and Jason Rosenhouse,
*Bounds on exponential sums and the polynomial Waring problem mod $p$*, J. London Math. Soc. (2)**67**(2003), no. 2, 319–336. MR**1956138**, DOI 10.1112/S0024610702004040 - Bruno Codenotti, Igor E. Shparlinski, and Arne Winterhof,
*On the hardness of approximating the permanent of structured matrices*, Comput. Complexity**11**(2002), no. 3-4, 158–170. MR**2022046**, DOI 10.1007/s00037-002-0174-3 - Richard Crandall and Carl Pomerance,
*Prime numbers*, Springer-Verlag, New York, 2001. A computational perspective. MR**1821158**, DOI 10.1007/978-1-4684-9316-0 - 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, - Maria Isabel González Vasco and Igor E. Shparlinski,
*On the security of Diffie-Hellman bits*, Cryptography and computational number theory (Singapore, 1999) Progr. Comput. Sci. Appl. Logic, vol. 20, Birkhäuser, Basel, 2001, pp. 257–268. MR**1944731** - D. R. Heath-Brown and S. Konyagin,
*New bounds for Gauss sums derived from $k\textrm {th}$ powers, and for Heilbronn’s exponential sum*, Q. J. Math.**51**(2000), no. 2, 221–235. MR**1765792**, DOI 10.1093/qjmath/51.2.221 - S. V. Konyagin,
*Estimates for Gaussian sums and Waring’s problem modulo a prime*, Trudy Mat. Inst. Steklov.**198**(1992), 111–124 (Russian); English transl., Proc. Steklov Inst. Math.**1(198)**(1994), 105–117. MR**1289921** - 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). - Sergei V. Konyagin and Igor E. Shparlinski,
*Character sums with exponential functions and their applications*, Cambridge Tracts in Mathematics, vol. 136, Cambridge University Press, Cambridge, 1999. MR**1725241**, DOI 10.1017/CBO9780511542930 - Wen-Ching W. Li, Mats Näslund, and Igor E. Shparlinski,
*Hidden number problem with the trace and bit security of XTR and LUC*, Advances in cryptology—CRYPTO 2002, Lecture Notes in Comput. Sci., vol. 2442, Springer, Berlin, 2002, pp. 433–448. MR**2055076**, DOI 10.1007/3-540-45708-9_{2}8 - Rudolf Lidl and Harald Niederreiter,
*Finite fields*, 2nd ed., Encyclopedia of Mathematics and its Applications, vol. 20, Cambridge University Press, Cambridge, 1997. With a foreword by P. M. Cohn. MR**1429394** - Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone,
*Handbook of applied cryptography*, CRC Press Series on Discrete Mathematics and its Applications, CRC Press, Boca Raton, FL, 1997. With a foreword by Ronald L. Rivest. MR**1412797** - Phong Q. Nguyen and Igor E. Shparlinski,
*The insecurity of the elliptic curve digital signature algorithm with partially known nonces*, Des. Codes Cryptogr.**30**(2003), no. 2, 201–217. MR**2007211**, DOI 10.1023/A:1025436905711 - Karl Prachar,
*Primzahlverteilung*, Springer-Verlag, Berlin-Göttingen-Heidelberg, 1957 (German). MR**0087685** - Oliver Schirokauer,
*Discrete logarithms and local units*, Philos. Trans. Roy. Soc. London Ser. A**345**(1993), no. 1676, 409–423. MR**1253502**, DOI 10.1098/rsta.1993.0139 - Oliver Schirokauer, Damian Weber, and Thomas Denny,
*Discrete logarithms: the effectiveness of the index calculus method*, Algorithmic number theory (Talence, 1996) Lecture Notes in Comput. Sci., vol. 1122, Springer, Berlin, 1996, pp. 337–361. MR**1446523**, DOI 10.1007/3-540-61581-4_{6}6 - Igor Shparlinski,
*On exponential sums with sparse polynomials and rational functions*, J. Number Theory**60**(1996), no. 2, 233–244. MR**1412961**, DOI 10.1006/jnth.1996.0121 - Igor E. Shparlinski,
*On the generalised hidden number problem and bit security of XTR*, Applied algebra, algebraic algorithms and error-correcting codes (Melbourne, 2001) Lecture Notes in Comput. Sci., vol. 2227, Springer, Berlin, 2001, pp. 268–277. MR**1913473**, DOI 10.1007/3-540-45624-4_{2}8 - 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. - Igor E. Shparlinski,
*Exponential sums and lattice reduction: applications to cryptography*, Finite fields with applications to coding theory, cryptography and related areas (Oaxaca, 2001) Springer, Berlin, 2002, pp. 286–298. MR**1995344** - Igor Shparlinski,
*Cryptographic applications of analytic number theory*, Progress in Computer Science and Applied Logic, vol. 22, Birkhäuser Verlag, Basel, 2003. Complexity lower bounds and pseudorandomness. MR**1954519**, DOI 10.1007/978-3-0348-8037-4 - Igor E. Shparlinski and Arne Winterhof,
*A nonuniform algorithm for the hidden number problem in subgroups*, Public key cryptography—PKC 2004, Lecture Notes in Comput. Sci., vol. 2947, Springer, Berlin, 2004, pp. 416–424. MR**2095823**, DOI 10.1007/978-3-540-24632-9_{3}0 - I. E. Shparlinski and A. Winterhof, “Noisy interpolation of sparse polynomials in finite fields”,
*Appl. Algebra in Engin., Commun. and Computing*, (to appear). - Douglas R. Stinson,
*Cryptography*, 2nd ed., CRC Press Series on Discrete Mathematics and its Applications, Chapman & Hall/CRC, Boca Raton, FL, 2002. Theory and practice. MR**1911330** - Arne Winterhof,
*A note on Waring’s problem in finite fields*, Acta Arith.**96**(2001), no. 4, 365–368. MR**1811878**, DOI 10.4064/aa96-4-6

## Additional Information

**Igor Shparlinski**- Affiliation: Department of Computing, Macquarie University, Sydney, New South Wales 2109, Australia
- MR Author ID: 192194
- Email: igor@ics.mq.edu.au
**Arne Winterhof**- Affiliation: RICAM, Austrian Academy of Sciences, Altenbergerstrasse 69, 4040 Linz, Austria
- Email: arne.winterhof@oeaw.ac.at
- Received by editor(s): March 3, 2003
- Published electronically: April 5, 2005
- © Copyright 2005 American Mathematical Society
- Journal: Math. Comp.
**74**(2005), 2073-2080 - MSC (2000): Primary 11T23, 11T71, 11Y16, 94A60
- DOI: https://doi.org/10.1090/S0025-5718-05-01797-7
- MathSciNet review: 2164114