A Generalized Framework for Folding Codes and Applications to Proofs of Proximity
Type
presentation
Date Issued
2024-05-25
Author(s)
Abstract
Deciding whether a vector belongs to a given error-correcting code or whether it is far from the code is a problem known as proximity testing. Over the last decade, two-party proximity testing protocols to prove the knowledge of a codeword have found a particular interest in designing succinct non-interactive arguments, along with applications in verifiable computation fulfilling post-quantum security. The framework of Interactive Oracle Proof of Proximity (IOPP) models the semantics of such probabilistic proof protocols and provides metrics to evaluate their efficiency. In particular, building protocols with very efficient, i.e., poly-logarithmic verification time, is considered a central challenge to achieving scalable IOPPs. We follow a line of work that started with the FRI protocol of Ben-Sasson et al. for Reed-Solomon codes, and more recently with the work of Bordage et al. for Algebraic Geometry codes over Kummer curves and the Hermitian tower.
We propose a generalization of these protocols for a wider class of codes satisfying some simple conditions associated with pairs of linear representations. In this talk, we will extend the core idea of recursively folding a code into a sequence of codes of reduced length and dimensions by translating the behavior of the protocol to the language of linear algebra and group actions. Based on this correspondence, we aim to identify a set of necessary conditions on the code's suitability for folding in the previous fashion by reformulating the construction of the code's folding sequence and the execution of the protocol in terms of the tested code's generator matrix. Moreover, we investigate how some sufficient properties (in particular, the assumptions for foldable Reed-Solomon codes and Algebraic Geometry codes) impact the soundness and efficiency of the protocol and classify tradeoffs achievable on the more generic folding-friendly codes. 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.
We propose a generalization of these protocols for a wider class of codes satisfying some simple conditions associated with pairs of linear representations. In this talk, we will extend the core idea of recursively folding a code into a sequence of codes of reduced length and dimensions by translating the behavior of the protocol to the language of linear algebra and group actions. Based on this correspondence, we aim to identify a set of necessary conditions on the code's suitability for folding in the previous fashion by reformulating the construction of the code's folding sequence and the execution of the protocol in terms of the tested code's generator matrix. Moreover, we investigate how some sufficient properties (in particular, the assumptions for foldable Reed-Solomon codes and Algebraic Geometry codes) impact the soundness and efficiency of the protocol and classify tradeoffs achievable on the more generic folding-friendly codes. 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
Keywords
Proof of Proximity
Code Equivalence
Group Actions
HSG Classification
contribution to scientific community
Refereed
Yes
Event Title
International Workshop on Code-Based Cryptography
Event Location
Zürich, Switzerland
Event Date
25-26 May 2024
Subject(s)
File(s)![Thumbnail Image]()
open.access
Name
Pasquereau_Adrien_CBC24.pdf
Size
703.27 KB
Format
Adobe PDF
Checksum (MD5)
0f83817eb1d5e8745956902ea30009d1