Paper 2019/188
ZeroKnowledge Proofs on SecretShared Data via Fully Linear PCPs
Abstract
We introduce and study the notion of fully linear probabilistically checkable proof systems. In such a proof system, the verifier can make a small number of linear queries that apply jointly to the input and a proof vector. Our new type of proof system is motivated by applications in which the input statement is not fully available to any single verifier, but can still be efficiently accessed via linear queries. This situation arises in scenarios where the input is partitioned or secretshared between two or more parties, or alternatively is encoded using an additively homomorphic encryption or commitment scheme. This setting appears in the context of secure messaging platforms, verifiable outsourced computation, PIR writing, private computation of aggregate statistics, and secure multiparty computation (MPC). In all these applications, there is a need for fully linear proof systems with short proofs. While several efficient constructions of fully linear proof systems are implicit in the interactive proofs literature, many questions about their complexity are open. We present several new constructions of fully linear zeroknowledge proof systems with sublinear proof size for "simple" or "structured" languages. For example, in the noninteractive setting of fully linear PCPs, we show how to prove that an input vector $x\in\mathbb{F}^n$ satisfies a single degree2 equation with a proof of size $O(\sqrt n)$ and $O(\sqrt n)$ linear queries, which we show to be optimal. More generally, for languages that can be recognized by systems of constantdegree equations, we can reduce the proof size to $O(\log n)$ at the cost of $O(\log n)$ rounds of interaction. We use our new proof systems to construct new short zeroknowledge proofs on distributed and secretshared data. These proofs can be used to improve the performance of many of the example systems mentioned above. Finally, we observe that zeroknowledge proofs on distributed data provide a generalpurpose tool for protecting protocols for secure multiparty computation (MPC) against malicious parties. Applying our short fully linear PCPs to "natural" MPC protocols in the honestmajority setting, we can achieve unconditional protection against malicious parties with sublinear additive communication cost. We use this to improve the communication complexity of recent honestmajority MPC protocols. For instance, using any pseudorandom generator, we obtain a 3party protocol for Boolean circuits in which the amortized communication cost is only one bit per AND gate per party (compared to 7 bits in the best previous protocol), matching the best known protocols for semihonest adversaries.
Note: This version fixes a typo in Section 6.2.3.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A major revision of an IACR publication in CRYPTO 2019
 Keywords
 linear PCPs proof systems zero knowledge multiparty computation
 Contact author(s)

dabo @ cs stanford edu
eboyle @ alum mit edu
henrycg @ csail mit edu
gilboan @ bgu ac il
yuvali @ cs technion ac il  History
 20220821: last of 7 revisions
 20190226: received
 See all versions
 Short URL
 https://ia.cr/2019/188
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/188, author = {Dan Boneh and Elette Boyle and Henry CorriganGibbs and Niv Gilboa and Yuval Ishai}, title = {ZeroKnowledge Proofs on SecretShared Data via Fully Linear PCPs}, howpublished = {Cryptology ePrint Archive, Paper 2019/188}, year = {2019}, note = {\url{https://eprint.iacr.org/2019/188}}, url = {https://eprint.iacr.org/2019/188} }