1
$\begingroup$

  1. Any hyperelliptic curve having base field characteristic dividing group order?

  2. A subgroup of order equal to the basefield characteristic, a large prime?

  3. Having hard DLP in that subgroup?

  4. Having pairing?

  5. New elliptic-hyperelliptic cycle anyone?

SNARKs were introduced with QAP "intermediate" language to define computer-science and real-file problems as systems of equations "with just a single multiplication", widely known thanx ZCash. Recursive SNARKs suggest verifying "previous" snark-proof(s) as a part of the current problem instance, that could be illustrated with proving a correct transaction and "good" previous blockchain state resulting in good current state.

"A cycle of curves" like MNT4-MNT6 is the only known "complete" solution implementing groth16 SNARK. There is a good reason for no single-curve recursive snarks.

Group order is roughly twice-bitlength (a square of) the field a genus-2 hyperelliptic curve is defined over. It is not "slightly different" from the field characteristic anymore it was with elliptic curves. Potentially there is a rich structure hopefully admitting recursion with a single curve, or alternative cycles.

Hyperelliptic curves are not so popular. Group element is a pair of points on a genus-2 curve, so you need to handle "divisors" rather than points.

There was a project 2019-2020 that resulted in a manager claimed me to discover an MNT5 curve, made public on ZCash forum. That team did "proofs for knowledge" and "recurrent proofs" in their papers in a Springer journal and an IEEE conference.

Update

The last point is the core question, the reason, and potentially a new idea.

MNT4-MNT6 elliptic curves pair is the only known "2-cycle": base field characteristic of the first equal to group order of the second, and vice versa. Informally, "splitting" the first property into two curves.

It seems feasible to have group order (Jacobian) to be a product of two primes, the base field characteristic $q$ and $(q+2)$ for a genus-2 (but not for elliptic) curve. At least, this is ok with the Hasse-Weil interval. This hopefully would mean avoiding "the largest prime divisor of the order of the Jacobian, is equal to the base field characteristic" (the wikipedia page suggested by Daniel S, thanx!) pre-condition of the known attack on anomalous curves. If confirmed, this might mean a "1-curve cycle" for zk-SNARKs.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
+50
$\begingroup$

  1. Yes, these are known as anomalous hyperelliptic curves.

  2. Yes, this follows from Cauchy's theorem.

  3. No, as noted in the first wikipedia article. With anomalous elliptic curves, there is a simple mapping to the additive group which renders the discrete logarithm problem tractable.

  4. As such no secure pairing can exist.

  5. Per 3 and 4 such a cycle would be a bad idea.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you Daniel. May I kindly ask to elaborate on (5) please? Why bad? It was a target of a research project, and the reason for this question. "A 2-cycle of curves" would mean two curves having base field characteristic of the first dividing (equal) group order of the second, and vice versa, best illustrated with MNT4-MNT6. In other words, "splitting" (1) into two curves. $\endgroup$
    – Vadym Fedyukovych
    Commented Oct 2, 2023 at 15:28
  • $\begingroup$ Citing "anomalous" wikipedia page, "We also have a problem, if $p$, the largest prime divisor of the order of the Jacobian, is equal to the characteristic of ${F} _{q}$. Should one expect a prime divisor of the Jacobian (group order) larger that base field feasible on genus-2? Any explicit reference for this mapping/attack please? $\endgroup$
    – Vadym Fedyukovych
    Commented Oct 2, 2023 at 17:07
  • $\begingroup$ @VadymFedyukovych: Reference is Ruck's 1999 Math. Comp. paper $\endgroup$
    – Daniel S
    Commented Oct 2, 2023 at 17:34
  • $\begingroup$ Apologies, I misunderstood your question 5. I shall think on this. $\endgroup$
    – Daniel S
    Commented Oct 2, 2023 at 17:35

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.