Paper 2016/313
Fiat-Shamir for Highly Sound Protocols is Instantiable
Arno Mittelbach and Daniele Venturi
Abstract
The Fiat-Shamir (FS) transformation (Fiat and Shamir, Crypto '86) is a popular paradigm for constructing very efficient non-interactive zero-knowledge (NIZK) arguments and signature schemes using a hash function, starting from any three-move interactive protocol satisfying certain properties. Despite its wide-spread 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 standard-model instantiations. In particular, we show that for a class of "highly sound" protocols that we define, instantiating the FS transform via a
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
- Fiat-Shamir transformnon-interactive zero-knowledgesignature schemesindistinguishability obfuscationstandard model
- Contact author(s)
- venturi @ di uniroma1 it
- History
- 2018-07-26: last of 2 revisions
- 2016-03-21: 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 = {Fiat-Shamir for Highly Sound Protocols is Instantiable}, howpublished = {Cryptology {ePrint} Archive, Paper 2016/313}, year = {2016}, doi = {10.1016/j.tcs.2018.05.001}, url = {https://eprint.iacr.org/2016/313} }