On Adaptive Security of Delayed-Input Sigma Protocols and Fiat-Shamir NIZKs

Michele Ciampi; Roberto Parisella; Daniele Venturi

Paper 2020/831

On Adaptive Security of Delayed-Input Sigma Protocols and Fiat-Shamir NIZKs

Michele Ciampi, Roberto Parisella, and Daniele Venturi

Abstract

We study adaptive security of delayed-input Sigma protocols and non-interactive zero-knowledge (NIZK) proof systems in the common reference string (CRS) model. Our contributions are threefold: - We exhibit a generic compiler taking any delayed-input Sigma protocol and returning a delayed-input Sigma protocol satisfying adaptive-input special honest-verifier zero-knowledge (SHVZK). In case the initial Sigma protocol also satisfies adaptive-input special soundness, our compiler preserves this property. - We revisit the recent paradigm by Canetti et al. (STOC 2019) for obtaining NIZK proof systems in the CRS model via the Fiat-Shamir transform applied to so-called trapdoor Sigma protocols, in the context of adaptive security. In particular, assuming correlation-intractable hash functions for all sparse relations, we prove that Fiat- Shamir NIZKs satisfy either: (i) Adaptive soundness (and non-adaptive zero-knowledge), so long as the challenge is obtained by hashing both the prover’s first round and the instance being proven; (ii) Adaptive zero-knowledge (and non-adaptive soundness), so long as the challenge is obtained by hashing only the prover’s first round, and further assuming that the initial trapdoor Sigma protocol satisfies adaptive-input SHVZK. - We exhibit a generic compiler taking any Sigma protocol and returning a trapdoor Sigma protocol. Unfortunately, this transform does not preserve the delayed-input property of the initial Sigma protocol (if any). To complement this result, we also give yet another compiler taking any delayed-input trapdoor Sigma protocol and returning a delayed-input trapdoor Sigma protocol with adaptive-input SHVZK. An attractive feature of our first two compilers is that they allow obtaining efficient delayed-input Sigma protocols with adaptive security, and efficient Fiat-Shamir NIZKs with adaptive soundness (and non-adaptive zero-knowledge) in the CRS model. Prior to our work, the latter was only possible using generic NP reductions.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. Minor revision. Conference on Security and Cryptography for Networks (SCN 2020)
Keywords: Sigma protocols Non-interactive zero knowledge Adaptive security.
Contact author(s): mciampi @ ed ac uk
roberto @ simula no
venturi @ di uniroma1 it
History: 2020-07-07: received
Short URL: https://ia.cr/2020/831
License: CC BY

BibTeX

@misc{cryptoeprint:2020/831,
      author = {Michele Ciampi and Roberto Parisella and Daniele Venturi},
      title = {On Adaptive Security of Delayed-Input Sigma Protocols and Fiat-Shamir NIZKs},
      howpublished = {Cryptology ePrint Archive, Paper 2020/831},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/831}},
      url = {https://eprint.iacr.org/2020/831}
}