What is the sign bit for in Feige-Fiat-Shamir?
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.