Criptografía multivariante

Campo de primitivas criptográficas asimétricas

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

Historia

Tsutomu Matsumoto y Hideki Imai  (1988) presentaron su denominado esquema C* en la conferencia Eurocrypt . Aunque Jacques Patarin (1995) ha descifrado C*, el principio general de Matsumoto e Imai ha inspirado una generación de propuestas mejoradas. En trabajos posteriores, Jacques Patarin desarrolló (en francés) los "criptosistemas monomiales ocultos" , que se basan en un campo de base y uno de extensión. Las " ecuaciones de campo oculto " (HFE), desarrolladas por Patarin en 1996, siguen siendo un esquema multivariable popular en la actualidad [P96]. La seguridad de HFE se ha investigado a fondo, empezando por un ataque directo de base de Gröbner [FJ03, GJS06], ataques de recuperación de claves (Kipnis y Shamir 1999) [BFP13] y más. Se considera que la versión simple de HFE está prácticamente descifrada, 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 minus y la variante vinegar, permiten fortalecer el HFE básico contra todos los ataques conocidos.

Además de HFE, Patarin desarrolló otros esquemas. En 1997 presentó “Aceite y vinagre equilibrados” y en 1999 “ Aceite y vinagre desequilibrados ”, en cooperación con Aviad Kipnis y Louis Goubin (Kipnis, Patarin y Goubin 1999).

Construcción

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

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

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

Firma

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 una función hash conocida. La firma se ${\displaystyle y\in F^{n}}$

${\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. Calcula el hash y comprueba que la firma cumple los requisitos . ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle P(x)=y}$

Aplicaciones

• Aceite y vinagre desequilibrados
• Ecuaciones de campos ocultos
• SFLASH de NESSIE
• Arcoíris
• TTS
• CUARZO
• QUAD (cifrado)
• Cuatro esquemas de firma de criptografía multivariable (GeMMS, LUOV, Rainbow y MQDSS) han llegado a la segunda ronda de la competencia post-cuántica del NIST: consulte la diapositiva 12 del informe. ^[2]

Referencias

1. Garey, Michael R. (1979). Computadoras e intratabilidad: una guía para la teoría de la completitud NP . Johnson, David S., 1945-. San Francisco: WH Freeman. ISBN 0-7167-1044-7.OCLC 4195125  .
2. Moody, Dustin. "La segunda ronda del proceso de estandarización PQC del NIST". NIST . Consultado el 11 de octubre de 2020 .

• [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 ocultas (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 de aceite y vinagre desequilibrados" (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 claves públicas de Matsumoto e Imai de Eurocrypt'88". Avances en criptología – CRYPT0' 95. Apuntes de clase sobre informática. Vol. 963. Berlín, Heidelberg: Springer. págs. 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 campos ocultos (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 basados ​​en el problema de ecuaciones cuadráticas multivariadas; Versión actual: 2005-12-15
• An Braeken, Christopher Wolf y Bart Preneel , Un estudio sobre la seguridad de los esquemas de firmas desequilibrados de aceite y vinagre, versión actual: 2005-08-06
• Jintai Ding, Proyecto de investigación: Criptoanálisis sobre el esquema de firma de clave pública multivariable Rainbow y TTS
• Jacques Patarin, Nicolas Courtois , Louis Goubin, SFLASH, un sistema de firma asimétrica rápido para tarjetas inteligentes de bajo costo. Especificación primitiva y documentación complementaria.
• Bo-Yin Yang, Chen-Mou Cheng, Bor-Rong Chen y Jiun-Ming Chen, Implementación de PKC multivariante minimizada en sistemas integrados 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 breves, 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

Enlaces externos

• [1] El cifrado y la firma de clave pública HFE
• [2] Impulso HFEE