Heurística de Fiat-Shamir

En criptografía , la heurística Fiat-Shamir es una técnica para tomar una prueba interactiva de conocimiento y crear una firma digital basada en ella. De esta manera, algún hecho (por ejemplo, el conocimiento de un cierto número secreto) puede probarse públicamente sin revelar información subyacente. La técnica se debe a Amos Fiat y Adi Shamir (1986). ^[1] Para que el método funcione, la prueba interactiva original debe tener la propiedad de ser moneda pública , es decir, las monedas aleatorias del verificador se hacen públicas a través del protocolo de prueba.

La heurística se presentó originalmente sin una prueba de seguridad; más tarde, Pointcheval y Stern ^[2] demostraron su seguridad contra los ataques de mensajes elegidos en el modelo de oráculo aleatorio , es decir, asumiendo que existen oráculos aleatorios . Este resultado fue generalizado al oráculo aleatorio de acceso cuántico (QROM) por Don, Fehr, Majenz y Schaffner, ^[3] y al mismo tiempo por Liu y Zhandry. ^[4] En el caso de que no existan oráculos aleatorios, la heurística Fiat-Shamir ha demostrado ser insegura por Shafi Goldwasser y Yael Tauman Kalai . ^[5]La heurística de Fiat-Shamir demuestra así una aplicación importante de oráculos aleatorios. De manera más general, la heurística de Fiat-Shamir también puede verse como una conversión de una prueba de conocimiento interactiva de moneda pública en una prueba de conocimiento no interactiva . Si la prueba interactiva se usa como una herramienta de identificación, entonces la versión no interactiva se puede usar directamente como una firma digital usando el mensaje como parte de la entrada al oráculo aleatorio.

Ejemplo

Para el algoritmo especificado a continuación, los lectores deben estar familiarizados con las leyes de la aritmética modular , especialmente con grupos multiplicativos de números enteros módulo n con prima q .

Aquí hay una prueba interactiva de conocimiento de un logaritmo discreto. ^[6]

1. Peggy quiere demostrarle a Victor el verificador que conoce : el logaritmo discreto de a la base (mod n ).${\displaystyle x}$${\displaystyle y=g^{x}}$${\displaystyle g}$
2. Ella elige al azar , calcula y envía a Víctor.${\displaystyle v\in \mathbb {Z} _{q}^{*}}$${\displaystyle t=g^{v}}$${\displaystyle t}$
3. Víctor elige uno al azar y se lo envía a Peggy.${\displaystyle c\in \mathbb {Z} _{q}^{*}}$
4. Peggy calcula y regresa a Victor.${\displaystyle r=v-cx{\bmod {\lambda }}(q)}$${\displaystyle r}$
5. Comprueba si . Esto es así porque .${\displaystyle t\equiv g^{r}y^{c}}$${\displaystyle g^{r}y^{c}=g^{v-cx}g^{xc}=g^{v}=t}$

La heurística de Fiat-Shamir permite reemplazar el paso interactivo 3 con un acceso al oráculo aleatorio no interactivo . En la práctica, podemos utilizar una función hash criptográfica en su lugar. ^[7]

1. Peggy quiere demostrar que lo sabe : el logaritmo discreto de a la base .${\displaystyle x}$${\displaystyle y=g^{x}}$${\displaystyle g}$
2. Ella elige al azar y calcula .${\displaystyle v\in \mathbb {Z} _{q}^{*}}$${\displaystyle t=g^{v}}$
3. Peggy calcula , donde es una función hash criptográfica.${\displaystyle c=H(g,y,t)}$${\displaystyle H()}$
4. Ella calcula . La prueba resultante es el par .${\displaystyle r=v-cx{\bmod {\lambda }}(q)}$${\displaystyle (t,r)}$
5. Cualquiera puede usar esta prueba para calcular y verificar si .${\displaystyle c}$${\displaystyle t\equiv g^{r}y^{c}}$

Como es un exponente de y estamos usando grupos cíclicos con orden , se puede calcular módulo , no módulo . es en el caso cuando es el primer orden de grupo.${\displaystyle r}$${\displaystyle g}$${\displaystyle q}$${\displaystyle \lambda (q)}$${\displaystyle q}$${\displaystyle \lambda (q)}$${\displaystyle q-1}$${\displaystyle q}$

Si el valor hash utilizado a continuación no depende del valor (público) de y , la seguridad del esquema se debilita, ya que un probador malintencionado puede seleccionar un cierto valor y para que se conozca el producto cx . ^[8]

Extensión de este método

Siempre que se pueda construir un generador aleatorio fijo con los datos conocidos por ambas partes, cualquier protocolo interactivo se puede transformar en uno no interactivo. ^{[ cita requerida ]}

Ver también

• Modelo de oráculo aleatorio
• Prueba de conocimiento cero no interactiva
• una aplicación en una red de veto anónima
• Lema de bifurcación

Referencias

1. Fiat, Amos; Shamir, Adi (1987). "Cómo demostrar su valía: soluciones prácticas a los problemas de identificación y firma" . Avances en criptología - CRYPTO '86 . Apuntes de conferencias en Ciencias de la Computación. Springer Berlín Heidelberg. 263 : 186-194. doi : 10.1007 / 3-540-47721-7_12 . ISBN 978-3-540-18047-0.
2. Pointcheval, David; Stern, Jacques (1996). "Pruebas de seguridad para esquemas de firma" . Avances en Criptología - EUROCRYPT '96 . Apuntes de conferencias en Ciencias de la Computación. Springer Berlín Heidelberg. 1070 : 387–398. doi : 10.1007 / 3-540-68339-9_33 . ISBN 978-3-540-61186-8.
3. Don, Jelle; Fehr, Serge; Majenz, Christian; Schaffner, Christian (2019). "Seguridad de la transformación Fiat-Shamir en el modelo Quantum Random-Oracle". Avances en Criptología - CRYPTO '19 . Apuntes de conferencias en Ciencias de la Computación. Springer Cham. 11693 : 356–383. arXiv : 1902.07556 . Código bibliográfico : 2019arXiv190207556D . doi : 10.1007 / 978-3-030-26951-7_13 . ISBN 978-3-030-26950-0.
4. Liu, Qipeng; Zhandry, Mark (2019). "Revisando Post-Quantum Fiat-Shamir". Avances en Criptología - CRYPTO '19 . Apuntes de conferencias en Ciencias de la Computación. Springer Cham. 11693 : 326–355. doi : 10.1007 / 978-3-030-26951-7_12 . ISBN 978-3-030-26950-0.
5. Goldwasser, S .; Kalai, YT (octubre de 2003). "Sobre la (In) seguridad del paradigma Fiat-Shamir". 44º Simposio Anual del IEEE sobre Fundamentos de las Ciencias de la Computación, 2003. Actas. : 102-113. doi : 10.1109 / SFCS.2003.1238185 . ISBN 0-7695-2040-5.
6. Camenisch, enero; Stadler, Markus (1997). "Sistemas de prueba para declaraciones generales sobre logaritmos discretos" (PDF) . Departamento de Ciencias de la Computación, ETH Zurich .
7. Bellare, Mihir; Rogaway, Phillip (1995). "Los oráculos aleatorios son prácticos: un paradigma para diseñar protocolos eficientes". Prensa ACM: 62–73. CiteSeerX 10.1.1.50.3345 . 
8. Bernhard, David; Pereira, Olivier; Warinschi, Bogdan. "Cómo no probarse a sí mismo: trampas de la heurística de Fiat-Shamir y aplicaciones a Helios" (PDF) . En Wang, Xiaoyun; Sako, Kazue (eds.). Avances en Criptología - ASIACRYPT 2012 . págs. 626–643.