Paper 2024/832

Hamming Weight Proofs of Proximity with One-Sided Error

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 $$ with one-sided error and sublinear proof length in three models (MA, PCP, IOP), where stronger models allow for smaller query complexity. For $$-bit input vectors, highlighting input query complexity, our MA has $$ query complexity, the PCP makes $$ 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 $$ with input query complexity $$ has proof length $$. 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 $$ must have a linear proof length, and complement this by presenting a SIQ-PCP with proof length $$. 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.