Communications in Cryptology IACR CiC

Proximity Testing with Logarithmic Randomness

Authors

Benjamin E. Diamond, Jim Posen
Benjamin E. Diamond
Ulvetanna, United States
bdiamond at ulvetanna dot io
Jim Posen
Ulvetanna, United States
jposen at ulvetanna dot io
Keywords: proximity testing succinct arguments error-correcting codes

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).

References

[AHIV23]
Scott Ames, Carmit Hazay, Yuval Ishai, and Muthuramakrishnan Venkitasubramaniam. Ligero: lightweight sublinear arguments without a trusted setup. Designs, Codes and Cryptography, 2023. https://doi.org/10.1007/s10623-023-01222-8.
Google Scholar ePrint
[BCC+16]
Jonathan Bootle, Andrea Cerulli, Pyrros Chaidos, Jens Groth, and Christophe Petit. Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology – EUROCRYPT 2016, 327–357. Berlin, Heidelberg, 2016. Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-662-49896-5_12.
Google Scholar ePrint
[BCG20]
Jonathan Bootle, Alessandro Chiesa, and Jens Groth. Linear-time arguments with sublinear verification from tensor codes. In Rafael Pass and Krzysztof Pietrzak, editors, Theory of Cryptography, 19–46. Cham, 2020. Springer International Publishing. https://doi.org/10.1007/978-3-030-64378-2_2.
Google Scholar ePrint
[BS22]
Alexandre Belling and Azam Soleimanian. Vortex: building a lattice-based snark scheme with transparent setup. 2022.
Google Scholar ePrint
[BSCI+23]
Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, and Shubhangi Saraf. Proximity gaps for reed–solomon codes. Journal of the ACM, 10 2023. https://doi.org/10.1145/3614423.
Google Scholar ePrint
[BSCS16]
Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. Interactive oracle proofs. In International Conference on Theory of Cryptography, volume 9986, 31–60. Berlin, Heidelberg, 2016. Springer-Verlag. https://doi.org/10.1007/978-3-662-53644-5_2.
Google Scholar ePrint
[BSKS18]
Eli Ben-Sasson, Swastik Kopparty, and Shubhangi Saraf. Worst-case to average case reductions for the distance to a code. In Rocco A. Servedio, editor, 33rd Computational Complexity Conference, 24:1–24:23. Dagstuhl Publishing, 2018. https://doi.org/?
Google Scholar ePrint
[CHM+20]
Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Noah Vesely, and Nicholas Ward. Marlin: preprocessing zkSNARKs with universal and updatable SRS. In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology – EUROCRYPT 2020, Lecture Notes in Computer Science, 738–768. Cham, 2020. Springer International Publishing. https://doi.org/10.1007/978-3-030-45721-1_26.
Google Scholar ePrint
[GLS+23]
Alexander Golovnev, Jonathan Lee, Srinath Setty, Justin Thaler, and Riad S. Wahby. Brakedown: linear-time and field-agnostic SNARKs for R1CS. In Helena Handschuh and Anna Lysyanskaya, editors, Advances in Cryptology – CRYPTO 2023, 193–226. Cham, 2023. Springer Nature Switzerland. https://doi.org/10.1007/978-3-031-38545-2_7.
Google Scholar ePrint
[HL10]
Carmit Hazay and Yehuda Lindell. Efficient Secure Two-Party Protocols. Information Security and Cryptography. Springer, Berlin, Heidelberg, 2010.
Google Scholar ePrint
[Set20]
Srinath Setty. Spartan: efficient and general-purpose zkSNARKs without trusted setup. In Daniele Micciancio and Thomas Ristenpart, editors, Advances in Cryptology – CRYPTO 2020, 704–737. Cham, 2020. Springer International Publishing. https://doi.org/10.1007/978-3-030-56877-1_25.
Google Scholar ePrint
[XZS22]
Tiancheng Xie, Yupeng Zhang, and Dawn Song. Orion: zero knowledge proof with linear prover time. In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology – CRYPTO 2022, 299–328. Berlin, Heidelberg, 2022. Springer-Verlag. https://doi.org/10.1007/978-3-031-15985-5_11.
Google Scholar ePrint

PDFPDF Open access

DOI: https://doi.org/10.62056/aksdkp10
History
Submitted: 2023-12-11
Accepted: 2024-03-05
Published: 2024-04-09
How to cite

Benjamin E. Diamond and Jim Posen, "Proximity Testing with Logarithmic Randomness," IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/aksdkp10.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.