Encoding points on hyperelliptic curves over finite fields in deterministic polynomial time. (English) Zbl 1290.94100

Kammerer, Jean-Gabriel; Lercier, Reynald; Renault, Guénaël

Joye, Marc (ed.) et al., Pairing-based cryptography – Pairing 2010. 4th international conference, Yamanaka Hot Spring, Japan, December 13–15, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-17454-4/pbk). Lecture Notes in Computer Science 6487, 278-297 (2010).

Summary: We provide new hash functions into (hyper)elliptic curves over finite fields. These functions aim at instantiating in a secure manner cryptographic protocols where we need to map strings into points on algebraic curves, typically user identities into public keys in pairing-based IBE schemes.
Contrasting with recent Icart’s encoding, we start from “easy to solve by radicals” polynomials in order to obtain models of curves which in turn can be deterministically “algebraically parameterized”. As a result of this strategy, we obtain a low degree encoding map for Hessian elliptic curves, and for the first time, hashing functions for genus 2 curves. More generally, we present for any genus (more narrowed) families of hyperelliptic curves with this property.
The image of these encodings is large enough to be “weak” encodings in the sense of Brier et al. As such they can be easily turned into admissible cryptographic hash functions.
For the entire collection see [Zbl 1200.94008].

MSC:

94A60	Cryptography
12F10	Separable extensions, Galois theory
14G50	Applications to coding theory and cryptography of arithmetic geometry

Keywords:

deterministic encoding; elliptic curves; Galois theory; hyperelliptic curves

Software:

Magma