A Generalized Framework for Folding Codes and Applications to Proofs of Proximity
Type
presentation
Date Issued
2024-06-07
Author(s)
Abstract
Deciding whether a vector is far from a given error-correcting code is a problem known as proximity testing. In two party computation, Interactive Oracle Proof of Proximity (IOPP) protocols model the semantics of (probabilistic) proximity testing. By translating the behavior of the protocols proposed by Ben-Sasson et al. (for Reed-Solomon codes) and Bordage et al. (for Algebraic Geometry Codes over Kummer Curves) from the point of view of function evaluation to the language of representation theory, we will describe a framework extending the idea of recursively folding a code into a sequence of codes of reduced length and dimensions. Our correspondence leads to a generalization for a wider class of codes, while also providing conditions for folding codes simply in terms of their generator matrices and some families of group actions. As a work in progress, we discuss the feasibility of folding algorithms in other metrics, and provide insights for when the protocol fails to generalize.
Language
English
HSG Classification
contribution to scientific community
Refereed
Yes
Event Title
Combinatorics 2024
Event Location
Carovigno (Br), Italy
Event Date
3-7 June 2024
Subject(s)
File(s)![Thumbnail Image]()
Name
Pasquereau_Combinatorics24.pdf
Size
690.58 KB
Format
Adobe PDF
Checksum (MD5)
988ddf27c6eed507e70c141b8207a23d