Compute key size in Hyperelliptic Curve Cryptography

PanosDgs

4/8/24, 5:40 PM

I am trying to implement a basic Diffie-Hellman key exchange using ECC and HECC of genus 2 and 3 and compare them. However, I am a bit confused about the concept of key size in HECC.

In ECC, from my understanding so far and considering I am new to the field, the private key size is basically the bit size of the prime that is used to define the prime finite field, where the elliptic curve is defined.

In HECC, instead of a point in the Curve, a Divisor class is used to define group elements. In my implementation, I have defined divisors in the Mumford representation, which is basically 2 polynomials u, v.

Based on this paper: https://www.researchgate.net/publication/305878169_A_Study_of_Hyperelliptic_Curves_in_Cryptography one can see that the key size drops while the genus g increases. However, I cannot actually understand what we define as a key size in HECC. Logically, the coefficients of the polynomials u, v define the private key, so the sum of their bit sizes should give us the key size. However, even if we choose a smaller finite field in HECC, because the degree of the polynomials u, v increases as the genus increases, that should not mean that the key size increases as well?

So if I want to compare ECC, HECC genus 2 and HECC genus 3 with a security level of 2048 for example, what is the bit size of the prime finite field that I should choose and what will be the actual key size in each implementation?

114

0 + 2

elliptic-curves

key-exchange

diffie-hellman

Sam Jaques

4/10/24, 11:11 AM

In, ECC, if you have $E[\mathbb{F}_p]$ for a prime $p$, then the order of the public generator $P$ is some *other* prime $q$. Your private key is $sP$ for a secret $s\in \mathbb{Z}/q\mathbb{Z}$, so you can just store $s$, not $sP\in E[\mathbb{F}_p]$. With ECC the bit size of $q$ and $p$ is roughly the same since we know the order of the elliptic curve group is in $p\pm O(\sqrt{p})$. If you take that logic to hyperelliptic curves, does that help?

PanosDgs

4/23/24, 10:54 AM

Thanks for the reply. I deleted my previous response since I did not answer properly. Similar to ECC, in HECC the secret s is stored that is used to scalarly multiply the public generator P, where P now instead of a point in the curve, is a divisor. However in HECC of genus 2 for example the order of the Group q is close to p^2, so the key size increases based on the genus of the curve. So I cannot understand how the key size decreases while the genus increases.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Compute key size in Hyperelliptic Curve Cryptography

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.