Criptografía multivariada

La criptografía multivariada es el término genérico para las primitivas criptográficas asimétricas basadas en polinomios multivariados sobre un campo finito.${\displaystyle F}$En ciertos casos, esos polinomios podrían definirse tanto sobre un cuerpo base como sobre un cuerpo de extensión . Si los polinomios tienen grado dos, hablamos de polinomios cuadráticos multivariados . Se ha demostrado que resolver sistemas de ecuaciones polinómicas multivariadas es NP-completo . ^{[ 1 ]} Estos esquemas suelen considerarse buenos candidatos para la criptografía postcuántica . La criptografía multivariada ha sido muy productiva en términos de diseño y criptoanálisis . En general, la situación es ahora más estable y los esquemas más robustos han resistido el paso del tiempo. Se admite comúnmente que la criptografía multivariada resultó ser más exitosa como enfoque para construir esquemas de firma principalmente porque los esquemas multivariados proporcionan la firma más corta entre los algoritmos postcuánticos.

Tsutomu Matsumoto y Hideki Imai ( 1988 ) presentaron su esquema denominado C* en la conferencia Eurocrypt . Aunque Jacques Patarin ( 1995 ) logró romper C* , el principio general de Matsumoto e Imai inspiró una generación de propuestas mejoradas. En trabajos posteriores, Jacques Patarin desarrolló (en francés) los "Criptosistemas Monomiales Ocultos" . Estos se basan en un campo base y un campo de extensión. Las " Ecuaciones de Campo Oculto " (HFE), desarrolladas por Patarin en 1996, siguen siendo un esquema multivariante popular en la actualidad [P96]. La seguridad de HFE ha sido investigada exhaustivamente, comenzando con un ataque directo a la base de Gröbner [FJ03, GJS06], ataques de recuperación de claves ( Kipnis y Shamir 1999 ) [BFP13], y más. La versión simple de HFE se considera prácticamente inviable, en el sentido de que los parámetros seguros conducen a un esquema poco práctico. Sin embargo, algunas variantes simples de HFE, como la variante menos y la variante vinagre, permiten fortalecer el HFE básico contra todos los ataques conocidos.  

Además de HFE, Patarin desarrolló otros esquemas. En 1997 presentó “Balanced Oil & Vinegar” y en 1999 “ Unbalanced Oil and Vinegar ”, en cooperación con Aviad Kipnis y Louis Goubin ( Kipnis, Patarin y Goubin 1999 ) . Cuatro esquemas de firma criptográfica multivariante (GeMMS, LUOV, Rainbow y MQDSS) llegaron a la segunda ronda de la competencia post-cuántica del NIST: véase la diapositiva 12 del informe. ^{[ 2 ]} El esquema Rainbow avanzó a la ronda 3 hasta que fue descifrado en 2022, ^{[ 3 ]} y ninguno de los demás quedó para la ronda 4. ^{[ 4 ]}

La función cuadrática multivariada implica una clave pública y una clave privada. La clave privada consta de dos transformaciones afines, S y T, y una función cuadrática fácil de invertir.${\displaystyle P'\colon F^{m}\rightarrow F^{n}}$. Denotamos el${\displaystyle n\times n}$matriz de los endomorfismos afines${\displaystyle S\colon F^{n}\rightarrow F^{n}}$por${\displaystyle M_{S}}$y el vector de desplazamiento por${\displaystyle v_{S}\in F^{n}}$y de manera similar para${\displaystyle T\colon F^{m}\rightarrow F^{m}}$. En otras palabras,

• ${\displaystyle S(x)=M_{S}x+v_{S}}$y
• ${\displaystyle T(y)=M_{T}y+v_{T}}$.

El triple${\displaystyle (S^{-1},{P'}^{-1},T^{-1})}$es la clave privada, también conocida como puerta trasera. La clave pública es la composición${\displaystyle P=S\circ P'\circ T}$lo cual, por suposición, es difícil de invertir sin el conocimiento de la trampilla.

Las firmas se generan utilizando la clave privada y se verifican utilizando la clave pública de la siguiente manera. El mensaje se convierte en un vector mediante hash.${\displaystyle y\in F^{n}}$mediante una función hash conocida. La firma es

${\displaystyle x=P^{-1}(y)=T^{-1}\left({P'}^{-1}\left(S^{-1}(y)\right)\right)}$.

El receptor del documento firmado debe tener en su poder la clave pública P. Él calcula el hash.${\displaystyle y}$y comprueba que la firma${\displaystyle x}$cumple${\displaystyle P(x)=y}$.

• Aceite y vinagre desequilibrados
• Ecuaciones de campo oculto
• SFLASH de NESSIE
• Arcoíris
• TTS
• CUARZO
• CUADRADO (cifrado)

• [BFP13] L. Bettale, Jean-Charles Faugère y L. Perret, Criptoanálisis de HFE, Multi-HFE y variantes para características pares e impares. DCC'13
• [FJ03] Jean-Charles Faugère y A. Joux, Criptoanálisis algebraico de criptosistemas de ecuaciones de campo oculto (HFE) utilizando bases de Gröbner. CRYPTO'03
• [GJS06] L. Granboulan, Antoine Joux, J. Stern: Invertir HFE es cuasipolinomial. CRYPTO'06.
• Kipnis, Aviad; Shamir, Adi (1999). «Criptoanálisis del criptosistema de clave pública HFE mediante relinealización». Avances en criptología – CRYPTO' 99. Berlín, Heidelberg: Springer. doi : 10.1007/3-540-48405-1_2 . ISBN 978-3-540-66347-8. ISSN 0302-9743 . MR 1729291 .  
• Kipnis, Aviad; Patarin, Jacques; Goubin, Louis (1999). «Esquemas de firma desequilibrados de aceite y vinagre» (PDF) . En Jacques Stern (ed.). Avances en criptología – CRYPTO' 99. Eurocrypt'99. Springer. doi : 10.1007/3-540-48910-x_15 . ISBN 3-540-65889-0. ISSN 0302-9743 . MR 1717470 .  
• Matsumoto, Tsutomu; Imai, Hideki (1988). «Tuplas polinómicas cuadráticas públicas para la verificación eficiente de firmas y el cifrado de mensajes». Lecture Notes in Computer Science . Berlín, Heidelberg: Springer. doi : 10.1007/3-540-45961-8_39 . ISBN 978-3-540-50251-7. ISSN 0302-9743 . MR 0994679 .  
• Patarin, Jacques (1995). «Criptoanálisis del esquema de clave pública de Matsumoto e Imai de Eurocrypt'88». Avances en criptología – CRYPT0' 95. Notas de clase en ciencias de la computación. Vol.  963. Berlín, Heidelberg: Springer. pp. 248–261 . doi : 10.1007/3-540-44750-4_20 . ISBN  978-3-540-60221-7. ISSN 0302-9743 . MR 1445572 .  
• [P96] Jacques Patarin, Ecuaciones de campo oculto (HFE) e isomorfismos de polinomios (IP): dos nuevas familias de algoritmos asimétricos (versión extendida); Eurocrypt '96
• Christopher Wolf y Bart Preneel , Taxonomía de esquemas de clave pública basada en el problema de ecuaciones cuadráticas multivariadas; Versión actual: 15/12/2005
• An Braeken, Christopher Wolf y Bart Preneel , Un estudio sobre la seguridad de los esquemas de firmas desequilibradas de petróleo y vinagre, Versión actual: 6 de agosto de 2005
• Jintai Ding, Proyecto de investigación: Criptoanálisis sobre el esquema de firma de clave pública multivariante Rainbow y TTS
• Jacques Patarin, Nicolas Courtois , Louis Goubin, SFLASH, un esquema de firma asimétrica rápida para tarjetas inteligentes de bajo coste. Especificación básica y documentación de apoyo.
• Bo-Yin Yang, Chen-Mou Cheng, Bor-Rong Chen y Jiun-Ming Chen, Implementación de PKC multivariado minimizado en sistemas embebidos de bajos recursos, 2006
• Bo-Yin Yang, Jiun-Ming Chen y Yen-Hung Chen, TTS: Firmas de alta velocidad en una tarjeta inteligente de bajo costo, 2004
• Nicolas T. Courtois , Firmas cortas, seguridad demostrable, ataques genéricos y seguridad computacional de esquemas polinomiales multivariados como HFE, Quartz y Sflash, 2005
• Alfred J. Menezes, Paul C. van Oorschot y Scott A. Vanstone, Manual de criptografía aplicada, 1997

• El cifrado y la firma de clave pública HFE
• HFEBoost