Design of Pseudorandom Binary Threshold Sequences over Elliptic Curves

Due to the high security level of elliptic curve cryptography, the constructions of pseudorandom sequences generated from elliptic curves have been paid more attention recently. But the study mainly is concentrated upon the application of elliptic curves over prime fields. This paper defines pseudorandom numbers in the interval 0,1) by using elliptic curves over extension fields and presents a construction of binary threshold sequences. A discrepancy bounds for the pseudorandom numbers is derived and used to study the pseudorandomness of the binary threshold sequences in terms of estimating upper bounds on the well-distribution measure and the correlation measure of order l, both introduced by Mauduit and Sarkozy. The proofs are based on bounds on exponential sums and earlier relations of Mauduit, Niederreiter and Sarkozy between discrepancy and both measures above. Moreover, a lower bound on the linear complexity profile of the binary threshold sequences is presented in terms of the correlation measure of order l.