Security level difference: supersingular vs non-singular elliptic curve

Question

In some evaluation of elliptic curve cryptography, it says that for same security level

In supersingular curve over $F_p$ with group of prime order $q$, p=512, q=160 bits

In non-singular curve , p=160, q=160 bits.

How to know such difference?

Answer 1

The reason why to achieve the same security level a supersingular elliptic curve requires to have a greater field size is due to the MOV attack.

In the MOV attack, for a curve $E(\mathbb{F}_p)$ you use a Weil Pairing to move the discrete logarithm from $E(\mathbb{F}_p)$ to $\mathbb{F}_{p^k}$ where $k$ is called the embedding degree of the curve. The discrete logarithm in multiplicative groups is easier to compute due to Index Calculus methods (e.g. the NFS for logarithms).

In the MOV paper the authors showed the value of $k$ for supersingular curve must be $k\le6$ so you should choose your original field accordingly in order to land in a cryptographically strong $\mathbb{F}_{p^k}$ after the application of the Weil's pairing.

To address the question specific parameters, supersingular curves over fields with characteristic not equal to $2$ or $3$ must have embedding degree $k\leq3$.

Assuming the more conservative option is selected (i.e. $k=3$) then with your parameters $\log(q)=160$, $\log(p)=512$ an attacker applying the MOV attack will need to solve a DL in $\mathbb{F_{p^3}}$, whose order have size $512*3=1536$ bit.

Thus in this settings the curve's generator assumed solving a DL over a $1536$ bit group as complex as solving an ECDLP over $160$ bit group (unless the curve had $k=2$ in which case DL would have been over a $1024$ bit group).

The values of $k$ for general curves are, in general, much larger so that the MOV attack is less efficient than the ECDLP computation (however it is a value that should be checked when generating new curves). SafeCurves have a list of embedding degree of evaluated curves.

Edited to address the edit in the question