DiSSECT: Distinguisher of Standard and Simulated Elliptic Curves via Traits

Abstract

It can be tricky to trust elliptic curves standardized in a non-transparent way. To rectify this, we propose a systematic methodology for analyzing curves and statistically comparing them to the expected values of a large number of generic curves with the aim of identifying any deviations in the standard curves.

For this purpose, we put together the largest publicly available database of standard curves. To identify unexpected properties of standard generation methods and curves, we simulate over 250 000 curves by mimicking the generation process of four standards. We compute 22 different properties of curves and analyze them with automated methods to pinpoint deviations in standard curves, pointing to possible weaknesses.

A A List of traits

The following is a list of all traits used for curve analysis. Each trait takes as an input an ordinary elliptic curve $E/\mathbb {F}_{p}:y^2=x^3+ax+b$ of order n.

Trait name	Input	Output
cofactor	int r	Tuple $(n_1, n_2)$ such that the group $E(\mathbb {F}_{p^r})$ is isomorphic to $\mathbb {Z}_{n_1}\times \mathbb {Z}_{n_2}$ and $n_1|n_2$ ($n_1=1$ for cyclic groups)
discriminant		The factorization of $D = t^2-4p = v^2d_K$, where $d_K$ is the discriminant of the endomorphism algebra of E
twist order	int r	The factorization of the cardinality of the quadratic twist of $E(\mathbb {F}_{p^r})$
kn fact.	int k	The factorizations of $kn+1$ , $kn-1$
torsion extension	prime l	$k_1,k_2,k_2/k_1$, where $k_1,k_2$ are the smallest integers satisfying $E[l]\cap E(\mathbb {F}_{p^{k_1}})\ne \emptyset$ and $E[l]\subseteq E(\mathbb {F}_{p^{k_2}})$
conductor	int r	The factorization of $D_r/D_1$, where $D_r = t_r^2-4p^{r}$ and $t_r$ is the trace of Frobenius of $E/\mathbb {F}_{p^r}$
embedding		The ratio $\phi (r)/e$, where $r\mid n$ is the order of the prime order subgroup and e is the multiplicative order of $q \pmod r$
class number		Upper bound [Dav80] and lower bound [Col85] on the class number of the endomorphism algebra of E
small prime order	prime l	The ratio $\phi (n)/m$ where m is the multiplicative order of $l \pmod n$
division pol.	prime l	The factorization of the l-th division polynomial
volcano	prime l	The depth and the degree of the l-volcano
isogeny extension	prime l	$i_1,i_2,i_2/i_1$ where $i_1,i_2$ are the smallest integers such that there exists a $\mathbb {F}_{p^{i_1}}$-rational l-isogeny and $l+1$ $\mathbb {F}_{p^{i_2}}$-rational l-isogenies from E
trace fact.	int r	A factorization of the trace of Frobenius of $E/\mathbb {F}_{p^r}$
isogeny neighbors	prime l	A number of roots of $\Phi _l(j(E),x)$ where $\Phi _l$ is the l-th modular polynomial
q torsion		Torsion order of $E'(\mathbb {Q})$ where $E'$ is given by the same equation $y^2=x^3+ax+b$
hamming x	int k	A number of points on E with the Hamming weight of the x-coordinate equal to k
square 4p-1		The factorization of square-free parts of $4p-1$ and $4n-1$ where n is the order of the generator point of E
pow distance		The distances of n to the nearest power of 2 and multiples of 32 and 64
multiples x	int k	The x-coordinate of $\frac{1}{k}G$
x962 inv.		The value $r = \frac{a^3}{b^2}$
brainpool overlap		$a_{160}-b_{-160}$ where $a_{160}$ are the $s-160$ rightmost bits of a and $b_{-160}$ are the $s-160$ leftmost bits of b
weierstrass		The parameters a, b