Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The Feige-Fiat-Shamir identity scheme is based on a ZKP assuming that square roots are "hard" modulo an integer of unknown factorization. The "parallel version" of this protocol includes a "sign bit" and the wikipedia article claims that the older version of the protocol leaked a bit, so the sign bit was added. Here is the protocol as given by wikipedia:

  1. Peggy chooses a random integer $r$, a random sign $s\in\{-1,1\}$ and computes $x \equiv s\cdot r^2 \pmod{n}$. Peggy sends $x$ to Victor.
  2. Victor chooses numbers $a_1, \cdots, a_k$ where $a_i$ equals 0 or 1. Victor sends these numbers to Peggy.
  3. Peggy computes $y \equiv rs_1^{a_1}s_2^{a_2} \cdots s_k^{a_k}\pmod{n}$. Peggy sends this number to Victor.
  4. Victor checks that $y^2 \equiv \pm\, x v_1^{a_1}v_2^{a_2} \cdots v_k^{a_k}\pmod{n}$.

I cannot find the old version of FFS, nor do I see what bit is leaked without the sign bit added. It must be something related to a Jacobi symbol?!

The relevant quote from Wikipedia that I'm asking about is:

In an early version, the Fiat-Shamir-Scheme (on which the Feige-Fiat-Shamir-Scheme was based), one bit of information was leaked. By the introduction of the sign s even this bit was concealed resulting in a zero-knowledge-protocol.

So if this sign value $s$ were removed, what would be leaked?

Note: After reading Samuel's response, I wonder if the wikipedia version of the scheme is actually correct?!

share|improve this question
up vote 4 down vote accepted

The original 1986 Fiat-Shamir paper can be found here. The subsequent Feige-Fiat-Shamir 1988 paper can be found here, and contains the answer (Section 3):

The $S_j$ (which are witnesses to the quadratic residuosity character of the $I_j$) are effectively hidden by the difficulty of extracting square roots $\bmod n$, and thus A can establish his identity by proving that he knows these $S_j$. By allowing $I_j$ to be either plus or minus a square modulo a Blum integer, we make sure that $I_j$ can range over all the numbers with Jacobi symbol $+1 \bmod n$ and thus the $S_j$ exist (from B’s point of view) regardless of $I_j$’s character, as required in zero knowledge proofs of knowledge.

share|improve this answer
The section you cite seems to be a (slightly) different scheme from the one cited in wikipedia (the wikipedia entry doesn't even contain the $I_j$'s; I wonder if it's correct?!) – Fixee Sep 1 '11 at 23:37
In the paragraph following what I quoted, they mention their use of $1/S_i^2$ instead of simply $S_i^2$ as having "no theoretical significance, but optimizes the practical implementations of the scheme". Wikipedia seems to use $S_i^2$, possibly to remain coherent with the original Fiat-Shamir approach. – Samuel Neves Sep 1 '11 at 23:52
It's more than this. The FFS scheme equiprobably multiplies each $1/S_i^2$ by -1 or 1. Since -1 is a non-square with Jacobi symbol 1 (because $n$ is a Blum integer), this preserves the Jacobi symbol while expanding the range of values produced. I don't know why they do this (and the wikipedia version doesn't do it at all). – Fixee Sep 2 '11 at 2:41
You're right, I missed the missing sign on the setup. The signed $I_j$ appear to only be required to make the scheme unrestricted input zero knowledge. This just means that the prover leaks nothing. Without the sign, we know a priori that $I_j$ is a quadratic residue modulo $n$, which would be a hard computational problem otherwise. The authors do mention some practical applications of this distinction later on in the JoC version of the paper, particularly when applying (public) transformations to $I_j$. – Samuel Neves Sep 2 '11 at 6:27
Hm, I'd never heard of "unrestricted input" ZK before. But in the excerpt you quoted above, FFS say that we must have our $I_j$ range over all Jacobi symbol +1 values for ZKPs of knowledge. They don't mention "unrestricted input" (perhaps they have some definition of ZK that requires it I guess). – Fixee Sep 2 '11 at 7:07

Without a sign the verifier learns that the number he received is a QR modulo n. Whether a number is a QR is a hard problem as he does not know the factors of n.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.