We provide a wide systematic study of proximity proofs with one-sided error for the Hamming weight problem \(\textsf{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 \(\textsf{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(\textrm{log} n)\) query complexity, the PCP makes \(O(\textrm{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 \(\textsf{Ham}_{\alpha }\) with input query complexity \(n^{1-\epsilon }\) has proof length \(\varOmega (\textrm{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 \(\textsf{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.

Hamming Weight Proofs of Proximity with One-Sided Error

会议论文
发表日期：

2025年

查看全文

Gal Arnon,
Shany Ben-David,
Eylon Yogev

摘要

We provide a wide systematic study of proximity proofs with one-sided error for the Hamming weight problem \(\textsf{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 \(\textsf{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(\textrm{log} n)\) query complexity, the PCP makes \(O(\textrm{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 \(\textsf{Ham}_{\alpha }\) with input query complexity \(n^{1-\epsilon }\) has proof length \(\varOmega (\textrm{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 \(\textsf{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.