Succinct Publicly-Certifiable Proofs (or: Can a Blockchain Verify a Designated-Verifier Proof?)

Matteo Campanelli; Hamidreza Khoshakhlagh

Paper 2021/1618

Succinct Publicly-Certifiable Proofs (or: Can a Blockchain Verify a Designated-Verifier Proof?)

Matteo Campanelli and Hamidreza Khoshakhlagh

Abstract

We study zero-knowledge arguments where proofs are: of knowledge, short, publicly-verifiable and produced without interaction. While zkSNARKs satisfy these requirements, we build such proofs in a constrained theoretical setting: in the standard-model---i.e., without a random oracle---and without assuming public-verifiable SNARKs (or even NIZKs, for some of our constructions) or primitives currently known to imply them. We model and construct a new primitive, SPuC (Succinct Publicly-Certifiable System), where: a party can prove knowledge of a witness $w$ by publishing a proof ; the latter can then be certified non-interactively by a committee sharing a secret; any party in the system can now verify the proof through its certificates; the total communication complexity should be sublinear in . We construct SPuCs generally from (leveled) Threshold FHE, homomorphic signatures and linear-only encryption, all instantiatable from lattices and thus plausibly quantum-resistant. We also construct them in the two-party case replacing TFHE with the simpler primitive of homomorphic secret-sharing. Our model has practical applications in blockchains and in other protocols where there exist committees sharing a secret and it is necessary for parties to prove knowledge of a solution to some puzzle. We show that one can construct a version of SPuCs with robust proactive security from similar assumptions. In a proactively secure model the committee reshares its secret from time to time. Such a model is robust if the committee members can prove they performed this resharing step correctly. Along the way to our goal we define and build Proactive Universal Thresholdizers, a proactive version of the Universal Thresholdizer defined in Boneh et al. [Crypto 2018].

Note: Preliminary full version of INDOCRYPT 2021 version.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Minor revision. INDOCRYPT 2021
DOI: 10.1007/978-3-030-92518-5_27
Contact author(s): matteo campanelli @ gmail com
hamidreza @ cs au dk
History: 2021-12-14: received
Short URL: https://ia.cr/2021/1618
License: CC BY

BibTeX

@misc{cryptoeprint:2021/1618,
      author = {Matteo Campanelli and Hamidreza Khoshakhlagh},
      title = {Succinct Publicly-Certifiable Proofs (or: Can a Blockchain Verify a Designated-Verifier Proof?)},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/1618},
      year = {2021},
      doi = {10.1007/978-3-030-92518-5_27},
      url = {https://eprint.iacr.org/2021/1618}
}