Paper 2023/630
Proximity Testing with Logarithmic Randomness
Abstract
A fundamental result dating to Ligero (Des. Codes Cryptogr. '23) 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 (CRYPTO '23).
Note: Final published version.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- A minor revision of an IACR publication in CIC 2024
- DOI
- 10.62056/aksdkp10
- Contact author(s)
-
bdiamond @ ulvetanna io
jposen @ ulvetanna io - History
- 2024-04-18: last of 3 revisions
- 2023-05-02: received
- See all versions
- Short URL
- https://ia.cr/2023/630
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/630,
author = {Benjamin E. Diamond and Jim Posen},
title = {Proximity Testing with Logarithmic Randomness},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/630},
year = {2023},
doi = {10.62056/aksdkp10},
url = {https://eprint.iacr.org/2023/630}
}
