[CFRG] Indifferentiable hashing to ordinary elliptic curves of j-invariant 0 with the cost of one exponentiation

[Dimitri Koshelev <[e-mail]>]

Dear CFRG participants,

As this is the broadest form for discussing the CFRG hash-to-curve draft
<https://datatracker.ietf.org/doc/draft-irtf-cfrg-hash-to-curve/>, I wanted
to mention my optimization. You'll find the paper on the IACR eprint server
<https://eprint.iacr.org/2021/301> or published at DCC
<https://link.springer.com/article/10.1007/s10623-022-01012-8>. This paper
provides a new hash function H (indifferentiable from a random oracle) to
many ordinary elliptic curves y^2 = x^3 + b (of j-invariant 0), including
most pairing-friendly curves of the family BLS12 (Barreto-Lynn-Scott) of
embedding degree 12. Hash functions to such curves are actively used in
numerous protocols such as the BLS (Boneh-Lynn-Shacham) aggregate signature.

My hash function H is much faster than previous state-of-the-art ones,
including the Wahby-Boneh indirect map to (the prime-order subgroup G1 of)
the curve BLS12-381 over a prime field Fp. As is known, this curve is a de
facto standard in today's real-world pairing-based cryptography. The
indifferentiable Wahby-Boneh hash function requires to extract two square
roots (i.e., to compute two exponentiations) in the field Fp. In
comparison, H extracts only one cubic root, which can be also expressed via
one exponentiation in Fp. And according to Section 1.1 of my other article
<https://eprint.iacr.org/2021/1082> the exponentiations for square and
cubic roots in Fp have short addition chains of about the same length.

I prepared a proof-of-concept implementation
<https://github.com/dishport/Indifferentiable-hashing-to-ordinary-elliptic-curves-of-j-0-with-the-cost-of-one-exponentiation>
in
Sage. You can also see a low-level implementation
<https://github.com/zhenfeizhang/indifferentiable-hashing> in Rust of my
colleague. The new hash is actually more efficient than the universal SW
(Shallue-van de Woestijne) hash. The colleague is not able to compare with
the Wahby-Boneh hash, because the latter is not yet implemented in arkworks
<https://github.com/arkworks-rs/curves>. He used this library as a base. At
the same time, H appears to be unimprovable, because it is highly unlikely
that there is a hash function to an elliptic curve without exponentiations
at all (even if it is supersingular).

Is there much interest in including the new hash function in the CFRG
hash-to-curve draft ?

Best regards,
Dimitri.