A dot-product proof (DPP) is a simple probabilistic proof system in which the input statement $x$ and the proof ${\pi}$ are vectors over a finite field $\mathbb{F}$, and the proof is verified by making a single dot-product query $\langle {q},({x} \| {\pi})\rangle$ jointly to ${x}$ and ${\pi}$. A DPP can be viewed as a 1-query {\em fully linear} PCP. We study the feasibility and efficiency of DPPs, obtaining the following results:

* Small-field DPP: For any finite field $\mathbb{F}$ and Boolean circuit $C$ of size $S$, there is a DPP for proving that there exists ${w}$ such that $C({x}, {w})=1$ with a proof ${\pi}$ of length $S\cdot\text{poly}(|\mathbb{F}|)$ and soundness error $\epsilon=O(1/\sqrt{|\mathbb{F}|})$. 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 $|\mathbb{F}|\ge\text{poly}(S/\epsilon)$, there is a similar DPP with soundness error $\epsilon$ and proof length $O(S)$ (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 $\mathbb{F}$ up to some constant factor $c>1$, independent of $\mathbb{F}$. 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.