Heurística de Fiat-Shamir

La heurística de Fiat-Shamir es una técnica criptográfica para a partir de una prueba de conocimiento cero interactiva obtener una prueba de conocimiento cero no interactiva. Si la prueba interactiva es un protocolo de identificación, entonces la versión no-interactiva puede ser usada directamente como una firma digital. Esta técnica fue aportada por Amos Fiat y Adi Shamir en 1986.^[1]​

Mecanismo

La heurística sigue los siguientes pasos:^[2]​

• El probador genera un mensaje de compromiso indicando que conoce el secreto.
• El probador toma el compromiso y otra información como entradas y devuelve el desafío aplicando alguna función hash criptográfica
• El probador calcula la respuesta y envía la transcripción que incluye el compromiso, el desafío y la respuesta al verificador.

Seguridad

La heurística fue presentada originalmente sin una prueba de seguridad; más tarde David Pointcheval y Jacques Stern^[3]​ probaron su seguridad contra un ataque de mensaje escogido en el modelo de oráculo aleatorio, esto es bajo la suposición de que el oráculo aleatorio existe (no se pueden predecir los resultados de una función hash). En caso de no existir el oráculo aleatorio se ha probado que es inseguro.^[4]​

Ejemplo

Veamos un ejemplo con la prueba interactiva sobre el conocimiento del logaritmo discreto.^[5]​

1. Alicia quiere probar a Bob que conoce ${\displaystyle x}$  el cual es el logaritmo discreto de ${\displaystyle y=g^{x}}$  para la base ${\displaystyle g}$ .
2. Alicia coge un número aleatorio ${\displaystyle v\in \mathbb {Z} _{q}}$ , calcula ${\displaystyle t=g^{v}}$  y envía a Bob ${\displaystyle t}$ .
3. Bob coge un número aleatorio ${\displaystyle c\in \mathbb {Z} _{q}^{*}}$  y se lo envía a Alicia.
4. Alicia calcula ${\displaystyle r=v-cx}$  y devuelve ${\displaystyle r}$  a Bob.
5. Bob comprueba que ${\displaystyle t\equiv g^{r}y^{c}}$  (lo cual sucede solo si ${\displaystyle g^{r}y^{c}=g^{v-cx}g^{xc}=g^{v}=t}$ ).

La heurística de Fiat-Shamir lo convierte en:^[6]​

1. Alicia quiere probar a Bob que conoce ${\displaystyle x}$  el cual es el logaritmo discreto de ${\displaystyle y=g^{x}}$  para la base ${\displaystyle g}$ .
2. Alicia coge un número aleatorio ${\displaystyle v\in \mathbb {Z} _{q}}$  y calcula ${\displaystyle t=g^{v}}$ .
3. Alicia calcula ${\displaystyle c=H(g,y,t)}$ , donde ${\displaystyle H()}$  es una función hash criptográfica.
4. Alicia calcula ${\displaystyle r=v-cx}$ . El resultado de la prueba es el par ${\displaystyle (t,r)}$ .
5. Cualquiera puede comprobar que ${\displaystyle t\equiv g^{r}y^{c}}$  ya que ${\displaystyle g^{r}y^{c}=g^{v-cx}g^{xc}=g^{v}=t}$ .

Se ha demostrado que si el valor hash usado no depende del valor (público) de y, la seguridad del esquema es débil ya que un probador malicioso puede entonces seleccionar cierto x tal que el producto de cx es conocido.^[7]​

Referencias

1. Amos Fiat and Adi Shamir: How to Prove Yourself: Practical Solutions to Identification and Signature Problems. CRYPTO 1986: pp. 186-194
2. Verifiable Voting Systems el 15 de octubre de 2013 en Wayback Machine.. Thea Peacock et ali.
3. David Pointcheval and Jacques Stern: Security Proofs for Signature Schemes. EUROCRYPT 1996: pp. 387-398
4. Shafi Goldwasser and Yael Kalai: On the (In)security of the Fiat-Shamir Paradigm. FOCS 2003: pp. 102
5. Camenisch, Jan; Stadler, Markus (1997). «Proof Systems for General Statements about Discrete Logarithms». Dept. of Computer Science, ETH Zurich. 
6. Bellare, Mihir; Rogaway, Phillip (1993). «Random Oracles are Practical: A Paradigm for Designing Efficient Protocols». ACM. 
7. Bernhard, David; Pereira, Olivier; Warinschi, Bogdan. «How not to Prove Yourself: Pitfalls of the Fiat-Shamir Heuristic and Applications to Helios». En Wang, Xiaoyun; Sako, Kazue, eds. Advances in Cryptology – ASIACRYPT 2012. pp. 626-643. 

•   Datos: Q5446341