Cryptology ePrint Archive: Report 2021/1082

Some remarks on how to hash faster onto elliptic curves

Dmitrii Koshelev

Abstract: In this article we propose three optimizations of indifferentiable hashing onto (prime order subgroups of) ordinary elliptic curves over finite fields $\mathbb{F}_{\!q}$. One of them is dedicated to elliptic curves $E$ provided that $q \equiv 11 \ (\mathrm{mod} \ 12)$. The other two optimizations take place respectively for the subgroups $\mathbb{G}_1$, $\mathbb{G}_2$ of some pairing-friendly curves. The performance gain comes from the smaller number of required exponentiations in $\mathbb{F}_{\!q}$ for hashing to $E(\mathbb{F}_{\!q})$, $\mathbb{G}_2$ (resp. from the absence of necessity to hash directly onto $\mathbb{G}_1$). In particular, our results affect the pairing-friendly curve BLS12-381 (the most popular in practice at the moment) and the (unique) French curve FRP256v1 as well as almost all Russian standardized curves and a few ones from the draft NIST SP 800-186.

Category / Keywords: implementation / BLS12 family of pairing-friendly curves, clearing cofactor, indifferentiable hashing to elliptic curves, optimal ate pairings

Date: received 23 Aug 2021, last revised 2 Dec 2021

Contact author: dimitri koshelev at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20211202:132507 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]