Pregunta:
¿Hay firmas basadas en la multiplicación de matrices con ruido? ¿Representar el mensaje como una matriz y multiplicar con cierta aleatoriedad proveniente de otra matriz de modo que la firma en sí sea una matriz?
Respuesta:
Hay dos familias principales de esquemas de firmas que se parecen un poco a lo que describió.
Firmas basadas en código: Courtois – Finiasz – Sendrier o CFS
La familia de esquemas de firmas CFS se basa en la criptografía basada en código, introducida por primera vez por Robert McEliece en 1978 y dualizada por Niederreiter . Trabajamos con códigos lineales binarios , de longitud $ n $ y rango $ k $ corrigiendo hasta $ t $ errores.
En el escenario del código de corrección de errores, un remitente con un mensaje de $ k $ -bit $ m $ lo codifica de forma redundante como una palabra de código de $ n $ -bit $ c $ de un subespacio de $ k $ -dimensional de todos los $ n $ -bit cadenas y lo envía por un canal ruidoso; el receptor, al recibir un mensaje posiblemente modificado $ c '= c + e $, puede recuperar de forma única $ c $ como la palabra de código más cercana a $ c' $ siempre que el patrón de error $ e $ no tenga más de $ t $ bits set, es decir , siempre que el peso de Hamming de $ e $ sea como máximo $ t $.
La matriz generadora de un código lineal es una matriz $ k $ -por- $ n $ $ G $ que transforma los mensajes de $ k $ -bit en palabras de código de $ n $ -bit: $ c = G m $. La matriz de verificación de paridad de un código lineal es una matriz $ n $ -by – $ (nk) $ $ K $ que transforma cadenas de $ n $ -bit en síndromes de $ (nk) $ – bit. Una cadena de $ n $ -bit es una palabra de código en el código si y solo si su síndrome es cero: $ K c = 0 $, y $ H c '= K \ cdot (c + e) = K c + K e = K e $. El problema de decodificación del síndrome es encontrar $ e $ dados $ K e $. La premisa de las firmas CFS es que encontrar el ruido dado un síndrome dado solo la matriz de verificación de paridad $ K $ parece ser difícil sin información adicional sobre la estructura del código lineal.
Parámetros. Tamaños de bits $ n $, $ k $, $ t $ para una familia de códigos lineales binarios, generalmente códigos Goppa binarios (otras propuestas como los códigos Reed-Solomon se han roto , aunque hay nuevos candidatos, por ejemplo , códigos Reed-Muller en el envío de pqsigRM a NIST PQCRYPTO ) y una función aleatoria $ H \ colon \ {0,1 \} ^ * \ to \ mathbb F_2 ^ {nk} $ de mensajes a síndromes.
Claves públicas. La clave pública de Alice es la matriz de verificación de paridad $ K $ de un código lineal binario de longitud $ n $ y rango $ k $ que corrige hasta $ t $ errores.
Firmas. Una firma de Alice en un mensaje $ m $ es un patrón de error $ e \ in \ mathbb F_2 ^ n $ tal que $ K e = H (m) $. Es decir, una firma es el ruido cuya multiplicación por una matriz de verificación de paridad produce un síndrome que es el hash de un mensaje.
Claves privadas y firma. Demasiado complicado para caber en los márgenes de esta publicación de crypto.se; consulte McBits para una estrategia de implementación moderna de firmas CFS y Niederreiter KEM, y Classic McEliece para una presentación NIST PQCRYPTO basada en ella (pero solo KEM, sin firmas), que también tiene sugerencias de parámetros concretos para niveles razonables de seguridad post-cuántica. (La presentación de pqsigRM a NIST PQCRYPTO también puede tener algunas ideas de implementación, pero su documentación de respaldo no menciona ataques de canal lateral o algoritmos de tiempo constante, y una breve mirada al código me hace sospechar).
Firmas basadas en celosía
Sea $ q $ un primo y sea $ F $ el campo $ \ mathbb Z / q \ mathbb Z $. Arregle un vector secreto $ s \ en F ^ n $, una muestra de vectores aleatorios uniformes $ a_i \ en F ^ n $ y una muestra de errores $ e_i \ in \ mathbb Z $ con alguna distribución $ \ chi $
El problema del aprendizaje computacional con errores , introducido por Regev en 2005 , es encontrar $ s $ dada la muestra $ (a_i, \ langle a_i, s \ rangle + e_i) \ en F ^ n \ veces F $ con una probabilidad no despreciable.
El problema del aprendizaje decisional con errores es distinguirlo de $ (a_i, v_i) $ para un $ v_i \ aleatorio uniforme en F $. Hay algunas variantes sobre el tema: por ejemplo, en el problema de aprendizaje del anillo con errores , reemplazamos el espacio vectorial $ F ^ n $ por el anillo $ F / (x ^ n + 1) $ cuando $ n $ es un potencia de dos, o $ F / (\ Phi (x)) $ para algún polinomio $ \ Phi (x) \ in F [x] $, que fue introducido por Lyubashevsky, Peikert y Regev en 2010 para admitir parámetros mucho más pequeños .
Este es un bosquejo del esquema de firma de aprendizaje con errores de Lyubahsevsky , derivado de la misma transformada Fiat-Shamir utilizada para derivar firmas de Schnorr , y en el que se basan los sistemas más nuevos, como la presentación qTESLA de NIST PQCRYPTO.
Parámetros. Campo $ F $; dimensiones $ n $, $ m $ y $ k $; consolidado $ d $; distribución acotada $ \ chi $ en $ \ mathbb Z ^ m $; una matriz $ n $ -por- $ m $ estándar $ A $ en $ F $; y una función aleatoria $ H \ colon \ {0,1 \} ^ * \ to \ {- 1,0, + 1 \} ^ k $ tal que $ \ lVert H (M) \ rVert_1 $ está acotado.
Claves públicas. La clave pública de Alice es una matriz de $ n $ -por- $ k $ $ T $ en $ F $.
Firmas. Una firma de Alice en un mensaje $ \ mu $ es un par de $ z \ in \ mathbb Z ^ m $ y $ c \ in \ mathbb Z ^ k $ tal que
- $ \ lVert z \ rVert ^ 2 = \ sum_i {z_i} ^ 2 $ es pequeño y
- $ c = H (\ underline {A z_q – T c_q} \ mathbin \ Vert \ mu) $, donde $ z_q $ y $ c_q $ son las proyecciones por componentes de $ z $ y $ c $ en $ F = \ mathbb Z / q \ mathbb Z $, y el subrayado es una codificación de cadena de bits canónica de $ F $.
(Para obtener detalles técnicos de lo que significa 'pequeño', consulte el documento).
Clave privada y firma. La clave privada de Alice es un $ m $ secreto -por- $ k $ matriz $ S $ en $ \ mathbb Z $ cuyos elementos se eligen uniformemente al azar de enteros como máximo $ d $ en valor absoluto. Sea $ S_q $ la proyección por componentes de la matriz $ S $ sobre $ F $. Alice calcula su clave pública por $ T = A S_q $. (Con una transformación apropiada de $ A $, esto no está lejos de la forma del problema del aprendizaje con errores).
Para firmar un mensaje $ \ mu $, Alice dibuja $ y \ in \ mathbb Z ^ m $ de $ \ chi $, calcula $ c = H (\ underline {A y_q} \ mathbin \ Vert \ mu) $ y $ z = S c + y $, y, con algún muestreo de rechazo en $ z $, revela $ (c, z) $.
Esto satisface el criterio (1) de firmas debido a los límites en $ S $, $ c = H (\ cdots) $ y $ y \ sim \ chi $.
Esto satisface el criterio (2) de firmas porque $ A z_q – T c_q = A S_q c_q + A y_q – A S_q c_q = A y_q $, entonces $ c = H (\ underline {A y_q} \ mathbin \ Vert \ mu) = H (\ subrayado {A z_q – T c_q} \ mathbin \ Vert \ mu) $.
Completar los detalles se deja como ejercicio para un osifrage menos cansado que éste, preferiblemente cuando no amanece.