Succinct Publicly-Certifiable Proofs: Or, Can a Blockchain Verify a Designated-Verifier Proof?

TY - GEN

T1 - Succinct Publicly-Certifiable Proofs

T2 - 22nd International Conference on Cryptology in India

AU - Campanelli, Matteo

AU - Khoshakhlagh, Hamidreza

N1 - Conference code: 22

PY - 2021

Y1 - 2021

N2 - 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 π 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) 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 FHE 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. Our constructions can be seen as a way to compile a designated-verifier SNARK into a proof system with a flavor of public-verifiability with similar efficiency features of the starting dvSNARK (e.g., proving time). 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].

AB - 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 π 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) 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 FHE 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. Our constructions can be seen as a way to compile a designated-verifier SNARK into a proof system with a flavor of public-verifiability with similar efficiency features of the starting dvSNARK (e.g., proving time). 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].

UR - http://www.scopus.com/inward/record.url?scp=85121904067&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-92518-5_27

DO - 10.1007/978-3-030-92518-5_27

M3 - Article in proceedings

SN - 978-3-030-92517-8

T3 - Lecture Notes in Computer Science

SP - 607

EP - 631

BT - Progress in Cryptology – INDOCRYPT 2021 - 22nd International Conference on Cryptology in India, 2021, Proceedings

A2 - Adhikari, Avishek

A2 - Küsters, Ralf

A2 - Preneel, Bart

PB - Springer

Y2 - 13 December 2021 through 15 December 2021

ER -