Esquema de identificación Feige–Fiat–Shamir

En criptografía , el esquema de identificación Feige-Fiat-Shamir es un tipo de prueba paralela de conocimiento cero desarrollado por Uriel Feige , Amos Fiat y Adi Shamir en 1988. Como todas las pruebas de conocimiento cero, permite que una parte, el Probador, pruebe a otra parte, el Verificador, que posee información secreta sin revelarle al Verificador cuál es esa información secreta. Sin embargo, el esquema de identificación Feige-Fiat-Shamir utiliza aritmética modular y un proceso de verificación paralelo que limita la cantidad de comunicaciones entre el Probador y el Verificador.

Configuración

Siguiendo una convención común , llamaremos al demostrador Peggy y al verificador Víctor.

Elija dos números primos grandes p y q y calcule el producto n = pq . Cree números secretos coprimos con n . Calcule . Peggy y Victor reciben mientras y se mantienen en secreto. Luego, a Peggy se le envían los números . Estos son sus números de inicio de sesión secretos. Peggy le envía los números a Victor cuando ella desea identificarse ante Victor. Victor no puede recuperar los números de Peggy a partir de sus números debido a la dificultad de determinar una raíz cuadrada modular cuando se desconoce la factorización del módulo. ${\displaystyle s_{1},\cdots ,s_{k}}$ ${\displaystyle v_{i}\equiv s_{i}^{2}{\pmod {n}}}$ ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle s_{i}}$ ${\displaystyle v_{i}}$ ${\displaystyle s_{i}}$ ${\displaystyle v_{i}}$

Procedimiento

1. Peggy elige un entero aleatorio , un signo aleatorio y calcula . Peggy se lo envía a Víctor. ${\displaystyle r}$ ${\displaystyle s\in \{-1,1\}}$ ${\displaystyle s\cdot x\equiv r^{2}{\pmod {n}}}$ ${\displaystyle x}$
2. Víctor elige números donde 0 o 1 son iguales. Víctor envía estos números a Peggy. ${\displaystyle a_{1},\cdots ,a_{k}}$ ${\displaystyle a_{i}}$
3. Peggy calcula . Peggy envía este número a Víctor. ${\displaystyle y\equiv rs_{1}^{a_{1}}s_{2}^{a_{2}}\cdots s_{k}^{a_{k}}{\pmod {n}}}$
4. Víctor comprueba eso y eso ${\displaystyle y^{2}{\pmod {n}}\equiv \pm \,xv_{1}^{a_{1}}v_{2}^{a_{2}}\cdots v_{k}^{a_{k}}{\pmod {n}}}$ ${\displaystyle x\neq 0.}$

Este procedimiento se repite con diferentes valores y hasta que Víctor está satisfecho de que Peggy efectivamente posee las raíces cuadradas modulares ( ) de sus números. ${\displaystyle r}$ ${\displaystyle a_{i}}$ ${\displaystyle s_{i}}$ ${\displaystyle v_{i}}$

Seguridad

En el procedimiento, Peggy no le da ninguna información útil a Víctor. Se limita a demostrarle que tiene los números secretos sin revelarle cuáles son. Cualquiera que intercepte la comunicación entre Peggy y Víctor sólo obtendrá la misma información. El espía no obtendrá nada útil sobre los números secretos de Peggy. ^{[ cita requerida ]}

Supongamos que Eve ha interceptado los números de Victor pero no sabe cuáles son los números de Peggy. Si Eve quiere intentar convencer a Victor de que ella es Peggy, tendría que adivinar correctamente cuáles serán los números de Victor. Luego elige un , lo calcula y se lo envía a Victor. Cuando Victor envía , Eve simplemente le devuelve su . Victor está satisfecho y concluye que Eve tiene los números secretos. Sin embargo, la probabilidad de que Eve adivine correctamente cuáles serán los de Victor es de 1 en . Al repetir el procedimiento veces, la probabilidad se reduce a 1 en . Para y la probabilidad de hacerse pasar por Peggy con éxito es menor que 1 en 1 millón. ${\displaystyle v_{i}}$ ${\displaystyle s_{i}}$ ${\displaystyle a_{i}}$ ${\displaystyle y}$ ${\displaystyle x\equiv y^{2}v_{1}^{-a_{1}}v_{2}^{-a_{2}}\cdots v_{k}^{-a_{k}}{\pmod {n}}}$ ${\displaystyle x}$ ${\displaystyle a_{i}}$ ${\displaystyle y}$ ${\displaystyle a_{i}}$ ${\displaystyle 2^{k}}$ ${\displaystyle t}$ ${\displaystyle 2^{kt}}$ ${\displaystyle k=5}$ ${\displaystyle t=4}$

Referencias

• Feige, Uriel; Fiat, Amos; Shamir, Adi (1988). "Pruebas de identidad de conocimiento cero". Revista de criptología . 1 (2): 77–94. doi : 10.1007/BF02351717 . S2CID  2950602.
• Trappe, Wade; Washington, Lawrence C. (2003). Introducción a la criptografía con teoría de codificación . Upper Saddle River: Prentice-Hall. págs. 231–233. ISBN 0-13-061814-4.
• Wong, Chung Kei; Lam, Simon S (agosto de 1999). "Firmas digitales para flujos y multidifusiones" (PDF) . Transacciones IEEE/ACM sobre redes . 7 (4).(eFFS, esquema ampliado Feige-Fiat-Shamir)