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$:

  1. A picks a random $r_i \in [0,n)$ and sends $x_i = r_i^2 (\mod n)$ to B.
  2. B sends a random binary vector $(e_{i1},…,e_{ik})$ to A.
  3. A sends to B :
    $$
    y_i = r_i \prod_{e_ij=1}s_j\mod n
    $$
  4. B checks that
    $$
    x_i = y_i \prod_{e_ij=1}v_j\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\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_ij=1}s_j\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_ij=1}v_j\mod n
    $$
  3. B verifies that the first kt bits of $f(m, x_1,…,x_t)$ are $e_{ij}$ matrix.