Paper 2021/1618

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

Matteo Campanelli and Hamidreza Khoshakhlagh


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 $\pi_0$; 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 $|w|$. 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.

Available format(s)
Publication info
Published elsewhere. Minor revision. INDOCRYPT 2021
Contact author(s)
matteo campanelli @ gmail com
hamidreza @ cs au dk
2021-12-14: received
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.