Cryptology ePrint Archive: Report 2001/098

Fast hashing onto elliptic curves over fields of characteristic 3

Paulo S. L. M. Barreto and Hae Yong Kim

Abstract: We describe a fast hash algorithm that maps arbitrary messages onto points of an elliptic curve defined over a finite field of characteristic 3. Our new scheme runs in time $O(m^2)$ for curves over $\GF{3^m}$. The best previous algorithm for this task runs in time $O(m^3)$. Experimental data confirms the speedup by a factor $O(m)$, or approximately a hundred times for practical $m$ values. Our results apply for both standard and normal basis representations of $\GF{3^m}$.

Category / Keywords: public-key cryptography / digital signatures, elliptic curve cryptosystem, hash functions

Date: received 15 Nov 2001

Contact author: pbarreto at scopus com br

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20011115:235413 (All versions of this report)

Short URL: ia.cr/2001/098

Discussion forum: Show discussion | Start new discussion