The most efficient indifferentiable hashing to elliptic curves of j-invariant 1728

Abstract

This article makes an important contribution to solving the long-standing problem of whether all elliptic curves can be equipped with a hash function (indifferentiable from a random oracle) whose running time amounts to one exponentiation in the basic finite field Fq{{\mathbb{F}}}_{q}. More precisely, we construct a new indifferentiable hash function to any ordinary elliptic Fq{{\mathbb{F}}}_{q}-curve Ea{E}_{a} of j-invariant 1728 with the cost of extracting one quartic root in Fq{{\mathbb{F}}}_{q}. As is known, the latter operation is equivalent to one exponentiation in finite fields with which we deal in practice. In comparison, the previous fastest random oracles to Ea{E}_{a} require to perform two exponentiations in Fq{{\mathbb{F}}}_{q}. Since it is highly unlikely that there is a hash function to an elliptic curve without any exponentiations at all (even if it is supersingular), the new result seems to be unimprovable.

Keywords

• calabi–yau threefolds
• double-odd curves
• indifferentiable hashing to elliptic curves
• j-invariant 1728
• pairing-based cryptography
• 14e05
• 14e08
• 14g15
• 14g50
• 14g05
• 14h52
• 14j26
• 14j27
• 14j32
• 14q20