[Resource Topic] 2023/1611: Power circuits: a new arithmetization for GKR-styled sumcheck

Welcome to the resource topic for 2023/1611

Power circuits: a new arithmetization for GKR-styled sumcheck

Authors: Lev Soukhanov


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 .