A summary on the FRI low degree test

Ulrich Haböck

Paper 2022/1216 Original: eprint.iacr.org/2022/1216 ↗

A summary on the FRI low degree test

Ulrich Haböck

Abstract

This document is an informal summary on the FRI low degree test [BSBHR18a], [BSCI+20], and DEEP algebraic linking from [BSGKS20]. Based on its most recent soundness analysis [BSCI+20], we discuss parameter settings for practical security levels, how FRI is turned into a polynomial commitment scheme, and the soundness of DEEP sampling in the list decoding regime. In particular, we illustrate the DEEP method applied to proving satisfiability of algebraic intermediate representations and prove a soundness error bound which slightly improves the one in [Sta21].

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
History: 2025-02-20: last updated; 2022-09-13: published
Short URL: https://ia.cr/2022/1216
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2022/1216,
      author = {Ulrich Haböck},
      title = {A summary on the FRI low degree test},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1216},
      year = {2022},
      url = {https://eprint.iacr.org/2022/1216}
}