Welcome to the resource topic for 2023/1478
Title:
Succinct Proofs and Linear Algebra
Authors: Alex Evans, Guillermo Angeris
Abstract:The intuitions behind succinct proof systems are often difficult to separate from some of the deep cryptographic techniques that are used in their construction. In this paper, we show that, using some simple abstractions, a number of commonly-used tools used in the construction of succinct proof systems may be viewed as basic consequences of linear algebra over finite fields. We introduce notation which considerably simplifies these constructions and slowly build a toolkit of useful techniques that can be combined to create different protocols. We also show a simple ‘probabilistic calculus’ which specifies how to combine these tools and bounds on their resulting security. To show the power of these abstractions and toolkit, we give a short proof of the security of the FRI protocol. Along the way, we discuss some natural generalizations of protocols in the literature and propose a conjecture related to proximity testing using linear error-correcting codes that is of independent interest.
ePrint: https://eprint.iacr.org/2023/1478
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .