NIWI and New Notions of Extraction for Algebraic Languages

TY - GEN

T1 - NIWI and New Notions of Extraction for Algebraic Languages

AU - Ganesh, Chaya

AU - Khoshakhlagh, Hamidreza

AU - Parisella, Roberto

PY - 2022

Y1 - 2022

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85137987948&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-14791-3_30

DO - 10.1007/978-3-031-14791-3_30

M3 - Article in proceedings

AN - SCOPUS:85137987948

SN - 9783031147906

T3 - Lecture Notes in Computer Science

SP - 687

EP - 710

BT - Security and Cryptography for Networks. SCN 2022

A2 - Galdi, Clemente

A2 - Jarecki, Stanislaw

PB - Springer

CY - Cham

T2 - 13th International Conference on Security and Cryptography for Networks, SCN 2022

Y2 - 12 September 2022 through 14 September 2022

ER -