Paper 2016/313
FiatShamir for Highly Sound Protocols is Instantiable
Arno Mittelbach and Daniele Venturi
Abstract
The FiatShamir (FS) transformation (Fiat and Shamir, Crypto '86) is a popular paradigm for constructing very efficient noninteractive zeroknowledge (NIZK) arguments and signature schemes using a hash function, starting from any threemove interactive protocol satisfying certain properties. Despite its widespread applicability both in theory and in practice, the known positive results for proving security of the FS paradigm are in the random oracle model, i.e., they assume that the hash function is modelled as an external random function accessible to all parties. On the other hand, a sequence of negative results shows that for certain classes of interactive protocols, the FS transform cannot be instantiated in the standard model. We initiate the study of complementary positive results, namely, studying classes of interactive protocols where the FS transform *does* have standardmodel 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" zeroknowledge flavor where the simulator works for all adversaries asking an apriori bounded number of queries $q$; in the case of signatures, we obtain the weaker notion of randommessage unforgeability against $q$bounded random message attacks. Our main idea is that when the protocol is highly sound, then instead of using randomoracle 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 3move interactive protocol with instanceindependent commitments and simulators (a property satisfied by the LapidotShamir 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 instanceindependent commitments (a property for example satisfied by the classical protocol for quadratic residuosity due to Blum, Crypto '81). For the second compiler we require dualmode commitments. We hope that our work inspires more research on classes of (efficient) 3move protocols where FiatShamir is (efficiently) instantiable.
Note: Journal version.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. Theoretical Computer Science
 DOI
 10.1016/j.tcs.2018.05.001
 Keywords
 FiatShamir transformnoninteractive zeroknowledgesignature schemesindistinguishability obfuscationstandard model
 Contact author(s)
 venturi @ di uniroma1 it
 History
 20180726: last of 2 revisions
 20160321: received
 See all versions
 Short URL
 https://ia.cr/2016/313
 License

CC BY
BibTeX
@misc{cryptoeprint:2016/313, author = {Arno Mittelbach and Daniele Venturi}, title = {FiatShamir for Highly Sound Protocols is Instantiable}, howpublished = {Cryptology ePrint Archive, Paper 2016/313}, year = {2016}, doi = {10.1016/j.tcs.2018.05.001}, note = {\url{https://eprint.iacr.org/2016/313}}, url = {https://eprint.iacr.org/2016/313} }