Polynomial products in Plonkish circuits
Steve Thakur and Kapil Shenvi Pause, Mozak
<br/>
We describe a protocol for multiple univariate polynomial products of varying degrees in a circuit. Each product $$f_{1,j}(X)\cdot f_{2,j}(X) = f_{1,2,j}(X)$$ entails $\deg(f_{1,2,j})+1$ gates in a 2-input 1-output Plonkish circuit. The equations of the form $$ f_{1,j}(X)\cdot f_{2,j}(X) ;=; f_{1,2,j}(X) \mod q_{j}(X)) $$ with $q_{j}(X)$ preprocessed and $f_{1,j}(X)$, $f_{2,j}(X),$ $f_{1,2,j}(X)$ of degree $\leq \deg(q_{j})-1$ (which are more relevant to our use cases), entail $\deg(q_{j})$ gates.
This note is a brief summary of a soon-to-be-released paper which will include security proofs and more details. The two primary use cases are:
field extension arithmetic in a circuit