Introduction to Cryptography with Coding Theory, 3rd Edition

19.2 The Feige-Fiat-Shamir Identification Scheme

The preceding protocol requires several communications between Peggy and Victor. The Feige-Fiat-Shamir method reduces this number and uses a type of parallel verification. This then is used as the basis of an identification scheme.

Again, let $n=pq$ be the product of two large primes. Peggy has secret numbers $s_1\text{,}\dots \text{,}{s}_k$. Let $v_i\equiv s_i^{-2}(\mathrm{m}\mathrm{o}\mathrm{d}n)$ (we assume $gcd(s_i\text{,}n)=1$). The numbers $v_i$ are sent to Victor. Victor will try to verify that Peggy knows the numbers $s_1\text{,}\dots \text{,}{s}_k$. Peggy and Victor proceed as follows:

1. Peggy chooses a random integer $r$, computes $x\equiv r^2(\mathrm{m}\mathrm{o}\mathrm{d}n)$ and sends $x$ to Victor.

2. Victor chooses numbers $b_1\text{,}\dots \text{,}{b}_k$ with each $b_i\in \{0\text{,}1\}$. He sends these to Peggy.

3. Peggy computes $y\equiv r{s}_1^{b_1}{s}_2^{b_2}\cdots s_k^{b_k}(\mathrm{m}\mathrm{o}$