Paper 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.
Keywords
Interactive Oracle Proofs STARK Low Degree Testing FRI
Contact author(s)
team @ orbislabs com
History
2022-09-21: revised
2022-09-13: received
See all versions
Short URL
https://ia.cr/2022/1216
License
Creative Commons Attribution
CC BY

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},
      note = {\url{https://eprint.iacr.org/2022/1216}},
      url = {https://eprint.iacr.org/2022/1216}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.