Cryptology ePrint Archive: Report 2009/226

How to Hash into Elliptic Curves

Thomas Icart

Abstract: We describe a new explicit function that given an elliptic curve $E$ defined over $\FF_{p^n}$, maps elements of $\FF_{p^n}$ into $E$ in \emph{deterministic} polynomial time and in a constant number of operations over $\FF_{p^n}$. The function requires to compute a cube root. As an application we show how to hash \emph{deterministically} into an elliptic curve.

Category / Keywords: Elliptic curve, Hash function

Publication Info: An extended abstract of this paper will appear at CRYPTO 2009. This is the full version.

Date: received 20 May 2009, last revised 24 May 2009

Contact author: thomas icart at gmail com

Available formats: PDF | BibTeX Citation

Version: 20090530:041605 (All versions of this report)

Discussion forum: Show discussion | Start new discussion