# What is the sign bit for in Feige-Fiat-Shamir?

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?!

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?!

-

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.

-
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.

-