2
$\begingroup$

I am reading about Hyper Elliptic Curve Cryptography here: https://en.wikipedia.org/wiki/Imaginary_hyperelliptic_curve#The_divisor_and_the_Jacobian

In Elliptic Curve Cryptography we have the tangent-and-chord method to find for instance the 3rd point when adding $ P + Q $ points on the Elliptic Curve. In the above wikipedia link the author calculates Divisors: $ D1 $ and $ D2 $ and then via Cantor's algorithm they calculate the Divisor $ D = D1 + D2 $. Any of the Divisors in Mumford's analysis consists of 2 points. So, $ D1 $ consists of 2 points, $ D2 $ consists of 2 points and $ D $ consists of 2 points. My question is very simple: Is the $ D = D1 + D2 $ of HECC the equivalent of the $ P + Q $ tangent-and-chord method as occurs in ECC in order to calculate the 3rd point? Do I miss something here?

$\endgroup$
5
  • 2
    $\begingroup$ In one sense it is similar as both are binary operations defining the respective groups. In another sense they aren't similar in terms of the procedure of the operation. $\endgroup$
    – madhurkant
    Commented May 15 at 2:40
  • $\begingroup$ From the 2 points on the hyperelliptic curve I get in D, which one I keep in order to do the calculations in HECDLP? $\endgroup$
    – someone
    Commented May 15 at 10:39
  • 1
    $\begingroup$ @someome I didn't get you. What calculations? $\endgroup$
    – madhurkant
    Commented May 15 at 13:35
  • $\begingroup$ There are algorithms which someone should use in order to calculate the D = D1 + D2. I am referring to the E.Cantor's algorithm. My question is the following, when I apply E.Cantor's algorithm to calculate D, I get two points in Mumford's representation. Which point do I use? Am I losing something here? $\endgroup$
    – someone
    Commented May 15 at 14:42
  • 1
    $\begingroup$ You should keep both the point as divisor is defined by those points. Additionally points have no role in calculations of divisors. $\endgroup$
    – madhurkant
    Commented May 15 at 16:12

1 Answer 1

1
+50
$\begingroup$

Any of the Divisors in Mumford's analysis consists of 2 points

No, this is true only for curves of genus 2. For curves of genus 3 and more it can be both true and false. This is because the number of cordinate represented by a Divisor depends upon the degree of first polynomial, $u(x)$, of Mumford representation.

For example for a genus 4 curve one can construct a Divisor whose first polynomial would be of degree 3 and thus the Divisor would represent three coordinates.

However, the maximum number of points a divisor can represent would be equal to genus of the curve.

Let $C$ be an imaginary hyper elliptic curve over $F_{103}$ of genus 4.

$C: y^2 = x^9 - 30x^7+273x^5 -820x^3+576x$

Over finite field it would become:

$C: y^2 = x^9 + 73x^7+67x^5+4x^3+61x$

The divisor of the curve $D$ can be constructed in such a way that it would represent three coordinates.

The following points are valid points on $C $:

$(1, 0),(2,0),(3,0),(4,0),(6,25)$

I can choose to construct a divisor that can represent three points as follows:

$D = (x^3+94x^2+20x+91, 18x^2+85x) $

The divisor represent the points $(1,0),(2,0),(6,25) $

Is the $D = D1 + D2$ of HECC the equivalent of the $P + Q $ tangent-and-chord method as occurs in ECC in order to calculate the 3rd point?

As I pointed in comment it depends on in which sense you are asking?

They are same as far as defining the group law for curves. For elliptic curve there exist an isomorphic map from the Jacobian of curve to the point (see Abel-Jacobi theorem) thus adding divisor is no different from adding points on elliptic curve. But the map is not isomorphic over curves with genus 2 or higher.

In cryptography sense yes, both of them are same, but in a mathematical sense no, they are not.

I get two points in Mumford's representation. Which point do I use? Am I losing something here?

Again it depends on what you are trying to achieve? Since divisors are formal sum of points one point can be part of many divisors.

Speaking mathematically, you should keep all the points. But speaking cryptographically you should not be keeping all the points. Because space is an issue in cryptography. The lower key size along with the a fair bits of security is considered good in cryptography.

If you are providing a 128 bit security with 512 bit key size there is a problem because we have more efficient schemes.

You can always define divisors with two points or even with one point (But I doubt if they would make any sense).

I cannot define a standard but can suggest you that stick with divisors that represent two coordinates and store both of them.

$\endgroup$

Your Answer

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

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