Cryptology ePrint Archive: Report 2021/1082

How to hash onto $\mathbb{G}_2$ and not to hash onto $\mathbb{G}_1$ for pairing-friendly curves

Dmitrii Koshelev

Abstract: Let $E_1$ be an ordinary pairing-friendly elliptic curve of embedding degree $k > 1$ over a finite field $\mathbb{F}_{\!q}$. Besides, let $E_2$ be a twist of $E_1$ of degree $d := \#\mathrm{Aut}(E_1)$ over the field $\mathbb{F}_{\!q^e}$, where $e := k/d \in \mathbb{N}$. As is customary, for a common prime divisor $r$ of the orders $N_1 := \#E_1(\mathbb{F}_{\!q})$ and $N_2 := \#E_2(\mathbb{F}_{\!q^e})$ denote by $\mathbb{G}_1 \subset E_1(\mathbb{F}_{\!q})$ and $\mathbb{G}_2 \hookrightarrow E_2(\mathbb{F}_{\!q^e})$ the eigenspaces of the Frobenius endomorphism on $E_1[r] \subset E_1(\mathbb{F}_{\!q^k})$, associated with the eigenvalues $1$, $q$ respectively. This short note explains how to hash onto $\mathbb{G}_2$ more efficiently and why we do not need to hash directly onto $\mathbb{G}_1$. In the first case, we significantly exploit the presence of clearing the cofactor $c_2 := N_2/r$. In the second one, on the contrary, clearing the cofactor $c_1 := N_1/r$ can be fully avoided. The fact is that optimal ate pairings $a\!: \mathbb{G}_2 \!\times\! \mathbb{G}_1 \to \mu_r \subset \mathbb{F}_{\!q^k}^*$ can be painlessly (unlike $E_2(\mathbb{F}_{\!q^e}) \!\times\! \mathbb{G}_1$) extended to $\mathbb{G}_2 \!\times\! E_1(\mathbb{F}_{\!q})$, at least in main pairing-based protocols. Throughout the text we mean hashing indifferentiable from a random oracle. At the moment, the curve BLS12-381 (with $e = 2$) is the most popular in practice. Earlier for this curve (and a number of others) the author constructed encodings $\mathbb{F}_{\!q}^2 \to E_1(\mathbb{F}_{\!q})$ and $\mathbb{F}_{\!q} \to E_2(\mathbb{F}_{\!q^2})$ computable in constant time of one exponentiation in $\mathbb{F}_{\!q}$. Combining the new ideas with these encodings, we obtain hash functions $\{0, 1\}^* \to E_1(\mathbb{F}_{\!q})$ and $\{0, 1\}^* \to \mathbb{G}_2$, which seem to be difficult to speed up even more. We also discuss how much performance gain they provide over hash functions that are actively applied in the industry.

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 27 Aug 2021

Contact author: dimitri koshelev at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20210827:165420 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]