Let $\mathbb{G}_1$, $\mathbb{G}_2$, $\mathbb{G}_T$ stand for three groups of the same large prime order $r$. I invented a pairing $e\!: \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$ (with embedding degree $k \in \mathbb{N}$) such that $$ \mathbb{G}_1 \subset J(\mathbb{F}_p), \qquad \mathbb{G}_2 \subset E(\mathbb{F}_{p^n}), \qquad \mathbb{G}_T \subset \mathbb{F}_{p^k}^*, $$ where $J$ is the Jacobian of some (hyperelliptic) curve of genus $2$ over a finite field $\mathbb{F}_p$ (of large characteristic) and $E$ is an elliptic curve over some extension $\mathbb{F}_{p^n}$.

For comparison, let's consider any other elliptic pairing $e^\prime\!: \mathbb{G}_1^\prime \times \mathbb{G}_2^\prime \to \mathbb{G}_T^\prime$ (with embedding degree $d \in \mathbb{N}$) such that $$ \mathbb{G}_1^\prime \subset E_1(\mathbb{F}_{q}), \qquad \mathbb{G}_2^\prime \subset E_2(\mathbb{F}_{q^m}), \qquad \mathbb{G}_T^\prime \subset \mathbb{F}_{q^d}^*, $$ where $E_1$, $E_2$ are some elliptic curves over finite fields $\mathbb{F}_{q}$, $\mathbb{F}_{q^m}$, respectively ($p$ is not necessarily the characteristic of $\mathbb{F}_q$). Here $\mathbb{G}_1^\prime$, $\mathbb{G}_2^\prime$, $\mathbb{G}_T^\prime$ are three more groups of the same large prime order $r^\prime$. Of course, I suppose that $p^2 \approx q$, and $p^k \approx q^d$, and $r \approx r^\prime$. However, it turns out that $p^n \ll q^m$ for my pairing. In other words, the arithmetic in $\mathbb{G}_2$ is more efficient than in $\mathbb{G}_2^\prime$. In turn, it is recognized that the arithmetic of $J(\mathbb{F}_{p})$ (i.e., $\mathbb{G}_1$) is comparable in complexity to that of $E_1(\mathbb{F}_q)$ (i.e., $\mathbb{G}_1^\prime$). Clearly, the same is true in general for the pair $\mathbb{G}_T$, $\mathbb{G}_T^\prime$.

What if I show that the new semi-hyperelliptic pairing $e$ can be evaluated faster than $e^\prime$ ? Will this result be groundbreaking or not ? If so, has $e$ a chance to be used in real-world cryptography ? I ask you, because for all its long time of existence, hyperelliptic cryptography has not found concrete applications in practice. Although certain earlier articles concluded that, with the proper choice of a genus $2$ curve, the group law on its Jacobian can be (slightly) cheaper than on elliptic curves with the same security level.

I would be very grateful to you for any comments.

  • $\begingroup$ More precisely, the advantage of $\mathbb{G}_2$ over $\mathbb{G}_2^\prime$ is the following: $\log_2(p^n)/\log_2(q^m) \approx n/(2m) \approx 3/4$. $\endgroup$ Aug 5 at 8:28
  • $\begingroup$ And the value $\rho := 2\log_2(p)/\log_2(r)$ can be bounded as follows: $2 < \rho < 3$. It is not small enough in comparison with elliptic pairings. Maybe, in the future there will be pairing-friendly genus $2$ curves with $1 \leqslant \rho \leqslant 2$. Such $\rho$-values are currently used in practice. $\endgroup$ Aug 5 at 9:02


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.