FourQ

The currently best known discrete logarithm attack is the generic Pollard's rho algorithm, requiring about ${\displaystyle 2^{122.5}}$ group operations on average. Therefore, it typically belongs to the 128 bit security level.

In order to prevent timing attacks, all group operations are done in constant time, i.e. without disclosing information about key material.[1]

Most cryptographic primitives, and most notably ECDH, require fast computation of scalar multiplication, i.e. ${\displaystyle [k]P}$ for a point ${\displaystyle P}$ on the curve and an integer ${\displaystyle k}$, which is usually thought as distributed uniformly at random over ${\displaystyle \{0,\ldots ,N-1\}}$.

Since we look at a prime order cyclic subgroup, one can write scalars ${\displaystyle \lambda _{\psi },\lambda _{\phi }}$ such that ${\displaystyle \psi (P)=[\lambda _{\psi }]P}$ and ${\displaystyle \phi (P)=[\lambda _{\phi }]P}$ for every point ${\displaystyle P}$ in the N-torsion subgroup.

Hence, for a given ${\displaystyle k}$ we may write

${\displaystyle k=a_{1}+a_{2}\lambda _{\phi }+a_{3}\lambda _{\psi }+a_{4}\lambda _{\phi }\lambda _{\psi }{\pmod {N}}}$

If we find small ${\displaystyle a_{i}}$, we may compute ${\displaystyle [k]P}$ quickly by utilizing the implied equation

${\displaystyle [k]P=[a_{1}]P+[a_{2}]\phi (P)+[a_{3}]\psi (P)+[a_{4}]\phi (\psi (P))}$

Babai rounding technique[7] is used to find small ${\displaystyle a_{i}}$. For FourQ it turns that one can guarantee an efficiently computable solution with ${\displaystyle a_{i}<2^{64}}$.

Moreover, as the characteristic of the field is a Mersenne prime, modulations can be carried efficiently.

Both properties (four dimensional decomposition and Mersenne prime characteristic), alongside usage of fast multiplication formulae (extended twisted Edwards coordinates), make FourQ the currently fastest elliptic curve for the 128 bit security level.