Paper 2024/1138

Dot-Product Proofs and Their Applications

Nir Bitansky, New York University, Tel Aviv University
Prahladh Harsha, Tata Institute of Fundamental Research
Yuval Ishai, Technion – Israel Institute of Technology
Ron D. Rothblum, Technion – Israel Institute of Technology
David J. Wu, The University of Texas at Austin
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.

Metadata
Available format(s)
PDF
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
2024-07-15: approved
2024-07-12: received
See all versions
Short URL
https://ia.cr/2024/1138
License
Creative Commons Attribution
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 = {Dot-Product Proofs and Their Applications},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1138},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1138}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.