Paper 2020/1022
Polynomial IOPs for Linear Algebra Relations
Alan Szepieniec and Yuncong Zhang
Abstract
This paper proposes new Polynomial IOPs for arithmetic circuits. They rely on the monomial coefficient basis to represent the matrices and vectors arising from the arithmetic constraint satisfaction system, and build on new protocols for establishing the correct computation of linear algebra relations such as matrix-vector products and Hadamard products. Our protocols give rise to concrete proof systems with succinct verification when compiled down with a cryptographic compiler whose role is abstracted away in this paper. Depending only on the compiler, the resulting SNARKs are either transparent or rely on a trusted setup.
Note: add sponsor
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- A minor revision of an IACR publication in PKC 2022
- Keywords
- SNARKPolynomial IOPZero-Knowledge
- Contact author(s)
-
alan szepieniec @ gmail com
shjdzhangyuncong @ sjtu edu cn - History
- 2021-12-02: last of 8 revisions
- 2020-08-27: received
- See all versions
- Short URL
- https://ia.cr/2020/1022
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/1022,
author = {Alan Szepieniec and Yuncong Zhang},
title = {Polynomial {IOPs} for Linear Algebra Relations},
howpublished = {Cryptology {ePrint} Archive, Paper 2020/1022},
year = {2020},
url = {https://eprint.iacr.org/2020/1022}
}
