IACR News item: 09 March 2013
Payman Mohassel, Saeed Sadeghian
ePrint ReportWe apply our framework to several well-known general-purpose MPC constructions, in each case, obtaining the most efficient PFE construction to date, for the considered setting. Similar to the previous work we only consider semi-honest adversaries in this paper.
\\begin{itemize} \\item In the \\emph{multiparty} case with dishonest majority, we apply our techniques to the seminal GMW protocol~\\cite{GMW87} and obtain the first general-purpose PFE with \\emph{linear complexity} in the circuit size.
\\item In the \\emph{two-party} case, we transform Yao\'s garbled circuit protocol~\\cite{yao86} into a constant-round two-party PFE. Depending on the instantiation of the underlying subprotocol, we either obtain a two-party PFE with linear complexity that improves on the only other work with similar asymptotic efficiency (Katz and Malka, ASIACRYPT 2011), or a two-party PFE that provides the best concrete efficiency to date despite not being linear.
\\item The above two constructions are for boolean circuits. In case of \\emph{arithmetic circuits}, we obtain the first PFE with linear complexity based on any additively homomorphic encryption scheme. \\end{itemize}
Though each construction uses different techniques, a common feature in all three is that the overhead of hiding the circuit $\\C$ is essentially equal to the cost of running the OEP protocol on a vector of size $|\\C|$. As a result, to improve efficiency, one can focus on lowering the cost of the underlying OEP protocol. OEP can be instantiated using a singly homomorphic encryption or any general-purpose MPC but we introduce a new construction that we show is significantly more efficient than these alternatives, in practice. The main building block in our OEP construction is an efficient protocol for \\emph{oblivious switching network evaluation} (OSN), a generalization of the previously studied oblivious shuffling problem which is of independent interest. Our results noticeably improve efficiency of the previous solutions to oblivious shuffling, yielding a factor of 25 or more gain in computation and communication.
Additional news items may be found on the IACR news page.