The Naor-Reingold sequences with elliptic curves are used in cryptography due to their nice construction and good theoretical properties. Here the authors give a new bound on the linear complexity of these sequences thereby improving the previous one obtained by {\it I. E. Shparlinski} and {\it J. H. Silverman} [Des. Codes Cryptography 24, No. 3, 279‒289 (2001; Zbl 1077.11504)] and holding in more cases. The following theorem is the main result: For $0<δ<1$ and $n<\tfrac 43 \log l+6$, the linear complexity $L_{\bold a}$ of the sequence $(u_k)_{k=0}^{2^n-1}$ satisfies $$L_{\bold a}\ge 2^{n/2} l^{-2/3-δ}/8$$ for all but at most $O((l-1)^{n-δ}$ vectors $\bold a\in(\Bbb F_l^*)^n$. The implied constant is absolute.
Reviewer: Olaf Ninnemann (Berlin)