EUVIMEDEUVIMED entdecken
Crossref

Dot-Product Proofs and Their Applications

Nir Bitansky, Prahladh Harsha, Yuval Ishai, Ron D. Rothblum, David J. Wu

SIAM Journal on Computing · 31.10.2026 · 55 (5) · FOCS24-365-FOCS24-434

DOI: 10.1137/25m1751505 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 08.06.2026. Verfasst von Nir Bitansky und 4 weiteren Autor:innen. Die Arbeit nennt 79 Literaturangaben. Gefördert von: European Research Council, Department of Atomic Energy, Government of India, Google.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A dot-product proof (DPP) is a simple probabilistic proof system in which the input statement [Formula: see text] and the proof [Formula: see text] are vectors over a finite field [Formula: see text] and the proof is verified by making a single dot-product query [Formula: see text] jointly to [Formula: see text] and [Formula: see text]. A DPP can be viewed as a one-query fully linear PCP. We study the feasibility and efficiency of DPPs, obtaining the following results. Small-field DPP: For any finite field [Formula: see text] and Boolean circuit [Formula: see text] of size [Formula: see text], there is a [Formula: see text] for proving that there exists [Formula: see text] such that [Formula: see text] with a proof [Formula: see text] of length [Formula: see text] and soundness error [Formula: see text]. We show this error to be asymptotically optimal. In particular and in contrast to the best-known [Formula: see text]s, there exist strictly linear-length [Formula: see text]s over constant-size fields. Large-field DPP: If [Formula: see text], there is a similar [Formula: see text] with soundness error [Formula: see text] and proof length [Formula: see text] (in field elements). The above results do not rely on the [Formula: see text] theorem, and their proofs are considerably simpler. We apply our [Formula: see text] 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 [Formula: see text] up to some constant factor [Formula: see text], independent of [Formula: see text]. Unlike previous [Formula: see text]-based proofs, our proof yields exponential-time hardness under the exponential-time hypothesis. 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.

Förderung

  • European Research Council
  • Department of Atomic Energy, Government of India
  • Google
  • Israel Science Foundation
  • United States-Israel Binational Science Foundation
  • National Science Foundation
  • Microsoft Research

Zitieren

APA

Bitansky, N., Harsha, P., Ishai, Y., Rothblum, R. D., & Wu, D. J. (2026). Dot-Product Proofs and Their Applications. SIAM Journal on Computing, 55(5), FOCS24-365-FOCS24-434. https://doi.org/10.1137/25m1751505

Vancouver

Bitansky N, Harsha P, Ishai Y, Rothblum RD, Wu DJ. Dot-Product Proofs and Their Applications. SIAM Journal on Computing. 2026;55(5):FOCS24-365-FOCS24-434. doi:10.1137/25m1751505

BibTeX
@article{Bitansky2026,
  author = {Bitansky, Nir and Harsha, Prahladh and Ishai, Yuval and Rothblum, Ron D. and Wu, David J.},
  title = {Dot-Product Proofs and Their Applications},
  journal = {SIAM Journal on Computing},
  year = {2026},
  volume = {55},
  number = {5},
  pages = {FOCS24--365--FOCS24--434},
  doi = {10.1137/25m1751505}
}
Kostenlos starten →