Paper 2022/1216
A summary on the FRI low degree test
, Polygon Labs, Orbis Labs, Horizen Labs, Inc.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].
Note: Correction of typo in FRI soundness error, example security parameters changed to algebraic batching.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Interactive Oracle ProofsSTARKLow Degree TestingFRI
- Contact author(s)
- uhaboeck @ polygon technology
- History
- 2023-03-31: last of 2 revisions
- 2022-09-13: received
- See all versions
- Short URL
- https://ia.cr/2022/1216
- License
-
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}
}
