We initiate the study of complementary positive results, namely, studying classes of interactive protocols where the FS transform *does* have standard-model instantiations. In particular, we show that for a class of "highly sound" protocols that we define, instantiating the FS transform via a $q$-wise independent hash function yields NIZK arguments and secure signature schemes. In the case of NIZK, we obtain a weaker "$q$-bounded" zero-knowledge flavor where the simulator works for all adversaries asking an a-priori bounded number of queries $q$; in the case of signatures, we obtain the weaker notion of random-message unforgeability against $q$-bounded random message attacks.
Our main idea is that when the protocol is highly sound, then instead of using random-oracle programming, one can use complexity leveraging. The question is whether such highly sound protocols exist and if so, which protocols lie in this class. We answer this question in the affirmative in the common reference string (CRS) model and under strong assumptions. Namely, assuming indistinguishability obfuscation and puncturable pseudorandom functions we construct a compiler that transforms any 3-move interactive protocol with instance-independent commitments and simulators (a property satisfied by the Lapidot-Shamir protocol, Crypto '90) into a compiled protocol in the CRS model that is highly sound. We also present a second compiler, in order to be able to start from a larger class of protocols, which only requires instance-independent commitments (a property for example satisfied by the classical protocol for quadratic residuosity due to Blum, Crypto '81). For the second compiler we require dual-mode commitments.
We hope that our work inspires more research on classes of (efficient) 3-move protocols where Fiat-Shamir is (efficiently) instantiable.Category / Keywords: foundations / Fiat-Shamir transform, non-interactive zero-knowledge, signature schemes, indistinguishability obfuscation, standard model Date: received 18 Mar 2016, last revised 19 Apr 2016 Contact author: venturi at di uniroma1 it Available format(s): PDF | BibTeX Citation Version: 20160419:094041 (All versions of this report) Short URL: ia.cr/2016/313 Discussion forum: Show discussion | Start new discussion