Paper 2023/630

Proximity Testing with Logarithmic Randomness

Benjamin E. Diamond, Ulvetanna
Jim Posen, Ulvetanna

A fundamental result dating to Ligero (CCS '17) establishes that each fixed linear block code exhibits proximity gaps with respect to the collection of affine subspaces, in the sense that each given subspace either resides entirely close to the code, or else contains only a small portion which resides close to the code. In particular, any given subspace's failure to reside entirely close to the code is necessarily witnessed, with high probability, by a uniformly randomly sampled element of that subspace. We investigate a variant of this phenomenon in which the witness is not sampled uniformly from the subspace, but rather from a much smaller subset of it. We show that a logarithmic number of random field elements (in the dimension of the subspace) suffice to effect an analogous proximity test, with moreover only a logarithmic (multiplicative) loss in the possible prevalence of false witnesses. We discuss applications to recent noninteractive proofs based on linear codes, including Brakedown and Orion (CRYPTO '22).

Available format(s)
Cryptographic protocols
Publication info
Contact author(s)
bdiamond @ ulvetanna io
jposen @ ulvetanna io
2023-05-03: approved
2023-05-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Benjamin E. Diamond and Jim Posen},
      title = {Proximity Testing with Logarithmic Randomness},
      howpublished = {Cryptology ePrint Archive, Paper 2023/630},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.