Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptographic protocols / SNARK, Polynomial IOP, Zero-Knowledge

Date: received 24 Aug 2020, last revised 3 Mar 2021

Contact author: alan szepieniec at gmail com, shjdzhangyuncong@sjtu edu cn

Available format(s): PDF | BibTeX Citation

Note: - add co-author Yuncong Zhang - reduce graph-theoretical perspective - include Polynomial IOPs for sparse relations

Version: 20210303:150002 (All versions of this report)

Short URL: ia.cr/2020/1022


[ Cryptology ePrint archive ]