Paper 2022/851

NIWI and New Notions of Extraction for Algebraic Languages

Chaya Ganesh, Indian Institute of Science
Hamidreza Khoshakhlagh, Aarhus University
Roberto Parisella, Simula UiB

We give an efficient construction of a computational non-interactive witness indistinguishable (NIWI) proof in the plain model, and investigate notions of extraction for NIZKs for algebraic languages. Our starting point is the recent work of Couteau and Hartmann (CRYPTO 2020) who developed a new framework (CH framework) for constructing non-interactive zero-knowledge proofs and arguments under falsifiable assumptions for a large class of languages called algebraic languages. In this paper, we construct an efficient NIWI proof in the plain model for algebraic languages based on the CH framework. In the plain model, our NIWI construction is more efficient for algebraic languages than state-of-the-art Groth-Ostrovsky-Sahai (GOS) NIWI (JACM 2012). Next, we explore knowledge soundness of NIZK systems in the CH framework. We define a notion of strong f-extractability, and show that the CH proof system satisfies this notion. We then put forth a new definition of knowledge soundness called semantic extraction. We explore the relationship of semantic extraction with existing knowledge soundness definitions and show that it is a general definition that recovers black-box and non-black-box definitions as special cases. Finally, we show that NIZKs for algebraic languages in the CH framework cannot satisfy semantic extraction. We extend this impossibility to a class of NIZK arguments over algebraic languages, namely quasi-adaptive NIZK arguments that are constructed from smooth projective hash functions.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. SCN 2022
Witness-indistinguishability NIWI proofs Black-box and non-black-box extraction Algebraic languages
Contact author(s)
chaya @ iisc ac in
hamidreza @ cs au dk
robertoparisella @ hotmail it
2022-06-29: approved
2022-06-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Chaya Ganesh and Hamidreza Khoshakhlagh and Roberto Parisella},
      title = {NIWI and New Notions of Extraction for Algebraic Languages},
      howpublished = {Cryptology ePrint Archive, Paper 2022/851},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.