Adrien Pasquereau
Last Name
Pasquereau
First name
Adrien
Email
adrien.pasquereau@unisg.ch
Phone
+41 71 224 78 63
2 results
Now showing 1 - 2 of 2
- Some of the metrics are blocked by yourconsent settings
Item type:Publication, A Generalized Framework for Folding Codes and Applications to Proofs of Proximity(2024-05-25)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.Type:presentation - Some of the metrics are blocked by yourconsent settings
Item type:Publication, A Generalized Framework for Folding Codes and Applications to Proofs of Proximity(2024-06-07)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.Type:presentation