<p>The Feige-Fiat-Shamir (FFS) identification protocol is a <strong>proof of knowledge</strong> (PoK), in which the prover (Peggy) proves her knowledge the square roots of the given input to the verifier (Victor).</p>

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

<p>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 <a href="http://en.wikipedia.org/wiki/Quadratic_residuosity_problem" rel="nofollow">famous hard problem</a>, FFS avoid it by allowing the input to be the plus or minus of some number squared. In <a href="http://www.springerlink.com/content/9gl5112723626462/" rel="nofollow">their own words</a> (changed a bit):</p>

<blockquote>
  <p>By allowing $v_i$ to  be either plus or minus a square modulo a <a href="http://en.wikipedia.org/wiki/Blum_integer" rel="nofollow">Blum integer</a>, we make sure that $v_i$ can range over all the numbers with <a href="http://en.wikipedia.org/wiki/Jacobi_symbol" rel="nofollow">Jacobi symbol</a> $+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.</p>
</blockquote>

<p>By <strong>unrestricted input zero-knowledge proofs of knowledge</strong>, 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).</p>

CC BY-SA 3.0
2011-09-07T21:12:23.633Z
Thanks for the answer, but I still don't follow: without signs the Jacobi symbol is +1.  With the signs, the Jacobi symbol is +1.  You say above "if we don't use the negative signs, it's possible that the inputs do not possess any square root."  How is that possible?  The input for the verifier is a list of squares that (assuming an honest prover) always have square roots.
Fixee
CC BY-SA 3.0
2011-09-07T21:12:53.150Z
Second question: are you saying that the signs are present only for the proof to go through?  Or is there an actual attack if they are omitted?
Fixee
CC BY-SA 3.0
2011-09-07T22:56:42.387Z
@Fixee: Assume a cheating prover who chooses his public keys ($v_i$'s) not according to the protocol; say a random value whose Jaccobi symbol is +1. The (poor) verifier has no way of saying whether $v_i$'s have square roots or not. The only way is to run the protocol, and get the help from the prover. That is, the prover is both proving her knowledge of the $s_i$'s, AND giving a proof of language membership (i.e. $v_i$'s belong to the lanuage QR of quadratic residues.) For some reason, FFS liked to separate this type of proof from "unrestricted input" proofs. I see this as a mere technicality.
Sadeq Dousti
CC BY-SA 3.0
2011-09-07T02:04:50.847Z
2011-09-09T17:55:06.140Z
2011-09-09T17:55:06.140Z
Sadeq Dousti
<p>In <a href="http://www.cacr.math.uwaterloo.ca/hac/about/chap10.pdf" rel="nofollow">chapter 10 of HAC (10.4.2)</a>, 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).</p>

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

<p>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$.</p>

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

<p>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, <a href="http://www.cs.princeton.edu/courses/archive/spring10/cos433/lec17new.pdf" rel="nofollow">Boaz Barak's lecture notes</a>).</p>

<p>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</p>

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

<p><strong>My Question:</strong> 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.</p>

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

<cr.crypto-security><proofs><zero-knowledge>
Why is Feige-Fiat-Shamir not Zero Knowledge without sign bits?
Fixee
# Why is Feige-Fiat-Shamir not Zero Knowledge without sign bits?

(Asked by: username_0 on 2011-09-06)

In [chapter 10 of HAC (10.4.2)](http://www.cacr.math.uwaterloo.ca/hac/about/chap10.pdf), 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](http://www.cs.princeton.edu/courses/archive/spring10/cos433/lec17new.pdf)).

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.

**Tags:** cr.crypto-security, proofs, zero-knowledge

---

## 1 answers

### Answer by username_1 on 2011-09-07. Score: 8 | Accepted answer

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](http://en.wikipedia.org/wiki/Quadratic_residuosity_problem), FFS avoid it by allowing the input to be the plus or minus of some number squared. In [their own words](http://www.springerlink.com/content/9gl5112723626462/) (changed a bit):

> By allowing $v\_i$ to be either plus or minus a square modulo a [Blum integer](http://en.wikipedia.org/wiki/Blum_integer), we make sure that $v\_i$ can range over all the numbers with [Jacobi symbol](http://en.wikipedia.org/wiki/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).

> **Comments:**
> **username_0**: Thanks for the answer, but I still don't follow: without signs the Jacobi symbol is +1.  With the signs, the Jacobi symbol is +1.  You say above "if we don't use the negative signs, it's possible that the inputs do not possess any square root."  How is that possible?  The input for the verifier is a list of squares that (assuming an honest prover) always have square roots.  
> **username_0**: Second question: are you saying that the signs are present only for the proof to go through?  Or is there an actual attack if they are omitted?  
> **username_1**: @Fixee: Assume a cheating prover who chooses his public keys ($v_i$'s) not according to the protocol; say a random value whose Jaccobi symbol is +1. The (poor) verifier has no way of saying whether $v_i$'s have square roots or not. The only way is to run the protocol, and get the help from the prover. That is, the prover is both proving her knowledge of the $s_i$'s, AND giving a proof of language membership (i.e. $v_i$'s belong to the lanuage QR of quadratic residues.) For some reason, FFS liked to separate this type of proof from "unrestricted input" proofs. I see this as a mere technicality.  

---

