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:


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.
Victor chooses numbers $a_1, \cdots, a_k$ where $a_i$ equals 0 or 1. Victor sends these numbers to Peggy.
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.
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?!
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.