Proximity Testing with Logarithmic Randomness

Proximity Testing with Logarithmic Randomness

2024-03-05 | Benjamin E. Diamond and Jim Posen
This paper introduces a new method for proximity testing of linear block codes, which reduces the problem of testing an interleaved code to a standard proximity test. The method uses only logarithmically many random coefficients, resulting in a logarithmic multiplicative loss in the possible prevalence of false witnesses. The approach is applied to recent noninteractive proofs based on linear codes, including Brakedown. The paper discusses the implications of this method for applications such as polynomial commitment schemes and zero-knowledge proofs. It also presents a detailed proof of a key result regarding proximity gaps for affine lines, which is used to establish the correctness of the new proximity test. The paper shows that the new method achieves a favorable tradeoff between randomness and soundness, requiring only logarithmically many parameters and incurring only logarithmic multiplicative soundness loss. The method is particularly effective for proximity parameters smaller than a third of the code's distance. The paper also discusses the implications of this result for the efficiency and security of various cryptographic protocols, including the Brakedown scheme and the Orion protocol.This paper introduces a new method for proximity testing of linear block codes, which reduces the problem of testing an interleaved code to a standard proximity test. The method uses only logarithmically many random coefficients, resulting in a logarithmic multiplicative loss in the possible prevalence of false witnesses. The approach is applied to recent noninteractive proofs based on linear codes, including Brakedown. The paper discusses the implications of this method for applications such as polynomial commitment schemes and zero-knowledge proofs. It also presents a detailed proof of a key result regarding proximity gaps for affine lines, which is used to establish the correctness of the new proximity test. The paper shows that the new method achieves a favorable tradeoff between randomness and soundness, requiring only logarithmically many parameters and incurring only logarithmic multiplicative soundness loss. The method is particularly effective for proximity parameters smaller than a third of the code's distance. The paper also discusses the implications of this result for the efficiency and security of various cryptographic protocols, including the Brakedown scheme and the Orion protocol.
Reach us at info@study.space