Appendix.tex

\appendix


\subsection{Protocols}\label{app:protocolboxes}
In the protocol listings (Figures \ref{fig:quadcheck} -- \ref{fig:distquadcheck}), {$\mathsf{pp}$ denotes the public parameters consisting of: 
{\small$\mathsf{pp} = (\FF, \GG, \rsc{\eta}{n,\ell}, \rsc{\alpha}{h,m},\rsc{\eta}{n,s+\ell-1},\rsc{\eta}{n,2\ell-1}, \rsc{\alpha}{h,2m-1}, \bm{g},h)$}
%Linear Check of Graphene
\begin{comment}
\begin{figure}[h!]
	{\footnotesize
		%\centering
		\begin{framed}
			\noindent{$\linearcheck(\mathsf{pp},A\in \mc{M}_{M,N},b\in \FF^M,[\pi];\ewit)$}: 			%\pnote{why $\wit$ is not part of the witness of linear check protocol?}
			
			\noindent{\bf Relation}: $\ewit=\open(\pi)\wedge A\wit=b$ for $\wit=\dec(\ewit)$.
			
			\begin{enumerate}[{\rm 1.}]
				\item $\verifier\rightarrow\prover$: $\rho\sample \FF^p$.
				\item $\prover$ computes: $=\sum_{i\in [p]}\rho_i\ewit[i,\cdot,\cdot]$, 
				commitments $\tilde{c}_1,\ldots,\tilde{c}_\ell$ as in Section ~\ref{sec:matrixcommitment}.
				\item $\prover\rightarrow\verifier$: $\tilde{\bm{c}}=(\tilde{c}_1,\ldots,\tilde{c}_\ell)$.
				\item $\verifier\rightarrow\prover$: $r\sample \FF^M$.
				\item $\prover\leftrightarrow\verifier$ compute: Polynomials $R^i$, $i\in [p]$ interpolating $R=r^TA$
				as in Section ~\ref{sec:lincheck}. 
				\item $\prover$ computes: Matrix $P$ from $R$ and $\ewit$ as described in Section ~\ref{sec:lincheck}. Samples $P_0\sample \FF^{2m-1}$, $\omega_0\sample \FF$ and $c_0\gets \comm(P_0,\omega_0)$.
				Computes commitments $c_1,\ldots,c_{s+\ell-1}$ from $P$.
				\item $\prover\rightarrow\verifier$: $c_0,c_1,\ldots,c_{s+\ell-1}$.
				\item $\verifier\rightarrow\prover$: $Q=\{(j_u,k_u):u\in [t]\}$ for $(j_u,k_u)\sample [h]\times [n]$ for $u\in [t]$.
				\item $\verifier\rightarrow\pi$: $\{k_u:u\in [t]\}$.
				\item $\prover\rightarrow\verifier$: $\ewit[\cdot,j_u,k_u]$ for $u\in [t]$.
				\item $\pi\rightarrow\verifier$: $\pi[\cdot,k_u]$ for $u\in [t]$.
				\item $\verifier\rightarrow\prover$: $\delta\sample \FF^p$, $\beta\sample \FF\backslash \{0\}$. 
				\item $\prover$ and $\verifier$ run inner product arguments to check:
				\begin{enumerate}
					\item $\innerproduct(\mathsf{pp},\bm{1}_{j_u}^T\Lambda_{h,2m-1},\mathsf{cm}_{k_u},v_u;\overline{P}[\cdot,k_u])$ 
					for $u\in [t]$ where $\mathsf{cm}_{k_u}=\prod_{a=1}^{s+\ell-1}c_a^{\Lambda^T_{n,s+\ell-1}[a,k_u]}$, 
					$v_u=\sum_{i=1}^pR^i(\alpha_{j_u},\eta_{k_u})U[i,j_u,k_u]$ (check consistency of $P$ with $\pi$).
					\item $\innerproduct(\mathsf{pp},1^m||0^{m-1},\mathsf{cm},r^Tb;z)$ where $z=\beta P_0+\overline{P}\varphi$ and $\mathsf{cm}=c_0^{\beta}\cdot \prod_{a=1}^{s+\ell-1}c_k^{\varphi_k}$ (check the condition $r^TAw=r^Tb$).
					\item $\innerproduct(\mathsf{pp},\bm{1}_{j_u}^T\Lambda_{h,m},C_u,\innp{\delta}{X_u})$ for $u\in [t]$ 
					where $C_u=\prod_{i=1}^p(\pi[i,k_u])^{\delta_i}$ (consistency of $X_u$ with $\pi$). 
				\end{enumerate}
				\item $\verifier$ checks: $\prod_{a=1}^\ell(\tilde{c}_a)^{\Lambda^T_{n,\ell}[a,k_u]}=\prod_{i=1}^p(\pi[i,k_u])^{\rho_i}$ for $u\in [t]$ (check proximity of $\ewit$ to $\mc{W}_1$).
				\item $\verifier$ accepts if all the checks succeed.
			\end{enumerate}
		\end{framed}
		\caption{Linear Check Protocol}
		\label{fig:linearcheck}
	}
\end{figure}
\end{comment}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Quadratic Check of Graphene
\begin{figure}[h!]
	{\footnotesize
		%\centering
		\begin{framed}
			\noindent{$\quadcheck(\mathsf{pp},[\pi_x],[\pi_y],[\pi_z];\ewit_x, \ewit_y, \ewit_z)$}:
			
			\noindent{\bf Relation}: $\ewit_a=\open(\pi_a)$ for $a\in \{x,y,z\}$,
			$\wit_x \circ \wit_y = \wit_z$ where  $\wit_a=\dec(\ewit_a)$ for $a\in \{x,y,z\}$.
			
			\begin{enumerate}[{\rm 1.}]
				\item $\verifier\rightarrow\prover$: $\rho\sample \FF^{3p}$.
				\item $\prover$ computes: (a) $\tilde{\ewit}=\sum_{i=1}^p[\rho_i\ewit_x[i,\cdot,\cdot]+
				\rho_{p+i}\ewit_y[i,\cdot,\cdot]+\rho_{2p+i}\ewit_z[i,\cdot,\cdot]]$, (b)
				commitments $\tilde{c}_1,\ldots,\tilde{c}_\ell$ as $\tilde{c}_k = \prod_{i=1}^{p} (\pi_x[i,k])^{\rho_i}\cdot (\pi_y[i,k])^{\rho_{p+i}}\cdot(\pi_z[i,k])^{\rho_{2p+i}}$ $\forall k\in[\ell]$.
				\item $\prover\rightarrow\verifier$: $\tilde{\bm{c}}=(\tilde{c}_1,\ldots,\tilde{c}_\ell)$.
				\item $\verifier\rightarrow\prover$: $r\sample \FF^p$.
				%\item $\prover\leftrightarrow\verifier$ compute: Polynomials $R^i$, $i\in [p]$ interpolating $R=r^TA$ as in Section ~\ref{sec:quadcheck}. 
				\item $\prover$ computes: (a) $p_j(\cdot) = \sum_{i\in[p]} r_i[Q^i_x(\alpha_j,\cdot)Q^i_y(\alpha_j,\cdot) - Q^i_z(\alpha_j,\cdot)]$ $\forall j\in [h]$
				(b) matrix $P$ such that $P[j,k] = p_j(\eta_k)$ as described in Section ~\ref{sec:quadcheck}, (c)
				computes commitments $c_1,\ldots,c_{2\ell}$ from $P$. $\prover$ also
				samples $P_0\sample \FF^{2m-1}$ with $P_0[j]=0^m$ for $j\in[m]$ and computes commitment $c_0$
				to $P_0$. 
				\item $\prover\rightarrow\verifier$: $c_0$, $c_1,\ldots,c_{2\ell-1}$.
				\item $\verifier\rightarrow\prover$: $Q=\{(j_u,k_u):u\in [t]\}$ for 	$Q\sample [h]\times [n]$, $u\in [t]$ and $\tau \sample \FF^s$, $\gamma \sample \FF^m$.
				\item $\verifier\rightarrow\pi$: $\{k_u:u\in [t]\}$.
				\item $\prover\rightarrow\verifier$: $X_u=\ewit_x[\cdot,j_u,k_u]$ , $Y_u=\ewit_y[\cdot,j_u,k_u]$ and $Z_u=\ewit_z[\cdot,j_u,k_u]$ for $u\in [t]$.
				
				\item $\pi\rightarrow\verifier$: $\pi[\cdot,k_u]$ for $u\in [t]$.
				\item $\verifier\rightarrow\prover$: $\delta\sample
				\FF^p$, $\beta_x\sample \FF$, $\beta_y\sample \FF$, $\beta_z\sample \FF$,
				$\beta\sample \FF\backslash \{0\}$.
				\item $\prover$ computes:
				$V_u=\sum_{i=1}^p\delta_i\big(\beta_x\ewit_x[i,\cdot,k_u]+\beta_y\ewit_y[i,\cdot,k_u]+\beta_z\ewit[i,\cdot,k_u]\big)$.
				%$\beta \FF\backslash \{0\}$. 
				\item $\prover \text{ and }\verifier$ compute:
				$W_u=\beta_xX_u+\beta_yY_u+\beta_zZ_u$ for $u\in [t]$.
				$T_u=(C_u)^{\beta_x}\cdot(D_u)^{\beta_y}\cdot(E_u)^{\beta_z}$, for $u\in [t]$ where
				$C_u=\prod_{i=1}^{p}(\pi_x[i,k_u])^{\delta_i}$, $D_u=\prod_{i=1}^{p}(\pi_y[i,k_u])^{\delta_i}$
				and $E_u=\prod_{i=1}^{p}(\pi_y[i,k_u])^{\delta_i}$.
				\item $\prover$ and $\verifier$ run inner-product arguments to check:
				\begin{enumerate}
					\item $\innerproduct(\mathsf{pp},\bm{1}_{j_u}^T\Lambda_{h,2m-1},\mathsf{cm}_{k_u},v_u;\overline{P}[\cdot,k_u])$ for $u\in [t]$ where $\mathsf{cm}_{k_u}=\prod_{a=1}^{2\ell-1}(c_a)^{\Lambda_{n,2\ell-1}^T[a,k_u]}$, 
					$v_u=\sum_{i=1}^p r_i[X_u[i]\cdot Y_u[i] - Z_u[i]]$ (check consistency of $P$ with $\pi$).
					\item $\innerproduct(\mathsf{pp},\gamma||0^{m-1},\mathsf{cm},0;z)$
					where $z=\beta P_0 +\overline{P}\varphi$, $\varphi = \Phi^T\tau$ and
					$\mathsf{cm} =  (c_0)^{\beta}\cdot\prod_{a=1}^{2\ell-1} (c_a)^{\varphi_a}$ %(check the condition $r^TAw = r^Tb$).
					\item
					$\innerproduct(\mathsf{pp},\bm{1}_{j_u}^T\Lambda_{h,m},T_u,w_u;\overline{V}_u])$, where $\overline{V}_u$ stands for first $m$ entries of $V_u$ and $w_u = \innp{\delta}{W_u}$ (consistency of $X_u, Y_u, Z_u$ with $\pi$). 
				\end{enumerate}
				\item $\verifier$ checks proximity of $\ewit_x,\ewit_y$
				and $\ewit_z$ according to Eqn \eqref{eq:combinedproximity}.
				\item $\verifier$ accepts if all the checks succeed.
			\end{enumerate}
		\end{framed}
		\caption{Quadratic Check Protocol}
		\label{fig:quadcheck}
	}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Distributed Linear Check of DP-Graphene

\begin{figure}[h]
	{\footnotesize
		%\centering
		\begin{framed}
			\noindent{$\distlinearcheck(\mathsf{pp}, \, A\in \mc{M}_{M,N}, \, b\in \FF^M, \, [\pi];\, \shr{\ewit}, \, \shr{0^{2m-1}})$}:
			%\pnote{why $\wit$ is not part of the witness of linear check protocol?}
			
			\noindent{\bf Relation}: $\ewit=\open(\pi)\wedge A\wit=b$ for $\shr{\wit}=\dec(\shr{\ewit})$ for all $\xi \in [\Num]$ and $\sum_{\xi\in[\Num]} \shr{\wit} = \wit$.
			
			\begin{enumerate}[{\rm 1.}]
				\item $\verifier\rightarrow\distprover$: $\rho\sample \FF^p$.
				\item $\distprover$ computes: $\shr{\tilde{\ewit}} = \sum_{i\in [p]}\rho_i\shr{\ewit}[i,\cdot,\cdot]$, 
				commitments $\shr{\tilde{c}_1},\ldots,\shr{\tilde{c}_\ell}$ as $\shr{\tilde{c}}_k = \prod_{i\in[p]}(\shr{\comoracle[i,k]})^{\rho_i}$ $\forall k\in[\ell]$
				\item $\distprover\rightarrow\Ag$: $\shr{\tilde{\bm{c}}} = (\shr{\tilde{c}_1},\ldots,\shr{\tilde{c}_\ell})$.
				\item  {$\Ag\rightarrow\verifier$: $\tilde{\bm{c}}=\combine(\shr{\tilde{\bm{c}}}$.} %(\tilde{c}_1,\ldots,\tilde{c}_\ell)$.
				\item $\verifier\rightarrow\distprover$: $r\sample \FF^M$.
				\item $\distprover \text{ and }\verifier$ compute: Polynomials $R^i$, $i\in [p]$ interpolating $R=r^TA$
				as in Section ~\ref{sec:lincheck}. 
				\item $\distprover$ computes: Matrix $\shr{P}$ from $R$ and $\shr{\ewit}$ as described in Section ~\ref{sec:lincheck}. Samples $\shr{P_0}\sample \FF^{2m-1}$, $\shr{\omega_0} \sample \FF$ and $\shr{c_0}\gets \comm(\shr{P_0},\shr{\omega_0})$,  and $\shr{d_0}\gets \comm(\shr{0^{2m-1}},\shr{o})$ where $\shr{o} \sample \FF$.
				Computes commitments $\shr{c_1},\ldots,\shr{c_{s+\ell-1}}$ from $\shr{P}$.
				\item $\distprover\rightarrow\Ag$: $\shr{c_0} ,\shr{c_1} ,\ldots, \shr{c_{s+\ell-1}}, \shr{d_0}$.
				\item  {$\Ag\rightarrow\verifier$: $c_k = \combine(\shr{c_k}) \, \forall k\in [s+\ell-1]$ and sends $c_0,c_1,\ldots,c_{s+\ell-1}$.}
				\item $\verifier\rightarrow\distprover$: $Q=\{(j_u,k_u):u\in [t]\}$ for %$(j_u,k_u)
				$Q\sample [h]\times [n]$ for $u\in [t]$.
				\item $\verifier\rightarrow\pi$: $\{k_u:u\in [t]\}$.
				\item $\distprover\rightarrow\Ag$: $\shr{X_u}=\shr{\ewit}[\cdot,j_u,k_u],  \shr{P_u} = \shr{P}[\cdot,k_u]$ for $u\in [t]$.
				\item  {$\Ag\rightarrow\verifier$: $X_u = \sum_{\xi\in[\Num]} \shr{X_u}, P_u= \sum_{\xi\in [\Num]} \shr{P_u}$ and sends ${X_u}$ for $u\in [t]$.}
				\item $\pi\rightarrow\verifier$: $\pi[\cdot,k_u]$ for $u\in [t]$.
				\item $\verifier\rightarrow\distprover$: $\delta\sample \FF^p$, $\beta\sample \FF\backslash \{0\}$. 
				\item $\distprover\rightarrow\Ag$: $\shr{z} = \beta\shr{P_0} + \shr{\overline{P}}\varphi + \shr{0^{2m-1}}$, $\shr{V_u} = \sum_{i\in[p]} \delta_i \shr{\ewit}[i,\cdot,k_u]$ and sends $\shr{z}$, $\shr{V_u}$.
				\item  {$\Ag$ computes $z=\sum_{\xi\in[\Num]} \shr{z}$, $V_u=\sum_{\xi\in[\Num]} \shr{V_u}$}.
				\item $\Ag$ and $\verifier$ run inner product arguments to check:
				\begin{enumerate}
					\item $\innerproduct(\mathsf{pp},\bm{1}_{j_u}^T\Lambda_{h,2m-1},\mathsf{cm}_u,v_u;\overline{P}[\cdot,k_u])$ 
					%\pnote{We can use $P[1:2m, k_u]$ to denote the first 2m entries of $P[\cdot,k_u]$ as $\overline{P}$ is the submatrix after cropping both the directions, $h$ and $n$.}
					for $u\in [t]$ where $\mathsf{cm}_u=\prod_{a=1}^{s+\ell-1}(c_a)^{\Lambda_{n,s+\ell-1}[a,k_u]}$, 
					$v_u=\sum_{i=1}^pR^i(\alpha_{j_u},\eta_{k_u})X_u[i]$ (check consistency of $P$ with $\pi$).
					\item $\innerproduct(\mathsf{pp},1^m||0^{m-1},\mathsf{cm},r^Tb;z)$ where $z=\beta P_0+\overline{P}\varphi$ and $\mathsf{cm}= (c_0)^{\beta}\cdot\prod_{a=1}^{s+\ell-1}(c_a)^{\varphi_a}$ (check the condition $r^TAw=r^Tb$).
					\item $\innerproduct(\mathsf{pp},\bm{1}_{j_u}^T\Lambda_{h,m},C_u,w_u;V_u)$ for $u\in [t]$ 
					where $C_u=\prod_{i=1}^p(\pi[i,k_u])^{\delta_i}$ and $w_u= \sum_{i\in[p]} \delta_i X_u[i]$(consistency of $X_u$ with $\pi$). 
				\end{enumerate}
				\item $\verifier$ checks: $\prod_{a=1}^\ell(\tilde{c}_a)^{\Lambda^T_{n,\ell}[a,k_u]}=\prod_{i=1}^p(\pi[i,k_u])^{\rho_i}$ for $u\in [t]$ (check proximity of $\ewit$ to $\mc{W}_1$).
			\end{enumerate}
		\end{framed}
		\caption{Distributed Linear Check Protocol}
		\label{fig:distlincheck}
	}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%
%Distributed Quadratic Check of DP-Graphene
\begin{figure}[h]
	{\footnotesize
		%\centering
		\begin{framed}
			\noindent{$\distquadcheck(\mathsf{pp}, [\pi_x], [\pi_y], [\pi_z];\, \shr{\ewit_x}, \shr{\ewit_y}, \shr{\ewit_z}\, \shr{0^{2m}})$}:
			%\pnote{why $\wit$ is not part of the witness of linear check protocol?}
			
			\noindent{\bf Relation}: $[\ewit_x||\ewit_y||\ewit_z]=\open(\pi)\wedge \wit_x \circ \wit_y = \wit_z$ for $\shr{\wit_a}=\dec(\shr{\ewit_a})$ for all $\xi \in [\Num]$ and $\sum_{\xi\in[\Num]} \shr{\wit_a} = \wit_a$ $\forall a\in \{x,y,z\}$.
			
			\begin{enumerate}[{\rm 1.}]
				\item $\verifier\rightarrow\distprover$: $\rho\sample \FF^{3p}$.
				\item $\distprover$ computes: $\shr{\tilde{\ewit}} =\sum_{i=1}^p[\rho_i\shr{\ewit_x}[i,\cdot,\cdot]+
				\rho_{p+i}\shr{\ewit_y}[i,\cdot,\cdot]+\rho_{2p+i}
				\shr{\ewit_z}[i,\cdot,\cdot]]$, 
				commitments $\shr{\tilde{c}_1},\ldots,\shr{\tilde{c}_\ell}$ as $\shr{\tilde{c}}_k = \prod_{i=1}^{p} (\shr{\comoracle_x}[i,k])^{\rho_i}\cdot (\shr{\comoracle_y}[i,k])^{\rho_{p+i}}\cdot(\shr{\comoracle_z}[i,k])^{\rho_{2p+i}}$ $\forall k\in[\ell]$.
				\item $\distprover\rightarrow\Ag$: $\shr{\tilde{\bm{c}}} = (\shr{\tilde{c}_1},\ldots,\shr{\tilde{c}_\ell})$.
				\item  {$\Ag\rightarrow\verifier$: $\tilde{\bm{c}}=\combine(\shr{\tilde{\bm{c}}})$.} %(\tilde{c}_1,\ldots,\tilde{c}_\ell)$.
				\item $\verifier\rightarrow\distprover$: $r\sample \FF^p$.
				\item Provers $\distprover$ run the MPC: $\shr{\ewit_x.\ewit_y}\leftarrow
				\mathsf{Mult}(\shr{\ewit_x},\shr{\ewit_y})$ to obtain shares of the hadamard product of the encodings.
				\item $\distprover$ computes: Matrix $\shr{P}$ from $r$ and $\shr{\ewit_x.\ewit_y}, \, \shr{\ewit_z}$ as described in Section ~\ref{sec:quadcheck}. Samples $\shr{P_0}\sample \FF^{2m-1}$ such that $P_0[j]=0 \forall j\in[m]$, $\shr{\omega_0} \sample \FF$ and $\shr{c_0}\gets \comm(\shr{P_0},\shr{\omega_0})$,  and 
				$\shr{d_0}\gets \comm(\shr{0^{2m-1}},\shr{o})$ where $\shr{o} \sample \FF$.
				Computes commitments $\shr{c_1},\ldots,\shr{c_{2\ell-1}}$ from $\shr{P}$.
				\item $\distprover\rightarrow\Ag$: $\shr{c_0} ,\shr{c_1} ,\ldots, \shr{c_{2\ell-1}}, \shr{d_0}$.
				\item  {$\Ag\rightarrow\verifier$: $c_k = \combine(\shr{c_k}) \, \forall k\in [2\ell-1]$ and sends $c_0,c_1,\ldots,c_{2\ell-1}$.}
				\item $\verifier\rightarrow\distprover$: $Q=\{(j_u,k_u):u\in [t]\}$ for %$(j_u,k_u)
				$Q\sample [h]\times [n]$ for $u\in [t]$. And $\tau \sample \FF^s, \, \gamma \sample \FF^m, \beta\sample \FF^\ast$.
				\item $\verifier\rightarrow\pi$: $\{k_u:u\in [t]\}$.
				\item $\distprover\rightarrow\Ag$: 
				%\begin{itemize}
					 $\shr{X_u}=\shr{\ewit_x}[\cdot,j_u,k_u]$,
					 $\shr{Y_u}=\shr{\ewit_y}[\cdot,j_u,k_u]$,
					 $\shr{Z_u}=\shr{\ewit_z}[\cdot,j_u,k_u]$,
					 $\shr{P_u} = \shr{P}[\cdot,k_u]$
				%\end{itemize} 
				 for $u\in [t]$.
				\item  {$\Ag\rightarrow\verifier$: $A_u = \sum_{\xi\in[\Num]} \shr{A_u}$ where $A\in \{X, Y, Z, P\}$ and sends ${X_u, Y_u, Z_u}$ for $u\in [t]$.}
				\item $\pi\rightarrow\verifier$: $\pi[\cdot,k_u]$ for $u\in [t]$.
				\item $\verifier\rightarrow\distprover$: $\delta\sample \FF^p$, $\beta_x\sample \FF$, $\beta_y\sample \FF$, $\beta_z\sample \FF$,
				$\beta\sample \FF\backslash \{0\}$. 
				
				\item $\distprover$ computes:
				$\shr{V_u}=\sum_{i=1}^p\delta_i\big(\beta_x\shr{\ewit_x}[i,\cdot,k_u]+\beta_y\shr{\ewit_y}[i,\cdot,k_u]+\beta_z\shr{\ewit}[i,\cdot,k_u]\big)$ and $\shr{z} =  \beta\cdot P_0 + \shr{\overline{P}}\varphi + \shr{0^{2m-1}}$.
				\item $\distprover\rightarrow\Ag$:  sends $\shr{z}, \shr{V_u}$.
				\item  {$\Ag$ computes $z=\sum_{\xi\in[\Num]} \shr{z}$} and $V_u = \sum_{\xi\in[\Num]} \shr{V_u}$.
				\item $\Ag \text{ and } \verifier$: Both compute $W_u = \beta_x X_u + \beta_y Y_u + \beta_z Z_u$ for $u\in[t]$. $T_u = (C_u)^{\beta_x}\cdot(D_u)^{\beta_y}\cdot(E_u)^{\beta_z}$, for $u\in [t]$ where
				$C_u=\prod_{i=1}^{p}(\pi_x[i,k_u])^{\delta_i}$, $D_u=\prod_{i=1}^{p}(\pi_y[i,k_u])^{\delta_i}$
				and $E_u=\prod_{i=1}^{p}(\pi_y[i,k_u])^{\delta_i}$.
				\item $\Ag$ and $\verifier$ run inner product arguments to check:
				\begin{enumerate}
					\item $\innerproduct(\mathsf{pp},\bm{1}_{j_u}^T\Lambda_{h,2m-1},\mathsf{cm}_{k_u},v_u;\overline{P}[\cdot,k_u])$ for $u\in [t]$ where $\mathsf{cm}_{k_u}=c_0^{\beta}\prod_{a=1}^{2\ell-1}(c_a)^{\Lambda_{n,2\ell-1}^T[a,k_u]}$, 
					$v_u=\sum_{i=1}^p r_i[X_u[i]\cdot Y_u[i] - Z_u[i]]$ (check consistency of $P$ with $\pi$).
					\item $\innerproduct(\mathsf{pp},\gamma||0^{m-1},\mathsf{cm},0;z)$ where $z=\beta\cdot P_0 + \overline{P}\times \varphi$ and $\varphi = \Phi^T\tau$ and $\mathsf{cm} = \prod_{a=1}^{2\ell-1} (c_a)^{\varphi_a}$ %(check the condition $r^TAw = r^Tb$).
					\item
					$\innerproduct(\mathsf{pp},\bm{1}_{j_u}^T\Lambda_{h,m},T_u,w_u;\overline{V}_u)$, where $\overline{V}_u$ stands for first $m$ entries of $V_u$ and $w_u = \innp{\delta}{W_u}$ (consistency of $X_u, Y_u, Z_u$ with $\pi$).
				\end{enumerate}
				\item $\verifier$ checks proximity of $\ewit_x,\ewit_y$ and $\ewit_z$ according to the Equation \eqref{eq:combinedproximity}.
			\end{enumerate}
		\end{framed}
		\caption{Distributed Quadratic Check Protocol}
		\label{fig:distquadcheck}
	}
\end{figure}

\begin{comment}
\subsection{Interleaved Codes: Alternative interpretation} \label{app:AltILC}
For concreteness, let $\FF$ be the finite field $\FF_q$, consisting of $q$
elements. Let $\HH$ denote the finite field consisting of $q^m$ elements. From
standard algebra, the field $\HH$ is specified by an irreducible polynomial $h(x)\in \FF[x]$ of
degree $m$ as follows:
\begin{itemize}
\item The elements of $\HH$ are polynomials $a(x)$ over $\FF$ of degree at most
$m-1$.
\item The field operations $(+,\cdot)$ on $\HH$ are defined as corresponding
polynomial operations modulo $h(x)$, i.e, on $\HH$ we define $a(x)+b(x) =
(a(x)+b(x)) \text{ mod } h(x)$ and $a(x)\cdot b(x) = (a(x)\cdot b(x)) \text{ mod
} h(x)$. 
\end{itemize}
We can identify the elements of field $\HH$ naturally with the set $\FF^m$ via
the bijection $f:\FF^m\leftrightarrow \HH$ given by
$f(a_0,\ldots,a_{m-1})=\sum_{i=0}a_ix^i$. For any $a,b\in \FF^m$ and $\alpha\in
\FF$, it is seen that $f(a+b)=f(a)+f(b)$ and $f(\alpha a)=\alpha f(a)$. We can
extend $f$ to the bijection $\tilde{f}$ between the set $\mc{M}_{m,n}$ of $m\times n$
matrices over $\FF$ and $\HH^n$ by defining:
\begin{equation}\label{lem:bijection}
\tilde{f}(A) = \big(f(A[\cdot,1]),\ldots,f(A[\cdot,n])\big)
\end{equation}
We have the following:
\begin{lemma}[Correspondence Lemma]\label{lem:correspondence}
Let $L$ be an $[n,k,d]$ code over the field $\FF=\FF_q$, and let $\mc{C} :=
\ric{L}{m}$ be the row interleaved code of $L$. Then $\tilde{f}(\mc{C})$ is an
$[n,k,d]$ code over the field $\HH$, where $\HH=\FF_{q^m}\cong \FF^m$. Moreover,
the generator matrix $\mc{G}$ of $L$ is also the generator matrix of
$\tilde{f}(\mc{C})$. We note that in the latter case $\mc{G}$ is viewed as a
matrix over the field $\HH$.
\end{lemma}
\begin{proof}
Let $\tilde{\mc{C}}$ denote the linear code over $\HH$ given by $\tilde{\mc{C}} :=
\{\mc{G}x: x\in \HH^k\}$. Clearly, $\tilde{\mc{C}}$ is a linear code over $\HH$.
Further it can be seen that $\tilde{\mc{C}}$ is an $[n,k,\ast]$ linear code because
$\mathsf{rank}_{\FF}(\calG)=\mathsf{rank}_{\HH}(\calG)$. This is because $\calG$
contains entries from the subfield $\FF$, and so the determinant of a submatrix of $\calG$
vanishes over $\HH$ if and only if it vanishes over the subfield $\FF$. Now,
consider $A\in \mc{C}$. Then there exists $m\times k$ matrix $P$ such that for all $j\in [n]$, 
we have $A[\cdot,j]=\sum_{i\in [m]}\calG[i,j]P[\cdot,i]$. Therefore, for all
$j\in [m]$,  we have
\begin{align*}
f(A[\cdot,j]) &= f\big(\sum_{i=1}^m \calG[i,j]P[\cdot,i]\big) =
	 \sum_{i=1}^k \calG[i,j]f(P[\cdot,i]) \\
	&= \sum_{i=1}^k \calG[i,j]p_i(x) \text{ where } p_i(x)=f(P[\cdot,i]).
\end{align*}
From the above, it can be seen that:
\[ \tilde{f}(A)=(f(A[\cdot,1]),\ldots,f(A[\cdot,n]))=\calG
[p_1(x),\ldots,p_k(x)]^T \]
 where we view $\tilde{f}(A)$ as a column vector. Thus
$\tilde{f}(\mc{C})\subseteq \tilde{\mc{C}}$. Similarly, one can show that
$\tilde{\mc{C}}\subseteq \tilde{f}(\mc{C})$ and thus conclude
$\tilde{f}(\mc{C})=\tilde{\mc{C}}$. Using similar arguments we can also show
that the code $\tilde{f}(\mc{C})=\tilde{\mc{C}}$ also has the same parity check
matrix as the code $L$, and hence has the same minimum distance $d$. We skip the
proof as it is standard. 
\end{proof}
\end{comment}
% removing proof of Lemma bicdecoding
\begin{comment}
%\subsection{Proof of Lemma~\ref{lem:bicdecoding} }\label{prooflemmaRScode}
\begin{proof}[Proof of Lemma ~\ref{lem:bicdecoding}]\label{prooflemmaRScode}
	Let $U_1 \in \mc{C}_1$  such that $\dham_1(U^\ast, U_1) \leq \dham(U^\ast, U) \forall U\in \mc{C}_1$ and let $\dham_1(U^\ast, U_1) = \beta_1$ with $\beta_1<e_1$
	Therefore $U^\ast$ differs from $U_1$ in $\beta_1$ many columns, i.e. in the remaining $n-\beta_1$ columns $U^\ast$ and $U_1$ are identical.
	So, there are columns $S_1 = \{j_{s} : s\in [n - \beta_1] \}$ for which $U^\ast[i,j] = U_1[i,j]$ $\forall j\in S$.
	Let $U_2 \in \mc{C}_2$  such that $\dham_2(U^\ast, U_2) \leq \dham(U^\ast, U) \forall U\in \mc{C}_2$ and let $\dham_1(U^\ast, U_2) = \beta_2$ with $\beta_2<e_2$
	Therefore $U^\ast$ differs from $U_2$ in $\beta_2$ many rows, i.e. in the remaining $n-\beta_1$ rows $U^\ast$ and $U_2$ are identical.
	So, there are rows $S_2 = \{i_{t} : t\in [h - \beta_2] \}$ for which $U^\ast[i,j] = U_2[i,j]$ $\forall i\in T$.
	
	$U_1\in \mc{C}_1 \implies \exists$ polynomials $p_1(\cdot), \ldots, p_h(\cdot)$ of degree $< \ell$
	
	$U_2\in \mc{C}_2 \implies \exists$ polynomials $q_1(\cdot), \ldots, q_n(\cdot)$ of degree $< m$
	
	Such that $p_i(\eta_j) = U_1[i,j] $ and $ q_i(\alpha_j) = U_2[j,i]$
	
	Therefore, $U_1[i,j] = U_2[i,j]$ $\forall i\in S_1, j\in S_2$. Choose a bivariate polynomial $Q(x,y)$ such that $deg_x(Q)<\ell $ and $deg_y(Q)<m$ and $Q(\eta_{i_s}, \alpha_{j_t}) = U_1[i_s,j_t] = U_2[i_s,j_t] \forall (i, j)\in S_1\times S_2$. 
	
	Defne $U = Q(\eta_i,\alpha_j)$ $\forall i\in[h], j\in[n]$, Then $U \in L_1\otimes L_2$ and $U^\ast[i,j] = U[i,j]$ $\forall (i,j) \in S_1 \times S_2$.
	
	And $|S_1|= n-\beta_1 > n-e_1$ and $|S_2|= h-\beta_2 > h-e_2$.
	This proves the above claim.	
\end{proof}
\end{comment}

\subsection{Proof of Proposition \ref{lem:3dcompression}} \label{app:ProofofLem3dcompression}
We need several observations to prove the proposition, which we present next.
Throughout this section, let $L$ be a linear $[n,k,d]$ code over a field $\HH$ and let $\FF\subseteq \HH$ be a subfield.  Let $m\geq 1$ be an integer, and let $\mc{C}$ denote the row interleaved code $\ric{L}{m}$. For a matrix $U\in \HH^{m\times n}$ and a vector $u_0\in \HH^n$, let $\aff{u_0}{U}$ denote the affine space as:
{
\begin{equation}\label{eq:affspace}
\aff{u_0}{U} := \{u_0+r^TU: r\in \FF^m\}
\end{equation}}
Note that in the above, the scalars in the linear combination come from $\FF$.

The following result was proved in \cite{ligero} for the setting $\HH=\FF$.
For completeness, we present an adaptation of the proof to the setting where
$\FF$ is a subfield of $\HH$.
\begin{lemma}\label{lem:farpoint}
Let $L$ and $\mc{C}$ be codes as defined, and let $e$ be a positive integer such that $e+2\leq |\FF|$. Then for any $u_0\in \HH^n$ and any $U^\ast\in \HH^{m\times n}$ such that $d(U^\ast,\mc{C})>e$, there exists $v\in \aff{u_0}{U^\ast}$ such that $d(v,L)>e$.
\end{lemma} 
\begin{proof}
For sake of contradiction, assume that $d(u,L)\leq e$ for all $u\in
\aff{u_0}{U^\ast}$. Let $x$ be the point in $\aff{u_0}{U^\ast}$ such that
$d(x,L)$ is maximum. By assumption $d(x,L)\leq e$. Let $v\in L$ be such that
$\Delta(x,v)=d(x,L)$. Let $E\subseteq [n]$ be the set of positions where $x$ and
$v$ differ. Since $d(U^\ast,\mc{C})>e$, there exists row $R$ of $U^\ast$ and there is some 
position $j\in [n]\backslash E$ 
such that $R_j\neq 0$. Let
$\alpha_1,\ldots,\alpha_{e+1}$ be distinct non zero elements in $\FF$. Let $E_k$
for $k=1,\ldots,e+1$ denote the set of positions where $x+\alpha_kR$ and $v$
differ. Fix a position $i\in E$. Then there exists at most one $k\in [e+1]$ such
that $i\not\in E_k$. By pegion hole principle, there exists $k\in [e+1]$ such
that $E\subseteq E_k$. We also observe that since $\alpha_k\neq 0$, $j\in E_k$.
Thus $d(x+\alpha_k,v)>d(x,v)$, contradicting the choice of $x$. This proves the
lemma.   
\end{proof}

Next we prove a result about lines with respect to linear codes. The result was
proved in \cite{ligero} for the case $\HH=\FF$ and $e<d/4$. The authors in
\cite{ligero} conjectured the result for $e<d/3$. Here we prove the result for
$e<d/3$ when $\FF$ can be an arbitrary subfield of $\HH$.

\begin{lemma}[Affine Line]\label{lem:affineline}
Let $L$ be the linear code as defined. Define an affine line $\ell_{u,v}$ in $\HH^n$ as $\ell_{u,v} := \{u + \alpha v:\alpha\in \FF\}$ for $u,v\in \HH^n$. Then for $e < d/3$ and any affine line $\ell_{u,v}$:
\begin{enumerate}[{\rm (i)}]
\item $d(x,L)\leq e$ for all $x\in \ell_{u,v}$, or
\item $d(x,L)> e$ for at most $d$ points in $\ell_{u,v}$.
\end{enumerate}
\end{lemma}
\begin{proof}
%\nnote{Candidate for Appendix: Putting it here just to have all content for the moment}
In this proof, let $\delta(x,y)$ denote the set of positions where the vectors
$x$ and $y$ differ, and let $\wt{x}$ denote $|\delta(x,\bm{0})|$. The above is equivalent to
proving that if there exist $d+1$ distinct points $X =
\{x_1,\ldots,x_{d+1}\}\subseteq \ell_{u,v}$ such
that $d(x_i,L)\leq e$ for all $i\in [d+1]$, then $d(x,L)\leq e$ for all $x\in
\ell_{u,v}$. Assume that there exists such a set $X$ of $d+1$ points. Let $\ell_i$ denote the point in $L$ closest to $x_i$ for $i\in
[d+1]$. Set $\eta_i=x_i-l_i$ for all $i$ and let
$\bm{\eta}=\{\eta_1,\ldots,\eta_{d+1}\}$. By assumption we have
$\wt{\eta_i}\leq e$ for all $i\in [d+1]$. Since $\ell_{u,v}$ is contained in affine
span of any two distinct points on it, we have tuples
$\{(\alpha_i,\beta_i)\}_{i\in [d+1]}d$ such that $\alpha_i + \beta_i=1$ and $x_i=\alpha_ix_1 +
\beta_ix_2$ for $i\in [d+1]$. Note that $(\alpha_1,\beta_1)=(1,0)$ and
$(\alpha_2,\beta_2)=(0,1)$. Observe that $\alpha_i$'s and $\beta_i$'s must be
distinct for all $i\in [d+1]$. We call $X$ as {\em degenerate} if there exist
$i\neq j$ satisfying $\alpha_j=\gamma\alpha_i$ and $\beta_j=\gamma\beta_j$ for
some $\gamma\in \FF\backslash {0}$. We consider two cases:

\noindent{\em $X$ is degenerate}: Degeneracy implies there exist $i\neq j$ such that $x_i=\gamma x_j$ for
some $\gamma\in \FF\backslash\{0\}$. In this case we have $0 =
\frac{1}{1-\gamma}x_i -\frac{\gamma}{1-\gamma}x_j\in \ell_{u,v}$. This implies
$\ell_{u,v}=\{\alpha x_i: \alpha\in \FF\}$
and hence $d(x,L)=d(x_i,L)\leq e$ for all $x\in \ell_{u,v}$. Thus the statement
of the Lemma holds in this case.\smallskip 

\noindent{\em X is not degenerate}: We first prove
that $\ell_i=\alpha_i\ell_1+\beta_i\ell_2$ and
$\eta_i=\alpha_i\eta_1+\beta_i\eta_2$ for
all $i\in [d+1]$. We have
\begin{align*}
\ell_i+\eta_i& = x_i = \alpha_ix_1 + \beta_ix_2 
    = \alpha_i(\ell_1+\eta_1) + \beta_i(\ell_2 + \eta_2) \\
    &= (\alpha_i\ell_1 + \beta_i\ell_2) + (\alpha_i\eta_1 + \beta_i\eta_2)
\end{align*}
Rearranging we have,
$
\ell_i - (\alpha_i\ell_1 + \beta_i\ell_2) = \alpha_i\eta_1 +
\beta_i\eta_2 - \eta_i
$.
In the above equation we see that LHS is a vector in $L$. Further
$\wt{\alpha_i\eta_1 + \beta_i\eta_2 - \eta_i}\leq
\wt{\eta_1}+\wt{\eta_2}+\wt{\eta_i}\leq 3e < d$. Thus the LHS must be equal to
$0$ and hence $\ell_i = \alpha_i\ell_1 + \beta_i\ell_2$ and
$\eta_i=\alpha_i\eta_1+\beta_i\eta_2$. Observe that any $x^\ast\in \ell_{u,v}$ can
be written as $x^\ast=\alpha^\ast x_1+\beta^\ast x_2$. Thus
$d(x^\ast,L)=d(\alpha^\ast x_1+\beta^\ast x_2,L)\leq \wt{\alpha^\ast
\eta_1+\beta^\ast \eta_2}\leq |E|$ where $E$ denotes the set
$\delta(\eta_1,0)\cup \delta(\eta_2,0)$. Our final effort will be to show that
$|E|\leq e$.

\noindent{\it Claim}: $|E|\leq e$ where $E = \delta(\eta_1,0)\cup
\delta(\eta_2,0)$. We consider the partition of $E$ into sets
$E_0=\delta(\eta_1,0)\backslash \delta(\eta_2,0)$,
$E_1=\delta(\eta_2,0)\backslash \delta(\eta_1,0)$ and
$E_{01}=\delta(\eta_1,0)\cap \delta(\eta_2,0)$. Let $t=|E|$. Consider a $t\times (d+1)$ matrix $M=(m_{ij})$
where $m_{ij}=0$ if $j^{th}$ coordinate ($\eta_i^j$) of $\eta_i$ is zero, and $m_{ij}=1$
otherwise. We will show that each row of $M$ has at most one $0$. Assume that
there exists $i$ such that $m_{ip}=0$ and $m_{iq}=0$ for $p\neq q$. We consider
three cases:
\begin{itemize}
\item If $i\in E_0$, the above condition implies $\alpha_p\eta_1^i =
\alpha_q\eta_1^i=0$, or $\alpha_p=\alpha_q=0$ as $\eta_1^i\neq 0$ for $i\in E_0$.
This contradicts the fact that $X$ is not degenerate.
\item The case $i\in E_1$ is similar to above.
\item If $i\in E_{01}$ we have
$\alpha_p\eta_1^i+\beta_p\eta_2^i=\alpha_q\eta_1^i+\beta_q\eta_2^i=0$ which
implies $\alpha_p/\beta_p=\alpha_q/\beta_q=-\eta_2^i/\eta_1^i$, or
$\alpha_p/\alpha_q = \beta_p/\beta_q$ which contradicts the fact that $X$ is
not degenerate. Note that all denominators can be argued to be non-zero for $i\in E_{01}$. 
\end{itemize}

From the above, we conclude that each row has at least $d$ entries as $1$.
Counting by columns, we have that each column has at most $e$ entries as $1$
(since $\wt{\eta_i}\leq e$ for all $i\in [d]$. Comparing the lower and upper
bounds on the number of $1$ entries in the matrix we have $td \leq e(d+1)$
which implies $t \leq e + e/d < e + 1$. Thus $t\leq e$, as we wanted to show.
This completes the proof.

\end{proof}

The following result underlies proximity protocols in our work and in
\cite{ligero}. Intuitively the result states that if a matrix is far away from the code $\mc{C}$, a random linear combination of its rows is far away from a codeword in $L$, and thus the proximity of the matrix to $\mc{C}$ may be tested by testing the proximity of a random linear combination of its rows to $L$.

\begin{lemma}[Affine Subspace]\label{lem:affinesubspace}
Let the codes $L$ and $\mc{C}$ be as defined and $e<d/3$ be an integer. Let $U\in \HH^{m\times n}$ be a matrix such that $d(U,\mc{C})>e$. Then for any $u_0\in \HH^n$, $\prob{d(u_0+r^TU,L)\leq e}\leq d/|\FF|$ for uniformly sampled $r\sample \FF^m$.
\end{lemma}
\begin{proof}
From Lemma \ref{lem:farpoint}, there exists $u\in \aff{u_0}{U}$ such that $d(u,L)>e$. Now we can write $\aff{u_0}{U}$ as union of affine lines passing through $u$. Applying lemma \ref{lem:affineline} to each line, we see that at most $d$ points $x$ on each affine line satisfy $d(x,L)\leq e$. Thus, a randomly sampled point $x$ in $\aff{u_0}{U}$, equivalently obtained as $u_0+r^TU$ for a randomly sampled vector $r\in \FF^m$ satisfies $d(x,L)$ with probability at most $d/|\FF|$.
\end{proof}

We are now in a position to prove Proposition \ref{lem:3dcompression}.
\begin{proof}[Proof of Proposition \ref{lem:3dcompression}]
Let $\HH$ denote the field $\FF^m$. Then $u_0$ can be viewed as a point in
$\HH^n$. Similarly $U$ can be viewed as $p\times n$ matrix over $\HH$.
We consider $\mc{C}$ as $[n,k,d]$ code over $\HH$ and $\mc{C}^p$ as the
interleaved code of $\mc{C}$ over the field $\HH$. Then by applying Lemma \ref{lem:affinesubspace}
with $\HH=\FF^m$ and codes $\mc{C}$ and $\mc{C}^p$ in place of codes $L$ and
$\mc{C}$, we have the desired bound.
\end{proof}

\subsection{Proof of knowledge for Linear Check}\label{app:linear_soundness}
\begin{proof}[{\bf Proof of Lemma ~\ref{lem:linearcheck_sound}:}]
Suppose the oracle $\pi$ commits to $\ewit$. $\ewit$ can be ``extracted'' by the appropriate extractor. Note that $\ewit\in (\mc{W}_2)^p$ as a commitment implicitly corresponds to such a matrix. Let $e<(n-\ell)/3$ be a parameter. First we show that an adversarial prover succeeds with negligible probability if $d(\ewit,(\mc{W}_1)^p)>e$. Second, we
show that for $d(\ewit,(\mc{W}_1)^p)\leq e$, the prover succeeds with negligible probability when $A\wit\neq b$ where $\wit=\dec(\ewit)$. Consider the case when $d(\ewit,(\mc{W}_1)^p)>e$. Then for
$\tilde{\ewit}=\sum_{i\in [p]}\rho_i\ewit[i,\cdot,\cdot]$, by Proposition ~\ref{lem:3dcompression},
 we have $d(\tilde{\ewit},\mc{C}_1)>e$ with probability $1-o(1)$. Let $\tilde{\bm{c}}=(\tilde{c}_1,
\ldots,\tilde{c}_\ell)$ be the commitments to $\tilde{\ewit}$ sent by the prover
(Step 3 in Figure ~\ref{fig:linearcheck}). Define 
the vector $\tilde{\bm{C}}=(\tilde{C}_1,\ldots,\tilde{C}_n)$ where
$\tilde{C}_k=\prod_{a=1}^\ell (\tilde{c}_a)^{\Lambda_{n,\ell}^T[a,k]}$ for $k\in [n]$.
 Let $\hat{\bm{C}}=(\hat{C}_1,\ldots,\hat{C}_n)$ where
$\hat{C}_k=\prod_{i=1}^p(\pi[i,k])^{\rho_i}$. Now if
$\Delta(\tilde{\bm{C}},\hat{\bm{C}})>e$, we see that the prover succeeds in the
proximity check equation \eqref{eq:proxchecks} with probability at most $(1-e/n)^t$. 
In the complete
proof, we show that when $\Delta(\tilde{\bm{C}},\hat{\bm{C}})\leq e$, 
while $d(\tilde{\ewit},\mc{C}_1)>e$, the prover knows two openings to a commitment.
Thus an adversarial prover succeeds with probability at most $(1-e/n)^t$ when
$d(\ewit,(\mc{W}_1)^p)>e$.

We now consider the case when $d(\ewit,(\mc{W}_1)^p)\leq e$. From Lemma
~\ref{lem:bicdecoding}, there exists (unique) $\ewit^*\in (\mc{W})^p$
such that $\Delta_1(\ewit,\ewit^*)\leq e$.
Let $\wit=\dec(\ewit)=\dec(\ewit^*)$. We consider the prover's success
probability when $A\wit\neq b$, and thus with overwhelming probability $r^TA \wit \neq
r^Tb$. Let $P^*$ denote the correctly computed intermediate matrix from $\ewit^*$ and let
$\hat{P}$ denote the correctly computed intermediate matrix from $\ewit$. We note that
$\Delta_1(\hat{P},P^*)\leq e$. Let $c_1,\ldots,c_{s+\ell-1}$ be the commitments
to the intermediate matrix sent by the prover. If these commitments correspond to a
matrix $P=P^*$, the inner product check
$\innerproduct(\mathsf{pp},[1^m||0^{m-1}],\mathsf{cm},r^Tb)$ fails when using the
commitment $\mathsf{cm}=\prod_{k=1}^{s+\ell-1}c_k^{\varphi_k}$ for
$\varphi=\Phi\times [1^s]$. This is because $\innp{1^m||0^{m-1}}{P^*[1:2m-1,1:s+\ell-1]\times
\varphi}=r^TA\wit\neq r^Tb$, %where $\overline{P^*}$ denotes the $(2m-1)\times (s+\ell-1)$ submatrix of $P^*$,
as discussed in the protocol. If the
commitments correspond  to a matrix $P\neq P^*$, we have
$\Delta_1(P,P^*)\geq n-s-\ell$ by distance property of the code
$\rsc{\eta}{n, s+\ell-1}$. 
(We note that a prover implicitly commits to a matrix in
$\rsc{\eta}{n,s+\ell-1}\otimes \rsc{\alpha}{h,2m-1}$).
Thus there exists a set $E$ of at least $n-s-\ell-e$ columns, such that for
$k\in E$, $\hat{P}[\cdot,k]=P^*[\cdot,k]\neq P[\cdot,k]$. The checks
$\innp{\bm{1}_{j_u}}{\ewit[i,\cdot,k_u]}=X_u[i]$ for $i\in [p]$ and $u\in [t]$ 
force the prover to provide vectors $X_u=\ewit[\cdot,j_u,k_u]$ with
overwhelming probability. Then the consistency check succeeds for the 
uniformly sampled query point $(j_u,k_u)$ when:
\[ P[j_u,k_u] = \sum_{i\in [p]}R^i(\alpha_{j_u},\eta_{k_u})X_u[i] =
\hat{P}[j_u,k_u] \]
For $k_u\in E$, the above holds when the distinct codewords $P^*[\cdot,k_u]$ and
$P[\cdot,k_u]$ in $\rsc{\alpha}{h,2m-1}$ agree on the position $j_u$, which happens with 
probability at most $2m/h$. Thus probability $\prob{\mc{E}_u}$ that above query succeeds is bounded by:
\begin{align*}
\prob{\mc{E}_u}&\leq \frac{s+\ell+e}{n} + \frac{n-s-\ell-e}{n}\cdot\frac{2m}{h}
\\
&= \frac{2m}{h}+\left(1-\frac{2m}{h}\right)\left(\frac{s+\ell+e}{n}\right)
\end{align*}
The above probability is smaller than a constant $\epsilon<1$ for suitable
choices of parameters. Hence, the overall probability of prover's success is
$\negl(\secpar)$ for $t=O(\secpar)$.

\smallskip
\paragraph{Extraction}: Let $\extrac_{ip}$ be the extractor of the inner product argument which takes, in expectation, $\Pip(n)$ amount of time, where $\Pip(\cdot)$ is polynomial, to output the private vector of length or breaking the binding of the commitment scheme. We will design an extractor $\extrac$ for $\linearcheck$, which uses $\extrac_{ip}$.

\smallskip
If $\prover^\ast$ fails in the proximity check (step 12) then $\verifier$ outputs reject, and so the extractor $\extrac$ terminates with $\abort$.
If $\prover^\ast$ succeeds in the proximity check (step 12) then $\ewit\in \mc{W}_1$ and $\extrac$ proceeds in the following way:

\smallskip
$\extrac$ plays the role of the verifier and rewinds the provers polynomially many times if required.

\smallskip
$\extrac$ runs the protocol till step 8, sends $Q$ and receives $\ewit[\cdot, j_u,k_u]$. %Then it rewinds $\prover^\ast$ and sends new random $Q$. $\extrac$ keeps rewinding till $k_u$'s of all the $Q$s covered $[n]$. In expectation it takes $O(n\log(n))$ rewinds.

$\extrac$ picks random $\delta\in \FF^p$ and $\beta\in\FF^\ast$ and proceeds to run the inner product arguments. $\extrac$ uses $\extrac_{ip}$ and gets:
\begin{itemize}
	\item  $\overline{P}[\cdot,k_u]$ in expected time $\Pip(m)$, $\forall u\in[t]$
	\item $z=\beta P_0 + \overline{P}\varphi$ in expected time $\Pip(m)$
	\item $V_u = \sum_{i\in[p]} \delta_i\ewit[i,\cdot,k_u]$ in expected time $\Pip(m)$, $\forall u\in[t]$
\end{itemize}
Then $\extrac$ rewinds $\delta, \beta$ $O(p\log(p))$ times and gets $P_0$ from $z$ and from $V_u$, $\extrac$ gets $\ewit[\cdot,\cdot,k_u]$. $\extrac$ checks $\ewit[\cdot,j_u,k_u]$ received in step 8, matches with the extracted $\ewit[\cdot,\cdot,k_u]$'s $j_u$ position or not. If does not, then $\extrac$ gets two opening of $\pi[\cdot,k_u]$ and outputs $\abort$, otherwise $\extrac$ proceeds in the following way: $\extrac$ rewinds $\prover^\ast$ and sends uniformly random $Q$ and keeps repeating untill all the $Q$'s together cover all the columns. It takes $n\log(n)$ rewindings in expectation. Then $\extrac$ extracts the whole $\ewit$ and checks if all the vectors are consistent or not. If not, that gives the break for the binding of the commitment scheme and if consistent, then it decodes $\ewit$ and outputs correct witness $\wit$. 
\smallskip
Therefore, expected Run time of $\extrac$ is $O(n\log(n)(O(p\log(p))(\Pip(m)) + \Pip(m) + \Pip(m))) $, which is polynomial in the size of the circuit.
\end{proof}

\subsection{Proof of knowledge of Quadratic Check }\label{app:quad_soundness}
\begin{proof}[{\bf Proof of Lemma ~\ref{lem:quadcheck_sound}:}]
	Suppose the oracle $\pi$ commits to $\ewit_x, \ewit_y, \ewit_z$. %In full version, we show how this 
	$\ewit_x, \ewit_y, \ewit_z$ can be ``extracted'' by the appropriate extractor. Note that $\ewit_x||\ewit_y||\ewit_z\in
	(\mc{W}_2)^{3p}$, where $\ewit = \ewit_x||\ewit_y||\ewit_z$ is the juxtaposing along $p$ direction, as a commitment implicitly corresponds to such a matrix. Let $e<(n-\ell)/3$ be a parameter. First we show that 
	an adversarial prover succeeds with negligible probability if $d(\ewit,(\mc{W}_1)^{3p})>e$. Second, we
	show that for $d(\ewit,(\mc{W}_1)^{3p})\leq e$, the prover succeeds with negligible probability when
	$\wit_x\circ\wit_y\neq\wit_z$ where $\wit_a=\dec(\ewit_a)$ for $a\in\{x,y,z\}$. Consider the case when $d(\ewit,(\mc{W}_1)^{3p})>e$. Then for
	$\tilde{\ewit}=\sum_{i\in [3p]}\rho_i\ewit[i,\cdot,\cdot]$, by Proposition ~\ref{lem:3dcompression},
	we have $d(\tilde{\ewit},\mc{C}_1)>e$ with probability $1-o(1)$. Let $\tilde{\bm{c}}=(\tilde{c}_1,
	\ldots,\tilde{c}_\ell)$ be the commitments to $\tilde{\ewit}$ sent by the prover
	(Step 3 in Figure ~\ref{fig:quadcheck}). Define 
	the vector $\tilde{\bm{C}}=(\tilde{C}_1,\ldots,\tilde{C}_n)$ where
	$\tilde{C}_k=\prod_{a=1}^\ell (\tilde{c}_a)^{\Lambda_{n,\ell}^T[a,k]}$ for $k\in [n]$.
	Let $\hat{\bm{C}}=(\hat{C}_1,\ldots,\hat{C}_n)$ where
	$\hat{C}_k=\prod_{i=1}^{3p}(\pi[i,k])^{\rho_i}$. Now if
	$\Delta(\tilde{\bm{C}},\hat{\bm{C}})>e$, we see that the prover succeeds in the
	proximity check equation \eqref{eq:proxchecks} with probability at most $(1-e/n)^t$. 
	In the complete
	proof, we show that when $\Delta(\tilde{\bm{C}},\hat{\bm{C}})\leq e$, 
	while $d(\tilde{\ewit},\mc{C}_1)>e$, the prover knows two openings to a commitment.
	Thus an adversarial prover succeeds with probability at most $(1-e/n)^t$ when
	$d(\ewit,(\mc{W}_1)^{3p})>e$.
	
	We now consider the case when $d(\ewit,(\mc{W}_1)^{3p})\leq e$. From Lemma
	~\ref{lem:bicdecoding}, there exists (unique) $\ewit^*\in (\mc{W})^{3p}$
	such that $\Delta_1(\ewit,\ewit^*)\leq e$.
	Let $\wit_a=\dec(\ewit_a)=\dec(\ewit^*_a)$. We consider the prover's success
	probability when $\wit_x\circ \wit_y = \wit_z$, and thus with overwhelming probability $\sum_{i\in[p]} r_i\cdot(\wit_x[i,\cdot,\cdot]\cdot\wit_y[i,\cdot,\cdot]-\wit_z[i,\cdot,\cdot]) = [\bm{0}]^{ms}$. Let $P^*$ denote the correctly computed intermediate matrix from $\ewit^*$ and let
	$\hat{P}$ denote the correctly computed intermediate matrix from $\ewit$. We note that
	$\Delta_1(\hat{P},P^*)\leq e$. Let $c_1,\ldots,c_{2\ell-1}$ be the commitments
	to the intermediate matrix sent by the prover. If these commitments correspond to a
	matrix $P=P^*$, the inner product check
	$\innerproduct(\mathsf{pp},[\gamma||0^{m-1}],\mathsf{cm},0)$ fails when using the
	commitment $\mathsf{cm}=\prod_{k=1}^{2\ell-1}c_k^{\varphi_k}$ for
	$\varphi=\Phi\times \tau$. This is because $\innp{\gamma||0^{m-1}}{P^*[1:2m-1,1:2\ell-1]\times
		\varphi}=\sum_{j\in[m]} \gamma_j\sum_{k\in[s]} \tau_k\sum_{i\in[p]}r_i[\wit_x[i,j,k]\cdot\wit_y[i,j,k]-\wit_z[i,j,k]] \neq 0$, %where $\overline{P^*}$ denotes the $(2m-1)\times (s+\ell-1)$ submatrix of $P^*$,
	as discussed in the protocol. If the
	commitments correspond  to a matrix $P\neq P^*$, we have
	$\Delta_1(P,P^*)\geq n-2\ell$ by distance property of the code
	$\rsc{\eta}{n, 2\ell-1}$. 
	(We note that a prover implicitly commits to a matrix in
	$\rsc{\eta}{n,2\ell-1}\otimes \rsc{\alpha}{h,2m-1}$).
	Thus there exists a set $E$ of at least $n-2\ell-e$ columns, such that for
	$k\in E$, $\hat{P}[\cdot,k]=P^*[\cdot,k]\neq P[\cdot,k]$. The checks
	$\innp{\bm{1}_{j_u}}{W_u}=\sum_{i\in[p]}\delta_i(\beta_x X_u + \beta_y Y_u + \beta_z Z_u)$ for $i\in [p]$ and $u\in [t]$ 
	force the prover to provide vectors $X_u=\ewit_x[\cdot,j_u,k_u], Y_u=\ewit_y[\cdot,j_u,k_u],
	Z_u=\ewit_z[\cdot,j_u,k_u]$ with
	overwhelming probability. Then the consistency check succeeds for the 
	uniformly sampled query point $(j_u,k_u)$ when:
	\[ P[j_u,k_u] = \sum_{i\in [p]}r_i(X_u[i]\cdot Y_u[i]-Z_u[i]) =
	\hat{P}[j_u,k_u] \]
	For $k_u\in E$, the above holds when the distinct codewords $P^*[\cdot,k_u]$ and
	$P[\cdot,k_u]$ in $\rsc{\alpha}{h,2m-1}$ agree on the position $j_u$, which happens with 
	probability at most $2m/h$. Thus probability $\prob{\mc{E}_u}$ that above query succeeds is bounded by:
	\begin{align*}
	\prob{\mc{E}_u}&\leq \frac{2\ell+e}{n} + \frac{n-2\ell-e}{n}\cdot\frac{2m}{h}
	\\
	&= \frac{2m}{h}+\left(1-\frac{2m}{h}\right)\left(\frac{2\ell+e}{n}\right)
	\end{align*}
	The above probability is smaller than a constant $\epsilon<1$ for suitable
	choices of parameters. Hence, the overall probability of prover's success is
	$\negl(\secpar)$ for $t=O(\secpar)$.
	
	\smallskip
	\paragraph{Extraction}: Let $\extrac_{ip}$ be the extractor of the inner product argument which takes, in expectation, $\Pip(n)$ amount of time, where $\Pip(\cdot)$ is polynomial, to output the private vector of length or breaking the binding of the commitment scheme. We will design an extractor $\extrac$ for $\quadcheck$, which uses $\extrac_{ip}$.
	
	\smallskip
	If $\prover^\ast$ fails in the proximity check (step 15) then $\verifier$ outputs reject, and so the extractor $\extrac$ terminates with $\abort$.
	If $\prover^\ast$ succeeds in the proximity check (step 15) then $\ewit\in \mc{W}_1$ and $\extrac$ proceeds in the following way:
	
	\smallskip
	$\extrac$ plays the role of the verifier and rewinds the provers polynomially many times if required.
	
	\smallskip
	$\extrac$ runs the protocol till step 7, sends $Q,\gamma, \tau$ and receives $\ewit_x[\cdot, j_u,k_u], \ewit_y[\cdot, j_u,k_u], \ewit_z[\cdot,j_u,k_u]$. %Then it rewinds $\prover^\ast$ and sends new random $Q$. $\extrac$ keeps rewinding till $k_u$'s of all the $Q$s covered $[n]$. In expectation it takes $O(n\log(n))$ rewinds.
	
	$\extrac$ picks random $\delta\in \FF^p$, $\beta_x,\beta_y,\beta_z\in\FF$ and $\beta\in\FF^\ast$ and proceeds to run the inner product arguments. $\extrac$ uses $\extrac_{ip}$ and gets:
	\begin{itemize}
		\item  $\overline{P}[\cdot,k_u]$ in expected time $\Pip(m)$, $\forall u\in[t]$
		\item $z=\beta P_0 + \overline{P}\varphi$ in expected time $\Pip(m)$
		\item $V_u = \sum_{i\in[p]} \delta_i(\beta_x\ewit_x[i,\cdot,k_u]+\beta_y\ewit_y[i,\cdot,k_u]+\beta_z\ewit_z[i,\cdot,k_u])$ in expected time $\Pip(m)$, $\forall u\in[t]$
	\end{itemize}
	Then $\extrac$ rewinds $\delta, \beta_x,\beta_y,\beta_z,\beta$ $O(p\log(p))$ times and gets $V_u$, $\extrac$ gets $\ewit_x[\cdot,\cdot,k_u], \ewit_y[\cdot,\cdot,k_u], \ewit_z[\cdot,\cdot,k_u]$ by solving a system of equation with $3p$ unknowns. $\extrac$ checks $\ewit_a[\cdot,j_u,k_u]$ received in step 7, matches with the extracted $\ewit_a[\cdot,\cdot,k_u]$'s $j_u$ position or not, for $a\in\{x,y,z\}$. If does not, then $\extrac$ gets two opening of $\pi_a[\cdot,k_u]$, for some $a\in\{x,y,z\}$ and outputs $\abort$, otherwise $\extrac$ proceeds in the following way: $\extrac$ rewinds $\prover^\ast$ and sends uniformly random $Q$ and keeps repeating untill all the $Q$'s together cover all the columns. It takes $n\log(n)$ rewindings in expectation. Then $\extrac$ extracts the whole $\ewit_x,\ewit_y,\ewit_z$ and checks if all the vectors are consistent or not. If not, that gives the break for the binding of the commitment scheme and if consistent, then it decodes $\ewit_a$ and outputs correct witness $\wit_a$ for $a\in\{x,y,z\}$. 
	\smallskip
	Therefore, expected Run time of $\extrac$ is $O(n\log(n)(O(p\log(p))(\Pip(m)) + \Pip(m) + \Pip(m))) $, which is polynomial in the size of the circuit.
\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{comment}
\subsection{Proof of soundness of Distributed Linear Check}
\begin{lemma}[Soundness with Extraction]\label{lem:distlinearcheck_sound}
	For all polynomially bounded adversary $\Adv$ controlling all the provers $\prover_1, \ldots, \prover_{\Num}$ and all $\pi\in\GG^{p\times n}$, $A\in\FF^{M\times N}, b\in\FF^M$, there exists an polynomial time extractor $\extrac$ with rewinding access to the transcript $\tr$ between the aggregator $\Ag$ and the verifier $\verifier$ such that $\extrac$ either breaks the commitment binding or outputs a witness with overwhelming probability whenever $\Adv$ succeeds, i.e.,
	
	{\small
		\begin{align*}
		\condprob{\begin{array}{c}
			\ewit=\open(\pi)\wedge \\
			A\wit=b
			\end{array}
		}{
			\begin{array}{c}
			\sigma\gets \gen(\secparam) \\
			\ewit\gets \extr^{\mathsf{tr}}(\bm{x},\sigma) \\
			\wit\gets \dec(\ewit)
			\end{array}}\geq
		\epsilon(\Adv)-\kappa_{lc}(\secpar)
		\end{align*} 
	}
where $\epsilon(\Adv):= \condprob{\langle \Adv(\bm{x},\sigma),\verifier^\pi(\bm{x},\sigma)\rangle=1}{\sigma\gets \gen(\secparam)}$ denotes the success probability of $\Adv$, $\kappa_{lc}$ denotes a negligible function, and $\bm{x}$ denotes the tuple $(A,b,M,N)$.
\end{lemma}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Proof of soundness of Distributed Quadratic Check}
\begin{lemma}[soundness with extraction]\label{lem:distquadcheck_sound}
	For all polynomoially bounded adversary $\Adv$, controlling all the provers $\prover_1, \ldots, \prover_{\Num}$ and $\pi\in\GG^{3p\times n}$, there exists an expected polynomial time extractor $\extrac$ with rewinding access to the transcript $\tr$ between the aggregator $\Ag$ and the verifier $\verifier$ such that $\extrac$ either breaks the commitment binding, or it outputs a witness with overwhelming probability whenever $\Adv$ succeeds, i.e.,
	
	{\footnotesize
		\begin{align*}
		\condprob{
			\begin{array}{c}
			{[}\ewit_x||\ewit_y||\ewit_z{]}=\open(\pi)\wedge \\
			\wit_z=\wit_x\circ\wit_y
			\end{array}
		}{
			\begin{array}{c}
			\sigma %\sample \gen(\secparam) \\
			\leftarrow \gen(\secparam) \\
			{[}\ewit_x||\ewit_y||\ewit_z{]}%\sample \extr^{\mc{O}}(\sigma)\\
			\leftarrow \extr^{\mathsf{tr}}(\sigma) \\ 
			\wit_a=\dec(\ewit_a), a\in \{x,y,z\}
			\end{array}
		}\\
		\geq \epsilon(\Adv) - \kappa_{\rm qd}(\secpar)
		\end{align*}
	}
	for some negligible function $\kappa_{qd}$. In the above, $\epsilon(\Adv)$
	denotes the success probability of the prover $P^\ast$ as before.
\end{lemma}
\end{comment}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{comment}
\section{cryptographic preliminaries}
\begin{comment}
\subsection{Commitment scheme} \label{app:DefCommitment}
\begin{definition}\label{defn:commscheme}
 A pair of $\ppt$ algorithms $(\gen,\com)$ constitute a non-interactive commitment scheme if $\sigma\sample \gen(\secparam)$ consists of description of sets $\calM_\sigma$ (message space), $\calR_\sigma$ (randomness space), $\calC_\sigma$ (commitment space) and an efficiently computable function $\com_\sigma: \calM_\sigma\times \calR_\sigma\rightarrow \calC_\sigma$ which is {\em hiding} and {\em binding} as defined later.
\end{definition}

For $x\in \calM_\sigma$, we generate a {\em commitment} of $x$ as $\com_\sigma(x,r)$ where $r\sample \calR_\sigma$ is drawn uniformly at random. For ease of notation, we simply use $\com$ instead of $\com_\sigma$ and use $\com(x)$ to denote the random variable corresponding to commitment of $x$. 

\begin{definition}[Hiding Commitment]\label{defn:hidingcomm}
A commitment scheme $(\gen,\com)$ is called perfectly {\em hiding}  if for all adversaries $\adv$, the following probability is  $1/2$:
{\small
\begin{align*}
\condprob{b=b'}{
\begin{array}{l}
\sigma\gets \gen(\secparam); \\
(x_0,x_1)\in \calM^2_p\gets \adv(\sigma); \\
b\sample \bitset; c\gets \com(x_b);\\
b'\gets \adv(\secparam,\sigma,c)
\end{array}
}
\end{align*}
}
\end{definition}

\begin{definition}[Binding Commitment]\label{defn:bindingcomm}
A commitment scheme $(\gen,\com)$ is called {\em binding} if for all $\ppt$  $\adv$, 
{\small
\begin{align*}
\condprob{
	\begin{array}{c}
	\com_\sigma(x_0,r_0)=\com_\sigma(x_1,r_1)\\
	\wedge x_0\neq x_1
\end{array}}{
\begin{array}{l}
\sigma \gets \gen(\secparam) \\
x_0,x_1,r_0,r_1 \gets \adv(\secparam,\sigma)
\end{array}
}\\
 < \negl(\lambda)
\end{align*}
}

\end{definition}

\subsection{Inter-product Arguments} \label{inner-product-instan}
\noindent{\em Logarithmic Inner-product Argument}: In this setting, we have $\calM=\bbZ^n_p$, $\calR=\bbZ_p$, $\calC=\bbG$ where $\bbG$ is group of prime order $p$. The algorithm $\gen$ samples generators $g_1,\ldots,g_n$, $h$ $\gets \bbG$. 
The commitment is a Pederson vector commitment  given by $\com({\bf x } ,r ) = h^r \cdot \prod_{i=1}^n {g_i}^{x_i}$ where ${\bf x}=(x_1,\ldots,x_n)$. 
We use the inner-product argument $(\prover,\verifier)$ from Bootle et. al in \cite{bulletproofs} for the commitment scheme $(\gen,\com)$. The interactive protocol $(\prover,\verifier)$ is a $O(\log n)$ round protocol with argument size $O(\log n)$. The verifier $\viplog$ performs $O(n)$ operations in $\bbZ_p$ and $O(n)$ operations in $\bbG$.\smallskip


\noindent{\em Square-root Inner-product Argument}: In this setting we use the same commitment scheme as above. For the inner product argument we use the interactive protocol $(\pipsq,\vipsq)$ from \cite{InnerProductDLS}. The construction in \cite{InnerProductDLS} gives a $5$-round protocol with total communication complexity $O(\sqrt{n})$. Here, the verifier $\vipsq$ performs $O(n)$ operations in $\bbZ_p$ and $O(\sqrt{n})$ operations in $\bbG$.
\end{comment}

\begin{comment}
\subsection{Forking Lemma and Knowledge Soundness}
We use the Forking Lemma from \cite{InnerProductDLS,bulletproofs} to describe 
expected polynomial time knowledge extractors for our protocols. Let
$(\prover,\verifier)$ be a public coin $(2\mu+1)$-move interactive protocol with
challenges $x_1,\ldots,x_\mu$ in sequence. Let $n_i\geq 1$ for $1\leq i\leq
\mu$. We call a collection of $n=\prod_{i=1}^\mu n_i$ accepting transcripts to be
$(n_1,\ldots,n_\mu)$-tree of accepting transcripts, if the challenges are
organized in the tree format that we describe now: \commentA{the following didn't make sense. what does a path from root to a leaf node signify? one sequence of challenges for an accepting execution? at any rate this portion needs a clean write-up} The root of the tree is
labelled with the statement being proved. Each node of depth $i<\mu$ has exactly
$n_i$ children, each labelled with a distinct value of the $i^{th}$ challenge
$x_i$. We call a $\ppt$ algorithm $\chi$ to be a {\em witness extraction
algorithm} if $\chi$ can extract a witness $w$ to the statement, given an
appropriate tree of accepting transcripts. This can be seen as a generalization
of the notion of special soundness for Sigma protocols with $n=2$ and $\mu=1$.
\end{comment}

% remove argument of knowledge
\begin{comment}
\begin{definition}[Argument of Knowledge]\label{def:argofknowledge}
Let $(\setup,\prover,\verifier)$ be an public coin interactive protocol. We say that
$(\setup,\prover,\verifier)$ is an {\em argument of knowledge} for the language
$\mc{L}$ if for every $\ppt$
prover $P^\ast$, there exists an expected polynomial time extractor $\extr$ such that for all $x$:
%\begin{comment}
{\small
\begin{align*}
\condprob{(x,w)\in \mc{L}}{
\begin{array}{c}
\sigma\gets\setup(\secparam) \\
w\gets \extr^{\mc{O}}(x,\sigma)
\end{array}
}\\
\geq \condprob{\langle
P^\ast(x,\sigma),\verifier(x,\sigma)\rangle=1}{\sigma\gets \setup(\secparam)} -
\negl(\lambda)
\end{align*}}
%
%\begin{align}
%&\prob{(x,w)\in\mc{L}| \sigma \sample \setup(\secparam); w\sample \extr^{\mc{O}}(x,\sigma)}\\
%\geq & \prob{\innp{P^*(x,\sigma)}{\verifier(x, \sigma)} = 1|\sigma\sample \setup(\secparam)} - \kappa(\lambda)
%\end{align}
for some negligible function $\negl$. In the above $\mc{O}$ denotes the transcript oracle  $\langle P^\ast(x,\sigma)$ ,$\verifier(x,\sigma)\rangle$which can be rewound to any previous state, and resumed with fresh randomness for the
verifier $\verifier$.
\end{definition}

Our argument of knowledge proofs rely on the following result from \cite{bulletproofs}.
While the result is originally stated and proved for showing witness-extended
emulation, we restate it for the case of argument of knowledge. The proof in
\cite{InnerProductDLS} also applies to this restricted case.



\begin{lemma}[Forking Lemma,\cite{bulletproofs}]\label{lem:forkinglemma}
Let $(\setup,\prover,\verifier)$ be a $(2\mu+1)$-round public coin interactive
protocol. Let $\chi$ be a $\ppt$ witness extraction algorithm that outputs a
witness with probability $1-\negl(\secpar)$ from an $(n_1,\ldots,n_\mu)$-tree
of accepting transcripts. Assuming that $\prod_{i=1}^\mu n_i$ is bounded by a
polynomial in security parameter $\secpar$, the protocol
$(\setup,\prover,\verifier)$ is an argument of knowledge.
\end{lemma}

\section{Proofs}
\begin{proof}[Proximity 2D]
The extractor $\extr$ starts by emulating the verifier in the protocol
$\proximityTwoD$. At the step 5, it uses the extractor $\extr_{ip}$ for the
inner product protocol to extract the witness $z$ for the $\innerproduct$
subprotocol. If the initial transcript rejects, $\extr$ fails with output
$\bot$. Otherwise, it rewinds transcript to step 2, till it finds $\ell+1$
additional accepting transcripts. Let $\tau^i,\delta^i$ denote the random
vectors in step 2, in the $i^{th}$ accepting transcript (we let $i=0$ denote the
initial transcript). Similarly, let $x^i$, $\mathsf{cm}^i$ denote the values of
vectors $x$ and $\mathsf{cm}$ in the $i^{th}$ accepting transcript, while $(z^i,o^i)$
denotes the witness extracted by the inner product extractor $\extr_{ip}$
corresponding to $x^i$ and $\mathsf{cm}^i$. If the inner product extractor
$\extr_{ip}$ fails with $z^i=\bot$ for any $i\in [\ell+1]$, the extractor $\extr$
fails with output $\bot$. From the inner product extractions we have the
following:
\begin{align*}
\begin{array}{rlll}
\comm(z^1,o^1)=& c_0 + \mu^1_1c_1+ & \hdots & +\mu^1_{\ell}c_{\ell} \\
\vdots & \vdots & \ddots & \vdots \\
\comm(z^{\ell+1},o^{\ell+1})=& c_0 + \mu^{\ell+1}_1c_1+ & \hdots & +\mu^{\ell+1}_{\ell}c_{\ell} 
\end{array}
\end{align*}
Let $\Lambda$ denote the $(\ell+1)\times (\ell+1)$ matrix $[1^{\ell+1}|\mathbf{M}]$ with $\mathbf{M}[i,j]=\mu^i_j$. For convenience of notation, we will consider row and column indices of $(\ell+1)\times (\ell+1)$ matrices in this proof to be over the set $\{0,\ldots,\ell\}$. 
Since $\mc{T}$ is a rank $\ell$ matrix, we see that $\Lambda$ is an invertible
matrix for random choices of vectors $\tau^i$, except with probability
$1/|\FF|$. Let $\Omega$ be the $(\ell+1)\times (\ell+1)$ matrix such that
$\Omega\Lambda=I_{\ell+1}$. Define $U_k = \sum_{i=0}^{\ell}\Omega[k,i]z^i$ and $\omega_k=\sum_{i=0}^{\ell}\Omega[k,i]o^i$. 
$k\in [\ell]$. Then for $k\geq 1$ we have,
\begin{align*}
\comm(U_k,\omega_k) &= \sum_{i=0}^{\ell}\Omega[k,i]\comm(z^i,o^i)  \\
	&= \sum_{i=0}^{\ell}\Omega[k,i]\sum_{j=0}^{\ell}\Lambda[i,j]c_j \\
	&= \sum_{j=0}^{\ell}\big(\sum_{i=0}^{\ell}\Omega[k,i]\Lambda[i,j]\big)c_j
\\
	&= c_k \text{ (using $\Omega\Lambda=I_{\ell+1})$ }
\end{align*}
Thus $\overline{U}=(U_1,\ldots,U_{\ell})$ and $\bm{\omega}=(\omega_1,\ldots,\omega_{\ell})$ satisfies $(\overline{U},\bm{\omega})=\open(\bm{c})$. Now we
consider the probability that $\overline{U}\mc{T}\in \mc{C}_2$. Let $A$ denote the event
that the first transcript accepts. Let $B\subseteq A$ be the event that
$(\overline{U}\neq\bot)\cap (\overline{U}\mc{T}\in \mc{C}_2)$. We have,
\begin{align*}
&\prob{B}\\ &= \prob{A} - \prob{A\cap \neg B} \\
	&\geq \prob{A} - \prob{A\cap (\overline{U}=\bot)} - \prob{A\cap
(\overline{U}\mc{T}\not\in \mc{C}_2)} \\
	&= \prob{A} - \prob{A\cap (\overline{U}=\bot)} - \prob{A\cap
(\mc{T}^T\overline{U}^T\mc{H}_2\neq 0)} \\
	&\geq \prob{A} - \prob{A\cap (\overline{U}=\bot)} -\\
& \text{     }\condprob{\tau^T\mc{T}^T\overline{U}^T\mc{H}_2\delta=
0}{\mc{T}^T\overline{U}^T\mc{H}_2\neq 0} \\
	&\geq \prob{\langle P^\ast(\bm{c},\sigma),\verifier(\bm{c},\sigma)\rangle=1}
- \big(\ell.\kappa_{ip}(\secpar)+1/|\FF|\big) - 2/|\FF|
\end{align*} 
In the above, we bound the probability $\condprob{\tau^T\mc{T}^T\overline{U}^T\mc{H}_2\delta=
0}{\mc{T}^T\overline{U}^T\mc{H}_2\neq 0}$ by $2/|\FF|$ as $\tau$ and $\delta$ are
distributed uniformly and independently of the extracted witness $\overline{U}$. The
probability $\prob{A\cap (\overline{U}=\bot)}$ is bound in terms of the probability
of inner product extractor returning an invalid witness or $\Lambda$ being
singular which is at most $\ell.\kappa_{ip}(\secpar)+1/|\FF|$. The
statement of the lemma now holds by setting
$\kappa_{2d}(\secpar):=\ell.\kappa_{ip}(\secpar) + 3/|\FF|$.
\end{proof}

%%% proximity 3d proof

\begin{proof}[Proximity 3D]
As before the extractor $\extr$ emulates the verifier in the protocol
$\proximityThreeD$. In case the first transcript is accepting, the extractor
rewinds the prover sufficiently many times to obtain a tree of accepting transcripts with $p$ distinct
choices of the randomness $r$ in step (1) and $\theta := tn$ different values of $Q$
on step (5). Let $r^{1},\ldots,r^{p}$ denote the values of $r$ in step (1)
and let $\tilde{\mathbf{c}}^{1},\ldots,\tilde{\mathbf{c}}^{p}$ denote the corresponding
commitment vectors in step (3). Similarly, let $Q^{uv}$ denote the $v^{th}$
choice of $Q$ corresponding to $u^{th}$ value of $r$ for $u\in [p]$ and $v\in
[\theta]$. We do not consider the initial transcript as part of the tree of
transcripts. We notice that we have $\cup_{v\in [\theta]}Q^{uv}=[n]$ for all
$u\in [p]$, except with probability at most $pn(1-1/n)^{nt}\leq pne^{-t}$. At
step (4), $\extr$ uses extractor $\extr_{2d}$ for the protocol $\proximityTwoD$
to extract $h\times \ell$ matrix $W^{u}$ for $u\in [p]$. The extractor $\extr$ fails with output $\bot$
if $\extr_{2d}$ fails in any of its invocations. By the property of $\extr_{2d}$
we have that $\open(\tilde{\bm{c}}^u)=W^u$ and $W^u\in L_1\oplus L_2$ for all
$u\in [p]$. We construct the witness $\ewit$ by solving for each $h$-length
vector $\ewit[i,\cdot,k]$ for $i\in [p], k\in [n]$ according to
\eqref{eq:extraction3d}. Let $T_1,\ldots,T_n$ denote the columns of matrix
$\mc{T}$. 
\begin{align}\label{eq:extraction3d}
\text{For each $k\in [n]$ we have:}  \nonumber \\
\begin{array}{cccc}
r^1_1\ewit[1,\cdot,k]+ &\hdots & +r^1_p\ewit[p,\cdot,k] &= W^1T_k \\
\vdots & \ddots & \vdots & \vdots \\
r^p_1\ewit[1,\cdot,k]+ &\hdots & +r^p_p\ewit[p,\cdot,k] &= W^pT_k 
\end{array}
\end{align}
Let $\Lambda$ denote the $p\times p$ matrix with $\Lambda[i,j]=r^i_j$. We may
assume that $\Lambda$ is invertible, except with probability $1/|\FF|$. Let
$\Omega$ be such that $\Omega\Lambda = I_p$. It can be seen that the system of
equations \eqref{eq:extraction3d} is satisfied by setting $\ewit[i,\cdot,k]=\sum_{j\in
[p]}\Omega[i,j]W^jT_k$ for $i\in [p],k\in [n]$. First we prove that
$\comm(\ewit[i,\cdot,k])=\pi[i,k]$ for all $i$ and $k$. Indeed,
\begin{align*}
\comm(\ewit[i,\cdot,k]) & =\sum_{j\in [p]}\Omega[i,j]\comm(W^jT_k) \\
	& = \sum_{j\in [p]}\Omega[i,j]\sum_{a\in [\ell]}\mc{T}[a,k]\comm(W^j[.,a]) \\
	& = \sum_{j\in [p]}\Omega[i,j]\sum_{a\in
[\ell]}\mc{T}[a,k]\tilde{\bm{c}}^j_a \\
	& = \sum_{j\in [p]}\Omega[i,j]\sum_{a\in [p]}r^j_a\pi[a,k] \text{ (using check
(7)) } \\
	& = \sum_{a\in [p]} \big(\sum_{j\in [p]}\Omega[i,j]\Lambda[j,a]\big)\pi[a,k]
\\
	& = \pi[i,k]
\end{align*}

Note that the columns
$\ewit[i,\cdot,k]$ are linear combinations of the columns of extracted matrices
$W^u, u\in [p]$ which are codewords in the code $L_2$. Thus, each column
$\ewit[i,\cdot,k]$ in the extracted witness $\ewit$ is a codeword in $L_2$. Thus
 $\ewit\in \mc{W}_2$. Next, we bound the probability that
$d_1(\ewit,\mc{W}_1)\leq e$. To do so, we define the
following events of interest:
\begin{itemize}
\item $A$: denotes the event that the first transcript is accepting. By
definition, $\prob{A}$ is the accepting probability $\prob{\langle
P^\ast(\sigma),\verifier(\sigma)\rangle=1}$.
\item $B$: denotes the sub-event of $A$ when the extracted opening $\ewit$ to the
commitment oracle $\pi$ is valid, i.e $d_1(\ewit,\mc{W}_1)\leq e$. 
\item $F$: denotes the event that $\extr$ fails with output $\bot$. This
happens when one of the invocations subprotocol extractor $\extr_{2d}$ fails, or
unlikely events that the matrix $\Lambda$ is singular, or that $\theta=tn$
repetitions of the random query locations $Q$ fail to cover the set of indices
$[n]$. As discussed in the proof, we can bound $\prob{F}$ by
$p\kappa_{2d}(\secpar) + pne^{-t} + 1/|\FF|$. 
\end{itemize}
Using an analysis similar to the one in the proof of Lemma
\ref{lem:proximity2d_sound}, we have:
\begin{equation}\label{eq:probeq1}
\prob{B}\geq \prob{A} - \prob{F} - \condprob{A}{d_1(\ewit,\mc{W}_1)>e}   
\end{equation}
Let $\tilde{\bm{c}}=(\tilde{c}_1,\ldots,\tilde{c}_\ell)$ denote the vector sent
by the prover in step (3). We consider the $n$-length vector $C_{adv}$
defined by $C_{adv}[k]=\sum_{i\in [\ell]}\mc{T}[i,k]\tilde{c}_i$ for $k\in [n]$. Let
$C_{hon}$ denote the honestly computed vector defined by $C_{hon}[k]=\sum_{i\in
[p]}r_i\pi[i,k]$. Note that for honest oracle $\pi\in\mc{W}$ and honest prover
we would have $C_{adv}=C_{hon}$. Let $\varepsilon := \Delta(C_{adv},C_{hon})$ denote the
hamming distance between the two vectors. Now we can write
$\condprob{A}{d_1(\ewit,\mc{W}_1)>e}$ as:
\begin{align}\label{eq:probeq3}
\condprob{A}{d_1(\ewit,\mc{W}_1)>e} &\leq \condprob{A}{d_1(\ewit,\mc{W}_1)>e,
\varepsilon \leq e}\nonumber \\ 
&\quad +\condprob{A}{d_1(\ewit,\mc{W}_1)>e, \varepsilon > e}
\end{align}
The above follows from the identity $\condprob{A}{X}\leq
\condprob{A}{X_1}+\condprob{A}{X_2}$ for $X=X_1\uplus X_2$. Next we note
that for $\varepsilon > e$, the check in step 7, succeeds with probability at most
$(n-e)^t/n^t=(1-e/n)^t$. Thus $\condprob{A}{d_1(\ewit,\mc{W}_1)>e,\varepsilon > e}\leq
(1-e/n)^t$. Next we bound $\condprob{A}{d_1(\ewit,\mc{W}_1)>e,\varepsilon\leq e}$.
With probability at least $1-\kappa_{2d}(\secpar)$, the extractor $\extr_{2d}$
produces a witness $\overline{U}$ such that $\overline{U}\mc{T}\in L_1\oplus L_2$, and
$\overline{U}=\open(\tilde{\bm{c}})$.  Let
$U_{adv} = \overline{U}\mc{T}$ denote the codeword in $L_1\oplus L_2$. We note that
$U_{adv}=\open(C_{adv})$. Define $U_{hon}=\sum_{i\in [p]}r_i\ewit[i,.,.]$. Note
that $U_{hon}=\open(C_{hon})$ by homomorphism of the commitment scheme. Since
$\varepsilon=d(C_{adv},C_{hon})\leq e$, we must have:
\begin{enumerate}[{\rm (i)}]
\item $\Delta_1(U_{adv},U_{hon})\leq e$ or,
\item There exists an index $j\in [n]$ such that $C_{adv}[j]=C_{hon}[j]$, but
their corresponding openings $U_{adv}[j]$ and $U_{hon}[j]$ are different. This
constitutes breakage to the binding property of the commitment scheme $\comm$. 
\end{enumerate}
Assuming $\Delta_1(U_{adv},U_{hon})\leq e$, we have $d_1(U_{hon},\mc{C}_1)\leq
e$. From the above, we can now write:
\begin{align*}\label{eq:probeq4}
&\condprob{A}{d_1(\ewit,\mc{W}_1)>e,\varepsilon\leq e}\\
\leq&
\condprob{d_1(U_{hon},\mc{C}_1)\leq e}{d_1(\ewit,\mc{W}_1)>e} + \mc{B}(\secpar)
\end{align*}
Since $U_{hon}=\sum_{i\in [p]}r_i\ewit[i,\cdot,\cdot]$, from Lemma
\ref{lem:3dcompression}, we have $\condprob{d_1(U_{hon},\mc{C}_1)\leq
e}{d_1(\ewit,\mc{W}_1)>e}<d_1/|\FF|$ where $d_1$ is the minimum distance of the
code $L_1$. Thus, Equation \eqref{eq:probeq3} gives us
\begin{equation}\label{eq:probeq5}
\condprob{A}{d_1(\ewit,\mc{W}_1)>e}\leq \left(1-\frac{e}{n}\right)^t,
\frac{d_1}{|\FF|}+\kappa_{2d}(\secpar) + \mc{B}(\secpar)
\end{equation}
From Equations \eqref{eq:probeq1} and \eqref{eq:probeq5} we see that the
statement of the Lemma holds for 
\[\kappa_{3d}(\secpar) := (p+1)\kappa_{2d}(\secpar) + pne^{-t} +
\left(1-\frac{e}{n}\right)^t + \frac{d_1+1}{|\FF|} + \mc{B}(\secpar) \]
\end{proof}


\begin{proof}[Linear Check]
We describe an extractor $\extr$ which outputs $\ewit$ such that $\open(\pi)=\ewit$ and $A\wit = b$ 
for $\wit=\dec(\ewit)$. The extractor $\extr$ uses the extractor $\extr_{3d}$ for
the protocol $\proximityThreeD$ to extract the witness $\ewit$ which opens to
the oracle $\pi$. Note that, with probability at least ($1-\kappa_{3d}(\secpar)$),
the extracted witness $\ewit$ satisfies $d_1(\ewit,\mc{W}_1)<e$ and $\ewit\in
\mc{W}_2$. It follows that for each slice $\ewit^i:=\ewit[i,\cdot,\cdot]$ for $i\in [p]$,
we have $\ewit^i\in \mc{C}_2$ and $d_1(\ewit^i,\mc{C}_1)<e$. Let $E\subseteq
[n]$ denote the indices of the {\em planes} where $\ewit$ differs from its closest
neighbor in $\mc{W}_1$. Since $e<d_1/2$, $E$ also denotes the set of columns
where slices $\ewit^i$ differ from their closest neighbors in $\mc{C}_1$. We
decode each slice seperately. Applying Lemma \ref{lem:bicdecoding} for each
slice, we have codewords $W^i\in L_1\oplus L_2$ for each $i\in [p]$ such that
$W^i[\cdot,k]=\ewit^i[\cdot,k]$ for all $k\not\in E$. Let $Q^i$, $i\in [p]$ be
the unique polynomials with $deg_x(Q^i)<m$ and $deg_y(Q^i)<\ell$ such that
$Q^i(\alpha_j,\eta_k)=W^i[j,k]$ for $(j,k)\in [h]\times [n]$. We define the
witness $\wit$ by $\wit[i,j,k] := Q^i(\alpha_j,\zeta_k)$ for $i\in [p],j\in
[m],k\in [s]$. Note that $\wit=\dec(\ewit)$. In case, the subprotocol extractor
$\extr_{3d}$ outputs $\ewit$ such that $d_1(\ewit,\mc{W}_1)>e$, the extractor
$\extr$ fails with output $\wit := \bot$. Let $\ewit_{\rm hon}$ denote the
encoding of $\wit$ given by $\ewit_{\rm hon}[i,j,k]=Q^i(\alpha_j,\eta_k)$ for
$i\in [p],j\in [h], k\in [n]$. Observe that we have $d_1(\ewit,\ewit_{\rm
hon})<e$. Let $\mc{S}$ denote the event that the
first transcript succeeds. As before, the key step to ensure soundness is to
upper bound the probability $\prob{\mc{S}\cap (A\wit\neq b)}\leq
\condprob{\mc{S}}{A\wit\neq b}\leq \condprob{\mc{S}}{r^TA\wit\neq r^Tb}+1/|\FF|$
where $r\sample \FF^N$ denotes the message sent by $\verifier$ in Step 1. Let
$P_{\rm hon}$ denote the matrix $P$ which is correctly computed from $\ewit_{\rm
hon}$ in
Step 3. Let $c_1,\ldots,c_{\ell}$ be the commitments sent (possibly,
adverserial) by the prover to the verifier in Step 4. Let $\overline{P}_{\rm adv}$ be the
witness extracted using the extractor $\extr_{2d}$ for the subprotocol in Step
10. Let $P_{\rm adv}$ denote the matrix $\overline{P}_{\rm adv}T$. Then with overwhelming
probability ($1-\kappa_{2d}(\secpar)$), $P_{\rm adv}\in \dashL_1\oplus \dashL_2$. Observe
that if $P_{\rm hon}=P_{\rm adv}$, then $r^TA\neq r^Tb$ implies that
$\overline{P}=\overline{P}_{\rm adv}$ does not satisfy Equation
\eqref{eq:necessarycondlin} and thus the subprotocol in Step 11 succeeds with
probability at most $\kappa_{ip}(\secpar)$, or $\extr$ succeeds in finding
distinct openings to the commitment in subprotocol in Step 11. Assume then that $P_{\rm hon}\neq
P_{\rm adv}$. Again, from subprotocol in Step 14, we conclude that $X_u =
\ewit[\cdot,j_u,k_u]$, except with probability $\kappa_{agg}(\secpar)$, or
$\extr$ outputs two openings to one of the commitments $\pi[j_u,k_u]$ for $u\in
[t]$. Similarly, assuming $\extr$ does not break binding of the commitment
scheme, the witnesses extracted for inner product protocols in Step 13, are the
columns $P_{\rm adv}[\cdot,k_u]$ for $u\in [t]$. Thus, with overwhelming probability, the inner product check in Step 13 is
equivalent to checking the following for all $u\in [t]$:
\begin{equation}\label{eq:check1}
P_{\rm adv}[j_u,k_u]=\sum_{i\in
[p]}R^i(\alpha_{j_u},\eta_{k_u})\ewit[i,j_u,k_u]
\end{equation}
For $u\in [t]$, let $\mc{E}_u$ denote the event that the above equation holds
for $u$. For $k_u\not\in E$, we have $\ewit[\cdot,\cdot,k_u]=\ewit_{\rm
hon}[\cdot,\cdot,k_u]$ and thus the right hand side in \eqref{eq:check1} equates
to $P_{\rm hon}[j_u,k_u]$. Now, $P_{\rm adv}$ and $P_{\rm hon}$ differ in at
least $\dashD_1$ columns, where $\dashD_1$ denotes the minimum distance of the
code $\dashL_1$. Let $E'$ denote the column indices where $P_{\rm adv}$ and
$P_{\rm hon}$ differ. For $k_u\in E'\backslash E$, the check succeeds if the
distinct codewords $P_{\rm adv}[\cdot,k_u]$ and $P_{\rm hon}[\cdot,k_u]$ agree
at position $j_u$. Since $(j_u,k_u)$ are sampled uniformly and independently
(also independent of extracted witness $\wit$), we have:
{\small
\begin{align}\label{eq:probeq6}
\prob{\mc{E}_u} &\leq \frac{n-\dashD_1+e}{n} +
\frac{\dashD_1-e}{n}.\frac{h-\dashD_2}{h}
\nonumber \\
	&\leq \frac{s+\ell+e}{n} + \frac{n-s-\ell-e}{n}.\frac{2m}{h} \nonumber \\
	& = \frac{2m}{h} +
\left(1-\frac{2m}{h}\right)\left(\frac{s+\ell+e}{n}\right)
\end{align}
}
For initial transcript to accept, all the $t$ checks should succeed, and thus we
have:
{\small
\begin{align}\label{eq:probeq7}
&\prob{\mc{S}\cap (A\wit\neq b)}\\
\leq&
\left(\frac{2m}{h}+\left(1-\frac{2m}{h}\right)\left(\frac{s+\ell+e}{n}\right)\right)^t
+ \kappa_{3d}(\secpar) + \mc{B}(\secpar) +
\frac{O(|C|)}{|\FF|} \nonumber \\
\leq& \left(1-\frac{e}{n}\right)^t +
\left(\frac{2m}{h}+\left(1-\frac{2m}{h}\right)\left(\frac{s+\ell+e}{n}\right)\right)^t
\\
& \qquad \, \, \,+ \frac{O(|C|)}{|\FF|} + \mc{B}(\secpar)
\end{align}
}
Thus the statement of the lemma holds for $\kappa_{lc}(\secpar) := (1-e/n)^t +
(2m/h + (1-2m/h)(2\ell/n + e/n))^t+O(|C|)/|\FF|+\mc{B}(\secpar)$.
\end{proof}


\begin{proof}[Simulation]
We consider the simulator as discussed. Let $\bm{r}=(r,\{j_u,k_u\}_{u\in
[t]},\beta,\tau,\delta,\rho,\tilde{\tau},\tilde{\delta})$ denote the vector
consisting of verifier's randomness, which is chosen exactly in the honest
protocol execution. Distributions $p(z|\bm{r})$ and $p(\tilde{z}|\bm{r})$ are
uniform distributions on $L_2$ due to the blinding vector $u_0\in L_2$ chosen by
the prover in the $\proximityTwoD$ protocol. Similarly, due to blinding vector
$P_0\in \dashL_2$ chosen in Step 3(d), the distribution
$p(z'|\bm{r})$ is also uniform on the vectors $z'$ in $\dashL_2$ satisfying
$\sum_{j\in [m]}z'[j]=0$. Since $t\leq \bi$, from Lemma
\ref{lem:boundedindependence}, we conclude that the planes
$\ewit[\cdot,\cdot,k_u]$ are distributed uniformly independent of $\bm{r}$. In
the real execution of the protocol, the prover chooses
$\omega_0,\omega_1,\ldots,\omega_{s+\ell}$ and $\nu_0$ independently at random
and computes:
\begin{align}\label{eq:simeq}
\chi_u &= \sum_{a\in [s+\ell]}T[a,k_u]\omega_a \forall u\in [t] \nonumber \\
\omega &= \omega_0 + \sum_{a\in [s+\ell]}\mu_a\omega_a \nonumber \\
\nu &= \nu_0 + \sum_{a\in [s+\ell]}\phi_a\omega_a
\end{align}    
Since any $t$ columns of $T$ are linearly independent, we see that the matrix of
coefficients in \eqref{eq:simeq} has full row rank, and thus the vector
$(\chi_1,\ldots,\chi_t,\omega,\nu)$ is disrtributed uniformly in $\FF^{t+2}$.
Similarly, $\{O[\cdot,k_u]\}_{u\in [t]}$ also consists of uniformly sampled
entries in $\FF$ as in the real protocol. We now consider computation of
$\tilde{\nu}$ in the honest protocol execution. We have:
\begin{align}\label{eq:simeq2}
\tilde{\nu} &= \tilde{\nu}_0 + \sum_{a\in [\ell]}\tilde{\mu}_a\tilde{\omega}_a
 \text{ where } \nonumber \\
\tilde{\omega}_a &= \sum_{i\in [p]}\rho_iO[i,a] \quad \forall a\in [\ell]
\end{align} 
Since $\tilde{\nu}_0$ is choesn randomly by the prover, the distribution of
$\tilde{\nu}$ is uniform, independent of other variables in the view. Finally,
the commitments in the view satisfy relations in Equation \ref{eq:commiteq} in
the real protocol, and are picked uniformly subject to those constraints by the
simulator. Thus the view output by the simulator perfectly simulates the
extended view of the verifier as defined. 
\begin{align}\label{eq:commiteq}
d_0 + \sum_{a=1}^{s+\ell}\mu_ac_a &= \comm(z,\nu) \nonumber \\
c_0 + \sum_{a=1}^{s+\ell}\varphi_ac_a &= \comm(z',\omega) \nonumber \\
\sum_{a=1}^{s+\ell}T[a,k_u]c_a &= \comm(P[\cdot,k_u],\chi_u) \text{ for } u\in [t] \nonumber \\
\sum_{a=1}^{\ell}\mc{T}[a,k_u]\tilde{c}_a &= \comm\big(\sum_{i\in
[p]}
[\cdot,k_u],\tilde{O}[\cdot, k_u]\big) \text{ for } u\in [t] \nonumber \\
\beta\tilde{d}_0 + \sum_{a=1}^{\ell}\tilde{\mu}_a\tilde{c}_a &=
\comm(\tilde{z},\tilde{\nu})
\end{align} 

\end{proof}
\end{comment}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{comment}
\subsection{Semi-honest to Malicious Security: }\label{app:semi-honesttomalicious} 
To achieve security against malicious provers, every prover $\distprover$ sends Zero-Knowledge Argument of Knowledge (ZKAoK) along with every committed value sent to $\Ag$, which says $\distprover$ knows what value is committed. A malicious secure MPC executes multiplication. Furthermore, all messages are sent via broadcast.
%In our protocol, when a prover $\distprover$ sends any commitment output to the aggregator, in the maliciously secure protocol $\distprover$ with that commitment output, he additionally sends a Zero-Knowledge Argument of Knowledge (ZKAoK) which says $\distprover$ knows which value is committed. This additional step is required in the simulation so that the simulator can extract the committed value and maliciously secure MPC to compute $\mathsf{Mult}$. Furthermore, all the messages to $\Ag$ are via broadcast. 
%\pnote{Give the overview of the proof. and explain why the does not go through when the aggregator is corrupt.}

\noindent{\bf Overview of the proof:} 
With the above modification, our protocol can withstand malicious provers. We can design a simulator for the protocol, which uses $\extrac$, the extractor of ZKAoK, Simulator $\Sim_{Mult}$ for the secure MPC for multiplication, and zero-knowledge simulator $\Sim_{ZK}$ of Graphene. 
$\Sim$ receives the messages from the corrupt parties to $\Ag$ due to broadcast. Then, $\Sim$ calls $\extrac$ and obtains opening of $\shr{\comoracle}$ for all corrupt $\xi$. Using $\Sim_{ZK}$, $\Sim$ prepares the messages of the honest parties, and if there is any interaction required between the provers, that interaction is generated via $\Sim_{Mult}$. $\Sim$ checks if all the messages are consistent or not with all the previous messages if not $\Sim$ sends consistent but random values on behalf of honest parties, otherwise, just before sending $\shr{z_{lc}}$ and $\shr{z_{qd}}$, $\Sim$ invokes the $\Func_{\DPZK}$ if it outputs 1, then $\Sim$ generates messages for honest parties using $\Sim_{ZK}$ otherwise it picks messages uniformly at random.
%\pnote{I think a little detailing is required here.}
%We will describe, in high-level, how to construct a simulator $\Sim$ which can generate a view which is indistinguishable from a real execution, where $\Sim$ has access to the extractor $\extrac$ for the ZKAoK and the simulator $\Sim_{Mult}$ for the secure multiplication and the zero-knowledge simulator $\Sim_{ZK}$ of \name. $\Sim$ receives the messages from the corrupt parties to $\Ag$ due to broadcast. Then, $\Sim$ calls $\extrac$ and obtains opening of $\shr{\comoracle}$ for all corrupt $\xi$. Using $\Sim_{ZK}$, $\Sim$ prepares the messages of the honest parties, and if there is any interaction required between the provers, that interaction is generated via $\Sim_{Mult}$. $\Sim$ checks if all the messages are consistent or not with all the previous messages if not $\Sim$ sends consistent but random values on behalf of honest parties, otherwise, just before sending $\shr{z_{lc}}$ and $\shr{z_{qd}}$, $\Sim$ invokes the $\Func_{\DPZK}$ if it outputs 1, then $\Sim$ generates messages for honest parties using $\Sim_{ZK}$ otherwise it picks messages uniformly at random.

\noindent{\bf Difficulty in simulation while aggregator is malicious:} The above proof works against malicious provers but semi-honest aggregator. To generate the messages on behalf of honest parties, $\Sim$ needs the output of $\Func_{DPZK}$. If $\Ag$ deviates from the protocol at the last round, then the simulator cannot generate an appropriate message, which gives the same output as real-execution. Though we don't have a simulator when $\Ag$ is malicious, we do not have an attack either. Also, it is possible to identify the malicious behavoiur of $\Ag$ since messages to $\Ag$ are via broadcast, and $\Ag$ does not require any internal randomness to generate messages to the $\verifier$. 
%In the above construction, it considered that provers might deviate while interacting among themselves. However, we do not consider the scenario if $\Ag$ deviates. We do not have a simulator that can simulate a view when all the provers (corrupt and honest) behaving correctly, but $\Ag$ sends a wrong combined value to $\verifier$. To resolve, one can try to invoke the $\Func_{\DPZK}$ after $\Ag$ sending the final value to $\verifier$. However, $\Ag$ needs honest parties messages to generate the message for $\verifier$, and the simulator needs the output of the $\Func_{\DPZK}$. So, it is difficult to get a simulator, which can generate a view indistinguishable from the real world execution. Though we can not construct a simulator for our protocol, we do not have an attack in this corruption model. Also, it is possible to identify the malicious behavoiur of $\Ag$ since messages to $\Ag$ are via broadcast, and $\Ag$ does not require any internal randomness to generate messages to the $\verifier$. 
\end{comment}

\begin{comment}
\begin{lemma}\label{lem:privacy}
For $\xi\in [K]$, let $\View^{\xi}_{\adv}$\pnote{fix notation} denotes the view of the adversary $\adv$ corrupting parties in $I$, where $I$ is a proper subset of the sets of the provers. Then there is a $\ppt$ simulator $\Sim$ which can generate a view of $\adv$ which is indistinguishable from the real execution of the protocol given there is a secure MPC for multiplication which withstand against the corrupt parties in $I$. \pnote{(Maybe a broadcast required)}
\end{lemma}

\begin{proof}
To prove the above theorem we will design a simulator $\Sim$ which has access to the ideal functionality $\Func_{\DPZK}$ (~\ref{func:DPZK}). Provers in $I$ encode and commit to their inputs and $\Sim$ gets $\shr{\comoracle}, \shr{\comoracle}_a$ $\forall a\in\{x,y,z\}$ and $\forall \xi \in I$. Since the provers are giving ZKAoK in addition to the commitment, by the extractor of argument of knowledge, $\Sim$ extracts and gets shares of $\wit, \wit_x,\wit_y,\wit_z$ of the parties in $I$. 
%Now $\Sim$ checks if all the steps of Linear and Quadratic checks are done using the same inputs extracted by $\Sim$. If yes, then $\Sim$ calls the functionality $\Func_{\DPZK}$ if it outputs 1, then $\Sim$ uses the same approach of  
%$\Sim$ picks random challenges for both linear and quadratic checks on behalf of the verifier (picking random challenges on behalf of the verifier is fine since the verifier is semi-honest). 
Then $\Sim$ uses the simulator for \name and gets an accepting transcript. Using that computes $\shr{\comoracle}, \shr{\comoracle}_a$ $\forall \xi\notin I$, using homomorphic property of the commitment scheme.
$\Sim$ gets $\shr{c_0}, \shr{c_1}, \ldots, \shr{c_{s+\ell}}$ and $\shr{Z}$ for all $\xi\in I$ in the linear check, as all the provers are sending this values to $\Ag$, which is done using broadcast. Using extraction of commitment $\Sim$ gets the decommitted values. If there is some inconsistency in the values extracted from $\shr{\comoracle}, \shr{\comoracle}_a$ $\forall a\in\{x,y,z\}$ and $\forall \xi \in I$ and these decommitted values then
%output $\abort$, else continue.
sets $\mathsf{state}$ as fail, otherwise pass.
For quadratic check, $\Sim$ calls the simulator, $\Sim_M$, of the secure multiplication protocol and extracts the input of the MPC, and does the consistency check, as in the linear case. If there is some inconsistency then 
%output $\abort$, else continue.
sets $\mathsf{state}$ as fail, otherwise, pass.
Similarly, $\mathsf{state}$ is set for the remaining part of the protocol.
(This part is informally stated here, details will be provided in the full version.)
Now for both the protocols if $\mathsf{state}$ remains pass till the provers send the final messages to $\Ag$, which are the witnesses of the inner product arguments, 
\pnote{Should we add the details such as what are the consistency checks? From the protocol that is quite evident.}
then $\Sim$ calls the functionality $\Func_{\DPZK}$ with the input $\wit, x,y,z$ of the parties in $I$. If it outputs 1, then $\Sim$ generates the final messages of the honest parties using the accepting transcript produced by the zero-knowledge simulator, else $\Sim$ picks any random message which is consistent with the transcript so far.

If there is some inconsistency in some intermediate step, i.e., the $\mathsf{state}$ is fail, then $\Sim$ calls the functionality $\Func_{\DPZK}$ on some random value and proceeds accordingly with the simulation.

This proves that the view of the corrupt provers can be simulated, which ensures privacy of the honest provers.
\end{proof}

%\end{enumerate}
\end{comment}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{$\DPZK$ of Bulletproof for R1CS}\label{app:BulletproofsDPZK}
In \cite{InnerProductDLS}, \cite{bulletproofs}, authors present a proof for a Hadamard-product relation. Suppose $\C$ is a circuit of size $N$. In their formulation,  $\bm{a}_L$, $\bm{a}_R$ and $\bm{a}_O$ denote the vectors corresponding to the left wire, right wire and output wire respectively. Then, $\bm{a}_L \circ \bm{a}_R = \bm{a}_O$ holds and satisfy the following linear constraints: 
%$\innp{\bm{w}_{L,q}}{\bm{a}_L} + \innp{\bm{w}_{R,q}}{\bm{a}_R} + \innp{\bm{w}_{O,q}}{\bm{a}_O} = c_q$ where $1\leq q \leq Q \leq 2n$ with .
%for a multiplication $g$ gate in a circuit $\C$ has $\bm{a}_L$, $\bm{a}_R$ and $\bm{a}_O$ as left input, right input and output wire values respectively, then $\bm{a}_L \circ \bm{a}_R = \bm{a}_O$ holds. Other than this, these vectors are supposed to satisfy additional $Q\leq 2n$ linear constraints, which is of the following form:
$$\innp{\bm{w}_{L,q}}{\bm{a}_L} + \innp{\bm{w}_{R,q}}{\bm{a}_R} + \innp{\bm{w}_{O,q}}{\bm{a}_O} = c_q \, \forall q\in [Q]$$
with $\bm{w}_{L,q}, \bm{w}_{R,q}, \bm{w}_{O,q} \in \ZZ^N_p$ and $c_q \in \ZZ_p$.
Consider
$W_A = [\bm{w}_{A,1}, \ldots, \bm{w}_{A,Q}]^T$, for $A\in \{L,R,O\}$ %\vspace{10pt} 
%$W_R = [\bm{w}_{R,1}, \ldots, \bm{w}_{R,Q}]^T$, %\vspace{10pt} 
%$W_O = [\bm{w}_{O,1}, \ldots, \bm{w}_{O,Q}]^T$,%\vspace{10pt} 
and $\bm{c} = [c_1, \ldots, c_q]^T$
%\pnote{what is $W_v$ and $\bm{v}$ is not clear.}

\noindent In \cite{bulletproofs}, these above checks are reduced to a single inner product argument. $\prover$ commits to the input vectors $\bm{a}_L, \bm{a}_R$, output vector $\bm{a}_O$ and sends the commitment values $A_I$ and $A_O$ to $\verifier$. $\prover$ picks $s_L$ and $s_R$ uniformly at random and computes the commitment $S$ and sends to $\verifier$.
$\verifier$ gives random challenges $y, z$ from $\ZZ^\ast_p$ to the prover.
Then $\prover$ computes vector polynomials $l(X)$ and $r(X)$ using $\bm{a}_L, \bm{a}_R, \bm{a}_O, s_L, s_R, y, z$ and other public vectors, and computes a polynomial $t(X) = \innp{l(X)}{r(X)}$. The construction of $l(X)$ and $r(X)$ is such that the co-efficient of $X^2$ in $t(X)$ is independent of $\bm{a}_L, \bm{a}_R, \bm{a}_O, s_L, s_R$, which can be computed by $\verifier$, if $\bm{a}_L, \bm{a}_R, \bm{a}_O$ satisfy the Hadamard-product relation and linear constraints. To prove this, $\prover$ commits to all the co-efficients of $t(X)$ other than the co-efficient of $X^2$, and verifier gives a random point $x$ to evaluate $\bm{l} = l(x)$ and $\bm{r} = r(x)$. Which reduces to an inner product check whose witness is $\bm{l}$ and $\bm{r}$, where $\bm{l}$ and $\bm{r}$ are vectors of length $N$. 
\smallskip

 We give a $\DPZK$ version of Bulletproofs, where $\distprover$ starts the protocol with $\shr{\bm{a}_L}, \shr{\bm{a}_R}, \shr{\bm{a}_O}$ $\forall \xi \in [\Num]$ such that $\sum_{\xi\in [\Num]} \shr{\bm{a}_A} = \bm{a}_A$ $\forall A\in \{L,R,O\} $. $\Ag$ is an aggregator.
$\distprover$ computes the commitment $\shr{A_I}, \shr{A_O}, \shr{S}$ and sends these values to $\Ag$. $\Ag$ combines and sends $A_I$, $A_O$ and $S$ to $\verifier$.
The verifier broadcasts the random challenge $y,z \sample \ZZ^\ast_p$.
Then each prover computes $\shr{l}(X)$ and $\shr{r}(X)$.
All the provers interact securely to compute shares of $t(x) = \innp{l(X)}{r(X)}$, where $l(X)= \sum_{\xi\in [\Num]} \shr{l}(X)$ and $r(X) = \sum_{\xi\in [\Num]} \shr{r}(X)$, i.e., output for $\distprover$ is $\shr{t}(X)$ such that $\sum_{\xi\in [\Num]} \shr{t}(X) = t(X)$.
$\distprover$ commits to all the coefficients of $\shr{t}(X)$ other than the coefficient of $X^2$. Sends these committed values to $\Ag$. $\Ag$ combines and sends them to $\verifier$.
$\verifier$ sends a random $x$. $\distprover$ evaluates $\shr{l}(x) = \shr{\bm{l}}$ and $\shr{r}(x) = \shr{\bm{r}}$ and sends these values to $\Ag$. $\Ag$ computes $\bm{l} = \sum_{\xi\in [\Num]} \shr{\bm{l}}$ and $\bm{r} = \sum_{\xi\in [\Num]} \shr{\bm{r}}$.
Finally, $\Ag$ and $\verifier$ run the inner product protocol, same as the single prover protocol, where the witness is $\bm{l}$ and $\bm{r}$.
Since, $\bm{l}$ and $\bm{r}$ afre vectors of length $N$, MPC is required for $N$ multiplications or in other words, a MPC for a depth 1 circuit of size $N$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{$\DPZK$ of Spartan for R1CS}\label{app:SpartanDPZK}
We will describe the distributed version of the interactive proof given in Spartan \cite{spartan}. We do not have a proof of privacy of the distributed version of the protocol.

Let $\C$ be an R1CS circuit of size $N$. For every R1CS circuit $\exists$ matrices $A,\;B,\;C$ and public input $io$ which defines the circuit. If the instance is true, then $\exists$ a witness $\wit\in\FF^N$ such that $A z \circ B z = C z$ where $z = (io,1,\wit)$ is the extended witness of $\C$.

Now, the prover wants to convince the verifier that the prover knows $z$ such that $A z \circ B z =C z$ holds. To that the prover defines a polynomial 
\begin{align*}
\tilde{F}_{io}(x)=\left(\sum_{y\in\{0,1\}^s}\tilde{A}(x,y)\tilde{Z}(y)\right)\left(\sum_{y\in\{0,1\}^s}\tilde{B}(x,y)\tilde{Z}(y)\right)-\\ \left(\sum_{y\in\{0,1\}^s}\tilde{C}(x,y)\tilde{Z}(y)\right)
\end{align*}
Where $\tilde{A}(x,y) = A(x,y)\;\forall  x,y$. $A(\cdot, \cdot)$ is defined as a function such that $A(x,y)$ is the $(x,y)th$ entry of the matrix $A$. Similarly, $B(\cdot, \cdot)$ and $C(\cdot, \cdot)$. And $\tilde{A},\;\tilde{B},\;\tilde{C}$ are the low-degree polynomial extensions of $A, B, C$ respectively, defined in Spartan\cite{spartan}. And $\tilde{Z}(y) = Z(y)\;\forall  x$. $Z(\cdot)$ is defined as a function such that $Z(y)$ is the $yth$ entry of the vector $z$, and $\tilde{Z}$ is the low-degree polynomial extensions of $Z$, defined in Spartan\cite{spartan}.
If $Az\circ Bz =Cz$ holds then $\tilde{F}_{io}(x)=0\;\forall x\in\{0,1\}^s$. That means the verifier needs to check for all $x\in\{0,1\}^s$ $\tilde{F}_{io}(x)=0$. To get rid of such check a new polynomial $Q_{io}(t) = \sum_{x\in\{0,1\}^s}\tilde{F}_{io}(x) \cdot eq(t,x)$ where $eq(t,x) = \prod_{i\in[s]}[t_i\cdot x_i+(1-t_i)(1-x_i)]$. Note that if $\tilde{F}_{io}(x)=0\;\forall x\in\{0,1\}^s$ then $Q_{io}$ is a zero polynomial i.e. $Q_{io}(\tau)=0$ for any random $\tau$. 

Define $\calG_{io,\tau}(x)=\tilde{F}_{io}(x)\cdot eq(\tau,x)$. Then $\sum_{x\in\{0,1\}^s} \calG_{io,\tau}(x) = Q_{io}(\tau)$. Therefore, it is enough to check that $\sum_{x\in\{0,1\}^s} \calG_{io,\tau}(x) = 0$. This check is done using the sum-check protocol described in Spartan \cite{spartan}.


 In the $\DPZK$ version of Spartan \cite{spartan} each prover holds a share of the witness $\wit$, say $\distprover$ has $\shr{\wit}$. In other words, $Z$ is distributedly shared among the provers. So, in the above protocol described in Spartan \cite{spartan} only $\calG_{io,\tau}$ generation is required interaction among the provers. Remaining all the messages can be generated by each prover locally and an aggregator can combine the messages to obtain corresponding message. Note that, $\calG_{io,\tau}(x)$ computation requires $O(n^2)$ multiplications which are shared across the provers.  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{comment}
\begin{figure}[h!]
\centering
\begin{framed}
\small
\begin{itemize}
\item {$\linearcheck(\FF,\GG,L_1,L_2,A\in \FF^{M\times N},b\in \FF^M,[\pi];\ewit)$}:
\pnote{Why $A$ is not a square matrix?}
\item {\bf Relation}: $\exists \ewit$ s.t. $\ewit=\open(\pi)$ and $A\wit = b$
for $\wit=\dec(\ewit)$.
\item {\bf Oracle Setup}: The prover $\prover$ computes
$\comoracle = \comm(\ewit)$ as in Section \ref{sec:construct_oracle}. 
The prover sets $\pi := \comoracle$ as the oracle.
\begin{enumerate}[{\rm 1.}]
\item $\verifier\rightarrow\prover$: $\verifier$ samples $r\sample \FF^N$ and
sends it to $\prover$.
\pnote{ dimension of $r$ is not correct}
\item $\prover\longleftrightarrow\verifier$: Both $\prover$ and $\verifier$
compute polynomials $R^i$, $i\in [p]$ such that
$R^i(\alpha_j,\zeta_k)=R[i,j,k]$, where $R=r^TA$. 
%\pnote{Polynomial $R^i(\cdot, \cdot)$ should not be constructed from $r$, it should be from $r^TA$}
\item $\prover$ computes:
	\begin{enumerate}
	\item Polynomials $p_j(\cdot) := \sum_{i\in
[p]}R^i(\alpha_j,\cdot).Q^i(\alpha,\cdot)$ for $j\in [h]$.
	\item An $h\times n$ matrix $P$ such that $P[j,k]=p_j(\eta_k)$.
	\item Commitments $c_k=\comm(P[\cdot,k],\omega_k)$ for $k\in [s+\ell]$
where $\omega_k\sample \FF$.
	\item Sample a codeword $P_0\in \dashL_2$ s.t $\sum_{j\in [m]}P_0[j]=0$.
Compute $c_0=\comm(P_0,\omega_0)$ for $\omega_0\sample \FF$.
	\end{enumerate}
\item $\prover\rightarrow\verifier$: The prover sends $c_0,c_1,\ldots,c_{s+\ell}$ to
the verifier.
\item $\verifier\rightarrow\prover$: $\verifier$ samples $(j_u,k_u)\sample [h]\times
[n]$ for $u\in [t]$. It also samples $\beta\sample\FF$. The verifier sends
$Q=\{(j_u,k_u):u\in [t]\}$ and $\beta$ to $\prover$.
\item $\prover\rightarrow\verifier$: The prover sends vectors
$X_u=\ewit[\cdot,j_u,k_u]$ for $u\in [t]$ to $\verifier$.
\item Oracle Queries: $\verifier$ queries the oracle $\pi$ with $\{k_u:u\in
[t]\}$. 
\item Oracle Answers: The oracle replies with columns $\pi[\cdot,k_u]$, $u\in
[t]$.
\item $\prover\longleftrightarrow\verifier$: Both $\prover$ and $\verifier$
compute $\varphi := \Phi^T[1^s]$ and $\mathsf{cm} := \beta c_0 + \sum_{k\in
[s+\ell]}\varphi_kc_k$.
\item $\prover$ and $\verifier$ run the subprotocol:
	\begin{itemize}
	\item $b_{\rm 2d} = \proximityTwoD(\FF,\GG,\dashL_1,\dashL_2,\bm{c};\overline{P})$
where $\bm{c}=(c_1,\ldots,c_{s+\ell})$ and $\overline{P}$ is the submatrix of $P$
consisting of the first $s+\ell$ columns. Here $\dashL_1=\rsc{\eta}{s+\ell}$ and
$\dashL_2=\rsc{\alpha}{2m}$.
	\end{itemize}
\item $\prover$ and $\verifier$ run the subprotocol:
	\begin{itemize}
	\item $b = \innerproduct(\GG,\bm{g},x,\mathsf{cm},v;z)$
with $x=(1^m,0^{h-m})$, $v=r^Tb$ and $z=\beta P_0+\overline{P}\varphi$.
	\end{itemize}
\item $\prover$ and $\verifier$ compute: For all $u\in [t]$ $c_{k_u} =
\sum_{a\in 2\ell}T[a,k_u]c_a$, where $T$ is the matrix such that $P=\overline{P}T$.
\item $\prover$ and $\verifier$ run inner product subprotocols for each $u\in
[t]$:
	\begin{itemize}
	\item $s_u=\innerproduct(\GG,\bm{g},x,c_{k_u},v;P[\cdot,k_u])$ with
$x=e_{j_u}$, $v=\sum_{i\in [p]}R^i(\alpha_{j_u},\eta_{k_u})X_u$.
	\end{itemize}
\item $\prover$ and $\verifier$ run aggregate inner product protocols for each
$u\in [t]$:
	\begin{itemize}
	\item
$a_u=\agginnerproduct(\GG,\bm{g},e_{j_u},\pi[\cdot,k_u],X_u;\ewit[\cdot,\cdot,k_u])$
	\end{itemize}
\item $\prover$ and $\verifier$ run the subprotocol: 
	\begin{itemize}
	\item $b_{\rm prox} = \proximityThreeD(\FF,\GG,L_1,L_2,[\pi];U)$
	\end{itemize}
\item The verifier accepts if all the subprotocols accept.
\end{enumerate}
\end{itemize}

\begin{itemize}
\item $\agginnerproduct(\FF,\GG,\bm{g},x,\bm{c}\in \GG^n,\bm{v}\in \FF^n;W\in
\FF^{m\times n})$:
\item {\bf Relation}: $\forall i\in [n]$: $W[i,\cdot]=\open(\bm{c}[i])$,
$\innp{x}{W[i,\cdot]}=v[i]$. 
\begin{enumerate}
\item $\verifier\rightarrow\prover$: Verifier samples $\delta\in \FF^n$ and
sends it to the prover.
\item $\prover\leftrightarrow\verifier$ compute: $\mathsf{cm}=\sum_{i\in
[n]}\delta_i\bm{c}[i]$, $V=\sum_{i\in [n]}\delta_i\bm{v}[i]$
\item $\prover$ and $\verifier$ run the subprotocol:
	\begin{itemize}
	\item $b=\innerproduct(\FF,\GG,\bm{g},\delta,\mathsf{cm},V;\bm{v}^TW)$
	\end{itemize}
\item $\verifier$ accepts if $b=1$.
\end{enumerate}
\end{itemize}

\end{framed}
\caption{Linear Check Protocol}
%\label{fig:linearcheck}
\end{figure}


\begin{figure}[h!]
\centering
\begin{framed}
\small
\begin{itemize}
\item $\quadcheck(\FF,\GG,L_1,L_2,[\pi];\wit_x,\wit_y,\wit_z)$:
\item {\bf Relation}: $\exists (\ewit_x,\ewit_y,\ewit_z)$
s.t. $[\ewit_x||\ewit_y||\ewit_z]=\open(\pi)$, $\wit_{a}=\dec(\ewit_a)$ for $a\in
\{x,y,z\}$ and $\wit_x\circ \wit_y = \wit_z$.
\item {\bf Oracle Setup}: The prover $\prover$ computes $\comoracle_a=\comm(\ewit_a)$ 
for $a\in \{x,y,z\}$. It sets $\pi :=
[\comoracle_x||\comoracle_y||\comoracle_z]$ where the notation denotes vertical
stacking of the matrices. 
\begin{enumerate}[{\rm 1.}]
\item $\verifier\rightarrow\prover$: Verifier samples $r\sample\FF^p$ and sends
it to $\prover$.
\item $\prover$ computes:
	\begin{itemize}
	\item polynomials $p_j(\cdot):=\sum_{i\in
[p]}r_i\big(Q^i_x(\alpha_j,\cdot)Q^i_y(\alpha_j,\cdot)-Q^i_z(\alpha_j,\cdot)\big)$
for $j\in [h]$.
	\item $h\times n$ matrix $P$ such that $P[j,k]=p_j(\eta_k)$.
	\item commitments $c_1,\ldots,c_{2\ell}$ to the first $2\ell$ columns of
$P$.
	\end{itemize}
\item $\prover\rightarrow\verifier$: The prover sends $c_1,\ldots,c_{2\ell}$ to
the verifier.
\item $\verifier\rightarrow\prover$: $\verifier$ samples $(j_u,k_u)\sample
[h]\times [n]$ for $u\in [t]$. The verifier also samples $\tau\sample
\FF^{\ell}$. It sends $Q=\{(j_u,k_u):u\in [t]\}$ and $\tau$ to $\prover$.
\item $\prover\rightarrow\verifier$: The prover sends vectors
$X_u=\ewit_x[\cdot,j_u,k_u],Y_u=\ewit_y[\cdot,j_u,k_u],Z_u=\ewit_z[\cdot,j_u,k_u]$
to the verifier, for all $u\in [t]$.
\item Oracle Queries: $\verifier$ queries the oracle $\pi$ with $\{k_u: u\in
[t]\}$.
\item Oracle Response: The oracle responds with columns $\pi[\cdot,k_u]$ for
$u\in [t]$.
\item $\prover\leftrightarrow\verifier$: Both $\prover$ and $\verifier$ compute
$\varphi := \Phi^T\tau$ and $\mathsf{cm}:= \sum_{k\in [2\ell]}\phi_kc_k$.
\item $\prover$ and $\verifier$ run the subprotocol:
	\begin{itemize}
	\item $b_{\rm
2d}=\proximityTwoD(\FF,\GG,\dashL_1,\dashL_2,\bm{c};\overline{P})$ where
$\bm{c}=(c_1,\ldots,c_{2\ell})$ and $\overline{P}$ is the submatrix of $P$ consisting
of the first $2\ell$ columns. Here $\dashL_1=\rsc{\eta}{2\ell}$ and
$\dashL_2=\rsc{\alpha}{2m}$.
	\end{itemize}
\item $\prover$ and $\verifier$ run the subprotocol:
	\begin{itemize}
	\item $b=\innerproduct(\FF,\GG,\bm{g},x,\mathsf{cm},v;z)$
with $x=(\gamma,0^{h-m})$, $v=0$ and $z=\overline{P}\varphi$.
	\end{itemize}
\item $\prover$ and $\verifier$ compute: For all $u\in [t]$ $c_{k_u} =
\sum_{a\in 2\ell}T[a,k_u]c_a$, where $T$ is the matrix such that $P=\overline{P}T$.
\item $\prover$ and $\verifier$ run inner product subprotocols for each $u\in
[t]$:
	\begin{itemize}
	\item $s_u=\innerproduct(\GG,\bm{g},x,c_{k_u},v;P[\cdot,k_u])$ with
$x=e_{j_u}$, $v=\sum_{i\in [p]}r_i(X_u[i]\cdot Y_u[i] - Z_u[i])$.
	\end{itemize}
\item $\prover$ and $\verifier$ run aggregate inner product protocols for each
$u\in [t]$:
	\begin{itemize}
	\item
$a_{1u}=\agginnerproduct(\GG,\bm{g},e_{j_u},\pi_x[\cdot,k_u],X_u;\ewit_x[\cdot,\cdot,k_u])$
	\item
$a_{2u}=\agginnerproduct(\GG,\bm{g},e_{j_u},\pi_y[\cdot,k_u],Y_u;\ewit_y[\cdot,\cdot,k_u])$
	\item
$a_{3u}=\agginnerproduct(\GG,\bm{g},e_{j_u},\pi_z[\cdot,k_u],Z_u;\ewit_z[\cdot,\cdot,k_u])$
	\end{itemize}
\item $\prover$ and $\verifier$ run the subprotocol: 
	\begin{itemize}
	\item $b_{\rm prox} =
\proximityThreeD(\FF,L_1,L_2,e,[\pi];[\ewit_x||\ewit_y||\ewit_z])$
	\end{itemize}
\item The verifier accepts if all the subprotocols accept.
\end{enumerate}
\end{itemize}
\end{framed}
\caption{Quadratic Check Protocol}
\label{fig:quadcheck}
\end{figure}
\end{comment} 

\begin{comment}
\begin{figure}[h!]
\centering
\begin{framed}
\footnotesize
\begin{itemize}
\item {$\distlinearcheck(\FF,\GG,L_1,L_2,A\in \FF^{M\times N},b\in
\FF^M,[\pi];\shr{\ewit},\shr{0^h})$}
\item {\bf Relation}: $\exists \ewit$ s.t. $\ewit=\open(\pi)$ and $A\wit = b$
for $\wit=\dec(\ewit)$.
\item {\bf Oracle Setup}: 
	\begin{itemize}
	\item $\distprover\rightarrow\Ag$: The prover $\distprover$ computes
$\shr{\comoracle} = \comm(\shr{\ewit})$ as in Section
\ref{sec:construct_oracle}. It sends $\shr{\comoracle}$ to $\Ag$. 
	\item {\color{red} $\Ag$ computes: $\comoracle := \combine(\shr{\comoracle})$ and
sets $\pi := \comoracle$}.
	\end{itemize}
\begin{enumerate}[{\rm 1.}]
\item $\verifier\rightarrow\distprover$: $\verifier$ samples $r\sample \FF^N$ and
sends it to $\distprover$.
\item $\distprover\leftrightarrow\verifier$: Provers ($\distprover$) and $\verifier$
compute polynomials $R^i$, $i\in [p]$ such that
$R^i(\alpha_j,\zeta_k)=R[i,j,k]$ where $R=r^TA$. 
\item $\distprover$ computes:
	\begin{enumerate}
	\item Polynomials $\shr{p_j}(\cdot) := \sum_{i\in
[p]}R^i(\alpha_j,\cdot).\shr{Q^i}(\alpha,\cdot)$ for $j\in [h]$. Here the
polynomial $\shr{Q^i}$ interpolates the witness share
$\shr{\wit}[i,\cdot,\cdot]$ on $G$.
	\item An $h\times n$ matrix $\shr{P}$ such that $\shr{P}[j,k]=\shr{p_j}(\eta_k)$.
	\item Commitments $\shr{c_k}=\comm(\shr{P}[\cdot,k],\shr{\omega}_k)$ for $k\in [s+\ell]$
where $\shr{\omega}_k\sample \FF$.
	\item Sample a codeword $\shr{P_0}\in \dashL_2$ s.t $\sum_{j\in
[m]}\shr{P_0}[j]=0$.
Compute $\shr{c_0}=\comm(\shr{P_0},\shr{\omega_0})$ for $\shr{\omega_0}\sample \FF$.
	\end{enumerate}
\item $\distprover\rightarrow\Ag$: Provers send
$\shr{c_0},\shr{c_1},\ldots,\shr{c_{s+\ell}}$ and $\shr{Z}$ to $\Ag$.

% Aggregation step
\item {\color{red} $\Ag$ computes: $(c_0,c_1,\ldots,c_{s+\ell}) :=
\combine(\shr{c_0},\shr{c_1},\ldots,\shr{c_{s+\ell}})$ and $Z :=
\combine(\shr{Z})$}.

\item $\verifier\rightarrow\distprover$: $\verifier$ samples $(j_u,k_u)\sample [h]\times
[n]$ for $u\in [t]$. It also samples $\beta\sample\FF$. The verifier sends
$Q=\{(j_u,k_u):u\in [t]\}$ and $\beta$ to provers $\distprover$.
\item $\distprover$ computes:
	\begin{itemize}
	\item $\shr{X_u}=\shr{\ewit}[\cdot,j_u,k_u]$ for $u\in [t]$.
	\item $\shr{Y_u}=\shr{P}[\cdot,k_u]$ for $u\in [t]$.
	\item $\shr{Z}=\beta\shr{P_0} + \shr{\overline{P}}\varphi + \shr{0^h}$ for $\varphi=\Phi^T[1^s]$.
	\item $\shr{\omega}=\beta\shr{\omega_0} +
\sum_{a=1}^{s+\ell}\varphi_a\shr{\omega_a}$.
	\item $\shr{\omega_{k_u}}=\sum_{a\in [s+\ell]}T[a,k_u]\shr{\omega_a}$
for $u\in [t]$.
	\end{itemize}
\item $\distprover\rightarrow\Ag$: Prover $\distprover$ sends $\shr{X_u}$,
$\shr{Y_u}$, $\shr{\omega_{k_u}}$ for $u\in [t]$, $\shr{Z}$ and $\shr{\omega}$ to $\Ag$.


% Aggregation step
\item {\color{red} $\Ag$ computes: $X_u=\combine(\shr{X_u})$,
$P[\cdot,k_u]=\combine(\shr{Y_u})$ for $u\in [t]$. It computes
$Z=\combine(\shr{Z})$ and $\omega=\combine(\shr{\omega})$ and 
$\omega_{k_u}=\combine(\shr{\omega_{k_u}})$ for $u\in [t]$}.
  
\item Oracle Queries: $\verifier$ queries the oracle $\pi$ with $\{k_u:u\in
[t]\}$. 
\item Oracle Answers: The oracle replies with columns $\pi[\cdot,k_u]$, $u\in
[t]$.
\item $\Ag\leftrightarrow\verifier$: Both $\Ag$ and $\verifier$
compute $\varphi := \Phi^T[1^s]$ and $\mathsf{cm} := \beta c_0 + \sum_{k\in
[s+\ell]}\varphi_kc_k$.
\item $\Ag$ and $\verifier$ run the subprotocol:
	\begin{itemize}
	\item $b_{\rm 2d} =
\distproxTwoD(\FF,\GG,s+\ell,\dashL_1,\dashL_2,\bm{c};[[\overline{P}]],[[\bm{\omega}]])$
where $\bm{c}=(c_1,\ldots,c_{s+\ell})$ and $\overline{P}$ is the submatrix of $P$
consisting of the first $s+\ell$ columns. Here $\dashL_1=\rsc{\eta}{s+\ell}$ and
$\dashL_2=\rsc{\alpha}{2m}$.
	\end{itemize}
\item $\Ag$ and $\verifier$ run the subprotocol:
	\begin{itemize}
	\item $b = \innerproduct(\GG,\bm{g},x,\mathsf{cm},v;z,\omega)$
with $x=(1^m,0^{h-m})$, $v=r^Tb$ and $z=Z$.
	\end{itemize}
\item $\Ag$ and $\verifier$ compute: For all $u\in [t]$ $c_{k_u} =
\sum_{a\in 2\ell}T[a,k_u]c_a$, where $T$ is the matrix such that $P=\overline{P}T$.
\item $\Ag$ and $\verifier$ run inner product subprotocols for each $u\in
[t]$:
	\begin{itemize}
	\item
$s_u=\innerproduct(\GG,\bm{g},x,c_{k_u},v;P[\cdot,k_u],\omega_{k_u})$ with
$x=e_{j_u}$, $v=\sum_{i\in [p]}R^i(\alpha_{j_u},\eta_{k_u})X_u$.
	\end{itemize}
\item $\Ag$ and $\verifier$ run aggregate inner product protocols for each
$u\in [t]$:
	\begin{itemize}
	\item
$a_u=\agginnerproduct(\GG,\bm{g},e_{j_u},\pi[\cdot,k_u],X_u;\ewit[\cdot,\cdot,k_u])$
	\end{itemize}
\item $\prover$ and $\verifier$ run the subprotocol: 
	\begin{itemize}
	\item $b_{\rm prox} =
\distproxThreeD(\FF,\GG,L_1,L_2,[\pi];[[\ewit]])$
	\end{itemize}
\item The verifier accepts if all the subprotocols accept.
\end{enumerate}
\end{itemize}
\end{framed}
\caption{Distributed Linear Check Protocol}
\label{fig:distlincheck}
\end{figure}


\begin{figure}[h!]
\centering
\begin{framed}
\small
\begin{itemize}
\item $\distquadcheck(\FF,\GG,L_1,L_2,[\pi];[[\wit_x]],[[\wit_y]],[[\wit_z]])$:
\item {\bf Relation}: $\exists (\ewit_x,\ewit_y,\ewit_z)$
s.t. $[\ewit_x||\ewit_y||\ewit_z]=\open(\pi)$, $\wit_{a}=\dec(\ewit_a)$ for $a\in
\{x,y,z\}$ and $\wit_x\circ \wit_y = \wit_z$.
\item {\bf Oracle Setup}: 
\begin{itemize}
\item $\distprover\rightarrow\Ag$: $\distprover$ computes $\shr{\comoracle_a}=\comm(\shr{\ewit_a})$ 
for $a\in \{x,y,z\}$. It sends $\shr{\comoracle_a}$, $a\in \{x,y,z\}$ to $\Ag$.
\item $\Ag$ computes: $\comoracle_a=\combine(\shr{\comoracle_a})$ for $a\in
\{x,y,z\}$ and sets $\pi := [\comoracle_x||\comoracle_y||\comoracle_z]$.
\end{itemize}
\begin{enumerate}[{\rm 1.}]
\item $\verifier\rightarrow\distprover$: Verifier samples $r\sample\FF^p$ and sends
it to $\distprover$.
\item Provers $\distprover$ run the MPC: $\shr{\ewit_x.\ewit_y}\leftarrow
\mathsf{Mult}(\shr{\ewit_x},\shr{\ewit_y})$ to obtain shares of the hadamard
product of the encodings.
\item $\prover$ computes:
	\begin{itemize}
	\item $h\times n$ matrix $\shr{P}$ such that 
	$\shr{P}[j,k]=\sum_{i\in
[p]}r_i(\shr{\ewit_x[i,j,k]\ewit_y[i,j,k]}-\shr{\ewit_z[i,j,k]})$.
	\item commitments $\shr{c_k}=\comm(\shr{P}[\cdot,k],\shr{\omega_k})$ for
$k\in [2\ell]$ where $\shr{\omega_k}$ are sampled randomly for all $k\in
[2\ell]$.
	\end{itemize}
\item $\distprover\rightarrow\Ag$: The prover $\distprover$ sends
$\shr{c_1},\ldots,\shr{c_{2\ell}}$ to $\Ag$.
\item $\Ag\rightarrow \verifier$: $\Ag$ computes $\bm{c}=(c_1,\ldots,c_{2\ell})$ where
$c_k=\combine(\shr{c_k})$ for $k\in [2\ell]$. It sends $\bm{c}$ to $\verifier$.

\item $\verifier\rightarrow\distprover$: $\verifier$ samples $(j_u,k_u)\sample
[h]\times [n]$ for $u\in [t]$. The verifier also samples $\tau\sample
\FF^{\ell}$. It sends $Q=\{(j_u,k_u):u\in [t]\}$ and $\tau$ to $\distprover$.
\item $\distprover$ computes:
	\begin{itemize}
	\item $\shr{X_u}=\shr{\ewit_x}[\cdot,j_u,k_u]$, $u\in [t]$.
	\item $\shr{Y_u}=\shr{\ewit_y}[\cdot,j_u,k_u]$, $u\in [t]$.
	\item $\shr{Z_u}=\shr{\ewit_z}[\cdot,j_u,k_u]$, $u\in [t]$.
	\item $\shr{\omega}=\sum_{a\in 2\ell}\varphi_a\shr{\omega_a}$.
	\item $\shr{\omega_{k_u}}=\sum_{a\in 2\ell}T[a,k_u]\shr{\omega_a}$,
$u\in [t]$.
	\end{itemize}
\item $\distprover\rightarrow\Ag$: The prover $\distprover$ sends
$\shr{X_u},\shr{Y_u},\shr{Z_u}$, $\shr{\omega_{k_u}}$ for $u\in [t]$ and
$\shr{\omega}$ to $\Ag$.
\item $\Ag$ computes: $\Ag$ obtains $X_u,Y_u,Z_u,\omega_{k_u}$ for $u\in [t]$
from the respective shares. It also obtains $\omega$ from its shares. 
\item Oracle Queries: $\verifier$ queries the oracle $\pi$ with $\{k_u: u\in
[t]\}$.
\item Oracle Response: The oracle responds with columns $\pi[\cdot,k_u]$ for
$u\in [t]$.
\item $\Ag\leftrightarrow\verifier$: Both $\Ag$ and $\verifier$ compute
$\varphi := \Phi^T\tau$ and $\mathsf{cm}:= \sum_{k\in [2\ell]}\phi_kc_k$.
\item $\Ag$ and $\verifier$ run the subprotocol:
	\begin{itemize}
	\item $b_{\rm
2d}=\distproxTwoD(\FF,\GG,\dashL_1,\dashL_2,\bm{c};[[\overline{P}]],[[\bm{\omega}]])$ where
$\bm{c}=(c_1,\ldots,c_{2\ell})$ and $\overline{P}$ is the submatrix of $P$ consisting
of the first $2\ell$ columns. Here $\dashL_1=\rsc{\eta}{2\ell}$ and
$\dashL_2=\rsc{\alpha}{2m}$.
	\end{itemize}
\item $\Ag$ and $\verifier$ run the subprotocol:
	\begin{itemize}
	\item $b=\innerproduct(\FF,\GG,\bm{g},x,\mathsf{cm},v;z,\omega)$
with $x=(\gamma,0^{h-m})$, $v=0$ and $z=\overline{P}\varphi$. Note that $z$ is
the unique codeword in $\dashL_2$ with $\sum_{j\in [m]}z[j]=0$ so $\Ag$ knows
this without receiving shares from the provers.
	\end{itemize}
\item $\Ag$ and $\verifier$ compute: For all $u\in [t]$ $c_{k_u} =
\sum_{a\in 2\ell}T[a,k_u]c_a$, where $T$ is the matrix such that $P=\overline{P}T$.
\item $\Ag$ and $\verifier$ run inner product subprotocols for each $u\in
[t]$:
	\begin{itemize}
	\item
$s_u=\innerproduct(\GG,\bm{g},x,c_{k_u},v;P[\cdot,k_u],\omega_{k_u})$ with
$x=e_{j_u}$, $v=\sum_{i\in [p]}r_i(X_u[i]\cdot Y_u[i] - Z_u[i])$.
	\end{itemize}
\item $\Ag$ and $\verifier$ run aggregate inner product protocols for each
$u\in [t]$:
	\begin{itemize}
	\item
$a_{1u}=\agginnerproduct(\GG,\bm{g},e_{j_u},\pi_x[\cdot,k_u],X_u;\ewit_x[\cdot,\cdot,k_u])$
	\item
$a_{2u}=\agginnerproduct(\GG,\bm{g},e_{j_u},\pi_y[\cdot,k_u],Y_u;\ewit_y[\cdot,\cdot,k_u])$
	\item
$a_{3u}=\agginnerproduct(\GG,\bm{g},e_{j_u},\pi_z[\cdot,k_u],Z_u;\ewit_z[\cdot,\cdot,k_u])$
	\end{itemize}
\item $\Ag$ and $\verifier$ run the subprotocol: 
	\begin{itemize}
	\item $b_{\rm prox} =
\distproxThreeD(\FF,L_1,L_2,e,[\pi];[\shr{\ewit_x||\ewit_y||\ewit_z}])$
	\end{itemize}
\item The verifier accepts if all the subprotocols accept.
\end{enumerate}
\end{itemize}
\end{framed}
\caption{Distributed Quadratic Check Protocol}
\label{fig:distquadcheck}
\end{figure}
\end{comment}
 
\section{Graphene for R1CS}\label{sec:graphener1cs}
We use the linear and quadratic check protocols from Section \ref{sec:graphene}
to describe an efficient protocol for rank one constraint system (R1CS). Let 
$A,B$ and $C$ be $M\times N$ matrices. We prove existence of $\wit\in \FF^N$
satisfying $A\wit\circ B\wit=C\wit$ by showing existence of
$\wit_x,\wit_y,\wit_z$ and $\wit\in \FF^N$ satisfying the linear relations $A\wit=\wit_x$,
$B\wit=\wit_y$ and $C\wit=\wit_z$ and a quadractic relation
$\wit_x\circ\wit_y=\wit_z$. We probabilistically reduce the three linear
relations to the linear relation:
\begin{align}\label{eq:comblincheck}
\begin{bmatrix}
\gamma_xI\,|\gamma_yI\,|\gamma_zI\,|-(\gamma_xA+\gamma_yB+\gamma_zC)
\end{bmatrix}\begin{bmatrix}
\wit_x\\
\wit_y\\
\wit_z\\
\wit
\end{bmatrix}=\bm{0}
\end{align}

for $\gamma_x,\gamma_y,\gamma_z\sample \FF$. As before, we
$\wit_x,\wit_y,\wit_z$ and $\wit$ as $p\times m\times s$ matrices. Let $\bwit$
denote the $4p\times m\times s$ matrix formed by stacking $\wit_x,\wit_y,\wit_z$
and $\wit$ along ``slices''. The encoding $\ewit\gets\enc(\bwit)$ and commitment to
the encoding $\comoracle\gets \comm(\ewit)$ are computed as in Sections
~\ref{sec:witencoding} and ~\ref{sec:construct_oracle}. Note that
$\comoracle$ is a $4p\times n$ matrix. 
We now present the high level protocol for R1CS instance $(A,B,C)$.\smallskip

\begin{figure}[h]
	{\footnotesize
		\begin{framed}
\noindent{$\grapheneRCS(\mathsf{pp},A,B,C,[\pi];\wit_x,\wit_y,\wit_z,\wit)$}:\\
\noindent{\bf Relation}: $A\wit\circ B\wit=C\wit$. \\
\noindent{\bf Oracle Setup}: Compute $\comoracle$ as described above. Set $\pi
:= \comoracle$.
\begin{enumerate}[{\rm 1.}]
\item $\verifier\rightarrow\prover$: $\gamma_x,\gamma_y,\gamma_z\sample \FF$,
$r_{lc}\sample \FF^M$, $r_{qd}\sample \FF^{p}$, $\rho\sample \FF^{4p}$.
\item $\prover\rightarrow\verifier$: $\prover$ computes $\tilde{\ewit}=\sum_{i\in
[4p]}\rho_i\ewit[i,\cdot,\cdot]$ and sends commitments
$\tilde{c}_1,\ldots,\tilde{c}_\ell$ to $\tilde{\ewit}$.
\item $\prover\leftrightarrow\verifier$ compute: $R=r_{lc}^TW$ for
$W=[\gamma_xI\,||\gamma_yI\,||\gamma_zI\,||-(\gamma_xA+\gamma_yB+\gamma_zC)]$,
 polynomials $R^i$,$i\in [4p]$ interpolating the slices of $R$ viewed as a
$4p\times m\times n$ matrix.
\item $\prover$ computes: 
\begin{itemize}
\item Polynomials $Q^i_x,Q^i_y,Q^i_z,Q^i$ for $i\in [p]$,
where polynomials $Q^i_a$, $i\in [p]$ correspond to $\wit_a$ for $a\in \{x,y,z\}$ and
polynomials $Q^i$,$i\in [p]$ correspond to $\wit$. 
\item $h\times n$ matrices $P_{lc}$ and $P_{qd}$ as ``P'' matrices for the linear check and
quadratic check respectively. Note that $p_j$ polynomial for $P_{lc}$ is given
by $p_j(\cdot)=\sum_{i=1}^p(R^i(\alpha_j,\cdot).Q_x^i(\alpha_j,\cdot)+
 R^{p+i}(\alpha_j,\cdot)Q^i_y(\alpha_j,\cdot)+R^{2p+i}(\alpha_j,\cdot)Q^i_z(\alpha_j,\cdot)+
R^{3p+i}(\alpha_j,\cdot)Q^i(\alpha_j,\cdot))$. The $p_j$ polynomials for the
matrix $P_{qd}$ are given by
$p_j(\cdot)=\sum_{i=1}^{p}r_{qd}[i](Q^i_x(\alpha_j,\cdot)Q^i_y(\alpha_j,\cdot)-Q^i_z(\alpha_j,\cdot))$.
\item Blinding vectors $U_{lc},U_{qd}\in \FF^{2m-1}$ for linear and quadratic check protocols
respectively, and commitments $c_0,d_0$ to vectors $U_{lc}$
and $U_{qd}$.
\end{itemize}
\item $\prover\rightarrow\verifier$: Commitments $c_0,c_1,\ldots,c_{s+\ell-1}$ for
the matrix $P_{lc}$ and commitments $d_0,d_1,\ldots,d_{2\ell-1}$ for matrix
$P_{qd}$. 
\item $\verifier\rightarrow\prover$: $Q=\{(j_u,k_u):u\in [t]\}$.
\item $\verifier\rightarrow\pi$: $\{k_u:u\in [t]\}$.
\item $\prover\rightarrow\verifier$: $S_u=\ewit[\cdot,j_u,k_u]$ for $u\in [t]$.
\item $\pi\rightarrow\verifier$: $\pi[\cdot,k_u]$, $u\in [t]$.
\item $\prover$ and $\verifier$ run the linear and quadratic check protocols in
parallel, parsing the vectors $S_u$ into $X_u,Y_u,Z_u,W_u$ as needed.
\item Check proximity as: $\prod_{a=1}^\ell
(\tilde{c}_a)^{\Lambda_{n,\ell}^T[a,k_u]}=\prod_{i=1}^{4p}(\pi[i,k_u])^{\rho_i}$ for $u\in [t]$.
\item $\verifier$ accepts if all the subprotocols accept.
\end{enumerate}
\end{framed}
}
\caption{$\grapheneRCS$ Protocol}
\label{fig:graphene}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Proof of knowledge of $\name$}
\begin{lemma}\label{app:POKgraphene}
	For all polynomially bounded provers $P^\ast$ and all $\pi\in\GG^{4p\times n}$, there exists an expected polynomial time extractor $\extrac$ with rewinding access to the transcript oracle $\tr = \innp{P^{\ast}}{\verifier^{\pi}}$ such that either $\extrac$ breaks the commitment binding, or it outputs a witness with overwhelming probability whenever $P^\ast$ succeeds, i.e.,
	
	{\footnotesize
		\begin{align*}
		\condprob{
			\begin{array}{c}
			{[}\ewit_x||\ewit_y||\ewit_z||\ewit{]}=\open(\pi)\wedge \\
			\wit_z=\wit_x\circ\wit_y\wedge \wit_x=A\wit\\
			\wit_y=B\wit \wedge \wit_z=C\wit
			\end{array}
		}{
			\begin{array}{c}
			\sigma %\sample \gen(\secparam) \\
			\leftarrow \gen(\secparam) \\
			{[}\ewit_x||\ewit_y||\ewit_z||\ewit{]}%\sample \extr^{\mc{O}}(\sigma)\\
			\leftarrow \extr^{\mathsf{tr}}(\sigma) \\ 
			\wit_a=\dec(\ewit_a), a\in \{x,y,z\}\\
			\wit=\dec(\ewit)
			\end{array}
		}\\
		\geq \epsilon(P^\ast) - \kappa_{\rm qd}(\secpar) -\kappa_{\rm lc}(\secpar)
		\end{align*}
	}
Where $\kappa_{\rm lc}(\secpar)$ and $\kappa_{\rm qd}(\secpar)$ are the negligible soundness error of $\linearcheck$ and $\quadcheck$ respectively. And $\epsilon(P^\ast)$ is the success probability of the prover.
\end{lemma}
\begin{proof}
	We will design an extractor $\extrac$ using the extractors $\extrac_{lc}$ and $\extrac_{qd}$ of $\linearcheck$ and $\quadcheck$ described in ~\ref{app:linear_soundness} and ~\ref{app:quad_soundness} respectively. $\extrac$ plays the role of the verifier and $\extrac_{lc}$, $\extrac_{qd}$ use the queries generated by $\extrac$.
\end{proof}
\begin{figure}[h]
	{\footnotesize
		\begin{framed}
	\noindent{$DP-\grapheneRCS(\mathsf{pp},A,B,C,[\pi];\wit_x,\wit_y,\wit_z,\wit)$}:\\
	\noindent{\bf Relation}: $A\wit\circ B\wit=C\wit$. \\
	\noindent{\bf Oracle Setup}: Compute $\comoracle$ as described above. Set $\pi
	:= \comoracle$.
	\begin{enumerate}[{\rm 1.}]
		\item $\verifier\rightarrow\distprover$: $\gamma_x,\gamma_y,\gamma_z\sample \FF$,
		$r_{lc}\sample \FF^M$, $r_{qd}\sample \FF^{p}$, $\rho\sample \FF^{4p}$.
		\item $\distprover\rightarrow\Ag$: $\distprover$ computes $\shr{\tilde{\ewit}}=\sum_{i\in
			[4p]}\rho_i\shr{\ewit}[i,\cdot,\cdot]$ and sends commitments
		$\shr{\tilde{c}_1},\ldots,\shr{\tilde{c}_\ell}$ to $\shr{\tilde{\ewit}}$.
		\item $\Ag \rightarrow \verifier$: $\Ag$ computes $\tilde{c}_k=\prod_{\xi \in [\Num]} \shr{\tilde{c}_k}$ and sends $\tilde{c}_1,\ldots, \tilde{c}_{\ell}$.
		\item $\distprover\leftrightarrow\verifier$ compute: $R=r_{lc}^TW$ for
		$W=[\gamma_xI\,||\gamma_yI\,||\gamma_zI\,||-(\gamma_xA+\gamma_yB+\gamma_zC)]$,
		polynomials $R^i$,$i\in [4p]$ interpolating the slices of $R$ viewed as a
		$4p\times m\times n$ matrix.
		\item $\distprover$ computes: 
		\begin{itemize}
			\item Polynomials $\shr{Q^i_x},\shr{Q^i_y},\shr{Q^i_z},\shr{Q^i}$ for $i\in [p]$,
			where polynomials $\shr{Q^i_a}$, $i\in [p]$ correspond to $\shr{\wit_a}$ for $a\in \{x,y,z\}$ and
			polynomials $\shr{Q^i}$,$i\in [p]$ correspond to $\shr{\wit}$. 
			\item \textbf{MPC}: provers interact to compute $\mathsf{Mult}(\shr{Q^i_x},\shr{Q^i_y})$ and $\distprover$ gets $\shr{Q^i_{xy}}$, share of the polynomial $Q^i_{xy}$.
			\item $h\times n$ matrices $\shr{P_{lc}}$ and $\shr{P_{qd}}$ as ``P'' matrices for the linear check and
			quadratic check respectively. Note that $\shr{p_j}$ polynomial for $\shr{P_{lc}}$ is given
			by $\shr{p_j}(\cdot)=\sum_{i=1}^p(R^i(\alpha_j,\cdot).\shr{Q_x^i}(\alpha_j,\cdot)+
			R^{p+i}(\alpha_j,\cdot)\shr{Q^i_y}(\alpha_j,\cdot)+R^{2p+i}(\alpha_j,\cdot)\shr{Q^i_z}(\alpha_j,\cdot)+
			R^{3p+i}(\alpha_j,\cdot)\shr{Q^i}(\alpha_j,\cdot))$. The $\shr{p_j}$ polynomials for the
			matrix $\shr{P_{qd}}$ are given by
			$\shr{p_j}(\cdot)=\sum_{i=1}^{p}r_{qd}[i](\shr{Q^i_{xy}}(\alpha_j,\cdot)-\shr{Q^i_z}(\alpha_j,\cdot))$.
			\item Blinding vectors $\shr{U_{lc}},\shr{U_{qd}}\in \FF^{2m-1}$ for linear and quadratic check protocols
			respectively, and commitments $\shr{c_0},\shr{d_0}$ to vectors $\shr{U_{lc}}$
			and $\shr{U_{qd}}$.
		\end{itemize}
		\item $\distprover\rightarrow\Ag$: Commitments $\shr{c_0},\shr{c_1},\ldots,\shr{c_{s+\ell-1}}$ for
		the matrix $\shr{P_{lc}}$ and commitments $\shr{d_0},\shr{d_1},\ldots,\shr{d_{2\ell-1}}$ for matrix
		$\shr{P_{qd}}$. 
		\item $\Ag \rightarrow \verifier$: $\Ag$ computes $c_k = \prod_{\xi \in [\Num]} \shr{c_k}$ $\forall k\in \{0,\ldots, s+\ell-1\}$ and $d_k = \prod_{\xi \in [\Num]} \shr{d_k}$ $\forall k\in \{0,\ldots,2\ell-1\}$ and sends $c_0,c_1,\ldots, c_{s+\ell-1}, d_0,d_1,\ldots,d_{2\ell-1}$.
		\item $\verifier\rightarrow\distprover$: $Q=\{(j_u,k_u):u\in [t]\}$.
		\item $\verifier\rightarrow\pi$: $\{k_u:u\in [t]\}$.
		\item $\distprover\rightarrow\Ag$: $\shr{S_u}=\shr{\ewit}[\cdot,j_u,k_u], \shr{Plc_{u}}=\shr{P_{lc}}[\cdot,k_u], \shr{Pqd_{u}}=\shr{P_{qd}}[\cdot,k_u]$ for $u\in [t]$.
		\item $\Ag$ computes $S_u=\sum_{\xi\in [\Num]} \shr{S_u}$, $Plc_{u}=\sum_{\xi\in [\Num]}\shr{Plc_{u}}$ and $Pqd_{u}=\sum_{\xi\in [\Num]}\shr{Pqd_{u}}$ for $u\in [t]$.
		\item $\Ag \rightarrow \verifier$: $S_u$ for $u\in[t]$
		\item $\pi\rightarrow\verifier$: $\pi[\cdot,k_u]$, $u\in [t]$.
		\item $\verifier \rightarrow \distprover$: $\delta_{lc}\sample \FF^{4p}, \delta_{qd}\sample \FF^p, \beta_{lc}, \beta_{qd} \sample \FF^\ast, \beta_x, \beta_y, \beta_z \sample \FF$
		\item $\distprover \rightarrow \Ag$: $\shr{Vlc_u} = \innp{\delta_{lc}}{\shr{U[\cdot,j_u,k_u]}}$,\\ $\shr{Vqd_u} = \innp{\delta_{qd}}{(\beta_x U_x[\cdot,j_u,k_u] + \beta_y U_y[\cdot,j_u,k_u]  + \beta_z U_z[\cdot,j_u,k_u])}$
		\item $\Ag$ computes $Vlc_{u} = \sum_{\xi\in [\Num]} Vlc_u$ and $Vqd_{u} = \sum_{\xi\in [\Num]} Vqd_u$
		\item $\Ag$ and $\verifier$ run the linear and quadratic check protocols in
		parallel, parsing the vectors $V_u$ into $X_u,Y_u,Z_u,W_u$ as needed. And compute $A_u = \beta_xX_u+\beta_yY_u+\beta_zZ_u$ for $u\in[t]$ and corresponding commitment.
		
		\item Check proximity as: $\prod_{a=1}^\ell
		(\tilde{c}_a)^{\Lambda_{n,\ell}^T[a,k_u]}=\prod_{i=1}^{4p}(\pi[i,k_u])^{\rho_i}$ for $u\in [t]$.
		\item $\verifier$ accepts if all the subprotocols accept.
	\end{enumerate}
	\end{framed}
}
\caption{Distributed $\grapheneRCS$ Protocol}
\label{fig:dpgraphene}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Reducing MPC Overhead for Small Shared Circuits}\label{sec:sharedcircuitopti}
Let $C$ be a circuit with $N$ wires (we assume a unique incoming wire for each
input gate), let $\wit=(w_1,\ldots,w_N)$ denote the vector of wire values in a
satisfying assignment according to some ordering on the wires. We consider the
case, when each input wire is ``assigned'' to a unique prover. Let $M$ be the
number of multiplication gates in $C$, and let $A$, $B$, $C$ 
 be $M\times N$ matrices such that $\wit_x=A\wit$, $\wit_y=B\wit$
and $\wit_z=C\wit$ are vectors of {\em left}, {\em right} and {\em out} values
of multiplication gates. For $i\in [m]$, we say that multiplication gate $i$ is
{\em isolated} if $\wit_x[i],\wit_y[i]$ and $\wit_z[i]$ depend on inputs of only
one prover. We call the remaining multiplication gates as {\em shared}. Let
$N_s$ be the number of shared gates. Without loss of generality, we can assume
that the gates $1,\ldots,N_s$ are shared (rows of  $A$, $B$, $C$ can be permuted
suitably). Now an additive sharing of the extended witness may be obtained by
(i) each prover locally computing the wires for isolated gates from their
inputs, while setting the shares of other parties for these wires to be $0$ and
(ii) running a secret sharing MPC on the subcircuit containing shared gates.
Let $p_s=\lceil N_s/ms \rceil$. Then the multiplication MPC $\mathsf{Mult}$ in
distributed quadratic check can be restricted to obtaining shares
$\shr{U_x[i,j,k].U_y[i,j,k]}$ for $i\in [p_s]$, as each prover can canonically 
the shares of other slices of $\ewit_x$ and $\ewit_y$. For slices, which depend
on the provers inputs, the prover computes randomized encoding of the slice, for
other slices (where its share is $0$) it computes a deterministic encoding by
setting the buffer columns to $0$. This gives an MPC of depth 1 on circuit of
size $O(\max(N_s, mn))$.

\subsection{Performance Parameters for Ligero and Bulletproofs}\label{sec:performance}
%We summarize the performance parameters for Ligero ~\cite{ligero}, and 
%Bulletproofs ~\cite{bulletproofs} that we use to derive our estimates in 
%Figure ~\ref{fig:standalonecompare}. Let $N$ denote the size of extended
%witness.

\noindent{\bf Ligero}: Let $m,s$ be such that $N=ms$. Let $t$ be a parameter,
and let $\ell=s+t$, $n=O(\ell)$ and $e\leq (n-\ell)/4$
Then the performance parameters for Ligero are then given by:
$\zkcomm=n+6\ell+4s+4mt+5t-5$,
 $t_\prover=O(N)\cfop+4m(\cfft(s)+\cfft(n))$,
$t_\verifier=O(N)+4m\cfft(s)$,
$\kappa_{lg}=(1-e/n)^t+5((2\ell+e)/n)^t$.

\noindent{\bf Bulletproofs}:
$\zkcomm=2\log(N)+13$, $t_\prover=9N\cexp +
2\cmexp(2N)+3\cmexp(N)$, $t_\verifier=N\cexp + \cmexp(2N)$, $\kappa_{bp}=N/|\FF|$.

For computing prover communication in distributed setting we use the expressions:
$\prcomm=MPC(\Num,\max(N_s,4m\ell),1)+\Num\times
[(4pn+5\ell+s+2)\bitsG+(4pt+4m+h)\bitsF]$, for $\dpname$ and
$\prcomm=MPC(\Num,N_s,1)+\Num\times [8\bitsG + N\bitsF]$ for Bulletproofs. Here
$MPC(\Num,N_s,1)$ denotes communication in an $\Num$ party MPC with circuit size
$N_s$ and depth as 1.
 
%\input{2D.tex}