Paper 2024/1138

Dot-Product Proofs and Their Applications

Abstract

A dot-product proof (DPP) is a simple probabilistic proof system in which the input statement and the proof are vectors over a finite field , and the proof is verified by making a single dot-product query $$ jointly to $$ and $$. A DPP can be viewed as a 1-query fully linear PCP. We study the feasibility and efficiency of DPPs, obtaining the following results: - Small-field DPP. For any finite field $$ and Boolean circuit $$ of size $$, there is a DPP for proving that there exists $$ such that $$ with a proof $$ of length $$ and soundness error $$. We show this error to be asymptotically optimal. In particular, and in contrast to the best known PCPs, there exist strictly linear-length DPPs over constant-size fields. - Large-field DPP. If $$, there is a similar DPP with soundness error $$ and proof length $$ (in field elements). The above results do not rely on the PCP theorem and their proofs are considerably simpler. We apply our DPP constructions toward two kinds of applications. - Hardness of approximation. We obtain a simple proof for the NP-hardness of approximating MAXLIN (with dense instances) over any finite field $$ up to some constant factor $$, independent of $$. Unlike previous PCP-based proofs, our proof yields exponential-time hardness under the exponential time hypothesis (ETH). - Succinct arguments. We improve the concrete efficiency of succinct interactive arguments in the generic group model using input-independent preprocessing. In particular, the communication is comparable to sending two group elements and the verifier's computation is dominated by a single group exponentiation. We also show how to use DPPs together with linear-only encryption to construct succinct commit-and-prove arguments.