Welcome to the resource topic for 2023/1611
Title:
Power circuits: a new arithmetization for GKR-styled sumcheck
Authors: Lev Soukhanov
Abstract:Goldwasser-Kalai-Rothblum protocol (GKR) for layered circuits is a sumcheck-based argument of knowledge for layered circuits, running in \sim 2\mu \ell amount of rounds, where \ell is the amount of layers and \mu is the average layer logsize.
For a layer $i$ of size $2^{\mu_i}$ the main work consists of running a sumcheck protocol of the form \[\underset{x,y}{\sum} \text{Add}_i(x,y,z)(f(x)+f(y)) + \text{Mul}_i(x,y,z)f(x)f(y)\] over a $2^{2\mu_i}$-dimensional cube, where $\text{Add}_i(x,y,z)$ and $\text{Mul}_i(x,y,z)$ are (typically relatively sparse) polynomials called "wiring predicates".
We present a different approach, based on the (trivial) observation that multiplication can be expressed through linear operations and squaring.
This leads to the different wiring, which is marginally more efficient even in a worst-case scenario, and decreases the amount of communication $\sim 2 \times$ in the case where wiring predicates are sparse.
ePrint: https://eprint.iacr.org/2023/1611
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 .