International Association for Cryptologic Research

International Association
for Cryptologic Research


Weak Zero-Knowledge via the Goldreich-Levin Theorem

Dakshita Khurana , University of Illinois Urbana-Champaign
Giulio Malavolta , Max Planck Institute for Security and Privacy
Kabir Tomer , University of Illinois Urbana-Champaign
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2023
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 {\em adaptive} verifiers assuming fully homomorphic encryption among other standard assumptions (Bitansky et. al., STOC 2019), and (2) security against {\em 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.
  title={Weak Zero-Knowledge via the Goldreich-Levin Theorem},
  author={Dakshita Khurana and Giulio Malavolta and Kabir Tomer},