cq.tex

% !tex encoding = utf-8 unicode

% this is a simple template for a latex document using the "article" class.
% see "book", "report", "letter" for other types of document.

\documentclass[11pt]{article} % use larger type; default would be 10pt



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% packages
\usepackage[
    type={CC},
    modifier={by-nc-sa},
    version={3.0},
]{doclicense}

\usepackage[utf8]{inputenc} % set input encoding (not needed with xelatex)
\usepackage[strict]{changepage}
    
    %%% examples of article customizations
    % these packages are optional, depending whether you want the features they provide.
    % see the latex companion or other references for full information.
    
    
    %%% page dimensions
\usepackage{geometry} % to change the page dimensions
\geometry{a4paper} % or letterpaper (us) or a5paper or....
    % \geometry{margin=2in} % for example, change the margins to 2 inches all round
    % \geometry{landscape} % set up the page for landscape
    %   read geometry.pdf for detailed page layout information
 \usepackage{numdef}
   
\usepackage{graphicx} % support the \includegraphics command and options
    % some of the article customisations are relevant for this class
\usepackage{amsmath,amsthm}
\usepackage{amsfonts} % math fonts such as \mathbb{}
\usepackage{amssymb} % \therefore
% \usepackage{bickham}
\usepackage{hyperref}
\usepackage{cryptocode}
\usepackage{framed} 
    % \usepackage[parfill]{parskip} % activate to begin paragraphs with an empty line rather than an indent
    
    %%% packages
\usepackage{booktabs} % for much better looking tables
\usepackage{array} % for better arrays (eg matrices) in maths
\usepackage{paralist} % very flexible & customisable lists (eg. Enumerate/itemize, etc.)
\usepackage{verbatim} % adds environment for commenting out blocks of text & for better verbatim
\usepackage{subfig} % make it possible to include more than one captioned figure/table in a single float
    % % these packages are all incorporated in the memoir class to one degree or another...
\usepackage{mathrsfs}
\usepackage{booktabs}
\usepackage{makecell}
\usepackage{adjustbox}

\usepackage{pgfplots}

\renewcommand\theadalign{bc}
\renewcommand\theadfont{\bfseries}
\renewcommand\theadgape{\Gape[4pt]}
  
    %%% headers & footers
\usepackage{fancyhdr} % this should be set after setting up the page geometry
\pagestyle{fancy} % options: empty , plain , fancy
\renewcommand{\headrulewidth}{0pt} % customise the layout...
\lhead{}\chead{}\rhead{}
\lfoot{}\cfoot{\thepage}\rfoot{}
    
    
    %%% section title appearance
\usepackage{sectsty}
\allsectionsfont{\sffamily\mdseries\upshape} % (see the fntguide.pdf for font help)
    % (this matches context defaults)
    
    %%% toc (table of contents) appearance
\usepackage[nottoc,notlof,notlot]{tocbibind} % put the bibliography in the toc
\usepackage[titles,subfigure]{tocloft} % alter the style of the table of contents
\renewcommand{\cftsecfont}{\rmfamily\mdseries\upshape}
\renewcommand{\cftsecpagefont}{\rmfamily\mdseries\upshape} % no bold!

 %%% end article customizations
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 % macros
 \newcommand{\code}[1]{\texttt{#1}}
\newcommand\tstrut{\rule{0pt}{2.6ex}}         % = `top' strut
\newcommand\bstrut{\rule[-0.9ex]{0pt}{0pt}}   % = `bottom' strut
\newcommand{\bgamma}{\boldsymbol{\gamma}}
\newcommand{\bsigma}{\boldsymbol{\sigma}}
\newcommand{\plonk}{\ensuremath{\mathcal{P} \mathfrak{lon}\mathcal{K}}\xspace}
\newcommand{\cq}{\ensuremath{\mathpgoth{cq} }\xspace}
\newcommand{\cqstar}{\ensuremath{\mathpgoth{cq^{\mathbf{*}} }}\xspace}
\newcommand{\flookup}{\ensuremath{\mathsf{\mathpgoth{Flookup}}}\xspace}
\newcommand{\baloo}{\ensuremath{\mathrm{ba}\mathit{loo}}\xspace}
\newcommand{\caulkp}{\ensuremath{\mathsf{\mathrel{Caulk}\mathrel{\scriptstyle{+}}}}\xspace}
\newcommand{\caulk}{\ensuremath{\mathsf{Caulk}}\xspace}
\newcommand{\plookup}{\ensuremath{\mathpgoth{plookup}}\xspace}
\newcommand{\tablegroup}{\ensuremath{\mathbb{H}}\xspace}
\newcommand{\V}{\ensuremath{\mathbf{V} }\xspace}



% \newcommand{\plonk}{\ensuremath{\mathtt{PLONK}}\xspace}
\newcommand{\papertitle}{\cq:\footnote{Pronounced ``seek you''.} Cached quotients for fast lookups}
%\newcommand{\authorname}}
\newcommand{\company}{}
\title{ \bf \papertitle \\[0.72cm]}
\author{ Liam Eagen \\ \tt{Alpen Labs} \and  Dario Fiore \\ \tt{IMDEA software institute}  \and Ariel Gabizon \\ \tt{Aztec Labs} } 
% 
% 	\large{\authorname} \\[0.5cm] \large{\company}
% 	\\ {DRAFT}
%}
%\date{} % activate to display a given date or no date (if empty),

% otherwise the current date is printed 
\DeclareMathAlphabet{\mathpgoth}{OT1}{pgoth}{m}{n}	
\ProvidesPackage{numdef}



%% Ariel Macros:
\num\newcommand{\G1}{\ensuremath{{\mathbb G}_1}\xspace}
\newcommand{\Gi}{\ensuremath{{\mathbb G}_i}\xspace}
%\newcommand{\G}{\ensuremath{{\mathbb G}}\xspace}
\newcommand{\Gstar}{\ensuremath{{\mathbb G}^*}\xspace}
\newcommand{\x}{\ensuremath{\mathbf{x}}\xspace}
\newcommand{\z}{\ensuremath{\mathbf{z}}\xspace}
\newcommand{\X}{\ensuremath{\mathbf{X}}\xspace}

\num\newcommand{\G2}{\ensuremath{{\mathbb G}_2}\xspace}
%\num\newcommand{\G11}{\ensuremath{\G1\setminus \set{0} }\xspace}
%\num\newcommand{\G21}{\ensuremath{\G2\setminus \set{0} }\xspace}
\newcommand{\grouppair}{\ensuremath{G^*}\xspace}
\newcommand{\prvperm}{\ensuremath{\mathrm{P_{\mathsf{\sigma}}}}\xspace}
\newcommand{\verperm}{\ensuremath{\mathrm{V_{\mathsf{\sigma}}}}\xspace}
\newcommand{\alg}{\ensuremath{\mathscr{A}}\xspace}

\newcommand{\Gt}{\ensuremath{{\mathbb G}_t}\xspace}
\newcommand{\F}{\ensuremath{\mathbb F}\xspace}
\newcommand{\Fstar}{\ensuremath{\mathbb F^*}\xspace}

\newcommand{\help}[1]{$#1$-helper\xspace}
\newcommand{\randompair}[1]{\ensuremath{\mathsf{randomPair}(#1)}\xspace}
\newcommand{\pair}[1]{$#1$-pair\xspace}
\newcommand{\pairs}[1]{$#1$-pairs\xspace}
\newcommand{\chalpoint}{\ensuremath{\mathfrak{z}}\xspace}

\newcommand{\pairone}[1]{\G1-$#1$-pair\xspace}
\newcommand{\pairtwo}[1]{\G2-$#1$-pair\xspace}
\newcommand{\sameratio}[2]{\ensuremath{\mathsf{SameRatio}(#1,#2)}\xspace}
\newcommand{\vecc}[2]{\ensuremath{(#1)_{#2}}\xspace}
\newcommand{\players}{\ensuremath{[n]}\xspace}
\newcommand{\adv}{\ensuremath{\mathcal A}\xspace}
\newcommand{\advprime}{\ensuremath{{\mathcal A}'}\xspace}
\newcommand{\extprime}{\ensuremath{E'}\xspace}
\newcommand{\advrand}{\ensuremath{\mathsf{rand}_{\adv}}\xspace}
% \num\newcommand{\srs1}{\ensuremath{\mathsf{srs_1}}\xspace}
% \num\newcommand{\srs2}{\ensuremath{\mathsf{srs_2}}\xspace}
\newcommand{\srs}{\ensuremath{\mathsf{srs}}\xspace}
\newcommand{\srsbase}{\ensuremath{\mathsf{srs_0}}\xspace}
\newcommand{\srsi}{\ensuremath{\mathsf{srs_i}}\xspace}
\newcommand{\com}{\ensuremath{\mathsf{com}}\xspace}
\newcommand{\comperm}{\ensuremath{\mathsf{com_{\sigma}}}\xspace}
\newcommand{\cm}{\ensuremath{\mathsf{cm}}\xspace}
\newcommand{\cmsig}{\ensuremath{\mathsf{cm_\sigma}}\xspace}
\newcommand{\open}{\ensuremath{\mathsf{open}}\xspace}
\newcommand{\openperm}{\ensuremath{\mathsf{open_{\sigma}}}\xspace}
\newcommand{\sigof}[1]{\ensuremath{\sigma(#1)}\xspace}
\newcommand{\proverexp}{\ensuremath{\mathsf{e}}\xspace}
\newcommand{\reducedelems}{\ensuremath{\mathsf{r}}\xspace}

\newcommand{\ci}{\ensuremath{\mathrm{CI}}\xspace}
\renewcommand{\deg}{\ensuremath{\mathrm{deg}}\xspace}
\newcommand{\pairvec}[1]{$#1$-vector\xspace}
\newcommand{\Fq}{\ensuremath{\mathbb{F}_q}\xspace}
\newcommand{\randpair}[1]{\ensuremath{\mathsf{rp}_{#1}}\xspace}
\newcommand{\randpairone}[1]{\ensuremath{\mathsf{rp}_{#1}^{1}}\xspace}
\newcommand{\abase}{\ensuremath{A_{\mathrm{\mathbf{0}}}}\xspace}
\newcommand{\bbase}{\ensuremath{B_{\mathrm{\mathbf{0}}}}\xspace}
\newcommand{\cbase}{\ensuremath{C_{\mathrm{\mathbf{0}}}}\xspace}
\newcommand{\bliop}[1]{\ensuremath{\mathsf{#1{\text{-}}{BLIOP}}}\xspace}
\newcommand{\blop}{\ensuremath{\mathsf{\mathscr{BL} {\text{-}}IOP}}\xspace}
\newcommand{\openprotinput}{\ensuremath{\mathcal{O}}\xspace}
\newcommand{\amid}{\ensuremath{A_{\mathrm{mid}}}\xspace}
\newcommand{\bmid}{\ensuremath{B_{\mathrm{mid}}}\xspace}
\newcommand{\cmid}{\ensuremath{C_{\mathrm{mid}}}\xspace}

\newcommand{\negl}{\ensuremath{\mathsf{negl}(\lambda)}\xspace}
\newcommand{\randpairtwo}[1]{\ensuremath{\mathsf{rp_{#1}^2}}\xspace}%the randpair in G2
\newcommand{\nilp}{\ensuremath{\mathscr N}\xspace}
\newcommand{\groupgen}{\ensuremath{\mathscr G}\xspace}
\newcommand{\qap}{\ensuremath{\mathscr Q}\xspace}
\newcommand{\polprot}[4]{$(#1,#2,#3,#4)$-polynomial protocol}
\newcommand{\rangedprot}[5]{$#5$-ranged $(#1,#2,#3,#4)$-polynomial protocol}

\newcommand{\rej}{\ensuremath{\mathsf{rej}}\xspace}
\newcommand{\acc}{\ensuremath{\mathsf{acc}}\xspace}
\newcommand{\res}{\ensuremath{\mathsf{res}}\xspace}
\newcommand{\sha}[1]{\ensuremath{\mathsf{COMMIT}(#1)}\xspace}
 \newcommand{\shaa}{\ensuremath{\mathsf{COMMIT}}\xspace}
 \newcommand{\comm}[1]{\ensuremath{\mathsf{comm}_{#1}}\xspace}
 \newcommand{\defeq}{:=}

\newcommand{\B}{\ensuremath{\vec{B}}\xspace}
\newcommand{\dom}{\ensuremath{H}\xspace}
\newcommand{\C}{\ensuremath{\vec{C}}\xspace}
\newcommand{\Btwo}{\ensuremath{\vec{B_2}}\xspace}
\newcommand{\treevecsimp}{\ensuremath{(\tau,\rho_A,\rho_A \rho_B,\rho_A\alpha_A,\rho_A\rho_B\alpha_B, \rho_A\rho_B\alpha_C,\beta,\beta\gamma)}\xspace}% The sets of elements used in simplifed relation tree in main text body
\newcommand{\rcptc}{random-coefficient subprotocol\xspace}
\newcommand{\rcptcparams}[2]{\ensuremath{\mathrm{RCPC}(#1,#2)}\xspace}
\newcommand{\verifyrcptcparams}[2]{\ensuremath{\mathrm{\mathsf{verify}RCPC}(#1,#2)}\xspace}
\newcommand{\randadv}{\ensuremath{\mathsf{rand}_{\adv}}\xspace}
 \num\newcommand{\ex1}[1]{\ensuremath{ #1\cdot g_1}\xspace}
 \num\newcommand{\ex2}[1]{\ensuremath{#1\cdot g_2}\xspace}
 \newcommand{\pr}{\mathrm{Pr}}
 \newcommand{\powervec}[2]{\ensuremath{(1,#1,#1^{2},\ldots,#1^{#2})}\xspace}
 \newcommand{\partition}{\ensuremath{{\mathcal T}}\xspace}
 \newcommand{\partof}[1]{\ensuremath{{\partition_{#1}}}\xspace}
\num\newcommand{\out1}[1]{\ensuremath{\ex1{\powervec{#1}{d}}}\xspace}
\num\newcommand{\out2}[1]{\ensuremath{\ex2{\powervec{#1}{d}}}\xspace}
 \newcommand{\nizk}[2]{\ensuremath{\mathrm{NIZK}(#1,#2)}\xspace}% #2 is the hash concatenation input
 \newcommand{\verifynizk}[3]{\ensuremath{\mathrm{VERIFY\mhyphen NIZK}(#1,#2,#3)}\xspace}
\newcommand{\protver}{protocol verifier\xspace} 
\newcommand{\hash}{\ensuremath{\mathcal{H}}\xspace} 
\newcommand{\mulgroup}{\ensuremath{\F^*}\xspace}
\newcommand{\lag}[1]{\ensuremath{L_{#1}}\xspace} 
\newcommand{\sett}[2]{\ensuremath{\set{#1}_{#2}}\xspace}
\newcommand{\omegaprod}{\ensuremath{\alpha_{\omega}}\xspace}
\newcommand{\lagvec}[1]{\ensuremath{\mathrm{LAG}_{#1}}\xspace}
\newcommand{\trapdoor}{\ensuremath{r}}
\newcommand{\trapdoorext}{\ensuremath{r_{\mathrm{ext}}}\xspace}
\newcommand{\trapdoorsim}{\ensuremath{r_{\mathrm{sim}}}\xspace}
\renewcommand{\mod}{\ensuremath{\;\mathrm{mod}\;}}
\newcommand{\hsub}{\ensuremath{H^*}\xspace}
\num\newcommand{\enc1}[1]{\ensuremath{\left[#1\right]_1}\xspace}
\newcommand{\enci}[1]{\ensuremath{\left[#1\right]_i}\xspace}
\num\newcommand{\enc2}[1]{\ensuremath{\left[#1\right]_2}\xspace}
\newcommand{\gen}{\ensuremath{\mathsf{gen}}\xspace}
\newcommand{\prv}{\ensuremath{\mathsf{\mathbf{P}}}\xspace}
\newcommand{\prvpoly}{\ensuremath{\mathrm{P_{\mathsf{poly}}}}\xspace}
\newcommand{\prvpc}{\ensuremath{\mathrm{P_{\mathsf{PC}}}}\xspace}
\newcommand{\verpoly}{\ensuremath{\mathrm{V_{\mathsf{poly}}}}\xspace}
\newcommand{\verpc}{\ensuremath{\mathrm{V_{\mathsf{PC}}}}\xspace}
\newcommand{\ideal}{\ensuremath{\mathcal{I}}\xspace}
\newcommand{\prf}{\ensuremath{\pi}\xspace}
\newcommand{\simprv}{\ensuremath{\mathrm{P^{sim}}}\xspace}

%\newcommand{\enc}[1]{\ensuremath{\left[#1\right]}\xspace}
%\num\newcommand{\G0}{\ensuremath{\mathbf{G}}\xspace}
\newcommand{\GG}{\ensuremath{\mathbf{G^*}}\xspace}  % would have liked to call this G01 but problem with name
\num\newcommand{\g0}{\ensuremath{\mathbf{g}}\xspace}
\newcommand{\inst}{\ensuremath{\phi}\xspace}
\newcommand{\inp}{\ensuremath{\mathsf{x}}\xspace}
\newcommand{\wit}{\ensuremath{\omega}\xspace}
\newcommand{\ver}{\ensuremath{\mathsf{\mathbf{V}}}\xspace}
\newcommand{\per}{\ensuremath{\mathsf{\mathbf{P}}}\xspace}
\newcommand{\sonic}{\ensuremath{\mathsf{Sonic}}\xspace}
\newcommand{\aurora}{\ensuremath{\mathsf{Aurora}}\xspace}
\newcommand{\auroralight}{\ensuremath{\mathsf{Auroralight}}\xspace}
\newcommand{\groth}{\ensuremath{\mathsf{Groth'16}}\xspace}
\newcommand{\kate}{\ensuremath{\mathsf{KZG}}\xspace}
\newcommand{\rel}{\ensuremath{\mathcal{R}}\xspace}
\newcommand{\lang}{\ensuremath{\mathcal{L}}\xspace}
\newcommand{\ext}{\ensuremath{E}\xspace}
\newcommand{\params}{\ensuremath{\mathsf{params}_{\inst}}\xspace}
\newcommand{\protparams}{\ensuremath{\mathsf{params}_{\inst}^\advv}\xspace}
\num\newcommand{\p1}{\ensuremath{P_1}\xspace}
\newcommand{\advv}{\ensuremath{ {\mathcal A}^{\mathbf{*}}}\xspace} % the adversary that uses protocol adversary as black box
\newcommand{\crs}{\ensuremath{\sigma}\xspace}
%\num\newcommand{\crs1}{\ensuremath{\mathrm{\sigma}_1}\xspace}
%\num\newcommand{\crs2}{\ensuremath{\mathrm{\sigma}_2}\xspace}
\newcommand{\set}[1]{\ensuremath{\left\{#1\right\}}\xspace}
\newcommand{\hgen}{\ensuremath{\mathbf{\omega}}\xspace}
\newcommand{\vgen}{\ensuremath{\mathbf{g}}\xspace}
\renewcommand{\sim}{\ensuremath{\mathsf{sim}}\xspace}%the distribution of messages when \advv simulates message of \p1
\newcommand{\real}{\ensuremath{\mathsf{real}}\xspace}%the distribution of messages when \p1 is honest and \adv controls rest of players
 \newcommand{\koevec}[2]{\ensuremath{(1,#1,\ldots,#1^{#2},\alpha,\alpha #1,\ldots,\alpha #1^{#2})}\xspace}
\newcommand{\mida}{\ensuremath{A_{\mathrm{mid}}}\xspace}
\newcommand{\midb}{\ensuremath{B_{\mathrm{mid}}}\xspace}
\newcommand{\midc}{\ensuremath{C_{\mathrm{mid}}}\xspace}
\newcommand{\chal}{\ensuremath{\mathsf{challenge}}\xspace}
\newcommand{\attackparams}{\ensuremath{\mathsf{params^{pin}}}\xspace}
\newcommand{\pk}{\ensuremath{\mathsf{pk}}\xspace}
\newcommand{\attackdist}[2]{\ensuremath{AD_{#1}}\xspace}
\renewcommand{\neg}{\ensuremath{\mathsf{negl}(\lambda)}\xspace}
\newcommand{\ro}{\ensuremath{{\mathcal R}}\xspace}
\newcommand{\elements}[1]{\ensuremath{\mathsf{elements}_{#1}}\xspace}
 \num\newcommand{\elmpowers1}[1]{\ensuremath{\mathrm{\mathsf{e}}^1_{#1}}\xspace}
 \num\newcommand{\elmpowers2}[1]{\ensuremath{\mathrm{\mathsf{e}}^2_{#1}}\xspace}
\newcommand{\elempowrs}[1]{\ensuremath{\mathsf{e}_{#1}}\xspace}
 \newcommand{\secrets}{\ensuremath{\mathsf{secrets}}\xspace}
 \newcommand{\polysofdeg}[1]{\ensuremath{\F_{< #1}[X]}\xspace}
 \newcommand{\bivar}[1]{\ensuremath{\F_{< #1}[X,Y]}\xspace}
 \newcommand{\sig}{\ensuremath{\mathscr{S}}\xspace}
 \newcommand{\prot}{\ensuremath{\mathscr{P}}\xspace}
 \newcommand{\PCscheme}{\ensuremath{\mathscr{S}}\xspace}
 \newcommand{\protprime}{\ensuremath{\mathscr{P^*}}\xspace}
 \newcommand{\sigprv}{\ensuremath{\mathsf{P_{sc}}}\xspace}
 \newcommand{\sigver}{\ensuremath{\mathsf{V_{sc}}}\xspace}
 \newcommand{\sigpoly}{\ensuremath{\mathsf{S_{\sigma}}}\xspace}
 \newcommand{\idpoly}{\ensuremath{\mathsf{S_{ID}}}\xspace}
\newcommand{\idpolyevala}{\ensuremath{\mathsf{\bar{s}_{ID1}}}\xspace}
\newcommand{\sigpolyevala}{\ensuremath{\mathsf{\bar{s}_{\sigma1}}}\xspace}
\newcommand{\sigpolyevalb}{\ensuremath{\mathsf{\bar{s}_{\sigma2}}}\xspace}
\newcommand{\bctv}{\ensuremath{\mathsf{BCTV}}\xspace}
\newcommand{\PI}{\ensuremath{\mathsf{PI}}\xspace}
\newcommand{\PIb}{\ensuremath{\mathsf{PI_B}}\xspace}
\newcommand{\PIc}{\ensuremath{\mathsf{PI_C}}\xspace}
\newcommand{\dl}[1]{\ensuremath{\widehat{#1}}\xspace}
\newcommand{\obgen}{\ensuremath{\mathcal O}\xspace}
\newcommand{\PC}{\ensuremath{\mathscr{P}}\xspace}
\newcommand{\permscheme}{\ensuremath{\sigma_\mathscr{P}}\xspace}

	
\newcommand{\selleft}{\ensuremath{\mathbf{q_L}}\xspace}
\newcommand{\selright}{\ensuremath{\mathbf{q_R}}\xspace}
\newcommand{\selout}{\ensuremath{\mathbf{q_O}}\xspace}
\newcommand{\selmult}{\ensuremath{\mathbf{q_M}}\xspace}
\newcommand{\selconst}{\ensuremath{\mathbf{q_C}}\xspace}
\newcommand{\selectors}{\ensuremath{\mathcal{Q}}\xspace}
\newcommand{\lvar}{\ensuremath{\mathbf{a}}\xspace}
\newcommand{\vars}{\ensuremath{\mathcal{V}}\xspace}
\newcommand{\rvar}{\ensuremath{\mathbf{b}}\xspace}
\newcommand{\ovar}{\ensuremath{\mathbf{c}}\xspace}
\newcommand{\pubvars}{\ensuremath{\mathcal{I}}\xspace}
\newcommand{\assignment}{\ensuremath{\mathbf{x}}\xspace}
\newcommand{\constsystem}{\ensuremath{\mathscr{C}}\xspace}
\newcommand{\relof}[1]{\ensuremath{\rel_{#1}}\xspace}
\newcommand{\pubinppoly}{\ensuremath{\mathsf{PI}}\xspace}
\newcommand{\sumi}[1]{\sum_{i\in[#1]}}
\newcommand{\summ}[1]{\sum_{i\in[#1]}}
\newcommand{\sumj}[1]{\sum_{j\in[#1]}}
\newcommand{\ZeroH}{\ensuremath{Z_{H}} \xspace}
\newcommand{\lpoly}{\ensuremath{\mathsf{a}}\xspace}
\newcommand{\rpoly}{\ensuremath{\mathsf{b}}\xspace}
\newcommand{\opoly}{\ensuremath{\mathsf{c}}\xspace}
\newcommand{\idpermpoly}{\ensuremath{\mathsf{z}}\xspace}
\newcommand{\lagrangepoly}{\ensuremath{\mathsf{L}}\xspace}
\newcommand{\zeropoly}{\ensuremath{\mathsf{\ZeroH}}\xspace}
\newcommand{\selmultpoly}{\ensuremath{\mathsf{q_M}}\xspace}
\newcommand{\selleftpoly}{\ensuremath{\mathsf{q_L}}\xspace}
\newcommand{\selrightpoly}{\ensuremath{\mathsf{q_R}}\xspace}
\newcommand{\seloutpoly}{\ensuremath{\mathsf{q_O}}\xspace}
\newcommand{\selconstpoly}{\ensuremath{\mathsf{q_C}}\xspace}
\newcommand{\idcomm}{\ensuremath{[s_{\mathsf{ID1}}]_1}\xspace}
\newcommand{\sigcomma}{\ensuremath{[s_{\mathsf{\sigma1}}]_1}\xspace}
\newcommand{\sigcommb}{\ensuremath{[s_{\mathsf{\sigma2}}]_1}\xspace}
\newcommand{\sigcommc}{\ensuremath{[s_{\mathsf{\sigma3}}]_1}\xspace}
\newcommand{\selleftcomm}{\ensuremath{[q_\mathsf{L}]_1}\xspace}
\newcommand{\selrightcomm}{\ensuremath{[q_\mathsf{R}]_1}\xspace}
\newcommand{\seloutcomm}{\ensuremath{[q_\mathsf{O}]_1}\xspace}
\newcommand{\selconstcomm}{\ensuremath{[q_\mathsf{C}]_1}\xspace}
\newcommand{\selmultcomm}{\ensuremath{[q_\mathsf{M}]_1}\xspace}

\newcommand{\multlinecomment}[1]{\directlua{-- #1}}
    

\newtheorem{lemma}{Lemma}[section]
\newtheorem{thm}[lemma]{Theorem}
\newtheorem{dfn}[lemma]{Definition}
\newtheorem{remark}[lemma]{Remark}

\newtheorem{claim}[lemma]{Claim}
\newtheorem{corollary}[lemma]{Corollary}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathcal{R}}
\newcommand{\crct}{\ensuremath{\mathsf{C}}\xspace}
\newcommand{\A}{\mathcal{A}}
%\newcommand{\G}{\mathcal{G}}
\newcommand{\Gr}{\mathbb{G}}
%\newcommand{\com}{\textsf{com}}  Ariel defined equivalent that also works in math mode
\newcommand{\cgen}{\text{cgen}}
\newcommand{\poly}{\ensuremath{\mathsf{poly(\lambda)}}\xspace}
\newcommand{\snark}{\ensuremath{\mathsf{snark}}\xspace}
\newcommand{\grandprod}{\mathsf{prod}}
\newcommand{\perm}{\mathsf{perm}}
%\newcommand{\open}{\mathsf{open}}
\newcommand{\update}{\mathsf{update}}
\newcommand{\Prove}{\mathcal{P}}
\newcommand{\Verify}{\mathcal{V}}
\newcommand{\Extract}{\mathcal{E}}
\newcommand{\Simulate}{\mathcal{S}}
\newcommand{\Unique}{\mathcal{U}}
\newcommand{\Rpoly}{\R{\poly}}
\newcommand{\Ppoly}{\Prove{\poly}}
\newcommand{\Vpoly}{\Verify{\poly}}
\newcommand{\Psnark}{\prv}%{\Prove{\snark}}
\newcommand{\Vsnark}{\ver}%{\Verify{\snark}}
\newcommand{\Rprod}{\R{\grandprod}}
\newcommand{\Pprod}{\Prove{\grandprod}}
\newcommand{\Vprod}{\Verify{\grandprod}}
\newcommand{\Rperm}{\R{\perm}}
\newcommand{\Pperm}{\Prove{\perm}}
\newcommand{\Vperm}{\Verify{\perm}}
% \newcommand{\zw}[1]{{\textcolor{magenta}{Zac:#1}}}
% \newcommand{\ag}[1]{{\textcolor{blue}{\emph{Ariel:#1}}}}
\newcommand{\prob}{\ensuremath{\mathrm{Pr}}\xspace}
\newcommand{\extprot}{\ensuremath{E_{\prot}}\xspace}
\newcommand{\transcript}{\ensuremath{\mathsf{transcript}}\xspace}
\newcommand{\extpc}{\ensuremath{E_{\PCscheme}}\xspace}
\newcommand{\advpc}{\ensuremath{\mathcal A_{\PCscheme}}\xspace}
\newcommand{\advprot}{\ensuremath{\mathcal A_{\prot}}\xspace}
\newcommand{\protmany}{\ensuremath{ {\prot}_k}\xspace}

\usepackage{pifont}% http://ctan.org/pkg/pifont
\newcommand{\cmark}{\ding{51}}%
\newcommand{\xmark}{\ding{55}}%
\newcommand{\marlin}{\ensuremath{\mathsf{Marlin}}\xspace}
\newcommand{\fractal}{\ensuremath{\mathsf{Fractal}}\xspace}
% \newcommand{\Rsnark}{\R{\snark}}
\newcommand{\Rsnark}{\R}
\newcommand{\subvec}[1]{\ensuremath{#1|_{\subspace}}\xspace}
\newcommand{\restricttoset}[2]{\ensuremath{#1|_{#2}}\xspace}
\newcommand{\isinvanishing}[1]{\ensuremath{\mathsf{IsInVanishing_{\subspace,#1}}}\xspace}
\newcommand{\batchedisinvanishing}[1]{\ensuremath{\mathsf{BatchedIsInVanishing_{\subspace,#1}}}\xspace}
\newcommand{\isconsistent}{\ensuremath{\mathsf{IsConsistent}}\xspace}
\newcommand{\isintable}{\ensuremath{\mathsf{IsInTable}}\xspace}
\newcommand{\isinvanishingtable}[1]{\ensuremath{\mathsf{IsInVanishingTable_{\subspace,#1}}}\xspace}
\newcommand{\isvanishingsubtable}[1]{\ensuremath{\mathsf{IsVanishingSubtable_{#1}}}\xspace}
\newcommand{\haslowerdegree}{\ensuremath{\mathsf{HasLowerDegree}}\xspace}
\newcommand{\haslowdegree}[1]{\ensuremath{\mathsf{HasLowDegree_{#1}}}\xspace}
\newcommand{\issubtable}[1]{\ensuremath{\mathsf{IsSubtable_{#1}}}\xspace}
\newcommand{\isinsubtable}[2]{\ensuremath{\mathsf{IsInSubtable_{#1,#2}}}\xspace}
\newcommand{\secbasezero}[1]{\ensuremath{\hat{\tau}_{#1}}\xspace}
\newcommand{\secbase}[1]{\ensuremath{\hat{\tau}_{#1}}\xspace}
\newcommand{\secbasereg}[1]{\ensuremath{\tau_{#1}}\xspace}
\newcommand{\secset}{\ensuremath{I}\xspace}
\newcommand{\pubbase}[1]{\ensuremath{\mu_{#1}}\xspace}
\newcommand{\subspace}{\ensuremath{\mathbb{H}}\xspace}
\newcommand{\bigspace}{\ensuremath{\mathbb{V}}\xspace}
\newcommand{\subtable}{\ensuremath{T_0}\xspace}
\newcommand{\tablelang}{\ensuremath{\lang_{T}}\xspace}
\newcommand{\vanishingtablelang}{\ensuremath{\lang_{\subspace}}\xspace}
\newcommand{\nonorm}[1]{\ensuremath{\Gamma^T_{#1}}\xspace}
\newcommand{\unnorm}[2]{\ensuremath{\Gamma^{#1}_{#2}}\xspace}
\newcommand{\bigspacebase}{\ensuremath{\lambda}\xspace}
\newcommand{\bigspacegen}{\ensuremath{\mathsf{h}}\xspace}
\newcommand{\modvan}[1]{\ensuremath{\mathrm{mod\;}Z_{#1}}\xspace}
\newcommand{\extractevaltable}{\ensuremath{\mathsf{ExtractEvalTable}_{C,\tablegroup}}\xspace}
\newcommand{\witsize}{\ensuremath{n}\xspace}
\newcommand{\witruntime}{\ensuremath{\witsize\log\witsize}\xspace}
\newcommand{\tabsize}{\ensuremath{N}\xspace}
\newcommand{\tabruntime}{\ensuremath{\tabsize\log\tabsize}\xspace}
\newcommand{\tab}{\ensuremath{\mathfrak{t}}\xspace}
 \renewcommand{\a}{\ensuremath{\mathsf{a}}\xspace}
\renewcommand{\b}{\ensuremath{\mathsf{b}_0}\xspace}
\renewcommand{\c}{\ensuremath{\mathsf{c}}\xspace}
\newcommand{\f}{\ensuremath{\mathsf{f}}\xspace}
\newcommand{\ftwo}{\ensuremath{\mathsf{f}_2}\xspace}
\renewcommand{\p}{\ensuremath{\mathsf{p}}\xspace}
\newcommand{\qa}{\ensuremath{\mathsf{q_a}}\xspace}
\newcommand{\qb}{\ensuremath{\mathsf{q_b}}\xspace}
\newcommand{\m}{\ensuremath{\mathsf{m}}\xspace}
\newcommand{\agam}{\ensuremath{a_\gamma}\xspace}
\newcommand{\gamproof}{\ensuremath{\mathsf{\pi_\gamma}}\xspace}
\newcommand{\zerproof}{\ensuremath{\mathsf{\a}_0}\xspace}
\newcommand{\bgam}{\ensuremath{b_\gamma}\xspace}
\newcommand{\bzergam}{\ensuremath{b_{0,\gamma}}\xspace}
\newcommand{\qbgam}{\ensuremath{Q_{b,\gamma}}\xspace}
\newcommand{\zgam}{\ensuremath{Z_{\bigspace,\gamma}}\xspace}
\newcommand{\fgam}{\ensuremath{f_{\gamma}}\xspace}
\newcommand{\pgam}{\ensuremath{P_{\gamma}}\xspace}
\newcommand{\supp}[1]{\ensuremath{\mathrm{supp}(#1)}\xspace}
\newcommand{\degoffset}{\ensuremath{\tabsize-1-(\witsize-2)}\xspace}
\begin{document}
    \maketitle
\begin{abstract}
 We present a protocol for checking the values of a committed polynomial $f(X)\in \polysofdeg{\witsize}$ over a multiplicative subgroup $\subspace\subset \F$ of size \witsize are contained in a
 table $\tab\in \F^\tabsize$. After an $O(\tabsize \log \tabsize)$ preprocessing step, the prover algorithm runs in time $O(\witsize\log \witsize)$.
 Thus, we continue to improve upon the recent breakthrough sequence of results\cite{caulk,caulkp,flookup,baloo} starting from \caulk~\cite{caulk}, which achieve sublinear complexity in the table size \tabsize. The two most recent works in this sequence \cite{flookup,baloo} achieved
 prover complexity $O(\witsize\cdot \log^2 \witsize)$.
 
 Moreover, \cq has the following attractive features.
 \begin{enumerate}
  \item As in \cite{caulk,caulkp,baloo} our construction relies on homomorphic table commitments, which makes them amenable to vector lookups.
 \item As opposed to \cite{caulk,caulkp,flookup,baloo} the \cq verifier doesn't involve pairings with prover defined \G2 points, which makes recursive aggregation of proofs more convenient.
 \end{enumerate}
 \end{abstract}

% !TEX root = ../flookup.texV

\section{Introduction}
The \emph{lookup problem} is fundamental to the efficiency of modern zk-SNARKs.
Somewhat informally, it asks for a protocol to prove the values of a committed polynomial $f(X)\in\polysofdeg{\witsize}$ are contained in a table $T$ of size $\tabsize$ of predefined legal values.
When the table $T$ corresponds to an operation without an efficient low-degree arithmetization in $\F$, such a protocol produces significant savings in proof construction time for programs containing the operation.
Building on previous work of \cite{arya}, \plookup \cite{plookup} was the first to explicitly describe a solution to this problem in the polynomial-IOP context. \plookup described a protocol with prover complexity quasilinear in both \witsize and \tabsize.
This left the intriguing question of whether the dependence on \tabsize could be made \emph{sublinear} after performing a preprocessing step for the table $T$.
\caulk \cite{caulk} answered this question in the affirmative by leveraging bi-linear pairings, achieving a run time of $O(\witsize^2+\witsize\log \tabsize)$. \caulkp \cite{caulkp} improved this to $O(\witsize^2)$ getting rid of the dependence on table size completely.\footnote{A nuance is that while the \emph{number} of field and group operations are independent of table size, the field and group must be larger than the table in all these constructions, including this paper.} 

Naturally, the quadratic dependence on \witsize  of these works made them impractical for a circuit with many lookup gates. This was resolved in two more recent protocols - \baloo\cite{baloo} and \flookup\cite{flookup} achieving a runtime of $O(\witsize\log^2\witsize)$.
While \flookup has better concrete constants, \baloo preserved an attractive feature of \caulk\space  - using a \emph{homomorphic commitment} to the table. This means that given commitments $\cm_1,\cm_2$ to tables $T_1,T_2$ with elements \set{a_i},\set{b_i} respectively;
we can check membership in the set of elements $\set{a_i+\alpha b_i}$ by running the protocol with $\cm\defeq \cm_1+\alpha\cdot \cm_2$ as the table commitment. This is crucial for vector lookups that have become popular in zk-SNARKs, as described in Section 4 of \cite{plookup}.

One drawback of all four recent constructions - \caulk,\caulkp,\baloo,\flookup; is that they require the verifier perform a pairing where both \G1 and \G2 pairing arguments are not fixed in the protocol, but prover defined. This makes it harder to recursively aggregate multiple proofs via random combination, in the style described e.g. in Section 8 of \cite{bcms}.

\subsection{Our results}

In this paper, we present a protocol called \cq\space  - short for ``cached quotients'' which is a central technical component in the construction (and arguably in all four preceding works). 
\cq
\begin{enumerate}
 \item Improves asymptotic prover performance in field operations from $O(\witsize\log^2\witsize)$ to $O(\witsize\log\witsize)$, and has smaller constants in group operations and proof size compared to \baloo.

 \item Uses homomorphic table commitments similarly to \caulk,\caulkp and \baloo, enabling convenient vector lookups.
 \item Achieves for the first time in this line of work convenient aggregatability by having all verifier pairings use fixed protocol-defined \G2 arguments.
\end{enumerate}

\begin{table}[!htbp]
	\caption{Scheme comparison. $\witsize$ = witness size, \tabsize = Table size, ``Aggregatable''= All prover defined pairing arguments are in \G1}
	\centering
\begin{adjustbox}{width=1\textwidth}
	\begin{tabular}{l|l|l|l|l|l|l}
	\thead{Scheme} & \thead{Preprocessing} & \thead{Proof size} & \thead{Prover Work} & \thead{Verifier Work} & \thead{Homomorphic?} & \thead{Aggregatable?} \\ \hline
		\caulk\cite{caulk}
		        & O(\tabruntime) \F,\G1 & $14$ \G1, 1 \G2, 4 \F      &   $O(\witsize^2+\witsize \cdot \log(\tabsize))$ \F,\G1 & $4P$  & \cmark & \xmark \\ \hline
		\caulkp\cite{caulkp} & $O(\tabruntime)$ \F,\G1 & $7$ \G1, $1$ \G2, $2$ \F      &    $O(\witsize^2)$ \F,\G1& $3P$ & \cmark & \xmark \\ \hline
		\flookup\cite{flookup} & $O(\tabsize \log^2 \tabsize)$ \F,\G1             & $6$ \G1, $1$ \G2, $4$ \F  & $6\witsize$ \G1, \witsize \G2, $O(\witsize\log^2\witsize)$ \F        & $3P$ & \xmark & \xmark \\ \hline
		\baloo\cite{baloo}       & $O(\tabruntime)$ \F,\G1   & $12$ \G1, $1$ \G2, $4$ \F    & $13n$ \G1 $n$ \G2, $O(n\log^2n)$ \F         & $5P$ & \cmark & \xmark \\ \hline
		\cq (this work)         & $O(\tabruntime)$ \F,\G1     & $8$ \G1, $3$ \F & $8n$ \G1, $O(n\log n)$ \F  & $5P$ & \cmark & \cmark \\ \hline
% 		\cqstar          &   \makecell[l]{$O(\tabruntime + \tabsize\cdot \witruntime)$ \F,\G1 \\ $O(\witruntime)$ \G2}  & $6$ \G1, $1$ \G2, $1$ \F & \makecell[l]{$9n + 9a$ \G1 exp , \\ $\approx54(n+a)\text{log}(n+a)$ \F mul}        & $9$ \G1, $6$ \F & \cmark & \xmark \\ \hline
	\end{tabular}
\end{adjustbox}
\label{table:prover-work}
\end{table} \


\subsection{Technical Overview}
We explain our protocol in the context of the line of work starting from \cite{caulk}.
\paragraph{The innovation of \caulk}
To restate the problem, we have an input polynomial $f(X)$,  a table \tab of size \tabsize encoded as the values of 
a polynomial $T(X)\in \polysofdeg{\tabsize}$ on a subgroup \bigspace of size \tabsize. We want to show $f$'s values on a subgroup \subspace of size \witsize are contained in \tab; concisely that $\restricttoset{f}{\subspace}\subset \tab$. We think of the parameters as $\witsize<<\tabsize$.
We want our prover \prv to perform a number of operations \emph{sublinear} in \tabsize, or ideally, a number of operations depending only on \witsize. 

One natural approach - is to send  the verifier \ver a polynomial $T_f$ encoding 
the \emph{\witsize values from \tab actually used in $f$}, and then run a lookup protocol using $T_f$.
The challenging problem is then to prove \emph{$T_f$ actually encodes values from $T$}.
Speaking imprecisely, the ``witness'' to $T_f$'s correctness is a quotient $Q$ of degree $\tabsize-\witsize$.
It would defeat our purpose to actually compute $Q$ - as that would require $O(\tabsize)$ operations.

The central innovation of \caulk\cite{caulk} is the following observation: If we precompute commitments to certain quotient polynomials, we can compute in a number of operations depending only on \witsize, the \emph{commitment} to $Q$.
Moreover, having only a commitment to $Q$ suffices to check, via pairings, that $T_f$ is valid.




This approach was a big step forward, enabling for the first time lookups sublinear in table size.
However, it has the following disadvantage:
``Extracting'' the subtable of values used in $f$, is analogous to looking at restrictions of the original table polynomial to arbitrary sets - far
from the nice subgroups we are used to in zk-SNARK world. Very roughly speaking, this is why all previous four works end up needing to 
work with interpolation and evaluation of polynomials on arbitrary sets. The corresponding algorithms for working on such sets have asymptotics of $O(\witsize\cdot \log^2 \witsize)$ rather than the $O(\witruntime)$ we get for subgroups (of order $2^k$ for example).

% Moreover, when desiring to work with a \emph{homomorphic} table commitment, the \caulk approach requires working
% with a $T'$ that encodes the subtable values on a ``hidden'', prover-defined set of inputs; consequently requiring more ingenuity and complexity to use the subtable, also after it has been extracted.
\paragraph{Our approach}
The key difference between \cite{caulk,caulkp,flookup,baloo} and \cq is that we use the idea of succinct computation
of quotient commitments, not to extract a subtable, \emph{but to directly run an existing lookup protocol on the original large table more efficiently}.
Specifically, we use as our starting point the ``logarithmic derivative based lookup'' of \cite{bplusplus,mvlookup}.

\cite{mvlookup} utilizes the following lemma (cf. Lemma \ref{lem:mvlookup} or Lemma 5 in \cite{mvlookup}):
$\restricttoset{f}{\subspace}\subset \tab$ if and only if for some $m\in \F^\tabsize$
 \[\sumi{\tabsize}\frac{m_i}{X+\tab_i}=\sumi{\witsize}\frac{1}{X+f_i},\]
 as rational functions.
\cite{mvlookup} checks this identity on a random $\beta$,
by sending commitments to polynomials $A$ and $B$ whose values correspond to the summands evaluated at $\beta$ of the LHS and RHS
respectively.
Given commitments to $A,B$, we can check the above equality holds via various sumcheck techniques, e.g. as described in \cite{aurora} (cf. Lemma \ref{lem:aurora}).
The RHS is not a problem because it is a sum of size \witsize.
Computing $A$'s commitment is actually not a problem either, because the number of its non-zero values on \bigspace
is at most \witsize. So when precomputing the commitments to the Lagrange base of  \bigspace, we can compute $A$'s commitment in  \witsize group operations.

The main challenge is to convince the verifier \ver that $A$ is correctly formed.
This is equivalent to the existence of a quotient polynomial $Q_A(X)$ such that
\[A(X)(T(X)+\beta)-m(X)= Q_A(X)\cdot Z_\bigspace(X).\]

It can be seen that this is the same $Q_A(X)$ as when writing
\[A(X)T(X)=Q_A(X)Z_\bigspace(X) +R(X),\]
for $R(X)\in\polysofdeg{\tabsize}$.

Here is where our central innovation, and the term ``cached quotients'' come from. We observe that while computing 
$Q_A$ would take too long, we can compute the commitment \enc1{Q_A(x)} to $Q_A$ in $O(\witsize)$ operations as follows.
We precompute for each $L_i(X)$ in the Lagrange basis of \bigspace its quotient commitment when multiplying with $T(X)$, i.e.
the commitment to $Q_i(X)$ such that for some remainder $R_i(X)\in \polysofdeg{\tabsize}$.

\[L_i(X)T(X)= Q_i(X)\cdot Z_\bigspace(X) + R_i(X).\]

Given the commitments \enc1{Q_i(x)}, \enc1{Q_A(x)} can be computed in $O(\witsize)$ \G1-operations via linear combination.
Moreover, all the elements \enc1{Q_i(x)} can be computed in an $O(\tabruntime)$ preprocessing phase leveraging the work of Feist and Khovratovich\cite{fastkzgproofsorig}. See Section \ref{sec:cachedquo} for details on this.
\section{Preliminaries}
\subsection{Terminology and Conventions}\label{sec:terminology}
We assume our field \F is of prime order.
We denote by \polysofdeg{d} the set of univariate polynomials over \F of degree smaller than d. 
We assume all algorithms described receive as an implicit parameter the security parameter $\lambda$.

Whenever we use the term \emph{efficient}, we mean an algorithm running in time \poly. Furthermore,
we assume an \emph{object generator} \obgen that is run with input $\lambda$ before all protocols, and returns all fields and groups used. Specifically, in our protocol $\obgen(\lambda) = (\F, \G1, \G2, \Gt, e, g_1, g_2,g_t)$ where
\begin{itemize}
\item \F is a prime field of super-polynomial size $r = \lambda^{\omega(1)}$
.
\item $\G1,\G2,\Gt$ are all groups of size $r$, and $e$ is an efficiently computable non-degenerate pairing
$e : \G1 \times \G2 \to \Gt$.
\item $g_1,g_2$ are uniformly chosen generators such that $e(g_1, g_2) = g_t$.
\end{itemize}
We usually let the $\lambda$ parameter be implicit, i.e.\ write \F instead of $\F(\lambda)$.
We write \G1 and \G2 additively. We use the notations $\enc1{x}\defeq x\cdot g_1$ and $\enc2{x}\defeq x\cdot g_2$.

We often denote by $[n]$ the integers \set{1,\ldots,n}.
% For example, when we refer below to the field $\F$, it is in fact a function $\F(\lambda)$ of $\lambda$, and part of
% the output of $\obgen(\lambda)$.
We use the acronym e.w.p. for ``except with probability''; i.e. e.w.p. $\gamma$ means with probability \emph{at least} $1-\gamma$.

\paragraph{universal SRS-based public-coin protocols}
We describe public-coin (meaning the verifier messages are uniformly chosen) interactive protocols between a prover and verifier; when deriving results for non-interactive protocols, we implicitly assume we can get a proof length equal to the total communication of the prover, using the Fiat-Shamir transform/a random oracle. Using this reduction between interactive and non-interactive protocols, we can refer to the ``proof length'' of an interactive protocol. 

We allow our protocols to have access to a structured reference string (SRS) that can be derived in deterministic \poly-time from an ``SRS of monomials'' of the form
\sett{\enc1{x^i}}{a\leq i \leq b}, \sett{\enc2{x^i}}{c\leq i \leq d}, for uniform $x\in \F$,
and some integers $a,b,c,d$ with absolute value bounded by \poly.
It then follows from Bowe et al. \cite{SecondMPC} that the required SRS can be derived in a universal and updatable setup requiring only one honest participant; in the sense that an adversary controlling all but one of the participants in the setup does not gain more than a \negl advantage in its probability of producing a proof of any statement.

For notational simplicity, we sometimes use the SRS \srs as an implicit parameter in protocols, and do not explicitly write it.


\paragraph{The Aurora lemma}
Our sumcheck relies on the following lemma originally used in the Aurora construction (\cite{aurora}, Remark 5.6).
\begin{lemma}\label{lem:aurora}
 Let $H\subset \F$ be a multiplicative subgroup of size $t$.
 For $f\in\polysofdeg{t}$, we have 
\[\sum_{a\in H}f(a) = t\cdot f(0).\]
\end{lemma}



\subsection{The algebraic group model}\label{subsec:agm}
We introduce some terminology from \cite{plonk} to capture analysis in the Algebraic Group Model of Fuchsbauer, Kiltz and Loss\cite{AGM}.

In our protocols, by an \emph{algebraic adversary} \adv in an SRS-based protocol we mean a \poly-time algorithm which satisfies the following.
\begin{itemize}
 \item For $i\in \set{1,2}$, whenever \adv outputs an element $A\in \Gi$, it also outputs a vector $v$ over \F such that $A = <v,\srsi>$.
\end{itemize}

First we say our \srs \emph{has degree $Q$} if all elements of \srsi are of the form  \enci{f(x)} for $f\in \polysofdeg{Q+1}$ and uniform $x\in \F$. In the following discussion let us assume we are executing a protocol with a degree $Q$ SRS, and denote by $f_{i,j}$ the corresponding polynomial for the $j$'th element of \srsi.

Denote by $a,b$ the vectors of $\F$-elements whose encodings in $\G1,\G2$ an algebraic adversary \adv outputs during a protocol execution; e.g., the $j$'th $\G1$ element output by \adv is \enc1{a_j}.

By a ``real pairing check'' we mean a check of the form
\[(a\cdot T_1) \cdot (T_2\cdot b)=0\]
for some matrices $T_1,T_2$ over $\F$.
Note that such a check can indeed be done efficiently given the encoded elements and the pairing function $e:\G1\times \G2\to \Gt$.



Given such a ``real pairing check'', and the adversary \adv and protocol execution during which the elements were output, define the corresponding ``ideal check'' as follows.
Since \adv is algebraic when he outputs \enci{a_j} he also outputs a vector $v$ such that, from linearity, $a_j = \sum v_\ell f_{i,\ell}(x)=R_{i,j}(x)$ for $R_{i,j}(X) \defeq \sum v_\ell f_{i,\ell}(X)$.
Denote, for $i\in \set{1,2}$ the vector of polynomials $R_i=(R_{i,j})_j$.
The corresponding ideal check, checks as a polynomial identity whether
\[(R_1 \cdot T_1)\cdot (T_2\cdot R_2) \equiv 0\]


The following lemma is inspired by \cite{AGM}'s analysis of \cite{Groth16},
and tells us that for soundness analysis against algebraic adversaries it suffices to look at ideal checks.
Before stating the lemma we define the $Q$-DLOG assumption similarly to \cite{AGM}.
\begin{dfn}\label{ref:qdlog}
 Fix integer $Q$. The \emph{$Q$-DLOG assumption for $(\G1,\G2)$} states that given 
 \[\enc1{1},\enc1{x},\ldots,\enc1{x^Q},\enc2{1},\enc2{x},\ldots,\enc2{x^Q}\]
 for uniformly chosen $x\in \F$, the probability of an efficient \adv outputting $x$
 is \negl.
\end{dfn}



\begin{lemma}\label{lem:AGManalysis}
Assume the $Q$-DLOG for $(\G1,\G2)$.
 Given an algebraic adversary \adv participating in a protocol with a degree $Q$ SRS,
 the probability of any real pairing check passing is larger by at most an additive \negl factor than the probability the corresponding ideal check holds.
\end{lemma}
See \cite{plonk} for the proof.

\paragraph{The log-derivative method}
We crucially use the following lemma from \cite{mvlookup}.
\begin{lemma}\label{lem:mvlookup}
 Assume the characteristic of \F is larger than $\max(n,N)$. Given $f\in \F^\witsize$, and $t\in \F^\tabsize$,
 we have $f\subset t$ as sets if and only if for some $m\in \F^\tabsize$ the following identity of rational functions holds
 \[\sumi{\witsize}\frac{1}{X+f_i}=\sumi{\tabsize}\frac{m_i}{X+t_i}.\]
\end{lemma}

\section{Cached quotients}\label{sec:cachedquo}


\paragraph{Notation:}
In this section and the next we use the following conventions.
$\bigspace\subset \F$ denotes a mutliplicative subgroup of order $N$ which is a power of two.
We denote by \vgen a generator of \bigspace. Hence, $\bigspace=\set{\vgen,\vgen^2,\ldots,\vgen^\tabsize =1}$.
Given $P\in \F[X]$ and integer $i\in [\tabsize]$, we denote $P_i\defeq P(\vgen^i)$.
For $i\in [\tabsize]$, we denote by $L_i\in\polysofdeg{\tabsize}$ the $i$'th Lagrange polynomial of \bigspace. Thus, $(L_i)_i=1$ and $(L_i)_j=0$ for $i\neq j\in [\tabsize]$. 

For a polynomial $A(X)\in \polysofdeg{\tabsize}$, we say it is \emph{\witsize-sparse} if $A_i\neq 0$ for at most \witsize values $i\in[\tabsize]$.
The \emph{sparse representation} of such $A$ consists of the (at most) \witsize pairs $(i,A_i)$ such that $A_i\neq 0$.
We denote $\supp{A}\defeq\set{i\in [\tabsize]| A_i\neq 0}$.\\

The main result of this section is a method to compute a commitment to a quotient polynomial - derived from a product with a preprocessed polynomial; in a number of operations depending only on the sparsity of the other polynomial in the product. 

The result crucially relies on the following lemma based on a result of Feist and Khovratovich\cite{fastkzgproofsorig}.

\begin{lemma}
\label{lem:cq-compute}
Fix $T\in \polysofdeg{\tabsize}$, and a subgroup $\bigspace\subset \F$ of size \tabsize. 
There is an algorithm that given the \G1 elements $\sett{\enc1{x^i}}{i\in \set{0,\ldots,\tabsize-1}}$ computes for $i\in [\tabsize]$, the elements 
$q_i\defeq \enc1{Q_i(x)}$
where $Q_i(X)\in \F[X]$ is such that
\[L_i(X)\cdot T(X)=T_i\cdot L_i(X) + Z_\bigspace(X)\cdot Q_i(X)\]
in $O(\tabsize\cdot \log \tabsize)$ \G1 operations.
 
\end{lemma}

\begin{proof} 
    Recall the definition of the Lagrange polynomial
    \[L_i(X) = \frac{Z_\bigspace(X)}{Z_\bigspace'(\vgen^i) (X - \vgen^i)}.\]
    Substituting this definition, we can write the quotient $Q_i(X)$ as 
    \[Q_i(X) = \frac{T(X) - T_i}{Z_\bigspace'(\vgen^i) (X - \vgen^i)} =
    Z_\bigspace'(\vgen^i)^{-1} K_i(X), \]
for $K_i(X)\defeq \frac{T(X)-T_i}{X-\vgen^i}$.
Note that the values \sett{\enc1{K_i(x)}}{i\in [\tabsize]} are exactly the KZG opening proofs of $T(X)$ at the
elements of \bigspace.
    Thus, the algorithm of Feist and Khovratovich \cite{fastkzgproofsorig, fastkzgproofs} 
    can be used to compute commitments to all the proofs $\enc1{K_i(x)}$ 
    in $O(\tabruntime)$ \G1-operations. This works by writing the vector of
    $\enc1{K_i(x)}$ as a the product of a matrix with the vector of
    $\enc1{x^i}$. This matrix is a DFT matrix times a Toeplitz matrix, both of
    which have algorithms for evaluating matrix vector products in
    $O(\tabruntime)$ operations. Thus, all the KZG proofs can be computed in
    $O(\tabruntime)$ field operations and operations in \G1.
    
    Finally, the algorithm just needs to scale each $\enc1{K_i(x)}$ by
    $Z_{\bigspace}'(\vgen^i)^{-1}$ to compute $\enc1{Q_i(x)}$. Conveniently, these
    values admit a very simple description when $Z_\bigspace(X) = X^\tabsize -
    1$ is a group of roots of unity.
    \[Z_\bigspace'(X)^{-1} = (\tabsize X^{\tabsize-1})^{-1} \equiv X / \tabsize \mod Z_\bigspace(X)\] 

    In total, the prover computes the coefficients of $T(X)$ in $O(\tabruntime)$
    field operations, computes the KZG proofs for $T(\vgen^i) = t_i$ in
    $O(\tabruntime)$ group operations, and then scales these proofs by $\vgen^i
    / N$ in $O(\tabsize)$ group operations. In total, this takes
    $O(\tabruntime)$ field and group operations in \G1.
\end{proof}


\begin{thm}\label{thm:sec3main}
Fix integer parameters $0\leq n\leq N$ such that $n,N$ are powers of two dividing $|\F|-1$. Fix $T\in \polysofdeg{\tabsize}$, and a subgroup $\bigspace\subset \F$ of size \tabsize. Let $\srs=\sett{\enc1{x^i}}{i\in[0,\ldots,\tabsize-1]}$ for some $x\in \F$. 
There is an algorithm \alg that after a preprocessing step of $O(\tabruntime)$ \F- and \G1-operations starting with \srs does the following.


Given input $A(X)\in \polysofdeg{\tabsize}$ that is \witsize-sparse and given in sparse representation, \alg computes in 
$O(\witsize)$ \F-operations and \witsize \G1-operations each of the elements
$\cm_1=\enc1{Q(x)},\cm_2=\enc1{R(x)}$ for $Q(X),R(X)\in \polysofdeg{\tabsize}$ such that
\[A(X)\cdot T(X) = Q(X)\cdot Z_{\bigspace}(X) + R(X).\]
\end{thm}
\begin{proof}
    The preprocessing step consists of computing the quotient commitments $\enc1{Q_i(X)}$ in $O(\tabruntime)$ operations, as described in Lemma \ref{lem:cq-compute}. As stated in the lemma,
    for each $i\in[\tabsize]$ we have
    \[L_i(X)\cdot T(X)=T_i\cdot L_i(X) + Z_\bigspace(X)\cdot Q_i(X).\]
    By assumption, the polynomial $A(X)$ can be written as a linear combination of
    at most $\witsize$ summands in the Lagrange basis of $\bigspace$.
    \[ A(X) = \sum_{i \in \supp{A}} A_i\cdot L_i(X) \]
    Substituting this into the product with $T(X)$, and substituting each of the products
    $L_i(X) T(X)$ with the appropriate cached quotient $Q_i(X)$ we find
    \[ A(X) T(X) = \sum_{i\in \supp{A}} A_i\cdot  L_i(X) T(X) =\sum_{i \in
    \supp{A}} A_i \cdot T_i L_i(X) + A_i\cdot Z_\bigspace(X) Q_i(X) \] 
   \[=\sum_{i \in  \supp{A}} A_i \cdot T_i L_i(X) +Z_\bigspace(X)\cdot \sum_{i \in
    \supp{A}} A_i \cdot Q_i(X).\] 
Observing that the terms of the first sum are all of degree smaller than \tabsize, we get that

    \begin{gather*}
Q(X)=\sum_{i \in  \supp{A}} A_i \cdot Q_i(X) \\
        R(X) = \sum_{i \in \supp{A}} A_i T_i \cdot L_i(X)
    \end{gather*}
    Hence, commitments to both the quotient $Q(X)$ and remainder $R(X)$ can be computed in
   at most \witsize group operations as 
    \begin{gather*}
        \enc1{Q(x)} = \sum_{i \in \supp{A}} A_i \cdot \enc1{Q_i(x)} \\
        \enc1{R(x)} = \sum_{i \in \supp{A}} A_i T_i \cdot \enc1{L_i(x)}
    \end{gather*}
\end{proof}


\section{$\cq\;$ - our main protocol}
Before describing our protocol, we give a definition of a lookup protocol secure against algebraic adversaries.
\begin{dfn}\label{dfn:lookupprot}
A \emph{lookup protocol} is a pair $\prot=(\gen,\isintable)$ such that
\begin{itemize}
 \item $\gen(\tabsize,\tab)$ is a randomized algorithm receiving as input parameters integer $\tabsize$ and $\tab\in \F^\tabsize$. 
 Given these inputs \gen outputs a string \srs of \G1 and \G2 elements.
 \item $\isintable(\cm,\tab,\srs,\subspace;f)$ is an interactive public coin protocol between \prv and \ver where \prv has private input $f\in \polysofdeg{\witsize}$, and both parties have access to $\tab,\cm$ and  $\srs=\gen(\tabsize,\tab)$;
 such that
 \begin{itemize}
  \item \textbf{Completeness:} If $\cm=\enc1{f(x)}$ and $\restricttoset{f}{\subspace}\subset \tab$ then \ver outputs \acc with probability $1-\negl$.
  \item \textbf{Knowledge soundness in the algebraic group model:}
    The probability of any efficient algebraic \adv to win the following game is \negl.

\begin{enumerate}
\item \adv chooses integer parameters $\tabsize,\witsize$ and a table $\tab\in \F^\tabsize$.
 \item We compute $\srs=\gen(\tab,\tabsize)$.
 \item \adv sends a message \cm and $f\in\polysofdeg{d}$ such that $\cm=\enc1{f(x)}$ where $d$ is such that all \G1 elements in \srs are linear
 combinations of \sett{\enc1{x^i}}{i\in \set{0,\ldots,d-1}}.
 \item \adv and \ver engage in the protocol $\isintable(\tab,\cm,\srs,\subspace)$, where $\subspace\subset \F$ is a subgroup of order \witsize, with \adv taking the role of \prv.
 \item \adv wins if 
 \begin{itemize}
  \item \ver outputs \acc, and
  \item $\restricttoset{f}{\subspace}\not\subset \tab$.
 \end{itemize}

\end{enumerate}
\end{itemize}
\end{itemize}
We say a lookup protocol is \emph{homomorphic} if for any fixed parameter \tabsize and fixed randomness, $\gen(\tab,\tabsize)$ can be written as $(\gen_1,\gen_2(\tab))$ such that $\gen_1$ is fixed, and $\gen_2$ is an $\F$-linear function of \tab.
\end{dfn}

\subsection{The \cq protocol}

\underline{$\gen(\tabsize,\tab)$:}\\ \noindent
\begin{enumerate}
\item Choose random $x\in \F$ compute and output $\sett{\enc1{x^i}}{i\in \set{0,\ldots,\tabsize-1}},\sett{\enc2{x^i}}{i\in \set{0,\ldots,\tabsize}}$.
\item Compute and output \enc2{Z_\bigspace(x)}.
\item Compute $T(X)=\sumi{\tabsize}\tab_i L_i(X)$. Compute and output \enc2{T(x)}.
 \item For $i\in [\tabsize]$, compute and output:
 \begin{enumerate}
  \item $q_i=\enc1{Q_i(x)}$ such that
  \[L_i(X)\cdot T(X)=\tab_i\cdot L_i(X) + Z_\bigspace(X)\cdot Q_i(X).\]
  \item $\enc1{L_i(x)}$.
  \item $\enc1{\frac{L_i(x)-L_i(0)}{x}}$.
 \end{enumerate}

\end{enumerate}

Before describing \isintable, we explain an optimization we use in Step \ref{step:compB0} of Round 2. Since we know in advance we are going to open $B$ at zero, it is more efficient to commit to the \emph{the opening proof polynomial  $B_0(X)\defeq \frac{B(X)-B(0)}{X}$ of $B$ at 0 instead of committing to $B$}. To evaluate $B$, \ver can use the relation $B(X)=B_0(X)\cdot X + b_0$.

We note  that it's possible to make a similar optimization for $A$ to further reduce proof size and prover time. However, this entails an additional verifier pairing for the check in Step \ref{step:checkqa} of Round 2.
\noindent
\\
\\
\noindent
\underline{$\isintable(\cm,\tab,\srs,\subspace;f)$:} \\ \noindent
\paragraph{\textbf{Round 1:} Committing to the multiplicities vector} \ \\
\begin{enumerate}
 \item \prv computes the polynomial $m(X)\in \polysofdeg{\tabsize}$ defined by setting\footnote{We assume here that $\tab$'s values are distinct. If there are duplicate values in \tab, one must rather set $m_i=0$ for the indices $i$ of the duplicates.} $m_i$, for each $i\in [\tabsize]$, to the number of times $\tab_i$ appears in \restricttoset{f}{\subspace}.
 \item \prv sends $\m\defeq \enc1{m(x)}$.
 \end{enumerate}
	\paragraph{\textbf{Round 2:} Interpolating the rational identity at a random $\beta$; checking correctness of  $A$'s values + degree check for $B$ using pairings} \ \\
 
\begin{enumerate}
 \item \ver chooses and sends random $\beta \in \F$.
\item \prv computes $A\in \polysofdeg{\tabsize}$ such that for $i\in [\tabsize]$, $A_i = m_i/(\tab_i+\beta)$.
\item \prv computes and sends $\a\defeq \enc1{A(x)}$.
\item\label{step:computeQA} \prv computes and sends $\qa \defeq \enc1{Q_A(x)}$ where $Q_A\in \polysofdeg{\tabsize}$ is such that 
\[A(X)(T(X)+\beta)-m(X)= Q_A(X)\cdot Z_\bigspace(X)\]
\item\label{step:zerden} \prv computes $B(X)\in \polysofdeg{\witsize}$ such that for $i\in [\witsize]$, $B_i=1/(f_i+\beta)$.
\item\label{step:compB0}  \prv computes $B_0(X)\in \polysofdeg{\witsize-1}$ defined as $B_0(X)\defeq \frac{B(X)-B(0)}{X}$.
\item \prv computes and sends $\b\defeq \enc1{B_0(x)}$.
\item \prv computes $Q_B(X)$ such that 
\[B(X)(f(X)+\beta)-1 = Q_B(X)\cdot Z_\subspace(X).\]
\item \prv computes and sends $\qb\defeq \enc1{Q_B(x)}$.

\item \prv computes and sends $\p=\enc1{P(x)}$ where
\[P(X)\defeq  B_0(X)\cdot X^{\degoffset}. \]
\item\label{step:checkqa} \ver checks that $A$ encodes the correct values:
\[e(\a,\enc2{T(x)})=e(\qa,\enc2{Z_\bigspace(x)})\cdot e(\m-\beta\cdot \a,\enc2{1})\]
\item\label{step:checkadeg} \ver checks that $B_0$ has the appropriate degree:
\[e\left(\b,\enc2{x^{\degoffset}}\right)=e(\p,\enc2{1}).\]
 \end{enumerate}
	\paragraph{\textbf{Round 3:} Checking correctness of  $B$ at random $\gamma \in \F$}
 \begin{enumerate}
\item \ver sends random $\gamma \in \F$.
\item \prv sends $\bzergam \defeq B_0(\gamma),\fgam \defeq f(\gamma)$.
\item \prv computes and sends the value $a_0\defeq A(0)$.
\item \label{step:setb0}\ver  sets $b_0\defeq (\tabsize\cdot a_0)/\witsize$.
\item\label{step:setQB} As part of checking the correctness of $B$, \ver computes $ Z_\subspace(\gamma) = \gamma^\witsize -1$, $\bgam\defeq \bzergam\cdot \gamma + b_0$ and
\[\qbgam\defeq \frac{\bgam\cdot (\fgam + \beta)-1}{Z_\subspace(\gamma)}.\]
\item To perform a batched KZG check for the correctness of the values  $\bzergam,\fgam,\qbgam$
  \begin{enumerate}
   \item \ver sends random $\eta\in \F$. \prv and \ver separately compute
   \[v\defeq \bzergam +\eta\cdot\fgam + \eta^2\cdot \qbgam.\]
   \item \prv computes $\gamproof\defeq \enc1{h(x)}$ for 
   \[h(X)\defeq \frac{ B_0(X)+ \eta\cdot f(X) + \eta^2\cdot Q_B(X) -v}{X-\gamma}\]
   \item\label{step:checkKZG1} \ver computes 
   \[\c\defeq \b+\eta\cdot \cm +\eta^2\cdot \qb\]
   and checks that 
   \[e(\c-\enc1{v}+\gamma\cdot \gamproof,\enc2{1})=e(\gamproof,\enc2{x}).\]
  \end{enumerate}
\item To perform a KZG check for the correctness of $a_0$
  \begin{enumerate}
   \item \prv computes and sends $\zerproof\defeq \enc1{A_0(x)}$ for 
   \[A_0(X)\defeq \frac{A(X)-a_0}{X}\]
   \item\label{step:checkKZG2} \ver checks that 
   \[e(\a-\enc1{a_0},\enc2{1})=e(\zerproof,\enc2{x}).\]
  \end{enumerate}

\end{enumerate}

Note that although the above description contains nine pairings, we can reduce to five pairings via the standard technique of  combining
several pairings equations into one pairing product via randomness, and then grouping pairings that share the same \G2 argument. (The different \G2 arguments are $\enc2{1},\enc2{x},\enc2{x^{\degoffset}},\enc2{Z_\bigspace(x)},\enc2{T(x)}$.)  It is easy to check that \cq is homomorphic according to Definition \ref{dfn:lookupprot}.
   
   There is a \negl probability that \prv  is computing expressions with a zero denominator in some of the steps; we assume \prv aborts in such a case.
   
                  
    The  main things to address are the efficiency of the \gen algorithm used for preprocessing, the efficiency of \prv in \isintable, and the knowledge soundness of \isintable.
    
    \paragraph{Runtime of \gen:}
We claim that \gen requires $O(\tabruntime)$ \G1- and \F-operations and $O(\tabsize)$ \G2-operations.
The claim regarding the \G2 operations is obvious.
The elements \set{q_i} can be computed in $O(\tabruntime)$ operations according to Lemma \ref{lem:cq-compute}.
The elements \set{\enc1{L_i(x)}} can be computed in $O(\tabruntime)$ via FFT as explained in Section 3.3 of \cite{FirstMPC}.
Given the element \enc1{L_i(x)}, the element \enc1{\frac{L_i(x)-L_i(0)}{x}} can be computed as
\[\enc1{\frac{L_i(x)-L_i(0)}{x}}=\vgen^{-i}\cdot \enc1{L_i(x)}- (1/\tabsize)\cdot \enc1{x^{\tabsize-1}}.\]

\paragraph{Runtime of \prv:}
Note first that the computation of $\m,\a$ can be done in \witsize \G1-operations as $m(X)$ and $A(X)$  are $\witsize$-sparse.
The main thing to address is the computation of \qa; that can be done in \witsize \G1-operations given \srs according to Theorem \ref{thm:sec3main}.
The only step requiring $O(\witruntime)$ \F-operations is the computation of the quotient $Q_B(X)$ which involves FFT on \subspace.
We also note that the commitment $\zerproof=\enc1{\frac{A(x)-A(0)}{x}}$ can be computed in \witsize \G1-operations
as the linear combination 
\[\enc1{\frac{A(x)-A(0)}{x}} =\sum_{i\in \supp{A}}A_i\cdot \enc1{\frac{L_i(x)-L_i(0)}{x}} . \]

\paragraph{Knowledge soundness proof:}
Let \adv be an efficient algebraic adversary participating in the Knowledge Soundness game from
Definition \ref{dfn:lookupprot}.
We show its probability of winning the game is \negl.
Let $f\in \polysofdeg{\tabsize}$ be the polynomial sent by \adv in the third step of the game
such that $\cm=\enc1{f(x)}$.
As \adv is algebraic, when sending the commitments \m,\a,\b,\p,\qa,\qb,\gamproof,\zerproof during protocol execution it also sends polynomials $m(X),A(X),B_0(X),$ $P(X),Q_A(X),Q_B(X),h(X),A_0(X)\in \polysofdeg{\tabsize}$ such that the former are their corresponding commitments.
Let $E$ be the event that \ver outputs \acc.
Note that the event that \adv wins the knowledge soundness game is contained in $E$. 
$E$ implies all pairing checks have passed.
Let $A\subset E$ be the event that one of the corresponding ideal pairing checks as defined in Section \ref{subsec:agm} didn't pass.
According to Lemma \ref{lem:AGManalysis}, $\prob(A)=\negl$.
Given that $A$ didn't occur, we have
\begin{itemize}
 \item From Round 2, Step \ref{step:checkqa} \[A(X)(T(X)+\beta)-M(X) = Q_A(X)\cdot Z_\bigspace(X)\]
Which means that for all $i\in [\tabsize]$,
\[A_i=\frac{M_i}{T_i+\beta}\]

\item From Round 2, Step  \ref{step:checkadeg}
\[X^{\degoffset}B_0(X)=P(X),\]
which implies  that  $\deg(B_0)\leq\witsize-2$. Note also that we know $\deg(A)<\tabsize$ simply from \enc1{x^{\tabsize-1}} being the highest \G1 power in \srs.\footnote{An important
point is that when using an SRS built with higher degrees in \G1, $A$ must also be degree checked via an additional pairing. In such a case, we must also change the power of $X$ in Step \ref{step:checkadeg} of Round 2 from $\degoffset$ to $d-(\witsize-2)$ where $d$ is the maximal SRS degree in \G1.}

\item Moving to Round 3, from the checks of steps \ref{step:checkKZG1} and \ref{step:checkKZG2},  e.w.p. $2/|\F|$ over $\eta\in\F$ (see e.g. Section 3 of \cite{plonk} for an explanation of batched KZG \cite{kate}), we have  
$\bzergam = B_0(\gamma),\qbgam =Q_B(\gamma),\fgam =f(\gamma),a_0=A(0)$.
\item Define $B(X)\defeq B_0(X)\cdot X + b_0$ for $b_0$ set as in step \ref{step:setb0}. 
Note that we have $\deg(B)<\witsize$ and $B(0)=b_0$. Let \hgen by a generator of \subspace.

\item By how $\bgam,\qbgam$ are set in step \ref{step:setQB},  the above implies that e.w.p. $(\tabsize+ \witsize)/|\F|$ over $\gamma$ 
\[B(X)\cdot (f(X)+\beta)=1+ Q_B(X)Z_\subspace(X),\]
which implies for all $i\in [\witsize]$ that
$B(\hgen^i)=\frac{1}{f(\hgen^i)+\beta}$.

\item We now have using Lemma \ref{lem:aurora} that
\[\tabsize\cdot a_0 = \sum_{i\in [\tabsize]} A_i = \sum_{i\in [\tabsize]}\frac{m_i}{T_i+\beta},\]
\[\witsize\cdot b_0 = \sum_{i\in [\witsize]} B(\hgen^i) = \sum_{i\in [\witsize]}\frac{1}{f(\hgen^i)+\beta}.\]
Recall that $b_0$ was set such that $\tabsize \cdot a_0=\witsize\cdot b_0 $.
Multiplying denominators, we see that e.w.p. $(\witsize+ \tabsize)/|\F|$ over $\beta\in \F$, we have 
\[\sum_{i\in [\tabsize]}\frac{m_i}{T_i+X}=\sum_{i\in [\witsize]}\frac{1}{f(\hgen^i)+X},\]
which implies $\restricttoset{f}{\subspace}\subset \tab$ by Lemma \ref{lem:mvlookup}.
\end{itemize}
In summary, we have shown the event that \ver outputs \acc while $\restricttoset{f}{\subspace}\not\subset \tab$
is contained in a constant number of events with probability \negl; and so \cq satisfies the knowledge soundness property.
\section*{Acknowledgements}
We thank Kobi Gurkan, Aurel Nicolas and Marek Sefranek for corrections.
\bibliographystyle{alpha}
\bibliography{references}
\end{document}