Where's the Flaw in Blum-Feldman-Micali's Method

Blum, Micali, and Feldman (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.

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 (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?

• We really need some more crypto people... – Ryan Williams Oct 13 '10 at 2:39