Evidence of the security of the elliptic curve over koalabear prime, and search algorithm for elliptic curves based on septic extensions of prime fields. This is forked from https://github.com/toposware/cheetah_evidence
This repository contains a search algorithm to generate curves over septic extensions of prime fields. It considers regular attacks on generic elliptic curve constructions (Pollard-Rho attack, twist attack, MOV attack, ...). The search algorithm aims at finding curves susceptible to provide close to 102 bits of security with the known state-of-the-art attacks on these special elliptic curves.
As a consequence, the search algorithm (in particular the portion dealing with the cover and decomposition attacks) should be modified before targeting other security levels (128 bits or 192 bits).
NOTE: Experimental results have shown limitations in Sagemath factorization algorithms for computing the embedded degree of some curve twists. Hence, in order to prevent running time clogging, only Pollard-Rho security against the twists is being checked. Making sure that their embedding degree is also sufficiently large should be done on the potential candidates the search algorithm may output.
A result of this search algorithm is y^2 = x^3 + 3u *x - 3, an elliptic-curve defined over a septic extension using polynomial u^7 + 2 * u - 8 over the prime field of charateristic
p = 2^31 - 2^24 + 1. To verify its security level, one can run the verify.sage script.
The chosen curve is the first candidate displayed from the sextic_search.sage script when running in sequential mode (argument --sequential).
NOTE: Running in sequential mode guarantees to have deterministic ordering of the output, but at the cost of a much slower search. To benefit from multithreading, one can remove the --sequential argument, allowing Sage to use as many parallel threads as possible.
To find a prime-order elliptic curve on a field extension GF(2^31 - 2^24 + 1)^7:
sage sextic_search.sage 2130706433To perform security checks on the Cheetah curve (you may need to install termcolor):
sage verify.sageA prototype implementation of the curve in Rust is available at https://github.com/Toposware/cheetah. The library features constant-time field and group arithmetic, and does not rely on the Rust standard library, allowing it to be compiled to WebAssembly.
Licensed under either of
- Apache License, Version 2.0, (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)
at your option.