article

On the period of the Naor--Reingold sequence

Author:

Álvar Ibeas MartínAuthors Info & Claims

Information Processing Letters, Volume 108, Issue 5

Pages 304 - 307

https://doi.org/10.1016/j.ipl.2008.05.025

Published: 01 November 2008 Publication History

Abstract

In this paper we study the period of the Naor-Reingold sequence. We prove that if the parameters used to define the sequence are chosen uniformly at random, then it reaches the maximum period on average.

References

[1]

Chou, W.-S., The period lengths of inversive congruential recursions. Acta Arith. v73 i4. 325-341.

Google Scholar

[2]

Chou, W.S., The period lengths of inversive pseudorandom vector generations. Finite Fields Appl. v1 i1. 126-132.

Digital Library

Google Scholar

[3]

Friedlander, J.B., Pomerance, C. and Shparlinski, I.E., Period of the power generator and small values of Carmichael's function. Math. Comp. v70 i236. 1591-1605.

Digital Library

Google Scholar

[4]

Hardy, G.H. and Wright, E.M., An Introduction to the Theory of Numbers. 1979. fifth ed. The Clarendon Press/Oxford University Press, New York.

Google Scholar

[5]

Lidl, R., Mullen, G.L. and Turnwald, G., Dickson Polynomials. 1993. Pitman Monographs and Surveys in Pure and Applied Mathematics, 1993.Longman Scientific & Technical, Harlow.

Google Scholar

[6]

Naor, M. and Reingold, O., Number-theoretic constructions of efficient pseudo-random functions. J. ACM. v51 i2. 231-262.

Digital Library

Google Scholar

[7]

Niederreiter, H., Random Number Generation and Quasi-Monte Carlo Methods. 1992. CBMS-NSF Regional Conference Series in Applied Mathematics, 1992.Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA.

Digital Library

Google Scholar

[8]

Niederreiter, H., Design and analysis of nonlinear pseudorandom number generators. In: Schuëller, G.I., Spanos, P.D. (Eds.), Monte Carlo Simulation, A.A. Balkema, Rotterdam.

Google Scholar

[9]

Niederreiter, H. and Shparlinski, I.E., Recent advances in the theory of nonlinear pseudorandom number generators. In: Monte Carlo and Quasi-Monte Carlo Methods, Springer, Berlin. pp. 86-102.

Google Scholar

[10]

Niederreiter, H. and Shparlinski, I.E., Dynamical systems generated by rational functions. In: Lecture Notes in Comput. Sci., vol. 2643. Springer, Berlin. pp. 6-17.

Digital Library

Google Scholar

[11]

Shparlinski, I.E., On the Naor--Reingold pseudo-random function from elliptic curves. Appl. Algebra Engrg. Comm. Comput. v11 i1. 27-34.

Google Scholar

[12]

Shparlinski, I.E., Cryptographic Applications of Analytic Number Theory. Complexity Lower Bounds and Pseudorandomness. 2003. Progress in Computer Science and Applied Logic, 2003.Birkhäuser Verlag, Basel.

Google Scholar

[13]

Shparlinski, I.E. and Silverman, J.H., On the linear complexity of the Naor--Reingold pseudo-random function from elliptic curves. Des. Codes Cryptogr. v24 i3. 279-289.

Digital Library

Google Scholar

[14]

Shparlinski, I.E., Pseudorandom points on elliptic curves over finite fields. In: Ser. Number Theory Appl., vol. 6. World Sci. Publ., Hackensack, NJ.

Google Scholar

[15]

Topuzoğlu, A. and Winterhof, A., Pseudorandom sequences. In: Algebra Appl., vol. 6. Springer, Dordrecht. pp. 135-166.

Google Scholar

Cited By

View all

Mefenza TVergnaud D(2019)Polynomial interpolation of the generalized Diffie---Hellman and Naor---Reingold functionsDesigns, Codes and Cryptography10.1007/s10623-018-0486-187:1(75-85)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1007/s10623-018-0486-1
Cruz MGóMez DSadornil D(2018)On the linear complexity of the Naor-Reingold sequence with elliptic curvesFinite Fields and Their Applications10.1016/j.ffa.2010.05.00516:5(329-333)Online publication date: 23-Dec-2018
https://dl.acm.org/doi/10.1016/j.ffa.2010.05.005

Index Terms

On the period of the Naor--Reingold sequence

Recommendations

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

We show that the new pseudo-random number function, introduced recently by M. Naor and O. Reingold, possesses one more attractive and useful property. Namely, it is proved that for almost all values of parameters it produces a uniformly distributed ...
The period of the LFSR based generalized shrinking-multiplexing generator
CompSysTech '07: Proceedings of the 2007 international conference on Computer systems and technologies

An architecture of Generalized Shrinking-Multiplexing Generator (GSMG) based on Linear Shift Feedback Register (LFSR) is investigated in the paper. The period of its output binary pseudo random sequences is established. Some period analysis and a ...
On the Linear Complexity of the Naor–Reingold Pseudo-random Function from Elliptic Curves

We show that the elliptic curve analogue of the pseudo-random number function, introduced recently by M. Naor and O. Reingold, produces a sequence with large linear complexity. This result generalizes a similar result of F. Griffin and I. E. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Information Processing Letters Volume 108, Issue 5

November, 2008

84 pages

ISSN:0020-0190

Issue’s Table of Contents

Publisher

Elsevier North-Holland, Inc.

United States

Publication History

Published: 01 November 2008

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Mefenza TVergnaud D(2019)Polynomial interpolation of the generalized Diffie---Hellman and Naor---Reingold functionsDesigns, Codes and Cryptography10.1007/s10623-018-0486-187:1(75-85)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1007/s10623-018-0486-1
Cruz MGóMez DSadornil D(2018)On the linear complexity of the Naor-Reingold sequence with elliptic curvesFinite Fields and Their Applications10.1016/j.ffa.2010.05.00516:5(329-333)Online publication date: 23-Dec-2018
https://dl.acm.org/doi/10.1016/j.ffa.2010.05.005

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

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

The period of the LFSR based generalized shrinking-multiplexing generator

On the Linear Complexity of the Naor–Reingold Pseudo-random Function from Elliptic Curves

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations