A Generic Transform from Multi-Round Interactive Proof to NIZK

Pierre-Alain Fouque; Adela Georgescu; Chen Qian; Adeline Roux-Langlois; Weiqiang Wen

Paper 2023/334

A Generic Transform from Multi-Round Interactive Proof to NIZK

Pierre-Alain Fouque

, Rennes University, CNRS, INRIA, Rennes, France

Adela Georgescu

, Department of Computer Science, University of Bucharest, Romania

Chen Qian

, Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Qingdao, Shandong, China, School of Cyber Science and Technology, Shandong University, Qingdao, Shandong, China

Adeline Roux-Langlois

, Normandie Univ, UNICAEN, ENSICAEN, CNRS, GREYC, 14000 Caen, France

Weiqiang Wen

, LTCI, Telecom Paris, Institut Polytechnique de Paris, France

Abstract

We present a new generic transform that takes a multi-round interactive proof for the membership of a language $\mathcal{L}$ and outputs a non-interactive zero-knowledge proof (not of knowledge) in the common reference string model. Similar to the Fiat-Shamir transform, it requires a hash function $\mathsf{H}$. However, in our transform the zero-knowledge property is in the standard model, and the adaptive soundness is in the non-programmable random oracle model ($\mathsf{NPROM}$). Behind this new generic transform, we build a new generic OR-composition of two multi-round interactive proofs. Note that the two common techniques for building OR-proofs (parallel OR-proof and sequential OR-proof) cannot be naturally extended to the multi-round setting. We also give a proof of security for our OR-proof in the quantum oracle model ($\mathsf{QROM}$), surprisingly the security loss in $\\mathsf{QROM}$ is independent from the number of rounds.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published by the IACR in PKC 2023
Keywords: Non-Interactive Zero-Knowledge Non-Programmable Random-Oracle
Contact author(s): pa fouque @ gmail com
adela georgescu @ unibuc ro
chen qian @ sdu edu cn
adeline roux-langlois @ cnrs fr
weiqiang wen @ telecom-paris fr
History: 2023-03-08: approved; 2023-03-07: received; See all versions
Short URL: https://ia.cr/2023/334
License: CC BY

BibTeX

@misc{cryptoeprint:2023/334,
      author = {Pierre-Alain Fouque and Adela Georgescu and Chen Qian and Adeline Roux-Langlois and Weiqiang Wen},
      title = {A Generic Transform from Multi-Round Interactive Proof to NIZK},
      howpublished = {Cryptology ePrint Archive, Paper 2023/334},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/334}},
      url = {https://eprint.iacr.org/2023/334}
}