Efficient NIZK Arguments with Straight-Line Simulation and Extraction

Michele Ciampi*, Ivan Visconti

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

Non-interactive zero-knowledge (NIZK) arguments allow a prover to convince a verifier about the truthfulness of an NP -statement by sending just one message, without disclosing any additional information. In several practical scenarios, the Fiat-Shamir transform is used to convert an efficient constant-round public-coin honest-verifier zero-knowledge proof system into an efficient NIZK argument system. This approach is provably secure in the random oracle model, crucially requires the programmability of the random oracle and extraction works through rewinds. The works of Lindell [TCC 2015] and Ciampi et al. [TCC 2016] proposed efficient NIZK arguments with non-programmable random oracles along with a programmable common reference string. In this work we show an efficient NIZK argument with straight-line simulation and extraction that relies on features that alone are insufficient to construct NIZK arguments (regardless of efficiency). More specifically we consider the notion of quasi-polynomial time simulation proposed by Pass in [EUROCRYPT 2003] and combine it with simulation and extraction with non-programmable random oracles thus obtaining a NIZK argument of knowledge where neither the zero-knowledge simulator, nor the argument of knowledge extractor needs to program the random oracle. Still, both the simulator and the extractor are straight-line. Our construction uses as a building block a modification of the Fischlin’s transform [CRYPTO 2005] and combines it with the concept of dense puzzles introduced by Baldimtsi et al. [ASIACRYPT 2016]. We also argue that our NIZK argument system inherits the efficiency features of Fischlin’s transform, which represents the main advantage of Fischlin’s protocol over existing schemes.

Original languageEnglish
Title of host publicationCryptology and Network Security - 21st International Conference, CANS 2022, Proceedings
EditorsAlastair R. Beresford, Arpita Patra, Emanuele Bellini
PublisherSpringer, Cham
Number of pages20
ISBN (Electronic)978-3-031-20974-1
ISBN (Print)978-3-031-20973-4
Publication statusPublished - 10 Nov 2022
Event21st International Conference on Cryptology and Network Security, CANS 2022 - Abu Dhabi, United Arab Emirates
Duration: 13 Nov 202216 Nov 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Cham
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference21st International Conference on Cryptology and Network Security, CANS 2022
Country/TerritoryUnited Arab Emirates
CityAbu Dhabi


Dive into the research topics of 'Efficient NIZK Arguments with Straight-Line Simulation and Extraction'. Together they form a unique fingerprint.

Cite this