Factoring ⇒ ID (Feige–Fiat–Shamir)

Fully-black-box reduction · standard model · FFS88

Statement

In the Feige–Fiat–Shamir scheme over a Blum integer , the secret key is and the public key is with for independent uniform signs. In each of sequential rounds the prover sends for and a uniform sign, the verifier replies with , and the prover answers ; the verifier accepts the round iff and . FFS88 define zero-knowledge proofs of knowledge and prove that the scheme is one for suitably small , and that if factoring Blum integers is hard it is a secure identification scheme: no efficient adversary that has first taken part, as an arbitrary verifier, in polynomially many sequential executions with the honest prover makes the honest verifier accept with probability non-negligibly greater than — FFS88. With this is security against impersonation under active attack, and hence under passive attack — standard.

Sketch

The reduction samples the itself, so it answers the adversary’s executions as the honest prover. Two accepting answers to one under challenges give for , since is not a square modulo a Blum integer. The adversary’s view is independent of which square roots of the reduction holds, so with probability , and then is a prime factor of — standard.

Notes

  • The scheme modifies the identification scheme of FS86, which has no random signs — FFS88. FS86 also derive a signature scheme from it by replacing the verifier’s challenge with a hash of the commitment and the message (Fiat–Shamir) — FS86.
  • If factoring is hard, the version that runs the rounds in parallel releases no transferable information, a notion FFS88 introduce for this purpose — FFS88.