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 functi on, introduced recently by M. Naor and O. Reingold, produces a sequence wit h large linear complexity. This result generalizes a similar result of F. G riffin and I. E. Shparlinski for the linear complexity of the original func tion of M. Naor and O. Reingold. The proof is based on some results about t he distribution of subset-products in finite fields and some properties of division polynomials of elliptic curves.