Paper 2023/1478

Succinct Proofs and Linear Algebra

Alex Evans, Bain Capital Crypto
Guillermo Angeris, Bain Capital Crypto

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.

Available format(s)
Publication info
Succinct proofslinear algebrazero knowledge
Contact author(s)
aevans @ baincapital com
gangeris @ baincapital com
2023-11-22: revised
2023-09-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alex Evans and Guillermo Angeris},
      title = {Succinct Proofs and Linear Algebra},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1478},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.