eprint.iacr.org will be offline for approximately an hour for routine maintenance again at 10pm UTC on Wednesday, April 17.

Paper 2022/1216

A summary on the FRI low degree test

Ulrich Haböck, 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
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.