On the uniformity of distribution of the RSA pairs

Shparlinski, Igor

doi:10.1090/S0025-5718-00-01274-6

On the uniformity of distribution of the RSA pairs
HTML articles powered by AMS MathViewer

by Igor E. Shparlinski PDF

Math. Comp. 70 (2001), 801-808 Request permission

Abstract:

Let $m= pl$ be a product of two distinct primes $p$ and $l$. We show that for almost all exponents $e$ with $\operatorname {gcd} (e, \varphi (m))= 1$ the RSA pairs $(x, x^e)$ are uniformly distributed modulo $m$ when $x$ runs through

the group of units $\mathbb {Z}_m^*$ modulo $m$ (that is, as in the classical RSA scheme);

the set of $k$-products $x = a_{i_1}\cdots a_{i_k}$, $1 \le i_1 < \cdots < i_k \le n$, where $a_1, \cdots , a_n \in \mathbb {Z}_m^*$ are selected at random (that is, as in the recently introduced RSA scheme with precomputation).

These results are based on some new bounds of exponential sums.

References

M. Ajtai, ‘Generating hard instances of lattice problems’, Electronic Colloq. on Comp. Compl., Univ. of Trier, TR96-007 (1996), 1–29.
W. Banks, F. Griffin, D. Lieman and I. E. Shparlinski, ‘Non-linear complexity of the Naor-Reingold pseudo-random function’, Proc. the 2nd Intern. Conf. on Information Security and Cryptology, Seoul, 1999, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, (to appear).
L. Blum, M. Blum, and M. Shub, A simple unpredictable pseudorandom number generator, SIAM J. Comput. 15 (1986), no. 2, 364–383. MR 837589, DOI 10.1137/0215025
V. Boyko, M. Peinado and R. Venkatesan, ‘Speeding up discrete log and factoring based schemes via precomputations’, Proc. of Eurocrypt’98, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 1403 (1998), 221–234.
R. Canetti, J. B. Friedlander, S. Konyagin, M. Larsen, D. Lieman and I. E. Shparlinski, ‘On the statistical properties of Diffie–Hellman distributions’, Israel J. Math., (to appear).
R. Canetti, J. B. Friedlander and I. E. Shparlinski, ‘On certain exponential sums and the distribution of Diffie–Hellman triples’, J. London Math. Soc., (1999), 799–812.
Thomas W. Cusick, Cunsheng Ding, and Ari Renvall, Stream ciphers and number theory, North-Holland Mathematical Library, vol. 55, North-Holland Publishing Co., Amsterdam, 1998. MR 1634586
Michael Drmota and Robert F. Tichy, Sequences, discrepancies and applications, Lecture Notes in Mathematics, vol. 1651, Springer-Verlag, Berlin, 1997. MR 1470456, DOI 10.1007/BFb0093404
J. B. Friedlander, D. Lieman and I. E. Shparlinski, ‘On the distribution of the RSA generator’, Proc. Intern. Conf. on Sequences and Their Applications (SETA’98), Singapore, Springer-Verlag, London, 1999, 205–212.
J. B. Friedlander, C. Pomerance and I. E. Shparlinski, ‘Period of the power generator and small values of Carmichael’s function’, Math. Comp., (to appear).
J. B. Friedlander and I. E. Shparlinski, ‘On the distribution of the power generator’, Math. Comp., (to appear).
F. Griffin and I. E. Shparlinski, ‘On the linear complexity of the Naor-Reingold pseudo-random function’, Proc. 2nd Intern. Conf. on Information and Communication Security, Sydney, 1999, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 1726 (1999), 301–308.
F. Griffin and I. E. Shparlinski, ‘On the linear complexity profile of the power generator’, Trans. IEEE Inform. Theory (to appear).
Russell Impagliazzo and Moni Naor, Efficient cryptographic schemes provably as secure as subset sum, J. Cryptology 9 (1996), no. 4, 199–216. MR 1426279, DOI 10.1007/s001459900012
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, DOI 10.1090/psapm/042/1095554
Michael Luby, Pseudorandomness and cryptographic applications, Princeton Computer Science Notes, Princeton University Press, Princeton, NJ, 1996. MR 1373652
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
M. Naor and O. Reingold, ‘Number-theoretic constructions of efficient pseudo-random functions’, Proc. 38th IEEE Symp. on Foundations of Comp. Sci., 1997, 458–467.
M. Naor and O. Reingold, ‘Synthesizers and their application to the parallel construction of pseudo-random functions’, J. Comp. and Sys. Sci., 58 (1999), 336–375.
P. Nguyen, I. E. Shparlinski and J. Stern, ‘Distribution of modular sums and the security of the server aided exponentiation’, Preprint, 2000, 1–16.
P. Nguyen and J. Stern, ‘The hardness of the hidden subset sum problem and its cryptographic implications’, Proc. CRYPTO’99, Santa Barbara, 1999, Springer-Verlag, Berlin, 1666 (1999), 31–46.
I. E. Shparlinski, ‘On the uniformity of distribution of the Naor-Reingold pseudo-random number function’, Finite Fields and Their Appl. (to appear).
I. E. Shparlinski, ‘On the Naor-Reingold pseudo-random number generator from elliptic curves’, Appl. Algebra in Engin., Commun. and Computing (to appear).
I. E. Shparlinski, ‘On the linear complexity of the power generator’, Designs, Codes and Cryptography, (to appear).
I. E. Shparlinski and J. H. Silverman, ‘Linear complexity of the Naor–Reingold pseudo-random number function from elliptic curves’, Preprint, 1999, 1–14.
Douglas R. Stinson, Cryptography, CRC Press Series on Discrete Mathematics and its Applications, CRC Press, Boca Raton, FL, 1995. Theory and practice. MR 1327060
Saunders MacLane and O. F. G. Schilling, Infinite number fields with Noether ideal theories, Amer. J. Math. 61 (1939), 771–782. MR 19, DOI 10.2307/2371335