Pseudorandom Bits From Points on Elliptic Curves

Abstract

Let $\E$ be an elliptic curve over a finite field $\F_{q}$ of $q$ elements, with $\gcd (q,6)=1$, given by an affine Weierstraß equation. We also use $x(P)$ to denote the $x$-component of a point $P = (x(P),y(P))\in \E$. We estimate character sums of the form $$ \sum_{n=1}^N χ\(x(nP)x(nQ)\) \quad \text{and}\quad \sum_{n_1, \ldots, n_k=1}^N ψ\(\sum_{j=1}^k c_j x\(\(\prod_{i =1}^j n_i\) R\)\) $$ on average over all $\F_q$ rational points $P$, $Q$ and $R$ on $\E$, where $\chi$ is a quadratic character, $\psi$ is a nontrivial additive character in $\F_q$ and $(c_1, \ldots, c_k)\in \F_q^k$ is a non-zero vector. These bounds confirm several recent conjectures of D. Jao, D. Jetchev and R. Venkatesan, related to extracting random bits from various sequences of points on elliptic curves.