Criptografía multivariada

Criptografía multivariada es el término genérico para primitivas criptográficas asimétricas basadas en polinomios multivariados sobre un campo finito . En ciertos casos, esos polinomios podrían definirse tanto sobre un campo terrestre como sobre un campo de extensión . Si los polinomios tienen grado dos, hablamos de cuadráticas multivariadas . Se ha demostrado que la resolución de sistemas de ecuaciones polinómicas multivariadas es NP-completa . ^[1] Es por eso que esos esquemas a menudo se consideran buenos candidatos para la criptografía poscuá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 planes más sólidos han resistido la prueba del tiempo. Comúnmente se admite 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 poscuánticos. ${\displaystyle F}$

Historia

Tsutomu Matsumoto y Hideki Imai  (1988) presentaron su llamado esquema C* en la conferencia Eurocrypt . Aunque Jacques Patarin (1995) rompió C*, el principio general de Matsumoto e Imai ha inspirado una generación de propuestas mejoradas. En un trabajo posterior, Jacques Patarin desarrolló (en francés) los "Criptosistemas monomios ocultos" . Se basa en un terreno y un campo de extensión. Las " ecuaciones de campo oculto " (HFE), desarrolladas por Patarin en 1996, siguen siendo un esquema multivariado popular en la actualidad [P96]. La seguridad de HFE ha sido investigada exhaustivamente, comenzando con un ataque directo de base 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 inservible, 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 negativa y la variante de vinagre, 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 colaboració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 un mapa cuadrático 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}}$.

El triple es la clave privada, también conocida como trampilla. La clave pública es la composición que, se supone, 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 codifica en un vector mediante una función hash conocida. la firma es ${\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 posesión la clave pública P. Calcula el hash y comprueba que se cumpla la firma . ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle P(x)=y}$

Aplicaciones

• Aceite y vinagre desequilibrados
• Ecuaciones de campo oculto
• SFLASH de NESSIE
• Arcoíris
• tts
• CUARZO
• QUAD (cifrado)
• Cuatro esquemas de firma de criptografía multivariante (GeMMS, LUOV, Rainbow y MQDSS) llegaron a la segunda ronda de la competencia poscuá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. De mal humor, Dustin. "La segunda ronda del proceso de estandarización del NIST PQC". 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 oculto (HFE) que utilizan bases de Gröbner. CRIPTO'03
• [GJS06] L. Granboulan, Antoine Joux, J. Stern: La inversión de HFE es cuasipolinomial. CRIPTO'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. SEÑOR  1729291.
• Kipnis, Aviad; Patarín, Jacques; Goubin, Luis (1999). "Esquemas de firmas desequilibrados de aceites y vinagres" (PDF) . En Jacques Stern (ed.). Avances en criptología - CRYPTO' 99 . Eurocripta'99. Saltador. doi : 10.1007/3-540-48910-x_15 . ISBN 3-540-65889-0. ISSN  0302-9743. SEÑOR  1717470.
• Matsumoto, Tsutomu; Imai, Hideki (1988). "Tuplas polinomiales cuadráticas públicas para verificación de firmas y cifrado de mensajes eficientes". Apuntes de conferencias sobre informática . Berlín, Heidelberg: Springer. doi :10.1007/3-540-45961-8_39. ISBN 978-3-540-50251-7. ISSN  0302-9743. SEÑOR  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 . Apuntes de conferencias 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. SEÑOR  1445572.
• [P96] Jacques Patarin, Ecuaciones de campo oculto (HFE) e isomorfismos de polinomios (IP): dos nuevas familias de algoritmos asimétricos (versión ampliada); Eurocripta '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: 2005-12-15
• An Braeken, Christopher Wolf y Bart Preneel , Un estudio sobre la seguridad de los esquemas de firma desequilibrados de petróleo 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 multivariante Rainbow y TTS
• Jacques Patarin, Nicolas Courtois , Louis Goubin, SFLASH, un esquema rápido de firma asimétrica para tarjetas inteligentes de bajo costo. Especificación primitiva y documentación de respaldo.
• 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 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

enlaces externos

• [1] Cifrado y firma de clave pública HFE
• [2] Impulso HFE