Any SuperSingular curve or similar with Fp = Fq which is not badly broken unless big field orders are used?

CPereez19

6/8/24, 7:37 AM

AFAIK, SuperSingular curves appear to be broken by MOV:

A. J. Menezes, T. Okamoto and S. A. Vanstone, "Reducing elliptic curve logarithms to logarithms in a finite field," in IEEE Transactions on Information Theory, vol. 39, no. 5, pp. 1639-1646, Sept. 1993, doi: 10.1109/18.259647.

I recall that with a big order chosen for the field ie. 1000-2000 bits, it was possible to have secure-enough curves. But the size of the fields makes the curves not appealing for software implementations that require fast primitives.

I know there are many types of SuperSingular curves. And that not all of them imply $Fq=Fp$. But I'd like to know if there's any type of curve that indeed has $Fp = Fq$ and at the same time, is not vulnerable to MOV for $|Fp| = |Fq| \approx 2^{256}$. If not, it would also be nice to know what's the closest not-broken primitive.

To add some context about the question, in latest Folding Scheme applications like Nova by Setty et.al among others, this curves would eliminate the need of having a cycle of curves to amortize the cost of wrong field arithmetic inside circuits in between folding rounds. And, instead, with a single curve we could end with one single IVC proof to perform at the end of the folding process.

1 + 0

elliptic-curves

pairings

snarks

Score:2

Crypto

Daniel S

6/8/24, 8:19 AM

If I interpret your question correctly, you want to know if there is a curve over a prime field $\mathbb F_p$ such that the order of the curve group is itself $p$. Such curves are called anomalous curves and they are even weaker than supersingular curves. The works of Semaev, Smart, Sato and Araki give attacks that work in linear time (as opposed to the merely subexponential MOV attack).

+ 0

Elon Musk

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

EN: Any SuperSingular curve or similar with Fp = Fq which is not badly broken unless big field orders are used?

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.