Doubly Sub-linear Interactive Proofs of Proximity (dsIPPs) for Approximate Verification

We study doubly sub-linear interactive proofs of proximity (dsIPPs), which can prove properties without reading the entire data. In this approach, generating the proof requires reading only a sub-linear portion of the input data, and the verification step aims for an ultra-fast process that requires reading an even smaller amount of data.

This system leverages the principles of Property Testing. An honest prover can pass the verifier for input that has a certain property, but a prover with input that is far from the property cannot fool the verifier.

The research team built proof schemes applicable to the following cases:

• Any property decidable by a ROOBP (Read-Once Oblivious Branching Program)
• Approximate verification of the Hamming weight of the input data
• A relaxed model of Bipartiteness in the bounded-degree graph model