Weak Zero-Knowledge via the Goldreich-Levin Theorem

Dakshita Khurana; Giulio Malavolta; Kabir Tomer

doi:10.1007/978-981-99-8724-5_5

Weak Zero-Knowledge via the Goldreich-Levin Theorem

Dakshita Khurana, Giulio Malavolta, Kabir Tomer

Siebel School of Computing and Data Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Obtaining three round zero-knowledge from standard cryptographic assumptions has remained a challenging open problem. Meanwhile, there has been exciting progress in realizing useful relaxations such as weak zero-knowledge, strong witness indistinguishability and witness hiding in two or three rounds. In particular, known realizations from generic assumptions obtain: (1) security against adaptive verifiers assuming fully homomorphic encryption among other standard assumptions (Bitansky et. al., STOC 2019), and (2) security against non-adaptive verifiers in the distributional setting from oblivious transfer (Jain et. al., Crypto 2017). This work builds three round weak zero-knowledge for NP in the non-adaptive setting from doubly-enhanced injective trapdoor functions. We obtain this result by developing a new distinguisher-dependent simulation technique that makes crucial use of the Goldreich-Levin list decoding algorithm, and may be of independent interest.

Original language	English (US)
Title of host publication	Advances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
Editors	Jian Guo, Ron Steinfeld
Publisher	Springer
Pages	142-173
Number of pages	32
ISBN (Print)	9789819987238
DOIs	https://doi.org/10.1007/978-981-99-8724-5_5
State	Published - 2023
Event	29th Annual International Conference on the Theory and Application of Cryptology and Information Security, Asiacrypt 2023 - Guangzhou, China Duration: Dec 4 2023 → Dec 8 2023

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	14439 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	29th Annual International Conference on the Theory and Application of Cryptology and Information Security, Asiacrypt 2023
Country/Territory	China
City	Guangzhou
Period	12/4/23 → 12/8/23

Keywords

Distinguisher
Goldreich-Levin
Simulation
Zero-knowledge

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Online availability

10.1007/978-981-99-8724-5_5

Library availability

Discover UIUC Full Text

Cite this

Khurana, D., Malavolta, G., & Tomer, K. (2023). Weak Zero-Knowledge via the Goldreich-Levin Theorem. In J. Guo, & R. Steinfeld (Eds.), Advances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings (pp. 142-173). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14439 LNCS). Springer. https://doi.org/10.1007/978-981-99-8724-5_5

Weak Zero-Knowledge via the Goldreich-Levin Theorem. / Khurana, Dakshita; Malavolta, Giulio; Tomer, Kabir.
Advances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. ed. / Jian Guo; Ron Steinfeld. Springer, 2023. p. 142-173 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14439 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Khurana, D, Malavolta, G & Tomer, K 2023, Weak Zero-Knowledge via the Goldreich-Levin Theorem. in J Guo & R Steinfeld (eds), Advances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14439 LNCS, Springer, pp. 142-173, 29th Annual International Conference on the Theory and Application of Cryptology and Information Security, Asiacrypt 2023, Guangzhou, China, 12/4/23. https://doi.org/10.1007/978-981-99-8724-5_5

Khurana D, Malavolta G, Tomer K. Weak Zero-Knowledge via the Goldreich-Levin Theorem. In Guo J, Steinfeld R, editors, Advances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Springer. 2023. p. 142-173. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-981-99-8724-5_5

Khurana, Dakshita ; Malavolta, Giulio ; Tomer, Kabir. / Weak Zero-Knowledge via the Goldreich-Levin Theorem. Advances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. editor / Jian Guo ; Ron Steinfeld. Springer, 2023. pp. 142-173 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{ec54e70778264865bb4d7181b85ab7cc,

title = "Weak Zero-Knowledge via the Goldreich-Levin Theorem",

abstract = "Obtaining three round zero-knowledge from standard cryptographic assumptions has remained a challenging open problem. Meanwhile, there has been exciting progress in realizing useful relaxations such as weak zero-knowledge, strong witness indistinguishability and witness hiding in two or three rounds. In particular, known realizations from generic assumptions obtain: (1) security against adaptive verifiers assuming fully homomorphic encryption among other standard assumptions (Bitansky et. al., STOC 2019), and (2) security against non-adaptive verifiers in the distributional setting from oblivious transfer (Jain et. al., Crypto 2017). This work builds three round weak zero-knowledge for NP in the non-adaptive setting from doubly-enhanced injective trapdoor functions. We obtain this result by developing a new distinguisher-dependent simulation technique that makes crucial use of the Goldreich-Levin list decoding algorithm, and may be of independent interest.",

keywords = "Distinguisher, Goldreich-Levin, Simulation, Zero-knowledge",

author = "Dakshita Khurana and Giulio Malavolta and Kabir Tomer",

note = "Publisher Copyright: {\textcopyright} 2023, International Association for Cryptologic Research.; 29th Annual International Conference on the Theory and Application of Cryptology and Information Security, Asiacrypt 2023 ; Conference date: 04-12-2023 Through 08-12-2023",

year = "2023",

doi = "10.1007/978-981-99-8724-5_5",

language = "English (US)",

isbn = "9789819987238",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "142--173",

editor = "Jian Guo and Ron Steinfeld",

booktitle = "Advances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings",

address = "Germany",

}

TY - GEN

T1 - Weak Zero-Knowledge via the Goldreich-Levin Theorem

AU - Khurana, Dakshita

AU - Malavolta, Giulio

AU - Tomer, Kabir

PY - 2023

Y1 - 2023

N2 - Obtaining three round zero-knowledge from standard cryptographic assumptions has remained a challenging open problem. Meanwhile, there has been exciting progress in realizing useful relaxations such as weak zero-knowledge, strong witness indistinguishability and witness hiding in two or three rounds. In particular, known realizations from generic assumptions obtain: (1) security against adaptive verifiers assuming fully homomorphic encryption among other standard assumptions (Bitansky et. al., STOC 2019), and (2) security against non-adaptive verifiers in the distributional setting from oblivious transfer (Jain et. al., Crypto 2017). This work builds three round weak zero-knowledge for NP in the non-adaptive setting from doubly-enhanced injective trapdoor functions. We obtain this result by developing a new distinguisher-dependent simulation technique that makes crucial use of the Goldreich-Levin list decoding algorithm, and may be of independent interest.

AB - Obtaining three round zero-knowledge from standard cryptographic assumptions has remained a challenging open problem. Meanwhile, there has been exciting progress in realizing useful relaxations such as weak zero-knowledge, strong witness indistinguishability and witness hiding in two or three rounds. In particular, known realizations from generic assumptions obtain: (1) security against adaptive verifiers assuming fully homomorphic encryption among other standard assumptions (Bitansky et. al., STOC 2019), and (2) security against non-adaptive verifiers in the distributional setting from oblivious transfer (Jain et. al., Crypto 2017). This work builds three round weak zero-knowledge for NP in the non-adaptive setting from doubly-enhanced injective trapdoor functions. We obtain this result by developing a new distinguisher-dependent simulation technique that makes crucial use of the Goldreich-Levin list decoding algorithm, and may be of independent interest.

KW - Distinguisher

KW - Goldreich-Levin

KW - Simulation

KW - Zero-knowledge

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

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

U2 - 10.1007/978-981-99-8724-5_5

DO - 10.1007/978-981-99-8724-5_5

M3 - Conference contribution

AN - SCOPUS:85180796925

SN - 9789819987238

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 142

EP - 173

BT - Advances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings

A2 - Guo, Jian

A2 - Steinfeld, Ron

PB - Springer

T2 - 29th Annual International Conference on the Theory and Application of Cryptology and Information Security, Asiacrypt 2023

Y2 - 4 December 2023 through 8 December 2023

ER -