Heurística de 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 determinado número secreto) puede demostrarse 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 lo largo del protocolo de prueba.

La heurística se presentó originalmente sin 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 cuántico accesible (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 oráculos aleatorios. De manera más general, también se puede considerar que la heurística Fiat-Shamir convierte 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 del totiente de Euler sobre la función totiente de Euler φ .

Aquí hay una prueba interactiva de conocimiento de un logaritmo discreto en , basada 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 con 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 revelarlo . ${\displaystyle x}$ ${\displaystyle y\equiv g^{x}}$ ${\displaystyle x}$
2. Lena elige un mensaje aleatorio , 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 es válido 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 3 interactivo con un acceso al oráculo aleatorio no interactivo . En la práctica, podemos utilizar una función hash criptográfica . ^[7]

1. Lena quiere demostrar que lo sabe sin revelarlo . ${\displaystyle x}$ ${\displaystyle y\equiv g^{x}}$ ${\displaystyle x}$
2. Lena elige al azar y calcula . ${\displaystyle v\in \mathbb {Z} _{q}^{*}}$ ${\displaystyle t=g^{v}}$
3. Lena calcula , donde hay 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 malicioso puede seleccionar un cierto valor 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, cualquier protocolo interactivo se puede transformar en uno no interactivo. ^{[ cita necesaria ]}

Ver también

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

Referencias

1. Fiat, Amós; Shamir, Adi (1987). "Cómo demostrar su valía: soluciones prácticas a problemas de identificación y firma". Avances en criptología - CRYPTO '86 . Apuntes de conferencias sobre informática. vol. 263. Springer Berlín 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 conferencias sobre informática. vol. 1070. Springer Berlín 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, cristiano; Schaffner, cristiano (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 conferencias sobre informática. vol. 11693. Springer Cham. págs. 356–383. arXiv : 1902.07556 . Código Bib : 2019arXiv190207556D. doi :10.1007/978-3-030-26951-7_13. ISBN 978-3-030-26950-0. S2CID  67769879.
4. Liu, Qipeng; Zhandry, Mark (2019). "Revisando el Fiat-Shamir poscuántico". Avances en Criptología – CRYPTO 2019 . Apuntes de conferencias sobre 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 del IEEE sobre fundamentos de la informática, 2003. Actas . págs. 102-113. doi :10.1109/SFCS.2003.1238185. ISBN 0-7695-2040-5. S2CID  295289.
6. Camenisch, enero; Stadler, Markus (1997). "Sistemas de prueba para enunciados generales sobre logaritmos discretos" (PDF) . Departamento de Informática, ETH Zurich . Archivado desde el original (PDF) el 17 de agosto de 2020.
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 .  {{cite journal}}: Citar diario requiere |journal=( ayuda )
8. Bernhard, David; Pereira, Olivier; Warinschi, Bogdan. "Cómo no demostrar su valía: 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