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
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; 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; 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, 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). doi: 10.1007/978-981-99-8724-5_5

@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 = "D. Khurana and K. Tomer were supported in part by NSF CAREER CNS-2238718, DARPA SIEVE and a gift from Visa Research. This material is based upon work supported by the Defense Advanced Research Projects Agency through Award HR00112020024. G. Malavolta was funded by the Deutsche Forschungs-gemeinschaft (DFG, German Research Foundation) under Germany{\textquoteright}s Excellence Strategy-EXC 2092 CASA-390781972.; 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",

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

N1 - D. Khurana and K. Tomer were supported in part by NSF CAREER CNS-2238718, DARPA SIEVE and a gift from Visa Research. This material is based upon work supported by the Defense Advanced Research Projects Agency through Award HR00112020024. G. Malavolta was funded by the Deutsche Forschungs-gemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy-EXC 2092 CASA-390781972.

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

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 -