International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Simultaneous Amplification: The Case of Non-interactive Zero-Knowledge

Authors:
Vipul Goyal
Aayush Jain
Amit Sahai
Download:
DOI: 10.1007/978-3-030-26951-7_21 (login may be required)
Search ePrint
Search Google
Abstract: In this work, we explore the question of simultaneous privacy and soundness amplification for non-interactive zero-knowledge argument systems (NIZK). We show that any $$\delta _s-$$sound and $$\delta _z-$$zero-knowledge NIZK candidate satisfying $$\delta _s+\delta _z=1-\epsilon $$, for any constant $$\epsilon >0$$, can be turned into a computationally sound and zero-knowledge candidate with the only extra assumption of a subexponentially secure public-key encryption.We develop novel techniques to leverage the use of leakage simulation lemma (Jetchev-Peitzrak TCC 2014) to argue amplification. A crucial component of our result is a new notion for secret sharing $$\mathsf {NP}$$ instances. We believe that this may be of independent interest.To achieve this result we analyze following two transformations:Parallel Repetition: We show that using parallel repetition any $$\delta _s-$$sound and $$\delta _z-$$zero-knowledge $$\mathsf {NIZK}$$ candidate can be turned into (roughly) $$\delta ^n_s-$$sound and $$1-(1-\delta _{z})^n-$$zero-knowledge candidate. Here n is the repetition parameter.MPC based Repetition: We propose a new transformation that amplifies zero-knowledge in the same way that parallel repetition amplifies soundness. We show that using this any $$\delta _s-$$sound and $$\delta _z-$$zero-knowledge $$\mathsf {NIZK}$$ candidate can be turned into (roughly) $$1-(1-\delta _s)^n-$$sound and $$2\cdot \delta ^n_{z}-$$zero-knowledge candidate. Then we show that using these transformations in a zig-zag fashion we can obtain our result. Finally, we also present a simple transformation which directly turns any $$\mathsf {NIZK}$$ candidate satisfying $$\delta _s,\delta _z<1/3 -1/\mathsf {poly}(\lambda )$$ to a secure one.
Video from CRYPTO 2019
BibTeX
@article{crypto-2019-29900,
  title={Simultaneous Amplification: The Case of Non-interactive Zero-Knowledge},
  booktitle={Advances in Cryptology – CRYPTO 2019},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  volume={11693},
  pages={608-637},
  doi={10.1007/978-3-030-26951-7_21},
  author={Vipul Goyal and Aayush Jain and Amit Sahai},
  year=2019
}