[en] The Fiat-Shamir (FS) transform is a well known and widely used technique to convert any constant-round public-coin honest-verifier zero-knowledge (HVZK) proof
or argument system CIPC=(Prov,Ver) in a non-interactive zero-knowledge (NIZK) argument system NIZK=(NIZK.Prove, NIZK.Verify).
The FS transform is secure in the random oracle (RO) model and is extremely efficient: it adds an evaluation of the RO for every message played by Ver.
While a major effort has been done to attack the soundness of the transform when the RO is instantiated with a ``secure'' hash function,
here we focus on a different limitation of the FS transform that exists even when there is a secure instantiation of the random oracle: the soundness of NIZK
holds against polynomial-time adversarial provers only. Therefore even when CIPC is a proof system, NIZK is only an argument system.
In this paper we propose a new transform from 3-round public-coin HVZK proof systems for several practical relations to NIZK proof systems in the RO model. Our transform outperforms the FS transform protecting the honest verifier from unbounded adversarial provers with no restriction on the number of RO queries.
The protocols our transform can be applied to are the ones for proving membership to the range of a one-way group homomorphism as defined by [Maurer - Design, Codes and Cryptography 2015] except that we additionally require the function to be endowed with a trapdoor and other natural properties. For instance, we obtain new efficient instantiations of NIZK proofs for relations related to quadratic residuosity and the RSA function.
As a byproduct, with our transform we obtain essentially for free the first efficient non-interactive zap (i.e., 1-round non-interactive witness indistinguishable proof system for several practical languages in the non-programmable RO model and in an ideal-PUF model.
Our approach to NIZK proofs can be seen as an abstraction of the celebrated work of [Feige, Lapidot and Shamir - FOCS 1990].
Research center :
Interdisciplinary Centre for Security, Reliability and Trust (SnT) > Applied Security and Information Assurance Group (APSIA)
Disciplines :
Computer science
Author, co-author :
Iovino, Vincenzo ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
Visconti, Ivan; University of Salerno
External co-authors :
yes
Language :
English
Title :
Non-interactive Zero Knowledge Proofs in the Random Oracle Model
Publication date :
2019
Event name :
International Conference on Codes, Cryptology, and Information Security
Event place :
Rabat, Morocco
Event date :
22-04-2019 to 24-04-2019
Audience :
International
Main work title :
Codes, Cryptology and Information Security
Publisher :
Springer, Cham
ISBN/EAN :
978-3-030-16457-7
Collection name :
Lecture Notes in Computer Science book series, 11445
