Paper 2024/1138
DotProduct Proofs and Their Applications
Abstract
A dotproduct proof (DPP) is a simple probabilistic proof system in which the input statement $\mathbf{x}$ and the proof $\boldsymbol{\pi}$ are vectors over a finite field $\mathbb{F}$, and the proof is verified by making a single dotproduct query $\langle \mathbf{q},(\mathbf{x} \ \boldsymbol{\pi}) \rangle$ jointly to $\mathbf{x}$ and $\boldsymbol{\pi}$. A DPP can be viewed as a 1query fully linear PCP. We study the feasibility and efficiency of DPPs, obtaining the following results:  Smallfield DPP. For any finite field $\mathbb{F}$ and Boolean circuit $C$ of size $S$, there is a DPP for proving that there exists $\mathbf{w}$ such that $C(\mathbf{x}, \mathbf{w})=1$ with a proof $\boldsymbol{\pi}$ of length $S\cdot\mathsf{poly}(\mathbb{F})$ and soundness error $\varepsilon=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 linearlength DPPs over constantsize fields.  Largefield DPP. If $\mathbb{F}\ge\mathsf{poly}(S/\varepsilon)$, there is a similar DPP with soundness error $\varepsilon$ 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 NPhardness 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 PCPbased proofs, our proof yields exponentialtime hardness under the exponential time hypothesis (ETH).  Succinct arguments. We improve the concrete efficiency of succinct interactive arguments in the generic group model using inputindependent 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 linearonly encryption to construct succinct commitandprove arguments.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. Major revision. FOCS
 Keywords
 dot product proofslinear PCPssuccinct argumentsETH hardness
 Contact author(s)

nbitansky @ gmail com
prahladh @ tifr res in
yuvali @ cs technion ac il
rothblum @ cs technion ac il
dwu4 @ cs utexas edu  History
 20240715: approved
 20240712: received
 See all versions
 Short URL
 https://ia.cr/2024/1138
 License

CC BY
BibTeX
@misc{cryptoeprint:2024/1138, author = {Nir Bitansky and Prahladh Harsha and Yuval Ishai and Ron D. Rothblum and David J. Wu}, title = {DotProduct Proofs and Their Applications}, howpublished = {Cryptology ePrint Archive, Paper 2024/1138}, year = {2024}, note = {\url{https://eprint.iacr.org/2024/1138}}, url = {https://eprint.iacr.org/2024/1138} }