### NIWI and New Notions of Extraction for Algebraic Languages

##### Abstract

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)
Category
Cryptographic protocols
Publication info
Published elsewhere. SCN 2022
Keywords
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
History
2022-06-29: approved
See all versions
Short URL
https://ia.cr/2022/851

CC BY

BibTeX

@misc{cryptoeprint:2022/851,
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{https://eprint.iacr.org/2022/851}},
url = {https://eprint.iacr.org/2022/851}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.