Esquema desequilibrado de aceites y vinagres.

Esquema de firma digital poscuántica

En criptografía , el esquema desequilibrado de aceite y vinagre (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 multivariada . La seguridad de este esquema de firma se basa en un problema matemático NP-difícil . Para crear y validar firmas, se debe resolver un sistema de ecuaciones cuadráticas mínimas. Resolver m ecuaciones con n variables es NP-difícil. Si bien el problema es fácil si m es mucho mayor o mucho menor que n , ^[1] 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 un computadora cuántica . Se han ideado múltiples esquemas de firma basados ​​en ecuaciones multivariadas 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 , n , el número de variables, se elige para que 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 ofrecería una seguridad comparable al 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 para criptografía, es necesario modificarlo. El cálculo de las variables necesitaría muchos recursos. Una computadora 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 en ciertos grupos. se transforma en . La segunda transformación transforma el vector variable 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í hay un mensaje dado que debe estar firmado. 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 mensaje dado , primero se debe transformar el mensaje para que encaje en el sistema de ecuaciones. se utiliza para "dividir" el mensaje en partes aceptables . Luego hay que construir las ecuaciones. Cada ecuación tiene 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 determinado 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 construyen la prefirma . Finalmente se transforma 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 petróleo se pueden calcular fácilmente utilizando, por ejemplo, un algoritmo de reducción gaussiano . La creación de firmas es en sí misma rápida y sencilla desde el punto de vista computacional.

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. Está modificado para 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 firma misma. Si cada resultado es igual a la parte correspondiente del mensaje original, entonces la verificación fue exitosa. ${\displaystyle y_{i}}$

Problemas y ventajas.

Una ventaja principal es que el problema matemático a resolver en el algoritmo es resistente a los cuánticos. Cuando se construya una computadora cuántica que pueda factorizar grandes números compuestos usando el algoritmo de Shor , esto romperá los esquemas de firmas comerciales como RSA o ElGamal que se basan en que el problema del logaritmo discreto no tiene solución. Los UOV pueden seguir siendo seguros porque no se conoce ningún algoritmo que dé a la computadora cuántica una gran ventaja en la resolución de sistemas de ecuaciones multivariados.

La segunda ventaja es que las operaciones utilizadas en las ecuaciones son relativamente simples. 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 . Los UOV no se han utilizado ampliamente. Si bien ya se conocen varios métodos de ataque, podrían aparecer más si el UOV se utiliza ampliamente. UOV aún no está listo para 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 la competencia del NIST para un estándar de firma digital poscuántica, aunque recientemente han salido a la luz importantes preocupaciones con respecto a su seguridad propuesta en la competencia del NIST. Se descubrió un nuevo ataque MinRank contra Rainbow, que reduce la seguridad de la creación de instancias de Rainbow propuesta a un nivel por debajo de los requisitos establecidos por NIST. ^[2] Beullens descubrió un nuevo ataque en 2022, que recupera la clave privada del conjunto de parámetros Rainbow L1 en un fin de semana. ^[3] El UOV en sí no se ve afectado por este ataque.

Referencias

1. Courtois, Nicolás; et al. "Resolución de sistemas infradefinidos de ecuaciones multivariadas" (PDF) . Consultado el 16 de octubre de 2016 .
2. Beullens, Ward (2021). "Criptoanálisis mejorado de UOV y Rainbow". En Canteaut, Ana; Standaert, François-Xavier (eds.). Avances en Criptología – EUROCRYPT 2021 . Apuntes de conferencias sobre informática. vol. 12696. Cham: Editorial Internacional Springer. págs. 348–373. doi :10.1007/978-3-030-77870-5_13. ISBN 978-3-030-77870-5. S2CID  226200424.
3. Beullens, Ward (2022). "Breaking Rainbow requiere un fin de semana en una computadora portátil". Archivo ePrint 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; Lobo, Cristóbal; Preneel, Bart: Un estudio de la seguridad de los esquemas de firma de petróleo y vinagre desequilibrados, ESAT-COSIC, 2 de septiembre de 2004
• Coron, Jean-Sebastien; de Weger, Benne: Dureza de los principales problemas computacionales utilizados en criptografía, ECRYPT D.AZTEC.6, 14 de marzo de 2007
• Kipnis, Aviad: Esquemas de firma de aceite y vinagre desequilibrados - versión ampliada, EURO-CRYPT, 1999
• Faugère, Jean-Charles y Perret, Ludovic. Sobre la seguridad de la UOV. Archivo de impresión electrónica de criptología. Informe 2009/483. 2009