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

Igor E. Shparlinski*, Joseph H. Silverman

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

17 Citations (Scopus)

Abstract

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. Shparlinski for the linear complexity of the original function of M. Naor and O. Reingold. The proof is based on some results about the distribution of subset-products in finite fields and some properties of division polynomials of elliptic curves.

Original languageEnglish
Pages (from-to)279-289
Number of pages11
JournalDesigns, Codes and Cryptography
Volume24
Issue number3
DOIs
Publication statusPublished - Dec 2001

Fingerprint Dive into the research topics of 'On the Linear Complexity of the Naor-Reingold Pseudo-random Function from Elliptic Curves'. Together they form a unique fingerprint.

Cite this