On the linear complexity profile of some sequences derived from elliptic curves (Q306337)

Pseudorandom sequences \(\{u_n\}\) are the basic tool of stream cipher cryptography. The linear complexity profile and the linear complexity of these sequences measure their randomness in terms of linear recurrence equations. One method to generate pseudorandom sequences is the power generator \((u_n=u_{n-1}^e \bmod m\), for some \(e\in \mathbb{N}\); the case \(e=2\) is the well-known Blum-Blum-Shub generator). \textit{F. Griffin} and \textit{I. E. Shparlinski} [IEEE Trans. Inf. Theory 46, No. 6, 2159--2162 (2000; Zbl 0997.94012)] studied the linear complexity profile of the power generator sequences and \textit{F. Hess} and \textit{I. E. Shparlinski} [Des. Codes Cryptography 35, No. 1, 111--117 (2005; Zbl 1116.14307)] the linear complexity profile of the elliptic curve generator \(w_n=f(nG)\), where \(G\in E(F_q)\), \(E\) elliptic curve defined over a finite field \(F_q\) and \(f\in F_q(E)\) a function. The present paper carries out a similar study of the complexity of those elliptic curve pseudorandom sequences, but using elliptic curves defined by Edwards models: \(u^2+v^2=c^2(1+du^2v^2)\), \(c,d\in \mathbb{F}_q\), \(d\neq 0,1\), \(c\neq 0\), see \textit{D. J. Bernstein} and \textit{T. Lange} [Asiacrypt 2007, Lect. Notes Comput. Sci. 4833, 29--50 (2007; Zbl 1153.11342)], instead of the classical Weierstrass models. The authors claim that this allows ``to deal with many \(f\) where Hess and Shparlinski's result does not apply''. Section 3 states the main results on the linear complexity of elliptic curve generator sequences \(\{w_n\}\), \(w_n= f(nG)\), \(n=1,2,\dots\), (Theorem 1) and elliptic curve power generator sequences \(\{r_n\}\), \(r_n= f(e^nG)\), \(n=1,2,\dots\), (Theorem 2). The proof of these two theorems is given in Sections 4 and 5.