Esquema desequilibrado de aceite y vinagre

Esquema de firma digital post-cuántica

En criptografía , el esquema de aceite y vinagre desequilibrado (UOV) es una versión modificada del esquema de aceite y vinagre diseñado por J. Patarin. Ambos son protocolos de firma digital . Son formas de criptografía multivariante . La seguridad de este esquema de firma se basa en un problema matemático NP-hard . Para crear y validar firmas, se debe resolver un sistema de ecuaciones cuadráticas mínimas. Resolver m ecuaciones con n variables es NP-hard. Si bien el problema es fácil si m es mucho mucho más grande o mucho mucho más pequeño que n , ^[1] lo que es importante para fines criptográficos, se cree que el problema es difícil en el caso promedio cuando m y n son casi iguales, incluso cuando se usa una computadora cuántica . Se han ideado múltiples esquemas de firma basados ​​en ecuaciones multivariantes con el objetivo de lograr resistencia cuántica .

Un inconveniente importante de UOV es que el tamaño de la clave puede ser grande. Normalmente , se elige que n , el número de variables, sea el doble de m , el número de ecuaciones. Codificar los coeficientes de todas estas ecuaciones en la clave requiere un espacio considerable, al menos 200 kilobytes para un sistema que ofrezca una seguridad comparable a la del algoritmo de firma digital o al algoritmo de firma digital de curva elíptica .

Clave de firma y verificación

Un esquema de firma tiene una clave de firma, que se mantiene privada, y una clave de verificación, que se revela públicamente. Por ejemplo, en los esquemas de firma basados ​​en RSA, las claves son ambas exponentes. En el esquema UOV, y en cualquier otro esquema de firma multivariante, las claves son más complejas.

El problema matemático consiste en resolver ecuaciones con variables. Todo el sistema de ecuaciones es la clave pública. ${\displaystyle m}$ ${\displaystyle n}$

Para utilizar un problema matemático en criptografía, es necesario modificarlo. El cálculo de las variables necesitaría muchos recursos. Un ordenador estándar no es capaz de calcular esto en un tiempo aceptable. Por lo tanto, se inserta una trampilla especial en el sistema de ecuaciones. Esta trampilla es la clave de firma. Consta de tres partes: dos transformaciones afines y un vector polinómico . Ambas transformaciones se utilizan para transformar elementos de ciertos grupos. transforma en . La segunda transformación transforma la variable vector en la firma válida. ${\displaystyle n}$ ${\displaystyle T}$ ${\displaystyle S}$ ${\displaystyle {\acute {P}}}$ ${\displaystyle T}$ ${\displaystyle y}$ ${\displaystyle y_{1},y_{2},...,y_{n}}$ ${\displaystyle S}$

El tercer elemento secreto proporciona ciertas herramientas para la creación de ecuaciones. Las ecuaciones se construyen con reglas que sólo conoce el propietario de la clave de firma. ${\displaystyle {\acute {P}}}$

Creación de firma

Para crear una firma válida, se debe resolver el siguiente sistema de ecuaciones

$${\displaystyle {\begin{aligned}y_{1}&=f_{1}(x_{1},\ldots ,x_{n})\\y_{2}&=f_{2}(x_{1},\ldots ,x_{n})\\&~\vdots \\y_{m}&=f_{m}(x_{1},\ldots ,x_{n})\\\end{aligned}}}$$

Aquí se muestra un mensaje que debe firmarse. La firma válida es . ${\displaystyle y=(y_{1},y_{2},\ldots ,y_{m})}$ ${\displaystyle x=(x_{1},x_{2},\ldots ,x_{n})}$

Para firmar un determinado mensaje, primero se debe transformar para que encaje en el sistema de ecuaciones. se utiliza para "dividir" el mensaje en partes aceptables . Luego se deben construir las ecuaciones. Todas las ecuaciones tienen la misma forma: ${\displaystyle y}$ ${\displaystyle T}$ ${\displaystyle y_{1},y_{2},\ldots ,y_{m}}$

$${\displaystyle y_{i}=\sum {\gamma _{ijk}a_{j}{\acute {a}}_{k}}+\sum {\lambda _{ijk}{\acute {a}}_{j}{\acute {a}}_{k}}+\sum {\xi _{ij}a_{j}}+\sum {{\acute {\xi }}_{ij}{\acute {a}}_{j}}+\delta _{i}}$$

Los siguientes pasos firman un mensaje dado y el resultado es una firma válida . ${\displaystyle y}$ ${\displaystyle x}$

1. Los coeficientes, , deben elegirse en secreto. ${\displaystyle \gamma _{ijk},\lambda _{ijk},\xi _{ij},{\acute {\xi }}_{ij},\delta _{i}}$
2. Las variables del vinagre ( ) se eligen aleatoriamente ${\displaystyle {\acute {a}}_{j}}$
3. El sistema de ecuaciones lineales resultante se resuelve para las variables del petróleo ( ) ${\displaystyle a_{i}}$

Las variables vinagre y aceite forman la prefirma . Finalmente, se transforman mediante la transformación privada para dar la firma válida . ${\displaystyle A=(a_{1},\ldots ,a_{n},{\acute {a}}_{1},\ldots ,{\acute {a}}_{v})}$ ${\displaystyle A}$ ${\displaystyle S}$ ${\displaystyle x=S^{-1}(A)}$

El sistema de ecuaciones se vuelve lineal si las variables del vinagre son fijas (ninguna variable del aceite se multiplica por otra variable del aceite en la ecuación). Por lo tanto, las variables del aceite se pueden calcular fácilmente utilizando, por ejemplo, un algoritmo de reducción gaussiana . La creación de la firma es en sí misma rápida y computacionalmente sencilla.

Validación de firma

La firma se transmite al interlocutor. La validación de la firma se realiza con ayuda de la clave pública, que es un sistema de ecuaciones.

$${\displaystyle {\begin{aligned}y_{1}&={f_{1}}^{*}(x_{1},x_{2},\ldots ,x_{n})\\y_{2}&={f_{2}}^{*}(x_{1},x_{2},\ldots ,x_{n})\\&~\vdots \\y_{m}&={f_{m}}^{*}(x_{1},x_{2},\ldots ,x_{n})\\\end{aligned}}}$$

Este sistema de ecuaciones es una versión ligeramente modificada del sistema necesario para la creación de firmas. Se modifica de modo que un atacante no pueda obtener información sobre los coeficientes secretos y el formato especial de las variables de aceite y vinagre. Cada ecuación de la clave pública debe resolverse para validar la firma. La entrada es la propia firma. Si cada resultado es igual a la parte correspondiente del mensaje original, entonces la verificación se ha realizado correctamente. ${\displaystyle y_{i}}$

Problemas y ventajas

Una ventaja principal es que el problema matemático que se debe resolver en el algoritmo es resistente a la tecnología cuántica. Cuando se construya una computadora cuántica que pueda factorizar números compuestos grandes utilizando el algoritmo de Shor , esto romperá los esquemas de firma comerciales como RSA o ElGamal que se basan en que el problema del logaritmo discreto es irresoluble. La UOV puede seguir siendo segura porque no se conoce ningún algoritmo que le dé a la computadora cuántica una gran ventaja en la resolución de sistemas de ecuaciones multivariantes.

La segunda ventaja es que las operaciones que se utilizan en las ecuaciones son relativamente sencillas. Las firmas se crean y validan únicamente con la suma y multiplicación de valores "pequeños", lo que hace que esta firma sea viable para hardware de bajos recursos como el que se encuentra en las tarjetas inteligentes .

Una desventaja es que UOV utiliza longitudes de clave muy largas, y la clave pública involucra todo el sistema de ecuaciones, lo que puede requerir varios cientos de kilobytes . UOV no se ha utilizado ampliamente. Si bien ya se conocen varios métodos de ataque, es posible que aparezcan más si UOV se vuelve ampliamente utilizado. UOV aún no está listo para su uso comercial porque su seguridad requiere más investigación. ${\displaystyle m}$

El criptosistema Rainbow se basa en UOV y es uno de los tres finalistas en el concurso del NIST para un estándar de firma digital postcuántica, aunque recientemente han surgido importantes preocupaciones con respecto a su seguridad, tal como se propuso en el concurso del NIST. Se descubrió un nuevo ataque MinRank contra Rainbow, que reduce la seguridad de la instanciación Rainbow propuesta a un nivel por debajo de los requisitos establecidos por el NIST. ^[2] Beullens descubrió un nuevo ataque en 2022, que recupera la clave privada para el conjunto de parámetros L1 de Rainbow en un fin de semana. ^[3] UOV en sí no se ve afectado por este ataque.

Referencias

1. Courtois, Nicolas; et al. "Resolución de sistemas indefinidos de ecuaciones multivariadas" (PDF) . Consultado el 16 de octubre de 2016 .
2. Beullens, Ward (2021). "Criptoanálisis mejorado de UOV y Rainbow". En Canteaut, Anne; Standaert, François-Xavier (eds.). Avances en criptología – EUROCRYPT 2021. Apuntes de clase en informática. Vol. 12696. Cham: Springer International Publishing. págs. 348–373. doi :10.1007/978-3-030-77870-5_13. ISBN 978-3-030-77870-5. Número de identificación del sujeto  226200424.
3. Beullens, Ward (2022). "Breaking Rainbow requiere un fin de semana en una computadora portátil". Archivo de impresión electrónica de criptología .

Enlaces externos

• Buchmann, Johannes; Coronado, Carlos; Doring, Martín; Engelbert, Daniela; Luis, Christoph; Overbeck, Rafael; Schmidt, Arturo; Vollmer, Ulrich; Weinmann, Ralf-Philipp: Firmas poscuánticas, –, 29 de octubre de 2004
• Wolf, Christopher: Polinomios cuadráticos multivariados en criptografía de clave pública, simposio DIAMANT/EIDMA 2005
• Braeken, An; Wolf, Christopher; Preneel, Bart: Un estudio sobre la seguridad de los esquemas de firmas desequilibradas de aceite y vinagre, ESAT-COSIC, 2 de septiembre de 2004
• Coron, Jean-Sebastien; de Weger, Benne: Dificultad de los principales problemas computacionales utilizados en criptografía, ECRYPT D.AZTEC.6, 14 de marzo de 2007
• Kipnis, Aviad: Esquemas de firmas desequilibrados de aceite y vinagre – versión ampliada, EURO-CRYPT, 1999
• Faugère, Jean-Charles y Perret, Ludovic. Sobre la seguridad de la UOV. Archivo de publicaciones electrónicas de criptología. Informe 2009/483. 2009