<p>I have not read the details of their flawed protocol, but I've heard about it on several occasions.  My impression was that their error was in how they used the PRG seed.  Their protocol puts the pseudorandom generator (PRG) seed in the public common reference string, and they attempt to argue that PRG security forces some statistical property of the PRG output to hold even with a known seed.  While it is possible to do this in a sound way (the signature schemes of Hohenberger and Waters <a href="https://link.springer.com/chapter/10.1007/978-3-642-03356-8_38?from=SL" rel="nofollow noreferrer">here</a> and <a href="https://link.springer.com/chapter/10.1007/978-3-642-01001-9_19?from=SL" rel="nofollow noreferrer">here</a> spring to mind), something went wrong in their argument.</p>

CC BY-SA 4.0
2010-10-13T18:07:10.250Z
2022-03-22T10:25:39.797Z
2022-03-22T10:25:39.797Z
David Cash
<p><a href="http://portal.acm.org/citation.cfm?id=62222">Blum, Micali, and Feldman</a> (BFM) put forward a new (cryptographic) model, in which all parties (honest or adversarial) have access to some string. The string is assumed to be selected according to some distribution (usually, uniform distribution) by a trusted party. It is called the <em>reference string</em>, and the model is aptly named the <em>common reference string</em> (CSR) model.</p>

<p>The model allows us to perform many interesting interactive protocols <em>non-interactively</em>, replacing queries by bits from the reference string. In particular, <strong>zero-knowledge</strong> proofs for any <strong>NP</strong> language can be conducted non-interactively, giving rise to the notion of <em>non-interactive zero-knowledge</em> (NIZK).</p>

<p>NIZK has a lot of applications, such as providing a method for realizing public-key cryptosystems secure against <a href="http://en.wikipedia.org/wiki/Chosen-ciphertext_attack">(adaptive) chosen-ciphertext attacks</a>.</p>

<p>BFM first proved the existence of a single-theorem version of NIZK for every <strong>NP</strong> language; that is, given a reference string $\rho$ and a language $L \in \bf{NP}$, one can prove only one single theorem of the form $x \in L$. In addition, the length of the theorem is bounded in $|\rho|$. If the prover attempts to reuse some bits of $\rho$ in later proofs, there's a danger of knowledge leakage (and the proof will no longer be NIZK).</p>

<p>To remedy this, BFM used a multi-theorem version based on the single-theorem NIZK. To this end, they used a pseudo-random generator to expand $\rho$, and then used the expanded bits. There are some other details as well, but I'm not going to dig in.</p>

<p><a href="http://dx.doi.org/10.1137/S0097539792230010">Feige, Lapidot, and Shamir</a> (in the first footnote on the first page of their paper) stated:</p>

<blockquote>
  <p>The method suggested in BFM for overcoming this <strong>difficulty</strong> was found to be flawed.</p>
</blockquote>

<p>(The <strong>difficulty</strong> refers to obtaining multi-theorem proofs rather than single-theorem ones.)</p>

<blockquote>
  <p>Where does the BFM flaw lie?</p>
</blockquote>

CC BY-SA 2.5
2010-10-13T02:39:26.843Z
We really need some more crypto people...
Ryan Williams
<cr.crypto-security>
Where's the Flaw in Blum-Feldman-Micali's Method
Sadeq Dousti
# Where's the Flaw in Blum-Feldman-Micali's Method

(Asked by: username_0 on 2010-10-12)

[Blum, Micali, and Feldman](http://portal.acm.org/citation.cfm?id=62222) (BFM) put forward a new (cryptographic) model, in which all parties (honest or adversarial) have access to some string. The string is assumed to be selected according to some distribution (usually, uniform distribution) by a trusted party. It is called the *reference string*, and the model is aptly named the *common reference string* (CSR) model.

The model allows us to perform many interesting interactive protocols *non-interactively*, replacing queries by bits from the reference string. In particular, **zero-knowledge** proofs for any **NP** language can be conducted non-interactively, giving rise to the notion of *non-interactive zero-knowledge* (NIZK).

NIZK has a lot of applications, such as providing a method for realizing public-key cryptosystems secure against [(adaptive) chosen-ciphertext attacks](http://en.wikipedia.org/wiki/Chosen-ciphertext_attack).

BFM first proved the existence of a single-theorem version of NIZK for every **NP** language; that is, given a reference string $\rho$ and a language $L \in \bf{NP}$, one can prove only one single theorem of the form $x \in L$. In addition, the length of the theorem is bounded in $|\rho|$. If the prover attempts to reuse some bits of $\rho$ in later proofs, there's a danger of knowledge leakage (and the proof will no longer be NIZK).

To remedy this, BFM used a multi-theorem version based on the single-theorem NIZK. To this end, they used a pseudo-random generator to expand $\rho$, and then used the expanded bits. There are some other details as well, but I'm not going to dig in.

[Feige, Lapidot, and Shamir](http://dx.doi.org/10.1137/S0097539792230010) (in the first footnote on the first page of their paper) stated:

> The method suggested in BFM for overcoming this **difficulty** was found to be flawed.

(The **difficulty** refers to obtaining multi-theorem proofs rather than single-theorem ones.)

> Where does the BFM flaw lie?

**Tags:** cr.crypto-security
> **Comments:**
> **username_1**: We really need some more crypto people...  

---

## 1 answers

### Answer by username_2 on 2010-10-13. Score: 11 | Accepted answer

I have not read the details of their flawed protocol, but I've heard about it on several occasions. My impression was that their error was in how they used the PRG seed. Their protocol puts the pseudorandom generator (PRG) seed in the public common reference string, and they attempt to argue that PRG security forces some statistical property of the PRG output to hold even with a known seed. While it is possible to do this in a sound way (the signature schemes of Hohenberger and Waters [here](https://link.springer.com/chapter/10.1007/978-3-642-03356-8_38?from=SL) and [here](https://link.springer.com/chapter/10.1007/978-3-642-01001-9_19?from=SL) spring to mind), something went wrong in their argument.


---

