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 firmas se basa en un problema matemático NP-hard . Para crear y validar firmas, se debe resolver un sistema de ecuación cuadrática mínima. Resolver m ecuaciones con n variables es NP-difícil. Si bien el problema es fácil si m es mucho más grande o mucho más pequeño que n , [1]importante para los propósitos de cifrado, el problema se piensa que es difícil en el caso promedio cuando m y n son casi iguales, incluso cuando se utiliza un ordenador cuántico . 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 firmas basados en RSA, las claves son ambos exponentes. En el esquema UOV, y en todos los demás esquemas de firma multivariante, las claves son más complejas.
El problema matemático es resolver ecuaciones con variables. Todo el sistema de ecuaciones es la clave pública.
Para utilizar un problema matemático para criptografía, debe modificarse. La computación de lalas variables necesitarían muchos recursos. Una computadora estándar no puede 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 y un vector polinomial . Ambas transformaciones se utilizan para transformar elementos en ciertos grupos. transforma a . La segunda transformación transforma el vector variable en la firma válida.
El tercer elemento secreto proporciona ciertas herramientas para la creación de ecuaciones. Las ecuaciones se construyen con reglas conocidas solo por el propietario de la clave de firma.
Creación de firmas
Para crear una firma válida, se debe resolver el siguiente sistema de ecuaciones
Aquí el es un mensaje dado que debe ser firmado. La firma válida es.
Para firmar un dado , el mensaje debe transformarse primero para que encaje en el sistema de ecuaciones. se utiliza para "dividir" el mensaje en partes aceptables . Entonces hay que construir las ecuaciones. Cada ecuación tiene la misma forma:
Los siguientes pasos firman un mensaje determinado y el resultado es una firma válida .
- Los coeficientes, , debe elegirse en secreto.
- Las variables de vinagre () son elegidos al azar
- El sistema de ecuaciones lineales resultante se resuelve para las variables de aceite ()
Las variables de vinagre y aceite crean la firma previa. . Finalmente se transforma por la transformación privada para dar la firma válida .
El sistema de ecuaciones se vuelve lineal si las variables de vinagre son fijas; ninguna variable de aceite se multiplica por otra variable de aceite en la ecuación. Por lo tanto, las variables del aceite se pueden calcular fácilmente usando, por ejemplo, un algoritmo de reducción gaussiano . La creación de firmas es en sí misma rápida y computacionalmente fácil.
Validación de firma
La firma se transmite al interlocutor. La validación de la firma se realiza con la ayuda de la clave pública, que es un sistema de ecuaciones.
Este sistema de ecuaciones es una versión ligeramente modificada del sistema necesario para la creación de firmas. Se modifica 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 propia firma. Si cada resultado es igual a la parte correspondiente del mensaje original, entonces la verificación se realizó correctamente.
Problemas y ventajas
Una ventaja principal es que el problema matemático que se resolverá en el algoritmo es resistente a los cuánticos. Cuando se construye una computadora cuántica que puede factorizar números compuestos grandes utilizando 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 . UOV puede permanecer seguro porque no se conoce ningún algoritmo que dé a la computadora cuántica una gran ventaja en la resolución de sistemas multivariados de ecuaciones.
La segunda ventaja es que las operaciones utilizadas en las ecuaciones son relativamente simples. Las firmas se crean y validan solo con la suma y la multiplicación de valores "pequeños", lo que hace que esta firma sea viable para hardware de bajos recursos como se encuentra en tarjetas inteligentes .
Una desventaja es que UOV usa longitudes de clave muy largas, con la clave pública que involucra a todo el sistema de ecuaciones, que pueden requerir varios cientos de kilobytes . UOV no se ha utilizado ampliamente. Si bien ya se conocen varios métodos de ataque, pueden aparecer más si UOV se usa ampliamente. UOV aún no está listo para uso comercial porque su seguridad requiere más investigación.
El criptosistema Rainbow se basa en UOV y es uno de los tres finalistas en la competencia NIST para un estándar de firma digital post-cuántica.
Referencias
- ↑ Courtois, Nicolas; et al. "Resolución de sistemas subdefinidos de ecuaciones multivariantes" (PDF) . Consultado el 16 de octubre de 2016 .
enlaces externos
- Buchmann, Johannes; Coronado, Carlos; Doring, Martin; Engelbert, Daniela; Ludwig, Christoph; Overbeck, Rafael; Schmidt, Arthur; Vollmer, Ulrich; Weinmann, Ralf-Philipp: Post-Quantum Signatures, -, 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: A Study of the Security of Unbalanced Oil and Vinegar Signature Schemes, 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: Unbalanced Oil and Vinegar Signature Schemes - versión extendida, EURO-CRYPT, 1999
- Faugère, Jean-Charles y Perret, Ludovic. Sobre la seguridad de UOV. Archivo eprint de criptología. Informe 2009/483. 2009