IACR News item: 27 December 2012
Prabhanjan Ananth, Raghav Bhaskar, Vipul Goyal, Vanishree Rao
ePrint ReportAn alternative to the Fiat-Shamir paradigm was proposed by Fischlin in Crypto 2005. Fischlin\\rq{}s transformation can be applied to any so called 3-round ``Fiat-Shamir proof of knowledge\\rq{}\\rq{} and can be used to derive non-interactive zero-knowledge proofs of knowledge as well as signature schemes. An attractive property of this transformation is that it provides online extractability (i.e., the extractor works without having to rewind the prover). Fischlin remarks that in comparison to the Fiat-Shamir transformation, his construction tries to ``decouple the hash function from the protocol flow\" and hence, the counterexample in the work of Goldwaaser and Kalai does not seem to carry over to this setting.
In this work, we show a counterexample to the Fischlin\'s transformation. In particular, we construct a 3-round Fiat-Shamir proof of knowledge (on which Fischlin\'s transformation is applicable), and then, present an adversary against both - the soundness of the resulting non-interactive zero-knowledge, as well as the unforegeability of the resulting signature scheme. Our attacks are successful except with negligible probability for any hash function, that is used to instantiate the random oracle, provided that there is an apriori (polynomial) bound on the running time of the hash function. By choosing the right bound, secure instantiation of Fischlin transformation with most practical cryptographic hash functions can be ruled out.
The techniques used in our work are quite unrelated to the ones used in the work of Goldwasser and Kalai. Our primary technique is to bind the protocol flow with the hash function if the code of the hash function is available. We believe that our ideas are of independent interest and maybe applicable in other related settings.
Additional news items may be found on the IACR news page.