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

DOI:
https://doi.org/10.1090/S0025-5718-05-01797-7

Published electronically:
April 5, 2005

MathSciNet review:
2164114

Full-text PDF Free Access

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.

- 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 https://doi.org/10.1016/S1631-073X%2803%2900281-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 https://doi.org/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 https://doi.org/10.1007/s00037-002-0174-3 - Richard Crandall and Carl Pomerance,
*Prime numbers*, Springer-Verlag, New York, 2001. A computational perspective. MR**1821158** - 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{\rm th}$ powers, and for Heilbronn’s exponential sum*, Q. J. Math.**51**(2000), no. 2, 221–235. MR**1765792**, DOI https://doi.org/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** - 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 https://doi.org/10.1007/3-540-45708-9_28 - 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 https://doi.org/10.1023/A%3A1025436905711 - 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 https://doi.org/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 https://doi.org/10.1007/3-540-61581-4_66 - Igor Shparlinski,
*On exponential sums with sparse polynomials and rational functions*, J. Number Theory**60**(1996), no. 2, 233–244. MR**1412961**, DOI https://doi.org/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 https://doi.org/10.1007/3-540-45624-4_28 - 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** - 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 https://doi.org/10.1007/978-3-540-24632-9_30 - 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 https://doi.org/10.4064/aa96-4-6

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

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

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