6
$\begingroup$

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.

$\endgroup$
3
  • $\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, 2022 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, 2022 at 9:02
  • $\begingroup$ Please let me double-check the target (multiplicative) group order and a hard DLP. "Recursion" might be a killer application: crypto.stackexchange.com/questions/108118/… $\endgroup$ Sep 28 at 12:17

1 Answer 1

2
$\begingroup$

It would be interesting to see if the proposed method results in a hyperelliptic curve group admitting a small ρ-value. To put this in context, BBCES11 mentions that the best-achieved ρ-value for pairing-friendly ordinary genus 2 curves with arbitrarily prescribed embedding degree k is 4, and specific examples of ρ-value between 2 and 4. It is interesting to see what the ρ-value of genus 2 curves would be achieved in the proposed research because that would determine how competitive they are with the BLS elliptic curves people use.

While I'm skeptical about the wide adoption of hyperelliptic curve cryptography among cryptographers anytime soon, mainly because potential attacks have been studied to a lesser extent compared to elliptic curves. However, confidence will be built, only if these systems are deployed in the real world. I am enthusiastic about hyperelliptic curve cryptography such as trace-zero sub-variety of the jacobian of genus 2 curves and their real-world implementation.

In particular, we at the research group of Web3 foundation are open to experience with more efficient emerging mathematical solutions and especially those which result in speeding up our zero-knowledge and succinct proof solutions. This includes systems which rely on hyperelliptic crypto for its security to demonstrate hyperelliptic cryptography in practice and encourage other researchers to evaluate their security.

In short, the proposed research seems to be of interest from many angles.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.