Skip to Main content Skip to Navigation
Conference papers

Improved Elliptic Curve Hashing and Point Representation

Abstract : For a large class of functions f : Fq → E(Fq) to the group of points of an elliptic curve E/Fq, Farashahi et al. (Math. Comp. 2013) established that the map (u, v) → f (u) + f (v) is regular, in the sense that for a uniformly random choice of (u, v) ∈ F 2 q , the elliptic curve point f (u) + f (v) is close to uniformly distributed in E(Fq). This result has several applications in cryptography, mainly to the construction of elliptic curve-valued hash functions and to the " Elligator Squared " technique 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 (u, v) → f (u) + g(v) where g has a much smaller domain than Fq, and we prove that the functions f considered by Farashahi et al. also satisfy requisite bounds when restricted to large intervals inside Fq. These improved estimates can be used to obtain more efficient hash function constructions, as well as much shorter " Elligator Squared " bitstring representations.
Document type :
Conference papers
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-01275711
Contributor : Jean-Pierre Tillich <>
Submitted on : Thursday, February 18, 2016 - 9:12:34 AM
Last modification on : Thursday, February 18, 2016 - 3:40:03 PM
Long-term archiving on: : Thursday, May 19, 2016 - 10:21:41 AM

File

wcc15-mo2-2.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01275711, version 1

Collections

Citation

Taechan Kim, Mehdi Tibouchi. Improved Elliptic Curve Hashing and Point Representation. WCC2015 - 9th International Workshop on Coding and Cryptography 2015, Anne Canteaut, Gaëtan Leurent, Maria Naya-Plasencia, Apr 2015, Paris, France. ⟨hal-01275711⟩

Share

Metrics

Record views

112

Files downloads

720