Why is Feige-Fiat-Shamir not Zero Knowledge without sign bits?

Question

In chapter 10 of HAC (10.4.2), we see the well-known Feige-Fiat-Shamir identification protocol based on a zero-knowledge proof using the (presumed) difficulty of extracting square roots modulo a composite that is hard to factor. I'll give the scheme in my own words (and hopefully get it right).

Let's start with a simpler scheme: let $n$ be a Blum integer (so $n=pq$ and each of $p$ and $q$ is 3 mod 4) of sufficiently large size that factoring is intractible. Since $n$ is a Blum integer, half of the elements of $Z_n^*$ have Jacobi symbol +1 and the other half have -1. For the +1 elements, half of those have square roots, and each element having a square root has four of them, exactly one being itself a square.

Now Peggy selects a random element $s$ from $Z_n^*$ and sets $v=s^2$. She then sends $v$ to Victor. Next is the protocol: Victor wishes to verify that Peggy knows a square root of $v$ and Peggy wishes to prove it to him without divulging anything about $s$ beyond the fact she knows such an $s$.

1. Peggy chooses a random $r$ in $Z_n^*$ and sends $r^2$ to Victor.
2. Victor equiprobably sends $b=0$ or $b=1$ back to Peggy.
3. Peggy sends $rs^b$ to Victor.

Victor can verify that Peggy has sent the correct answer by squaring what he receives and comparing to the correct result. Of course, we repeat this interaction to reduce the chance that Peggy is just a lucky guesser. This protocol is claimed to be ZK; a proof can be found in various places (eg, Boaz Barak's lecture notes).

When we extend this protocol to make it more efficient it is called Feige-Fiat-Shamir; it's very similar to the above. We start Peggy with $k$ random values $s_1\cdots s_k$ and random signs $t_1 = \pm 1, \cdots t_k = \pm 1$ she publishes their squares as $v_1=t_1s_1^2, \cdots, v_k = t_ks_k^2$. In other words, we randomly negate some of the $v_i$. Now

1. Peggy chooses a random $r$ in $Z_n^*$ and sends $r^2$ to Victor.
2. Victor equiprobably sends $k$ values $b_i$ from $\{0,1\}$ back to Peggy.
3. Peggy sends $r\Pi_{i=1}^ks_i^{b_i}$ to Victor.

My Question: Why are the $t_i$ sign bits necessary? In parentheses, HAC notes that they are there as a technical requirement required to prove that no secret information is leaked. The wikipedia page for Feige-Fiat-Shamir (which gets the protocol wrong) implies that without this a bit is leaked.

I cannot find an attack that extracts anything from Peggy if she omits the signs.

Answer 1

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