How large must the field be for a dot-product proof?
One dot-product query, linear proof length, and a ninth power of the circuit size
Motivation
A dot-product proof is what is left of a probabilistically checkable proof when the verifier is allowed exactly one query, and that query must be a linear functional applied jointly to the statement and the proof. It is the minimal interface for the linear-only-encryption route to succinct arguments: encrypt the query vector, let the prover homomorphically evaluate, decrypt one field element, accept or reject. The resulting arguments are as laconic as anything known without heavy machinery — a single ciphertext — which is why the parameters of the underlying proof system decide what those arguments can actually prove.
Over constant-size fields the picture is settled: soundness error \(\Theta(1/\sqrt q)\) is achievable with strictly linear proof length, and no better. Over large fields, where negligible soundness lives and where the cryptographic applications are, the constraint is on how large the field must be — and that is where the analysis is loose.
Provenance and history
Dot-product proofs are introduced by Bitansky, Harsha, Ishai, Rothblum and Wu, Dot-Product Proofs and Their Applications (IACR ePrint 2024/1138), building on the linear-only encryption compiler of Bitansky, Chiesa, Ishai, Ostrovsky and Paneth and on Barta, Ishai, Ostrovsky and Wu’s laconic arguments from groups. Two constructions: over constant-size fields, proof length \(S \cdot \mathrm{poly}(q)\) with optimal soundness \(\Theta(1/\sqrt q)\), avoiding the PCP theorem; and over large fields, a promise DPP of proof length \(O(S\log(S/\varepsilon))\) with soundness \(\varepsilon\), for any prime \(p \ge \widetilde\Omega(S^9/\varepsilon^6)\).
The paper is explicit twice over that the second bound is not tight — once of the compiler (“we believe that the analysis of our compiler is not tight”), once of the circuit-size dependence in a footnote, which points at the random-walk concentration argument that removes the analogous loss for the Hadamard-based linear PCP and says the formal analysis in the square-span-program setting is much harder. A follow-up line on the same laconic-argument application appears in the paper’s own comparison with subsequent work.
Parameter lattice
Field size against soundness against proof length.
| Field | Soundness | Proof length | Field-size requirement | |
|---|---|---|---|---|
| Small fields (Theorem 1.2) | constant \(q > 2\) | \(\Theta(1/\sqrt q)\), proved optimal | \(S \cdot \mathrm{poly}(q)\) | — |
| Large fields (Theorem 1.3) | prime \(p\) | \(\varepsilon\) | \(O(S\log(S/\varepsilon))\) | \(p \ge \widetilde\Omega(S^9/\varepsilon^6)\) — c/0070, conjectured improvable |
| Large fields, shorter proof | prime \(p\) | \(\varepsilon\) | \(O(S)\) | worse polynomial in \(S/\varepsilon\) |
| Large fields, non-promise | prime \(p\) | \(\varepsilon\) | \(O(S + n^2)\) | worse polynomial in \(S/\varepsilon\) |
| The optimum the source names | large | \(O(1/\sqrt{\lvert\mathbb{F}\rvert})\) | — | unstated: the source says closing this gap “might call for an entirely different approach” and treats it as a separate question |