Criptografía de traza cero

Métodos criptográficos construidos utilizando variedades de traza cero de geometría algebraica

En 1998, Gerhard Frey propuso por primera vez el uso de variedades de traza cero con fines criptográficos. Estas variedades son subgrupos del grupo de clases divisoras en una curva hiperelíptica de género bajo definida sobre un cuerpo finito . Estos grupos se pueden utilizar para establecer criptografía asimétrica utilizando el problema del logaritmo discreto como primitivo criptográfico.

Las variedades de traza cero tienen un mejor rendimiento de multiplicación escalar que las curvas elípticas. Esto permite realizar cálculos aritméticos rápidos en estos grupos, lo que puede acelerar los cálculos con un factor 3 en comparación con las curvas elípticas y, por lo tanto, acelerar el criptosistema.

Otra ventaja es que, en el caso de grupos de tamaño criptográficamente relevante, el orden del grupo se puede calcular simplemente utilizando el polinomio característico del endomorfismo de Frobenius. Esto no sucede, por ejemplo, en la criptografía de curva elíptica , cuando el grupo de puntos de una curva elíptica sobre un cuerpo primo se utiliza con fines criptográficos.

Sin embargo, para representar un elemento de la variedad de traza cero se necesitan más bits en comparación con los elementos de curvas elípticas o hiperelípticas. Otra desventaja es el hecho de que es posible reducir la seguridad de la TZV en ^{1/6 de la longitud} _de ^bits mediante un ataque de cobertura.

Antecedentes matemáticos

Una curva hiperelíptica C de género g sobre un cuerpo primo donde q = p ⁿ ( p primo) de característica impar se define como ${\displaystyle \mathbb {F} _{q}}$

${\displaystyle C:~y^{2}+h(x)y=f(x),}$

donde f mónica, deg( f ) = 2 g  + 1 y deg( h ) ≤ g. La curva tiene al menos un punto de Weierstraß -racional. ${\displaystyle \mathbb {F} _{q}}$

La variedad jacobiana de C es para toda extensión finita isomorfa al grupo de clases ideal . Con la representación de Mumford es posible representar los elementos de con un par de polinomios [u, v] , donde u , v ∈ . ${\displaystyle J_{C}(\mathbb {F} _{q^{n}})}$ ${\displaystyle \mathbb {F} _{q^{n}}}$ ${\displaystyle \operatorname {Cl} (C/\mathbb {F} _{q^{n}})}$ ${\displaystyle J_{C}(\mathbb {F} _{q^{n}})}$ ${\displaystyle \mathbb {F} _{q^{n}}[x]}$

El endomorfismo de Frobenius σ se utiliza sobre un elemento [u, v] de para elevar la potencia de cada coeficiente de ese elemento a q : σ( [u, v] ) = [ u ^q (x), v ^q (x)]. El polinomio característico de este endomorfismo tiene la siguiente forma: ${\displaystyle J_{C}(\mathbb {F} _{q^{n}})}$

${\displaystyle \chi (T)=T^{2g}+a_{1}T^{2g-1}+\cdots +a_{g}T^{g}+\cdots +a_{1}q^{g-1}T+q^{g},}$

donde una _yo en ${\displaystyle \mathbb {Z} }$

Con el teorema de Hasse-Weil es posible recibir el orden de grupo de cualquier campo de extensión utilizando las raíces complejas τ _i de χ( T ): ${\displaystyle \mathbb {F} _{q^{n}}}$

${\displaystyle |J_{C}(\mathbb {F} _{q^{n}})|=\prod _{i=1}^{2g}(1-\tau _{i}^{n})}$

Sea D un elemento de C , entonces es posible definir un endomorfismo de , la llamada traza de D : ${\displaystyle J_{C}(\mathbb {F} _{q^{n}})}$ ${\displaystyle J_{C}(\mathbb {F} _{q^{n}})}$

${\displaystyle \operatorname {Tr} (D)=\sum _{i=0}^{n-1}\sigma ^{i}(D)=D+\sigma (D)+\cdots +\sigma ^{n-1}(D)}$

Basándose en este endomorfismo se puede reducir la variedad jacobiana a un subgrupo G con la propiedad de que cada elemento es de traza cero:

${\displaystyle G=\{D\in J_{C}(\mathbb {F} _{q^{n}})~|~{\text{Tr}}(D)={\textbf {0}}\},~~~({\textbf {0}}{\text{ neutral element in }}J_{C}(\mathbb {F} _{q^{n}})}$

G es el núcleo del endomorfismo de traza y, por lo tanto, G es un grupo, la llamada (sub)variedad de traza cero (TZV) de . ${\displaystyle J_{C}(\mathbb {F} _{q^{n}})}$

La intersección de G y se produce por los elementos de torsión n de . Si el máximo común divisor de la intersección está vacío y se puede calcular el orden de grupo de G : ${\displaystyle J_{C}(\mathbb {F} _{q})}$ ${\displaystyle J_{C}(\mathbb {F} _{q})}$ ${\displaystyle \gcd(n,|J_{C}(\mathbb {F} _{q})|)=1}$

${\displaystyle |G|={\dfrac {|J_{C}(\mathbb {F} _{q^{n}})|}{|J_{C}(\mathbb {F} _{q})|}}={\dfrac {\prod _{i=1}^{2g}(1-\tau _{i}^{n})}{\prod _{i=1}^{2g}(1-\tau _{i})}}}$

El grupo real que se utiliza en aplicaciones criptográficas es un subgrupo G ₀ de G de un orden primo grande l . Este grupo puede ser el propio G. ^{[1] [2]}

Existen tres casos diferentes de relevancia criptográfica para TZV: ^[3]

• g = 1, n = 3
• g = 1, n = 5
• g = 2, n = 3

Aritmética

La aritmética utilizada en el grupo TZV G ₀ se basa en la aritmética para todo el grupo , pero es posible utilizar el endomorfismo de Frobenius σ para acelerar la multiplicación escalar. Esto se puede lograr si G ₀ se genera por D de orden l, entonces σ(D) = sD , para algunos enteros s . Para los casos dados de TZV s se puede calcular de la siguiente manera, donde a _i proviene del polinomio característico del endomorfismo de Frobenius : ${\displaystyle J_{C}(\mathbb {F} _{q^{n}})}$

• Para g = 1, n = 3: ${\displaystyle s={\dfrac {q-1}{1-a_{1}}}{\bmod {\ell }}}$
• Para g = 1, n = 5: ${\displaystyle s={\dfrac {q^{2}-q-a_{1}^{2}q+a_{1}q+1}{q-2a_{1}q+a_{1}^{3}-a_{1}^{2}+a_{1}-1}}{\bmod {\ell }}}$
• Para g = 2, n = 3: ${\displaystyle s=-{\dfrac {q^{2}-a_{2}+a_{1}}{a_{1}q-a_{2}+1}}{\bmod {\ell }}}$

Sabido esto, es posible sustituir cualquier multiplicación escalar mD (|m| ≤ l/2) por:

${\displaystyle m_{0}D+m_{1}\sigma (D)+\cdots +m_{n-1}\sigma ^{n-1}(D),~~~~{\text{where }}m_{i}=O(\ell ^{1/(n-1)})=O(q^{g})}$

Con este truco, el producto escalar múltiple se puede reducir a aproximadamente 1/( n  − 1) ^de las duplicaciones necesarias para calcular mD , si las constantes implícitas son lo suficientemente pequeñas. ^{[3] [2]}

Seguridad

La seguridad de los sistemas criptográficos basados ​​en subvariedades de traza cero según los resultados de los artículos ^{[2] [3]} es comparable a la seguridad de las curvas hiperelípticas de género bajo g' sobre , donde p' ~ ( n  − 1)( g/g' ) para |G| ~128 bits. ${\displaystyle \mathbb {F} _{p'}}$

Para los casos donde n = 3, g = 2 y n = 5, g = 1 es posible reducir la seguridad a un máximo de 6 bits, donde |G| ~ 2 ²⁵⁶ , porque no se puede estar seguro de que G esté contenido en un jacobiano de una curva de género 6. La seguridad de las curvas de género 4 para campos similares es mucho menos segura.

Ataque encubierto en un sistema criptográfico de traza cero

El ataque publicado en ^[4] muestra que el DLP en grupos de traza cero de género 2 sobre campos finitos de característica distinta de 2 o 3 y una extensión de campo de grado 3 se puede transformar en un DLP en un grupo de clase de grado 0 con género de como máximo 6 sobre el campo base. En este nuevo grupo de clase el DLP se puede atacar con los métodos de cálculo de índices. Esto conduce a una reducción de la longitud de _bit en ^{1/6 .}

Notas

1. Frey, Gerhard ; Lange, Tanja (2005). "Antecedentes matemáticos de la criptografía de clave pública" (PDF) . Seminarios y congresos . 11 : 41–73.
2. Lange, Tanja (2003). "Subvariedad Trace Zero para criptosistemas". Archivo de ePrints de criptología .
3. Avanzi, Roberto M.; Cesena, Emanuele (2008). "Variedades de traza cero sobre campos de característica 2 para aplicaciones criptográficas" (PDF) . Geometría algebraica y sus aplicaciones : 188–215. doi :10.1142/9789812793430_0010. ISBN 978-981-279-342-3.
4. Diem, Claus; Scholten, Jasper. "Un ataque a un criptosistema Trace-Zero" . CiteSeerX 10.1.1.295.9027 . 

Referencias

• Wienecke, Malta; Paar, Christof (17 de febrero de 2008). Criptografía sobre variedades Trace-Zero (PDF) . Universidad del Ruhr en Bochum.
• Sutherland, Andrew V. (2007). "101 variedades útiles de traza cero". Instituto Tecnológico de Massachusetts.