Welcome to the resource topic for 2024/832
Title:
Hamming Weight Proofs of Proximity with One-Sided Error
Authors: Gal Arnon, Shany Ben-David, Eylon Yogev
Abstract:We provide a wide systematic study of proximity proofs with one-sided error for the Hamming weight problem \mathsf{Ham}_{\alpha} (the language of bit vectors with Hamming weight at least \alpha), surpassing previously known results for this problem. We demonstrate the usefulness of the one-sided error property in applications: no malicious party can frame an honest prover as cheating by presenting verifier randomness that leads to a rejection.
We show proofs of proximity for \mathsf{Ham}_{\alpha} with one-sided error and sublinear proof length in three models (MA, PCP, IOP), where stronger models allow for smaller query complexity. For n-bit input vectors, highlighting input query complexity, our MA has O(\mathrm{log} n) query complexity, the PCP makes O(\mathrm{loglog} n) queries, and the IOP makes a single input query. The prover in all of our applications runs in expected quasi-linear time. Additionally, we show that any perfectly complete IP of proximity for \mathsf{Ham}_{\alpha} with input query complexity n^{1-\epsilon} has proof length \Omega(\mathrm{log} n).
Furthermore, we study PCPs of proximity where the verifier is restricted to making a single input query (SIQ). We show that any SIQ-PCP for \mathsf{Ham}_{\alpha} must have a linear proof length, and complement this by presenting a SIQ-PCP with proof length n+o(n).
As an application, we provide new methods that transform PCPs (and IOPs) for arbitrary languages with nonzero completeness error into PCPs (and IOPs) that exhibit perfect completeness. These transformations achieve parameters previously unattained.
ePrint: https://eprint.iacr.org/2024/832
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .