Finite Fields and security level in HECC (Hyper Elliptic Curve Cryptography)

Question

How to calculate the security level for HECC (Hyper Elliptic Curve Cryptography) genus = 2, 3, for a Finite Field of 128-bits or 256-bits or 512-bits, by following the below rationale of the ECC here: Key size and finite fields in ECC (References) ? Do I follow the same logic?

Answer 1

I was looking at the question from couple of days but refrain from answering for the reasons, as in Para 3. I wouldn’t be able to provide a practical answer but would provide a theoretical one.

do I follow the same logic?

Absolutely yes, that is how security is calculated. You calculate it by $\log_2$ of the expected cost in bit operations of the best attack.

But the problem arises with best operation in the following way:

The security story for HECC is complex, precisely and honestly speaking has not been researched much. Literature about Hyper Elliptic Curves is not sufficient. The way ECC (Elliptic Curve Cryptography) has been investigated into over the past years has produced a great amount of literature but for HECC there is very less. Most of the papers refers to “Tata Lectures on Theta II” a book by D. Mumford.

The problem with answering question is security in cryptography depends on the solution to a problem. In case of ECC it is ECDLP and in HECC it is HCDLP. A basic construction of HCDLP:

For an hyperelliptic curve H over a finite field P and given the reduced divisors $D_1,D_2 \in J(P)$ find the smallest positive integer $z \in \mathbb{Z}$ such that $D_2 = zD_1$ ( $J$ is jacobian of hyper elliptic curve over $P$)

Curves with genus 1

Since HECs (Hyper Elliptic Curves) are generalised form of ECs (Elliptic Curves) this curve would simply be an elliptic curve. We already know that to achieve a $112$ but security the ECC key size is about $224$ bits.

Curves with genus 2

For these curves I am not aware of using index-calculus. HECs of this genus have been proposed for cryptographic use. Generic1271 is such a curve. There is a paper available here for genus 2 curve security.

The results are that for $254$ bit prime order of jacobian the security achieved was approx $126$ bits (assuming NIST P-256) using speed up of pollard-rho. This was already expected as index-calculus was not available, or if it was it could have nothing better than pollard-rho itself (see Gaudry),to use so we were wound with square-root algorithms.

This is still not the complete story. You need to be careful before using genus 2 curves. In this paper the researcher warned against using even degree finite field as they allow Weil-descent attack allowing to transform HCDLP over genus 2 curve to a genus 8 curve where it would be less secure. Also see example 56 here (page 31-32) to understand how HCDLP on few genus 2 HECs can be reduced to DLP in an extensions field.

Curves with genus 3, 4 and beyond

These curves allow the use of index-calculus method combined with few speed ups for solving HCDLP. The speed up methods can be found here.

Conclusion

In short, since there are no defined standards for choosing secure HECs there exist no defined notion of security for the.