Reza Rezaeian Farashahi (TU Eindhoven): Extractors for Binary Elliptic Curves

A deterministic extractor for an elliptic curve is a function that converts a random point on the curve to a random bit-string, which is statistically close to a uniformly random bit-string. The problem of converting random points of an elliptic curve into random bits has several cryptographic applications. In this talk, we propose two simple and efficient deterministic extractors for an ordinary elliptic curve E defined over GF(2^N), where N=2l and l is an arbitrary positive integer. Our first extractor, H_0, for a given point P on E, outputs the first GF(2^l)-coefficient of the abscissa of the point P. Similarly the second extractor, H_1, for a given point on E, outputs the second GF(2^l)-coefficient of the abscissa of the point. Provided that the point P is chosen uniformly at random, the extracted bits of the point P are indistinguishable from a uniformly random bit-string of length l.