Reference : Non-interactive Zero Knowledge Proofs in the Random Oracle Model
Scientific congresses, symposiums and conference proceedings : Paper published in a book
Engineering, computing & technology : Computer science
Security, Reliability and Trust
Non-interactive Zero Knowledge Proofs in the Random Oracle Model
Iovino, Vincenzo mailto [University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > >]
Visconti, Ivan [University of Salerno]
Codes, Cryptology and Information Security
Springer, Cham
Lecture Notes in Computer Science book series, 11445
International Conference on Codes, Cryptology, and Information Security
22-04-2019 to 24-04-2019
[en] FS transform ; NIZK ; random oracle model
[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].
Interdisciplinary Centre for Security, Reliability and Trust (SnT) > Applied Security and Information Assurance Group (APSIA)
Researchers ; Professionals
FnR ; FNR11299247 > Vincenzo Iovino > FESS > Functional Encrypted Secure Systems > 01/12/2016 > 30/11/2019 > 2016

File(s) associated to this reference

Fulltext file(s):

Limited access
nizkro.pdfContact the first author for the full version.Author postprint536.98 kBRequest a copy

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.