[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].
Centre de recherche :
Interdisciplinary Centre for Security, Reliability and Trust (SnT) > Applied Security and Information Assurance Group (APSIA)
Disciplines :
Sciences informatiques
Auteur, co-auteur :
IOVINO, Vincenzo ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
Visconti, Ivan; University of Salerno
Co-auteurs externes :
yes
Langue du document :
Anglais
Titre :
Non-interactive Zero Knowledge Proofs in the Random Oracle Model
Date de publication/diffusion :
2019
Nom de la manifestation :
International Conference on Codes, Cryptology, and Information Security
Lieu de la manifestation :
Rabat, Maroc
Date de la manifestation :
22-04-2019 to 24-04-2019
Manifestation à portée :
International
Titre de l'ouvrage principal :
Codes, Cryptology and Information Security
Maison d'édition :
Springer, Cham
ISBN/EAN :
978-3-030-16457-7
Collection et n° de collection :
Lecture Notes in Computer Science book series, 11445
