Fiat-Shamir Heuristic

Fiat, Amos, and Adi Shamir. “How to prove yourself: Practical solutions to identification and signature problems.” Conference on the theory and application of cryptographic techniques. Berlin, Heidelberg: Springer Berlin Heidelberg, 1986.

Trust Setup

f: A pseudo random function
I: Information

1. Compute the values $v_j=f(I,j)$ for small values of $j$.
2. Pick $k$ distinct values of $j$ for which $v_j$ is a quadratic residue (mod n) and compute the smallest square root $s_j$, of $v_j^{-1}$ (mod n).
3. Issue $I$ , the k $s_j$ values, and their indices.

Interactive Protocol

1. A sends $I$ to B.
2. B generates $v_j=f(I,j)$ for $j=1,...,k$.

Repeat steps 3 to 6 for $i=1,...,t$:

3. A picks a random $r_i\in [0,n)$ and sends $x_i=r_i^2(\mathrm{mod}n)$ to B.
4. B sends a random binary vector $(e_{i1},...,e_{ik})$ to A.
5. A sends to B :
   $$y_i=r_i\prod _{e_{i}j=1}{s}_j\mathrm{mod}n$$
6. B checks that
   $$x_i=y_i\prod _{e_{i}j=1}{v}_j\mathrm{mod}n$$

Non-interactive Protocol (Signature)

To sign a message $m$:

1. A picks random $r_1,...,r_t\in [O,n)$ and computes $x_i=r_i^2\mathrm{mod}n$.
2. A computes $f(m,x_1,...,x_t)$and uses its first kt bits as $e_{ij}$ values.
3. A computes
   $$y_i=r_i\prod _{e_{i}j=1}{s}_j\mathrm{mod}n$$
   and sends $I$,$m$, the $e_{ij}$ matrix and all the $y_i$ to B.

To verify A’s signature on $m$:

1. B computes $v_j=f(I,j)$ for $j=1,...,k$.
2. B computes
   $$x_i=y_i\prod _{e_{i}j=1}{v}_j\mathrm{mod}n$$
3. B verifies that the first kt bits of $f(m,x_1,...,x_t)$ are $e_{ij}$ matrix.