On the linear complexity of the Naor-Reingold sequence with elliptic curves (Q708437)

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 \textit{I. E. Shparlinski} and \textit{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<\delta <1\) and \(n<\tfrac 43 \log l+6\), the linear complexity \(L_{\mathbf a}\) of the sequence \((u_k)_{k=0}^{2^n-1}\) satisfies \[ L_{\mathbf a}\geq 2^{n/2} l^{-2/3-\delta}/8 \] for all but at most \(O((l-1)^{n-\delta}\) vectors \(\mathbf a\in(\mathbb F_l^*)^n\). The implied constant is absolute.