Heurística Fiat-Shamir

Técnica criptográfica

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 de moneda pública , es decir, las monedas aleatorias del verificador se hacen públicas a lo largo 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 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 accesible cuánticamente (QROM) por Don, Fehr, Majenz y Schaffner, ^[3] y simultáneamente por Liu y Zhandry. ^[4] En el caso de que no existan oráculos aleatorios, Shafi Goldwasser y Yael Tauman Kalai han demostrado que la heurística Fiat-Shamir es insegura . ^[5] La heurística Fiat-Shamir demuestra así una aplicación importante de los oráculos aleatorios. De manera más general, la heurística Fiat-Shamir también puede verse como la conversión de una prueba de conocimiento interactiva de moneda pública en una prueba de conocimiento no interactiva . Si la prueba interactiva se utiliza como herramienta de identificación, entonces la versión no interactiva se puede utilizar directamente como firma digital utilizando 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 los grupos multiplicativos ${\displaystyle \mathbb {Z} _{q}^{*}}$ , donde q es un número primo, y el teorema totient de Euler sobre la función totient de Euler φ .

Aquí hay una prueba interactiva de conocimiento de un logaritmo discreto en , basado en la firma de Schnorr . ^[6] Los valores públicos son y un generador g de , mientras que el valor secreto es el logaritmo discreto de y en base g . ${\displaystyle \mathbb {Z} _{q}^{*}}$ ${\displaystyle y\in \mathbb {Z} _{q}^{*}}$ ${\displaystyle \mathbb {Z} _{q}^{*}}$

1. Lena quiere demostrarle a Ole, el verificador, que sabe satisfacer sin revelar nada . ${\displaystyle x}$ ${\displaystyle y\equiv g^{x}}$ ${\displaystyle x}$
2. Lena elige un número al azar , lo calcula y se lo envía a Ole. ${\displaystyle v\in \mathbb {Z} _{q}^{*}}$ ${\displaystyle t=g^{v}}$ ${\displaystyle t}$
3. Ole elige uno al azar y se lo envía a Lena. ${\displaystyle c\in \mathbb {Z} _{q}^{*}}$
4. Lena calcula y regresa con Ole. ${\displaystyle r=v-cx{\bmod {\varphi }}(q)}$ ${\displaystyle r}$
5. Ole comprueba si . Esto se cumple porque y . ${\displaystyle t\equiv g^{r}y^{c}}$ ${\displaystyle g^{r}y^{c}\equiv g^{v-cx}g^{xc}\equiv g^{v}\equiv t}$ ${\displaystyle g^{\varphi (q)}\equiv 1}$

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

1. Lena quiere demostrar que lo sabe todo sin revelarlo . ${\displaystyle x}$ ${\displaystyle y\equiv g^{x}}$ ${\displaystyle x}$
2. Lena elige un número al azar y calcula . ${\displaystyle v\in \mathbb {Z} _{q}^{*}}$ ${\displaystyle t=g^{v}}$
3. Lena calcula , donde es una función hash criptográfica. ${\displaystyle c=H(g,y,t)}$ ${\displaystyle H}$
4. Lena calcula . La prueba resultante es el par . ${\displaystyle r=v-cx{\bmod {\varphi }}(q)}$ ${\displaystyle (t,r)}$
5. Cualquiera puede utilizar esta prueba para calcular y comprobar si . ${\displaystyle c}$ ${\displaystyle t\equiv g^{r}y^{c}}$

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 entonces seleccionar un valor determinado t para que se conozca el producto cx . ^[8]

Ampliación de este método

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

Véase también

• Modelo de oráculo aleatorio
• Prueba de conocimiento cero no interactiva
• Una aplicación en red de veto anónimo
• 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 clase en informática. Vol. 263. Springer Berlin Heidelberg. págs. 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 clase en informática. Vol. 1070. Springer Berlin Heidelberg. págs. 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 cuántico de oráculo aleatorio". Avances en criptología – CRYPTO 2019. Apuntes de clase en informática. Vol. 11693. Springer Cham. págs. 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.S2CID67769879  .​
4. Liu, Qipeng; Zhandry, Mark (2019). "Revisitando el Fiat-Shamir postcuántico". Avances en criptología – CRYPTO 2019. Apuntes de clase en informática. Vol. 11693. Springer Cham. págs. 326–355. doi :10.1007/978-3-030-26951-7_12. ISBN 978-3-030-26950-0.S2CID 75135227  .
5. Goldwasser, S.; Kalai, YT (octubre de 2003). "Sobre la (in)seguridad del paradigma Fiat-Shamir". 44.º Simposio anual IEEE sobre fundamentos de la informática, 2003. Actas . pp. 102–113. doi :10.1109/SFCS.2003.1238185. ISBN . 0-7695-2040-5. Número de identificación del sujeto  295289.
6. Camenisch, Jan; Stadler, Markus (1997). "Sistemas de prueba para enunciados generales sobre logaritmos discretos" (PDF) . Departamento de Ciencias de la Computación, ETH Zurich . Archivado desde el original (PDF) el 2020-08-17.
7. Bellare, Mihir; Rogaway, Phillip (1995). "Los oráculos aleatorios son prácticos: un paradigma para diseñar protocolos eficientes". ACM Press: 62–73. CiteSeerX 10.1.1.50.3345 .  {{cite journal}}: Requiere citar revista |journal=( ayuda )
8. Bernhard, David; Pereira, Olivier; Warinschi, Bogdan. "Cómo no demostrar lo que vales: trampas de la heurística Fiat-Shamir y aplicaciones a Helios" (PDF) . En Wang, Xiaoyun; Sako, Kazue (eds.). Avances en criptología – ASIACRYPT 2012 . págs. 626–643.|https://eprint.iacr.org/2016/771.pdf