NIWI and New Notions of Extraction for Algebraic Languages

Chaya Ganesh; Hamidreza Khoshakhlagh; Roberto Parisella

doi:10.1007/978-3-031-14791-3_30

NIWI and New Notions of Extraction for Algebraic Languages

Chaya Ganesh, Hamidreza Khoshakhlagh^*, Roberto Parisella

^*Corresponding author af dette arbejde

Institut for Datalogi

Publikation: Bidrag til bog/antologi/rapport/proceeding › Konferencebidrag i proceedings › Forskning › peer review

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.

Originalsprog	Engelsk
Titel	Security and Cryptography for Networks. SCN 2022
Redaktører	Clemente Galdi, Stanislaw Jarecki
Antal sider	24
Udgivelsessted	Cham
Forlag	Springer
Publikationsdato	2022
Sider	687-710
ISBN (Trykt)	9783031147906
ISBN (Elektronisk)	978-3-031-14791-3
DOI	https://doi.org/10.1007/978-3-031-14791-3_30
Status	Udgivet - 2022
Begivenhed	13th International Conference on Security and Cryptography for Networks, SCN 2022 - Amalfi, Italien Varighed: 12 sep. 2022 → 14 sep. 2022

Konference

Konference	13th International Conference on Security and Cryptography for Networks, SCN 2022
Land/Område	Italien
By	Amalfi
Periode	12/09/2022 → 14/09/2022

Navn	Lecture Notes in Computer Science
Vol/bind	13409
ISSN	0302-9743

Adgang til dokumentet

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

Andre filer og links

Link to publication in Scopus

Citationsformater

@inproceedings{796ff0f302af45cb8232499d11364f55,

title = "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.",

author = "Chaya Ganesh and Hamidreza Khoshakhlagh and Roberto Parisella",

year = "2022",

doi = "10.1007/978-3-031-14791-3_30",

language = "English",

isbn = "9783031147906",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "687--710",

editor = "Clemente Galdi and Stanislaw Jarecki",

booktitle = "Security and Cryptography for Networks. SCN 2022",

address = "Netherlands",

note = "13th International Conference on Security and Cryptography for Networks, SCN 2022 ; Conference date: 12-09-2022 Through 14-09-2022",

}

Ganesh, C, Khoshakhlagh, H & Parisella, R 2022, NIWI and New Notions of Extraction for Algebraic Languages. i C Galdi & S Jarecki (red), Security and Cryptography for Networks. SCN 2022. Springer, Cham, Lecture Notes in Computer Science, bind 13409, s. 687-710, 13th International Conference on Security and Cryptography for Networks, SCN 2022, Amalfi, Italien, 12/09/2022. https://doi.org/10.1007/978-3-031-14791-3_30

NIWI and New Notions of Extraction for Algebraic Languages. / Ganesh, Chaya; Khoshakhlagh, Hamidreza; Parisella, Roberto.
Security and Cryptography for Networks. SCN 2022. red. / Clemente Galdi; Stanislaw Jarecki. Cham: Springer, 2022. s. 687-710 (Lecture Notes in Computer Science, Bind 13409).

Publikation: Bidrag til bog/antologi/rapport/proceeding › Konferencebidrag i proceedings › Forskning › peer review

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 -