Triply Adaptive UC NIZK

Ran Canetti; Pratik Sarkar; Xiao Wang

Paper 2020/1212

Triply Adaptive UC NIZK

Ran Canetti, Boston University

Pratik Sarkar

, Boston University

Xiao Wang, Northwestern University

Abstract

Non-interactive zero knowledge (NIZK) enables proving the validity of NP statement without leaking anything else. We study multi-instance NIZKs in the common reference string (CRS) model, against an adversary that adaptively corrupts parties and chooses statements to be proven. We construct the first such $\textit{triply adaptive}$ NIZK that provides full adaptive soundness, as well as adaptive zero-knowledge, assuming either LWE or else LPN and DDH (previous constructions rely on non-falsifiable knowledge assumptions). In addition, our NIZKs are universally composable (UC). Along the way, we: - Formulate an ideal functionality, $\mathcal{F}_\textsf{NICOM}$, which essentially captures $\textit{non-interactive}$ commitments, and show that it is realizable by existing protocols using standard assumptions. - Define and realize, under standard assumptions, Sigma protocols which satisfy triply adaptive security with access to $\mathcal{F}_\textsf{NICOM}$. - Use the Fiat-Shamir transform, instantiated with correlation intractable hash functions, to compile a Sigma protocol with triply adaptive security with access to $\mathcal{F}_\textsf{NICOM}$ into a triply adaptive UC-NIZK argument in the CRS model with access to $\mathcal{F}_\textsf{NICOM}$, assuming LWE (or else LPN and DDH). - Use the UC theorem to obtain UC-NIZK in the CRS model.

Note: Removed "Ignore future (Com,ssid, ·) inputs with the same ssid." from Fig. 1 allowing reusability of the same ssid for multiple commitments.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published by the IACR in ASIACRYPT 2022
Keywords: Non-interactive Zero Knowledge Correlation Intractability Adaptive Security Zero Knowledge Universal Composability
Contact author(s): canetti @ bu edu
pratik93 @ bu edu
wangxiao @ cs northwestern edu
History: 2023-05-29: last of 6 revisions; 2020-10-06: received; See all versions
Short URL: https://ia.cr/2020/1212
License: CC BY

BibTeX

@misc{cryptoeprint:2020/1212,
      author = {Ran Canetti and Pratik Sarkar and Xiao Wang},
      title = {Triply Adaptive UC NIZK},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1212},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1212}},
      url = {https://eprint.iacr.org/2020/1212}
}