Heurística de Fiat-Shamir

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.

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]

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]