0
$\begingroup$
F = GF(next_primt(2^80))
x = F['x'].gen()
f = x^5 + x^3 + 1
H = HyperellipticCurve(f, 0)
J = H.jacobian()(F)
P = H.lift_x(F(3))
D = J(P)             # divisor

Is D the divisor? And can it be multiplied by a random integer to generate a secure parameter like the one used with elliptic curves?

And if this is correct, why is ECC time = 13.2 milliseconds, but HECC time = 185 milliseconds?

$\endgroup$
  • 2
    $\begingroup$ This looks like a code of a high-level language implementing group operation on hyperelliptic curve. It would be reasonable to state the missing parts of the question. Most likely, you need a textbook to learn genus-2 curves, group operation over pairs of points on such a curve, divisor definition. $\endgroup$ – Vadym Fedyukovych Jun 7 '17 at 7:42
2
$\begingroup$

Is D the divisor? And can it be multiplied by a random integer to generate a secure parameter like the one used with elliptic curves?

Well...you're asking if the discrete logarithm problem can apply to hyperelliptic curves. The answer is yes. But it's a bit more complicated than for the elliptic curve case. This is a great introduction. I sketch out some details below if you want to take the plunge.


The problem is more complicated to formulate for hyperelliptic curves than for elliptic curves. This is because there is no natural group structure for points on the hyperelliptic curves like there are for elliptic curves. (Note that elliptic curves are a special case of hyperelliptic curves, with genus $g=1$.) However, you can formulate the discrete log problem over a group associated with hyperelliptic curve, called the Jacobian group. You have Jacobians in your Sage code, for example.

To understand Jacobians, you have to understand divisors. A divisor is a formal sum over points on the curve: $D := \sum_{P \in \mathcal{C}} c_P [P]$, where $c_P \in \mathbb{Z}$ and the number of nonzero $c_P$ is finite. By "formal sum", I mean bookkeeping. For example, if $P,Q,R$ are points on a curve, then a divisor may be $D = 2[P] + 4[Q] - 7[R]$. That's it.

You can also have divisors over functions. If a zero is a point where a function vanishes and a pole is a point where a function is undefined, then the divisor of a function $div(f) $ is a way of bookkeeping the relative number of zeroes and poles. For example, if $f(x) = \frac{x-a}{x-b}$, then you have a zero and a pole, and could write the divisor as $D = 1[a] - 1[b]$. (Notice poles are negative in the sum.) A divisor is called a principal divisor if it's equal to the divisor of a rational function. The set of principal divisors $Prin(\mathcal{C})$ forms a group.

The degree of a divisor is the sum of the divisor's coefficients. So in the above example, the degree is $1 - 1 = 0$. The set of divisors of degree zero is important and is called $Div^0(\mathcal{C})$. Since rational functions have as many zeroes as poles, they all have degree zero, which means $Prin(\mathcal{C}) \subset Div^0(\mathcal{C})$.

Finally, we can define the Jacobian group as the quotient group $Div^0(\mathcal{C}) /Prin(\mathcal{C})$. You can "add" two divisors using Cantor's theorem. Now that we have elements and addition, we can talk about the hyperelliptic curve discrete log problem:

Given a hyperelliptic curve $\mathcal{C}$ of genus $g$, two divisors $D_1$ and $D_2$, both in the Jacobian group, with $D_2$ in the subgroup generated by $D_1$, and the order $q$ of $D_1$, find the scalar $s$ (modulo $q$) such that $D_2 = s\cdot D_1$.

It's harder to visualize, but the Wikipedia article has an example. It looks like you are using some Sage code. I haven't used Sage for this, but this documentation talks about how to do "divisor addition" (using Cantor's theorem on the Mumford representation of divisors). They reference another great introduction.

|improve this answer|||||
$\endgroup$

Your Answer

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

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