Paper 2020/1204

Single-to-Multi-Theorem Transformations for Non-Interactive Statistical Zero-Knowledge

Marc Fischlin and Felix Rohrbach

Abstract

Non-interactive zero-knowledge proofs or arguments allow a prover to show validity of a statement without further interaction. For non-trivial statements such protocols require a setup assumption in form of a common random or reference string (CRS). Generally, the CRS can only be used for one statement (single-theorem zero-knowledge) such that a fresh CRS would need to be generated for each proof. Fortunately, Feige, Lapidot and Shamir (FOCS 1990) presented a transformation for any non-interactive zero-knowledge proof system that allows the CRS to be reused any polynomial number of times (multi-theorem zero-knowledge). This FLS transformation, however, is only known to work for either computational zero-knowledge or requires a structured, non-uniform common reference string. In this paper we present FLS-like transformations that work for non-interactive statistical zero-knowledge arguments in the common random string model. They allow to go from single-theorem to multi-theorem zero-knowledge and also preserve soundness, for both properties in the adaptive and non-adaptive case. Our first transformation is based on the general assumption that one-way permutations exist, while our second transformation uses lattice-based assumptions. Additionally, we define different possible soundness notions for non-interactive arguments and discuss their relationships.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in PKC 2021
DOI
10.1007/978-3-030-75248-4_8
Keywords
Non-interactive argumentsstatistical zero-knowledgesoundnesstransformationone-way permutationlatticesdual-mode commitments
Contact author(s)
marc fischlin @ cryptoplexity de
felix rohrbach @ cryptoplexity de
History
2021-04-15: revised
2020-10-06: received
See all versions
Short URL
https://ia.cr/2020/1204
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1204,
      author = {Marc Fischlin and Felix Rohrbach},
      title = {Single-to-Multi-Theorem Transformations for Non-Interactive Statistical Zero-Knowledge},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1204},
      year = {2020},
      doi = {10.1007/978-3-030-75248-4_8},
      note = {\url{https://eprint.iacr.org/2020/1204}},
      url = {https://eprint.iacr.org/2020/1204}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.