Related_work.tex

\subsection{Related Work}\label{sec:relatedwork}
%\commentA{this section does not look comprehensive}
As mentioned earlier in the introduction, Pedersen \cite{Ped92} defines the
notion of distributed proof genration and proposes a generic construction using
MPC. Over the years, works have discussed distributed proof generation for a
restricted class of predicates: Desmedt et al. \cite{DDB94} proposing proofs for
graph isomorphism, various works \cite{King05, DDS, Desmedt2011} for proposing
threshold signatures, Keller et al. \cite{EfficientTZ} for a class of sigma
protocols. Bulletproof  \cite{bulletproofs} presents a
``distributed'' protocol to produce an aggregation of range proofs on inputs
held by different parties. However, their completeness property is weaker than
ours, i.e, a set of provers with valid witness can only prove the statement only if each input gate is exclusive to one prover. 
Trinocchio \cite{trinocchio} proposes a distributed proof generation method for
 Pinocchio  \cite{pinnochio_PHGR} but only when there is a
honest majority of semi-honest parties. Moreover, it needs the trusted setup
model. The work DIZK \cite{dizk} provides a distributed implementation of the proof generation of a non-interactive zero-knowledge protocol (zkSNARK).
 In Table ~\ref{tab:SPZK}, we compare the different metrics of efficiency for both the available $\DPZK$ protocols. Here $N$ is the size of the circuit and, $c$ is a positive integer of our choice. $\Num$ is the number provers in the $\DPZK$ setting. $M$ is to indicate the amount of computation required for a single multiplication on the field elements, and $E$ is to indicate the amount of computation required for single exponentiation on the group elements, in which $\mathsf{Dlog}$ is assumed to be hard. And $N_s$ denotes the size of the shared circuit.
\begin{table*}[htp] 
	\centering
	\resizebox{\textwidth}{!}{
		%\begin{threeparttable}
		\begin{tabular}{|c|c|c|c|c|c|c|} 
			\hline
			Protocols &  $\zkcomm$ & $\zkrounds$ & $t_\prover$ & $t_\verifier$ & $\prrounds$ & $\prcomm$ \\
			\hline
			D-Bulletproofs & $\log (N)$ & $\log(N)$ & $O(N)E$ & $O(N)E$ & 2 & $ \Num\cdot N + \Num^2\cdot N_s$ \\
			\hline
			\name & $N^{1/c}$ & $\log(N)$ & $O(\frac{N}{\log(N)})E + O(N\log(N))M$ & $O(N^{1-2/c})E + O(N)M$ & 2 & $ \Num\cdot N^{1-2/c} + \Num^2\cdot \max(N_s,N^{1-1/c})$ \\
			\hline
			%&computation & communi- cation & MPC rounds& & & \\ 
			%\hline
			%Ligero & $O(n\log n)M$ & NA & NA &$O(n)M$ & $O(\sqrt{n})$ & 4\\
			%\hline
			%Bulletproofs & $O(nE+q(n+m)M)$ & $O(2N-1)$ & $O(\log n)$& $O(nE+$ $q(n+m)M)$ & $O(\log n)$ & $O(\log n)$  \\
			%\hline
			%Spartan & & & & & &\\
			%\hline
			%Aurora & & & & & &\\
			%\hline
			%\name2D & $O(n \log n)M$  $+nE)$ & $O(2N-1)$ & 1 &$O((nM +$ $ n^{1-1/c}E))$ & $O(n^{1/c})$ & $O(\log n)$ \\
			%\hline
			%\name3D & $O(nM+nE)$ & $O(2N-1)$& 1 & $O(nM+$ $n^{1-2/c}E)$ & $O(n^{1/c})$ & $O(\log n) $\\
			%\hline
		\end{tabular}
		%\end{threeparttable}
	}
	\caption{Comparison amongst the $\DPZK$s }\label{tab:SPZK}
	%\pnote{Con}
\end{table*}
%.\dnote{should section and subsection titles have caps only for the first letter of the first word, or in the first letter of every word?}
%Ligero \cite{ligero}, a zero-knowledge protocol was given, which attains sublinear proof size, without any trusted setup and assuming that finding the collision for a hash function is difficult. Then in \cite{bulletproofs} zero-knowledge argument of logarithmic size without trusted setup, assuming the discrete log is hard. And then \cite{aurora} gave an IOP based protocol which is better than \cite{ligero} in terms of proof size, but not as good as \cite{bulletproofs}, but hardness assumption is a collision-resistant hash function. \cite{spartan} provides an argument which attains sublinear proof as well as sublinear verification, on the hardness assumption of the discrete log. Verification of \cite{bulletproofs} requires the exponentiation operation of linear order, which is very expensive in terms of practice. Whereas \cite{aurora} does not require exponentiation, but as all its messages are constructed as oracles, it takes too much memory in practice. \cite{spartan} is better in terms of verification. In our work, we provide a zero-knowledge protocol which has a sublinear proof size, same as \cite{spartan} and in verification number of required field operations is linear in size of the circuit but the number of exponentiations is very less, lesser than \cite{spartan}, in practice which can outperform all the above works.

%In \cite{DDS} notion of distributed prover protocol was introduced, where provers jointly provide a signature. Generalization of this work came in 2012 by Marcel et al. \cite{EfficientTZ}, which gave a generic notion of the distributed proof generation system. In this paper, the protocols were restricted to $\Sigma$-protocol.
%%Another contribution of our paper is to define the notion of distributed proof generation for zero-knowledge.
%In our work, we are revisiting the definition and providing an efficient protocol for general arithmetic circuits, which supports this notion. In \cite{bulletproofs}, it was given that the range proof supports the notion of distributed proof generation. In \cite{trinocchio}, a zero-knowledge protocol provided in \cite{pinnochio_PHGR} was converted into a distributed proof generation zero-knowledge protocol, but these protocols are based on the trusted setup. Later in this paper, we will describe how state-of-the-art zero-knowledge protocols lack efficiency while converting into distributed proof generation zero-knowledge protocol. \cite{spartan} requires an MPC of quadratic order in the size of the verification circuit. \cite{ligero, aurora} can not be transformed into $\DPZK$ directly. These works can be made $\DPZK$; in that case, the oracle constructions are needed to be changed such that it must have homomorphic property. This makes $\DPZK$ from \cite{aurora} very inefficient because every message in this protocol is constructed as an oracle. We describe a different approach to obtain $\DPZK$ from the inner product adapted from \cite{bulletproofs}.
%\pnote{Include Marcel Keller's paper \cite{EfficientTZ}}