Improved elliptic curve hashing and point representation

摘要

For a large class of functions to the group of points of an elliptic curve (typically obtained from certain algebraic correspondences between E and ), Farashahi et al. (Math Comput 82(281):491-512, 2013) established that the map is regular, in the sense that for a uniformly random choice of , the elliptic curve point is close to uniformly distributed in . This result has several applications in cryptography, mainly to the construction of elliptic curve-valued hash functions and to the "Elligator Squared" technique by Tibouchi (in: Christin and Safavi-Naini (eds) Financial cryptography. LNCS, vol 8437, pp 139-156. Springer, Heidelberg, 2014) for representating uniform points on elliptic curves as close to uniform bitstrings. In this paper, we improve upon Farashahi et al.'s character sum estimates in two ways: we show that regularity can also be obtained for a function of the form where g has a much smaller domain than , and we prove that the functions f considered by Farashahi et al. also satisfy requisite bounds when restricted to large intervals inside . These improved estimates can be used to obtain more efficient hash function constructions, as well as much shorter "Elligator Squared" bitstring representations.