Proximity Testing with Logarithmic Randomness

Proximity Testing with Logarithmic Randomness

2024-03-05 | Benjamin E. Diamond and Jim Posen
The paper introduces a novel approach to proximity testing of linear block codes, focusing on a variant where the witness is sampled from a smaller subset of the subspace rather than uniformly. The authors show that a logarithmic number of random field elements, in the dimension of the subspace, are sufficient to perform an analogous proximity test with only a logarithmic multiplicative loss in the prevalence of false witnesses. This result is particularly useful for applications in succinct noninteractive proofs, including the *Brakedown* protocol. The main contribution is a batching process that reduces the interleaved code's proximity testing problem to the standard proximity testing problem using only logarithmically many random coefficients. The error parameter of this procedure is only slightly worse than the base error parameter for the standard affine parameter test. The authors also discuss the efficiency and simplicity improvements of their approach in the context of polynomial commitment schemes, such as the *Brakedown multilinear polynomial commitment scheme*. They demonstrate how their batching procedure simplifies the testing and evaluation phases of this scheme, reducing the proof size by a factor of \(\sqrt{2}\) and improving both the prover's and verifier's runtimes by a factor of 2, up to lower-order terms. The paper concludes with a detailed proof of the main theorem, which establishes the effectiveness of the batching procedure in the context of interleaved proximity testing.The paper introduces a novel approach to proximity testing of linear block codes, focusing on a variant where the witness is sampled from a smaller subset of the subspace rather than uniformly. The authors show that a logarithmic number of random field elements, in the dimension of the subspace, are sufficient to perform an analogous proximity test with only a logarithmic multiplicative loss in the prevalence of false witnesses. This result is particularly useful for applications in succinct noninteractive proofs, including the *Brakedown* protocol. The main contribution is a batching process that reduces the interleaved code's proximity testing problem to the standard proximity testing problem using only logarithmically many random coefficients. The error parameter of this procedure is only slightly worse than the base error parameter for the standard affine parameter test. The authors also discuss the efficiency and simplicity improvements of their approach in the context of polynomial commitment schemes, such as the *Brakedown multilinear polynomial commitment scheme*. They demonstrate how their batching procedure simplifies the testing and evaluation phases of this scheme, reducing the proof size by a factor of \(\sqrt{2}\) and improving both the prover's and verifier's runtimes by a factor of 2, up to lower-order terms. The paper concludes with a detailed proof of the main theorem, which establishes the effectiveness of the batching procedure in the context of interleaved proximity testing.
Reach us at info@study.space
Understanding Proximity Testing with Logarithmic Randomness