CuatroQ

El ataque de logaritmo discreto más conocido actualmente es el algoritmo rho genérico de Pollard , que requiere aproximadamente${\displaystyle 2^{122.5}}$operaciones de grupo en promedio. Por lo tanto, normalmente pertenece al nivel de seguridad de 128 bits.

Para evitar ataques de temporización , todas las operaciones de grupo se realizan en tiempo constante, es decir, sin revelar información sobre el material clave. ^{[ 1 ]}

La mayoría de las primitivas criptográficas, y en particular ECDH , requieren un cálculo rápido de la multiplicación escalar, es decir${\displaystyle [k]P}$por un punto${\displaystyle P}$en la curva y un número entero${\displaystyle k}$, que generalmente se considera distribuida uniformemente al azar sobre${\displaystyle \{0,\ldots ,N-1\}}$.

Dado que observamos un subgrupo cíclico de orden primo , se pueden escribir escalares${\displaystyle \lambda _ {\psi},\lambda _ {\phi}}$de tal manera que${\displaystyle \psi (P)=[\lambda _ {\psi }]P}$y${\displaystyle \phi (P)=[\lambda _ {\phi }]P}$por cada punto${\displaystyle P}$en el subgrupo de torsión N.

Por lo tanto, para un dado${\displaystyle k}$podemos escribir

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

Si encontramos pequeños${\displaystyle a_{i}}$, podemos calcular${\displaystyle [k]P}$rápidamente utilizando la ecuación implícita

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

La técnica de redondeo de Babai ^{[ 7 ]} se utiliza para encontrar pequeños${\displaystyle a_{i}}$Para FourQ resulta que se puede garantizar una solución computable de manera eficiente con${\displaystyle a_{i}<2^{64}}$.

Además, como la característica del campo es un número primo de Mersenne , las modulaciones se pueden transportar de manera eficiente.

Ambas propiedades (descomposición tetradimensional y característica prima de Mersenne), junto con el uso de fórmulas de multiplicación rápidas ( coordenadas de Edwards retorcidas extendidas ), hacen de FourQ la curva elíptica más rápida actualmente para el nivel de seguridad de 128 bits.