Paper 2023/1611
Power circuits: a new arithmetization for GKRstyled sumcheck
Abstract
GoldwasserKalaiRothblum protocol (GKR) for layered circuits is a sumcheckbased 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 worstcase scenario, and decreases the amount of communication $\sim 2 \times$ in the case where wiring predicates are sparse.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint.
 Keywords
 verifiable computationcircuit evaluationGKR
 Contact author(s)
 0xdeadfae @ gmail com
 History
 20231020: approved
 20231017: received
 See all versions
 Short URL
 https://ia.cr/2023/1611
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/1611, author = {Lev Soukhanov}, title = {Power circuits: a new arithmetization for GKRstyled sumcheck}, howpublished = {Cryptology ePrint Archive, Paper 2023/1611}, year = {2023}, note = {\url{https://eprint.iacr.org/2023/1611}}, url = {https://eprint.iacr.org/2023/1611} }