TL;DR: The two elliptic curves implementation can be found here.
We aim to construct an elliptic curve satisfying the following criteria:
To achieve the target security level, we adopt an approach similar to EcGFp5. Specifically, we define the extension field over
We select the polynomial because:
The following Sage script verifies that the previous claims about are true:
To check whether an element is a quadratic residue, we use Euler's criterion, raising to the power .
This exponentiation can be optimized by noting that:
which follows from the cyclotomic polynomial decomposition.
To compute to the power over , we need to efficiently compute the first and second Frobenius operator. Moreover, notice that when this exponentation is done, we get an element such that and this can only happen when ; so the second exponentiation is over instead.
Exponentiation by is done by observing that:
and using repeated squaring.
As we have shown in the previous section, we must be able compute the first and second Frobenius operator over an element in efficiently. A naive implementation would take -operations, but we will do it much better.
Write as , with . Then, we can compute the frobenius operators as follows:
with and . Hence, assuming the precomputation of for , we can compute and by four multiplications each.
Proof:
On the one hand, using Fermat's little theorem we have that .
On the other hand, notice and therefore , where .
Using the previous observations, we have:
which can be computed using a few multiplications.
Similarly, notice and therefore , where .
TODO: Develop on generating a subgroup of order .
Playing a little bit, we can refine exponentiation by :
where is viewed as a -element.
To compute the square root of an element we will use in our favour the fact that to check its quadratic residuosity we have to raise it to .
After a bit of algebra, we get the following identity:
so we can compute the squaring by:
Found by Thomas Pornin, the EcGFp5 curve is defined by the equation:
with constants:
and order for the -bit prime:
Since is odd, the points belonging to the subgroup of order are precisely the -torsion of the curve.
We follow the RFC 9380: Hashing to Elliptic Curves to get a deterministic mapping.
We choose the short Weierstrass equation:
because assuming that and that the cost of addition, subtraction, multiplication and division over the field is the same (something true in SNARK settings), point addition costs field operations and point doubling costs field operations.
Setting also restricts to be from the extension field, rather from the prime field; otherwise the curve could not be of primer order.
Since has no impact in group operations, we perform a linear search:
The first elliptic curve found was:
with a -bit prime order:
The name for this curve was chosen to be EcMasFp5 (Elliptic Curve for Maximum Aggregation Speed over ).
Thanks to Robin Salen for help and discussion.
We follow the criteria in Safe Curves.
More details are given below.
Since the extension field is the same as the one in EcGFp5, we inherit by default its security. In particular, this field selection approximately achieves a -bit security level, well beyond the target one.
We use the following code to find the embedding degree :
Finding that , as large as it can possibly be, avoiding MOV-type attacks.
The CM Discriminant was found to be a -bit integer:
The number factorizes as:
It is the same as the one for EcFp5 with the exception that this one does not need to clean the cofactor.