Character sums with division polynomials

Abstract

We obtain nontrivial estimates of quadratic character sums of division polynomials ${\Psi }_n(P)$, $n=1,2,...$, evaluated at a given point $P$ on an elliptic curve over a finite field of $q$ elements. Our bounds are nontrivial if the order of $P$ is at least $q^{1/2+\epsilon }$ for some fixed $\epsilon >0$. This work is motivated by an open question about statistical indistinguishability of some cryptographically relevant sequences which has recently been brought up by K. Lauter and the second author.