Zero-Knowledge Proofs on Secret-Shared 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.