signature – ¿Hay firmas basadas en la multiplicación de matrices con ruido?

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

  1. $ \ lVert z \ rVert ^ 2 = \ sum_i {z_i} ^ 2 $ es pequeño y
  2. $ 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.

Deja un comentario

Tu dirección de correo electrónico no será publicada.

Ir arriba