Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

On the Multidimensional Distribution of the Naor-Reingold Pseudo-Random Function


Authors: San Ling, Igor Shparlinski and Huaxiong Wang
Journal: Math. Comp. 83 (2014), 2429-2434
MSC (2010): Primary 11K45, 11T23, 65C10, 94A60
DOI: https://doi.org/10.1090/S0025-5718-2014-02794-4
Published electronically: January 17, 2014
MathSciNet review: 3223338
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We show that the pseudo-random number function, introduced by M. Naor and O. Reingold (FOCS, 1997), possesses one more attractive and useful property. Namely, it is proved that for almost all values of parameters it produces a uniformly distributed sequence. The proof is based on some recent bounds of character sums with exponential functions.


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

  • [1] 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., 1787, Springer-Verlag, Berlin, 2000, 53-59.
  • [2] J. Bourgain, Mordell's exponential sum estimate revisited, J. Amer. Math. Soc. 18 (2005), no. 2, 477-499. MR 2137982 (2006b:11099), https://doi.org/10.1090/S0894-0347-05-00476-5
  • [3] Marcos Cruz, Domingo Gómez, and Daniel Sadornil, On the linear complexity of the Naor-Reingold sequence with elliptic curves, Finite Fields Appl. 16 (2010), no. 5, 329-333. MR 2678621 (2011g:14062), https://doi.org/10.1016/j.ffa.2010.05.005
  • [4] Michael Drmota and Robert F. Tichy, Sequences, discrepancies and applications, Lecture Notes in Mathematics, vol. 1651, Springer-Verlag, Berlin, 1997. MR 1470456 (98j:11057)
  • [5] Domingo Gómez, Jaime Gutierrez, and Álvar Ibeas, On the linear complexity of the Naor-Reingold sequence, Inform. Process. Lett. 111 (2011), no. 17, 854-856. MR 2849394 (2012e:11145), https://doi.org/10.1016/j.ipl.2011.05.017
  • [6] 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., 1726, Springer-Verlag, Berlin, 1999, 301-308.
  • [7] 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.
  • [8] Harald Niederreiter, Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc. 84 (1978), no. 6, 957-1041. MR 508447 (80d:65016), https://doi.org/10.1090/S0002-9904-1978-14532-7
  • [9] Igor E. Shparlinski, On the Naor-Reingold pseudo-random function from elliptic curves, Appl. Algebra Engrg. Comm. Comput. 11 (2000), no. 1, 27-34. MR 1817696 (2001m:65015), https://doi.org/10.1007/s002000000023
  • [10] Igor E. Shparlinski, Linear complexity of the Naor-Reingold pseudo-random function, Inform. Process. Lett. 76 (2000), no. 3, 95-99. MR 1801380, https://doi.org/10.1016/S0020-0190(00)00133-2
  • [11] Igor E. Shparlinski, On the uniformity of distribution of the Naor-Reingold pseudo-random function, Finite Fields Appl. 7 (2001), no. 2, 318-326. MR 1826340 (2002b:11104), https://doi.org/10.1006/ffta.2000.0291
  • [12] Igor E. Shparlinski and Joseph H. Silverman, On the linear complexity of the Naor-Reingold pseudo-random function from elliptic curves, Des. Codes Cryptogr. 24 (2001), no. 3, 279-289. MR 1857142 (2002j:11087), https://doi.org/10.1023/A:1011223204345

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11K45, 11T23, 65C10, 94A60

Retrieve articles in all journals with MSC (2010): 11K45, 11T23, 65C10, 94A60


Additional Information

San Ling
Affiliation: Division of Mathematical Sciences, School of Physical & Mathematical Sciences, Nanyang Technological University, Singapore 637371, Singapore
Email: lingsan@ntu.edu.sg

Igor Shparlinski
Affiliation: Department of Computing, Macquarie University, Sydney NSW 2109, Australia
Email: igor.shparlinski@mq.edu.au

Huaxiong Wang
Affiliation: Division of Mathematical Sciences, School of Physical & Mathematical Sciences, Nanyang Technological University, Singapore 637371, Singapore
Email: hxwang@ntu.edu.sg

DOI: https://doi.org/10.1090/S0025-5718-2014-02794-4
Keywords: Naor-Reingold pseudo-random function, discrepancy, exponential sums
Received by editor(s): July 28, 2012
Received by editor(s) in revised form: December 17, 2012
Published electronically: January 17, 2014
Additional Notes: During the preparation of this paper, the authors were supported by NRF Grant CRP2-2007-03 (Singapore).
The second author was supported in part by ARC Grant DP1092835 (Australia).
Article copyright: © Copyright 2014 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society