Why is Feige-Fiat-Shamir not Zero Knowledge without sign bits?
The Feige-Fiat-Shamir (FFS) identification protocol is a proof of knowledge (PoK), in which the prover (Peggy) proves her knowledge the square roots of the given input to the verifier (Victor).

FFS want to discriminate PoK from proofs of language membership, in which Peggy proves that the input has some property (more formally, the input belongs to a certain language).

If we don't use the negative signs, it's possible that the inputs do not possess any square root. For instance, the number 20 does not have any square roots mod 21. Since distinguishing squares and non-squares is a famous hard problem, FFS avoid it by allowing the input to be the plus or minus of some number squared. In their own words (changed a bit):


  By allowing $v_i$ to  be either plus or minus a square modulo a Blum integer, we make sure that $v_i$ can range over all the numbers with Jacobi symbol $+1 \bmod n$ and  thus the $s_i$ exist (from V's point of view) regardless of $v_i$ character, as required in unrestricted input zero-knowledge proofs of knowledge.


By unrestricted input zero-knowledge proofs of knowledge, they mean a ZK PoK whose corresponding proof of language membership is trivial; i.e. V can by himself decide that the input is the plus or minus of some square (by just checking the Jacobi symbol).