Zero-knowledge proofs of identity

Let us introduce two new protagonists:

• Peggy wishes to prove to Victor that she knows a secret.

• Victor wishes to verify that Peggy knows the secret.

The proof will be based on challenge-response pairs and it will be probabilistic.

The probability that an impersonator is accepted (false proof) decreases as more challenge-response pairs are used.

One of the first published ways to do it uses (again) the hardness of factoring large integers.

Again, the underlying problem is computing square roots modulo $n = pq$.

Feige-Fiat-Shamir scheme