In the first part of this talk, we will introduce a new type of proof system, called fully linear probabilistically checkable proofs ("fully linear PCPs"). Fully linear PCPs apply naturally to the setting in which the verifier has only an encryption of the statement being proven or when the statement being proven is secret shared among multiple verifiers. In these settings, minimizing the proof length is an important efficiency goal. While some constructions of fully linear PCPs are implicit in the literature, we also present new constructions that have sublinear proof size for "simple" or "structured" languages. In the second part of the talk, we show how to apply fully linear PCPs to improve the efficiency of systems for multiparty computation, private messaging, private ad targeting, and more. For example, we use our new fully linear PCPs to convert semi-secure multiparty computation protocols into malicious-secure ones at sublinear additive communication cost, thereby improving the state of the art in multiparty computation. This work appeared at CRYPTO 2019.

In the second part of the talk, we show how to apply fully linear PCPs to improve the efficiency of systems for multiparty computation, private messaging, private ad targeting, and more. For example, we use our new fully linear PCPs to convert semi-secure multiparty computation protocols into malicious-secure ones at sublinear additive communication cost, thereby improving the state of the art in multiparty computation.

This work appeared at CRYPTO 2019.