Encoding points on hyperelliptic curves over finite fields in deterministic polynomial time

Jean-Gabriel Kammerer (1) , Reynald Lercier (1) , Guénaël Renault (2)

1 IRMAR - Institut de Recherche Mathématique de Rennes
2 SALSA - Solvers for Algebraic Systems and Applications

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.

Domaines: Cryptographie et sécurité [cs.CR]

Jean-Gabriel Kammerer, Reynald Lercier, Guénaël Renault. Encoding points on hyperelliptic curves over finite fields in deterministic polynomial time. PAIRING 2010 - 4th International Conference on Pairing-Based Cryptography, Dec 2010, Ishikawa, Japan. pp.278-297, ⟨10.1007/978-3-642-17455-1_18⟩. ⟨hal-00694136⟩