International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Fast hashing onto elliptic curves over fields of characteristic 3

Authors:
Paulo S. L. M. Barreto
Hae Yong Kim
Download:
URL: http://eprint.iacr.org/2001/098
Search ePrint
Search Google
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}$.
BibTeX
@misc{eprint-2001-11510,
  title={Fast hashing onto elliptic curves over fields of characteristic 3},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / digital signatures, elliptic curve cryptosystem, hash functions},
  url={http://eprint.iacr.org/2001/098},
  note={ pbarreto@scopus.com.br 11641 received 15 Nov 2001},
  author={Paulo S. L. M. Barreto and Hae Yong Kim},
  year=2001
}