Protocolo Feig - Fiat - Shamir

El protocolo Feig-Fiat-Shamir es un protocolo de identificación de conocimiento cero , una generalización del anterior protocolo Fiat-Shamir , desarrollado por Uriel Feige , Amos Fiat [ ] y Adi Shamir . ) en 1986. Este esquema simple de implementar y comercialmente significativo fue patentado por los autores un año después de su desarrollo.

El protocolo permite que una parte (proveedor A) demuestre a otra parte (verificador B) que tiene información secreta sin revelar ni un solo bit de esa información.

La seguridad del protocolo se basa en la dificultad de extraer la raíz cuadrada módulo de un número compuesto n suficientemente grande cuya factorización se desconoce.

Hay algunas mejoras en la versión principal del protocolo para reducir la complejidad de las interacciones entre los participantes o para incorporar identidades en el esquema.

Además, el esquema de identificación Feig-Fiat-Shamir se puede convertir fácilmente en un esquema de firma.

Historia

En 1986, los científicos israelíes del Instituto Wyman Uriel Feige, Amos Fiat y Adi Shamir desarrollaron un esquema práctico de identificación de conocimiento cero que podría implementarse incluso en dispositivos con procesadores de bajo consumo, como tarjetas inteligentes, computadoras personales, documentos de identificación personal [ 1] . Por razones comerciales, los autores solicitaron una patente estadounidense el 9 de julio de 1986 . La Oficina de Patentes y Marcas de EE . UU. tenía que decidir en un plazo de seis meses sobre la decisión de emitir una orden para eliminar el régimen de secreto [2] [3] .

Apenas unos días antes de la expiración de un determinado período, la Oficina de Patentes emitió una orden prohibiendo cualquier divulgación o publicación de información sobre el protocolo, explicando esto como una amenaza para la seguridad nacional. Además, los autores tuvieron que notificar a todos los ciudadanos estadounidenses con conocimiento del esquema Feig-Fiat-Shamir que su divulgación podría dar lugar a sanciones graves: dos años de prisión o una multa de diez mil dólares. También fue necesario informar sobre todos los estados extranjeros a los que se divulgó información sobre el estudio [2] [3] .

En ese momento, Feige, Fiat y Shamir ya habían realizado numerosas presentaciones en universidades de Israel, Europa y los Estados Unidos, y se habían postulado para la conferencia de la Association for Computing Machinery , que se celebraría en Nueva York en mayo de 1987 [ 2] [3] .

Aunque los desarrolladores del protocolo esperaban que el Instituto Weizmann, donde se realizó el estudio, apelara la orden, enviaron una carta al comité de la conferencia explicando la situación. Después de eso, muchas organizaciones, como Bell Labs y The New York Times , se unieron rápidamente para resolver el problema. La mayor contribución la hizo la Agencia de Seguridad Nacional (NSA), que inicialmente desconocía la orden emitida. Después de que la NSA fuera informada al respecto, en dos días se canceló la orden [2] [3] .

Shamir habló en una conferencia de la Association for Computing Machinery el 26 de mayo [4] y 5 días después los autores recibieron una patente para el protocolo desarrollado [5] .

Esquema de identificación

A demuestra su conocimiento del secreto a B en el transcurso de las rondas sin revelar un solo bit del secreto en sí [1] . $s$ $t$

Selección de opciones del sistema

El centro de confianza T publica un gran número , donde y son números primos que se mantienen en secreto. También se seleccionan números enteros y - parámetros de seguridad [6] . $n=pq$ $pags$ $q$ $k$ $t$

Generación de secretos para los participantes

Cada participante elige números enteros aleatorios y bits aleatorios . $k$ $s_1, s_2, ..., s_k, 1 \leqslant s_i \leqslant n-1$ $k$ $b_1, b_2, ..., b_k$

Luego calcula . $v_i = (-1)^{b_i}\cdot (s_i^2)^{-1} \mod n, 1 \leqslant i \leqslant k$

El participante se identifica ante los demás utilizando los valores que actúan como su clave pública, mientras que la clave secreta solo la conoce el participante [6] . $(v_1, v_2, ..., v_k;n)$ $s = (s_1, s_2, ..., s_k)$

Acciones de protocolo dentro de una ronda

A elige un entero aleatorio $r, 1 \leqslant r \leqslant n-1$ calcula: y envía a la parte B. $x = r^2 \mod n$ $X$
B envía a A un vector de bits aleatorios donde o . $k$ $(e_1, e_2, ..., e_k)$ $e_i = 0$ $e_i = 1$
A calcula y envía B : . $y = r\cdot \prod^{k}_{i=1}s_i^{e_i} \mod n$
B evalúa: y comprueba que y [7] [6] . $z = y^2\cdot \prod^{k}_{i=1} v_i^{e_i} \mod n$ $z=\pm x\mod n$ $z \neq 0$

Seguridad

Lema 1: Si A y B siguen el protocolo, entonces B siempre acepta las pruebas A : Prueba: por definición

$z = y^2 \cdot \prod^{k}_{i=1} v_i^{e_i} = r^2 \cdot \prod^{k}_{i=1} (s_i^{2e_i} v_i^ {e_i}) = \pm r^2 = \pm x \mod n$

- Amos Fiat, Adi Shamir "Cómo probarse a sí mismo: soluciones prácticas a problemas de identificación y firma"

Suponiendo que la factorización es una tarea computacionalmente imposible, la probabilidad de un ataque de protocolo exitoso es . Un atacante puede intentar hacerse pasar por un usuario honesto adivinando los valores correctos de , preparándose para el primer paso y proporcionando en el tercer paso. Entonces B se asegurará de que . Pero la probabilidad de elegir correctamente los valores está en una ronda y, por tanto, en todo el protocolo [1] . $norte$ $2^{-kt}$ $e_{yo}$ $x = \pm r^2\cdot \prod^{k}_{i=1} v_i^{e_i} \mod n$ $y = r$ $z = y^2\cdot \prod^{k}_{i=1} v_i^{e_i} = r^2\cdot \prod^{k}_{i=1} v_i^{e_i} = \pm X$ $k$ $(e_1, e_2, ..., e_k)$ $2^{-k}$ $2^{-kt}$

Así, para alcanzar el nivel de seguridad , por ejemplo, basta con elegir y . Esto significa que solo uno de un millón de intentos por parte de un usuario deshonesto para engañar al verificador puede tener éxito. $2^{-20}$ $k = 5$ $t=4$

El protocolo prueba que A tiene su clave privada sin revelar ningún conocimiento de ella cuando y [1] . $k = O(\log \log n)$ $t = O(\log n)$

Ejemplo

Deje que el centro de confianza T elija números primos y publique . Configuración de seguridad del sistema: , . $p=683$ $q = 811$ $n=pq=553913$ $k = 3$ $t=1$
Para el participante A , se seleccionan números aleatorios: , y 3 bits: , , . $s_1 = 187$ $s_2 = 37411$ $s_3 = 5204$ $b_1 = 1$ $b_2 = 1$ $b_3 = 0$ se calculan los valores: , , . $v_1 = 307124$ $v_2 = 115268$ $v_3 = 403211$ Clave pública A : , clave privada: . $(307124, 115268, 403211; 553913)$ $(187, 37411, 5204)$
(a) A elige un número aleatorio , un bit aleatorio , calcula: y lo envía a B. $r=1337$ $segundo = 1$ $x=428083$

(b) B envía a A un vector de 3 bits: .

(0,1,0)

y=r\cdot s_2\mod n=166337

(d) B calcula: y acepta la prueba de A ya que y .

z = y^2\cdot v_2 \mod n = 428083

z=\pm x\mod n

z \neq 0

Mejoras y modificaciones del esquema de identificación

Puede negarse a elegir un número común para todos los participantes y permitir que cada uno de ellos elija el suyo. Sin embargo, seguirá siendo necesaria la existencia de un centro de confianza T para asociar a cada participante a su módulo [6] . $norte$
Para reducir la complejidad de la interacción entre A y B , puede reemplazar el primer mensaje enviado de A a B con un valor hash . En consecuencia, en la última iteración del protocolo, B tendrá que operar en lugar de [6] en sí mismo . $X$ $h(x)$ $h(z)$ $z$
El esquema se puede modificar para que se base en la identidad de cada participante. Para ello, el centro de confianza T asigna a cada usuario A una cadena identificativa única con información sobre el participante (por ejemplo, nombre, dirección, número de pasaporte, etc.). Luego el centro calcula los valores , donde debería ser indistinguible de una función aleatoria en tiempo polinomial. Luego, conociendo la factorización , el centro de confianza calcula y da salida a sus valores A. Los valores y se convierten, respectivamente, en las claves pública y privada del participante A , y las acciones posteriores se realizan de acuerdo con el esquema descrito anteriormente [7] [6] [3] . $I A}$ $v_i = f(I_A,i), 1 \leqslant i \leqslant k$ $F$ $norte$ $s_i = \sqrt {v_i^{-1}} \mod n$ $v_{i}$ $si}$
El protocolo descrito se puede realizar en paralelo. En este caso, los mensajes enviados de A a B y viceversa deben contener datos para todas las rondas al mismo tiempo. La ventaja de este enfoque es que le permite reducir la complejidad de la ejecución al reducir el número de iteraciones producidas. Tal esquema es seguro, pero debido a razones técnicas, pierde su propiedad de conocimiento cero. El hecho es que la ejecución paralela puede permitir que el verificador B deshonesto determine no al azar, sino como funciones del conjunto completo que le envió A en el primer paso. Si B hace esto usando una función hash unidireccional , entonces podrá obtener información que de otro modo podría calcular solo si supiera el secreto de A. Sin embargo, se cree que esta información no es "útil" (conociéndola, B no podrá hacerse pasar por A ante algún otro participante), lo que nos permite considerar que el esquema aún es confiable [1] [8] . $t$ $e_{es}$ $x_t$

Firma Feig - Fiat - Shamira

La parte B juega un papel muy importante en el esquema de identidad interactivo : genera valores aleatorios que evitan que el participante A haga trampa . $e_{yo}$

Para convertir el esquema de identificación en un esquema de firma, es suficiente cambiar esta acción B para usar una función hash secreta para calcular [7] [6] [3] . $h$ $e_{yo}$

Firma del mensaje

Sea A quiere firmar un mensaje . $metro$

A elige un número entero aleatorio y calcula: . $r, 1 \leqslant r \leqslant n-1$ $x = r^2 \mod n$
A calcula: . $e_i = h(x||m), 1 \leqslant i \leqslant k$
A calcula: . $y = r\cdot \prod^{k}_{i=1}s_i^{e_i} \mod n$
A envía a B un mensaje , firma y . $metro$ $(e_1, e_2, ..., e_k)$ $y$

Verificación de firma

Que B quiera comprobar la firma debajo del mensaje . $metro$

B calcula: . $x' = y^2\cdot \prod^{k}_{i=1} v_i^{e_i} \mod n$
B utiliza para calcular : . $X'$ $e'_i$ $e'_i = h(x'||m), 1 \leqslant i \leqslant k$
Si los valores calculados coinciden con la firma recibida de A , entonces B acepta la firma . $(e'_1, e'_2, ..., e'_k)$ $(e_1, e_2, ..., e_k)$ $metro$

Notas

↑ 1 2 3 4 5 Feige, Uriel; Fiat, Amós; Shamir, Adi. Pruebas de identidad de conocimiento cero (inglés) (enlace inaccesible) (1987). Consultado el 10 de noviembre de 2015. Archivado desde el original el 17 de noviembre de 2015.
↑ 1 2 3 4 Susan Landau. Zero Knowledge y el Departamento de Defensa (inglés) (1988). Consultado el 10 de noviembre de 2015. Archivado desde el original el 16 de enero de 2016.
↑ 1 2 3 4 5 6 Schneier B. Criptografía aplicada. Protocolos, Algoritmos, Códigos Fuente C (2002). Consultado el 10 de noviembre de 2015. Archivado desde el original el 20 de noviembre de 2015. (indefinido)
↑ Alfred V. Aho. STOC'87 19ª Conferencia Anual ACM sobre Teoría de la Computación . ACM Nueva York, NY, EE. UU. (1987).
↑ Método, aparato y artículo para identificación y firma ( 31 de mayo de 1987). Consultado el 11 de noviembre de 2015. Archivado desde el original el 21 de noviembre de 2015.
↑ 1 2 3 4 5 6 7 A. Menezes, P. van Oorschot y S. Vanstone. Manual de criptografía aplicada (inglés) (1996). Consultado el 10 de noviembre de 2015. Archivado desde el original el 8 de diciembre de 2015.
↑ 1 2 3 Amos Fiat, Adi Shamir. Cómo probarse a sí mismo: soluciones prácticas a problemas de identificación y firma (inglés) (enlace no disponible) (1986). Consultado el 10 de noviembre de 2015. Archivado desde el original el 3 de marzo de 2016.
↑ Gilles Brassard, Claude Crepeau, Moti Yung. Todo en NP se puede argumentar en conocimiento cero perfecto en un número limitado de rondas (inglés) (1989). Fecha de acceso: 13 de noviembre de 2015. Archivado desde el original el 17 de noviembre de 2015.

Literatura

Fiat A. , Shamir A. Cómo probarse a sí mismo: soluciones prácticas para problemas de identificación y firma // Avances en criptología - CRYPTO '86 :6.ª Conferencia internacional anual de criptología, Santa Bárbara, California, EE. UU., 1986, Actas / A. M. Odlyzko - Berlín , Heidelberg , Nueva York, NY , Londres [etc.] : Springer Berlin Heidelberg , 1987. - P. 186-194. — 490p. - ( Lecture Notes in Computer Science ; Vol. 263) - ISBN 978-3-540-18047-0 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-47721-7_12
Landau S. Zero Knowledge y el Departamento de Defensa // Avisos Amer . Matemáticas. soc. / F. Morgan - AMS , 1988. - vol. 35, edición. 1.- Pág. 5-12. — ISSN 0002-9920 ; 1088-9477
Feige U. , Fiat A. , Shamir A. Pruebas de identidad de conocimiento cero (inglés) // Revista de criptología / I. Damgård - Springer Science + Business Media , Asociación internacional para la investigación criptológica , 1988. - Vol. 1, edición. 2.- Pág. 77-94. — ISSN 0933-2790 ; 1432-1378 - doi:10.1007/BF02351717
Menezes A. J. , Oorschot P. v. , Vanstone S. A. Handbook of Applied Cryptography (Inglés) - CRC Press , 1996. - 816 p. - ( Matemáticas discretas y sus aplicaciones ) - ISBN 978-0-8493-8523-0
Schneier B. Criptografía aplicada. Protocolos, algoritmos, código fuente en lenguaje C = Criptografía Aplicada. Protocolos, Algoritmos y Código Fuente en C. - M. : Triumph, 2002. - 816 p. - 3000 copias. - ISBN 5-89392-055-4 .