La criptografía multivariante es el término genérico para las primitivas criptográficas asimétricas basadas en polinomios multivariados sobre un campo finito . En ciertos casos, esos polinomios podrían definirse tanto en un terreno como en un campo de extensión . Si los polinomios tienen el grado dos, hablamos de cuadráticas multivariadas . Se ha demostrado que la resolución de sistemas de ecuaciones polinomiales multivariadas es NP-completa . [1] Es por eso que esos esquemas a menudo se consideran buenos candidatos para la criptografía post-cuántica . La criptografía multivariante 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 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 construiresquemas de firma principalmente porque los esquemas multivariados proporcionan la firma más corta entre los algoritmos post-cuánticos.
Historia
Tsutomu Matsumoto y Hideki Imai ( 1988 ) presentaron su llamado esquema C * en la conferencia Eurocrypt . Aunque C * ha sido roto por Jacques Patarin ( 1995 ), 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 monomiales ocultos" . Se basa en un terreno y un campo de extensión. " Hidden Field Equations " (HFE), desarrollado por Patarin en 1996, sigue siendo un esquema multivariado popular en la actualidad [P96]. La seguridad de HFE se ha investigado a fondo, 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. Se considera que la versión simple de HFE está prácticamente rota, 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 de 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 & Goubin 1995 ) .
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 elmatriz de los endomorfismos afines por y el vector de desplazamiento por y de manera similar para . En otras palabras,
- y
- .
El triple es la clave privada, también conocida como trampilla. La clave pública es la composición que es, por supuesto, difícil de invertir sin el conocimiento de la trampilla.
Firma
Las firmas se generan usando la clave privada y se verifican usando la clave pública de la siguiente manera. El mensaje se convierte en un vector ena través de una función hash conocida. La firma es
- .
El receptor del documento firmado debe tener la clave pública P en posesión. El calcula el hash y comprueba que la firma cumple .
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) se han abierto camino en la segunda ronda de la competencia post-cuántica del NIST: consulte la diapositiva 12 del informe. [2]
Referencias
- ^ Garey, Michael R. (1979). Computadoras e intratabilidad: una guía para la teoría de NP-completitud . Johnson, David S., 1945-. San Francisco: WH Freeman. ISBN 0-7167-1044-7. OCLC 4195125 .
- ^ Moody, Dustin. "La segunda ronda del proceso de estandarización 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 ecuación de campo oculto (HFE) utilizando bases de Gröbner. CRYPTO'03
- [GJS06] L. Granboulan, Antoine Joux, J. Stern: La inversión de HFE es cuasipolinomial. CRYPTO'06.
- Kipnis, Aviad; Patarin, Jacques; Goubin, Louis (1999). "Esquemas de firma de aceite y vinagre desequilibrados". Avances en Criptología - EUROCRYPT '99 . Berlín, Heidelberg: Springer. doi : 10.1007 / 3-540-48910-x_15 . ISBN 978-3-540-65889-4. ISSN 0302-9743 . Señor 1717470 .
- Kipnis, Aviad; Shamir, Adi (1999). "Criptoanálisis del criptosistema de clave pública HFE por reinearizació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 .
- Matsumoto, Tsutomu; Imai, Hideki (1988). "Tuplas polinomiales cuadráticas públicas para la verificación de firmas y el cifrado de mensajes eficientes". Apuntes de conferencias en Ciencias de la Computación . 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 Matsumoto e Imai de Eurocrypt'88". Avances en criptología - CRYPT0 '95 . Apuntes de conferencias en Ciencias de la Computación. 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 ocultas (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: 2005-12-15
- An Braeken, Christopher Wolf y Bart Preneel , Un estudio de la seguridad de los esquemas de firma de aceite y vinagre desequilibrados, versión actual: 2005-08-06
- Jintai Ding, Proyecto de investigación: Criptoanálisis en Rainbow y esquema de firma de clave pública multivariante TTS
- Jacques Patarin, Nicolas Courtois , Louis Goubin, SFLASH, un esquema de firma asimétrico rápido 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, Implementing Minimized Multivariate PKC on Low-Resource Embedded Systems, 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] El cifrado y la firma de la clave pública HFE
- [2] HFEBoost