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?

  • 2
    $\begingroup$ We really need some more crypto people... $\endgroup$ Oct 13, 2010 at 2:39

1 Answer 1


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 and here spring to mind), something went wrong in their argument.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.