International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Hae Yong Kim

Publications

Year
Venue
Title
2002
CRYPTO
2001
FSE
2001
EPRINT
Fast hashing onto elliptic curves over fields of characteristic 3
Paulo S. L. M. Barreto Hae Yong Kim
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}$.