We present several solutions which differ in their efficiency, generality, and underlying intractability assumptions. These include: \begin{itemize}
\item An {\em unconditionally secure} protocol in the OT-hybrid model which makes a black-box use of an arbitrary ring $R$, but where the number of ring operations grows linearly with (an upper bound on) $\log|R|$.
\item Computationally secure protocols in the OT-hybrid model which make a black-box use of an underlying ring, and in which the numberof ring operations does not grow with the ring size. The protocols rely on variants of previous intractability assumptions related to linear codes. In the most efficient instance of these protocols, applied to a suitable class of fields, the (amortized) communication cost is a constant number of field elements per multiplication gate and the computational cost is dominated by $O(\log k)$ field operations per gate, where$k$ is a security parameter. These results extend a previous approach of Naor and Pinkas for secure polynomial evaluation ({\em SIAM J.\ Comput.}, 35(5), 2006).
\item A protocol for the rings $\mathbb{Z}_m=\mathbb{Z}/m\mathbb{Z}$ which only makes a black-box use of a homomorphic encryption scheme. When $m$ is prime, the (amortized) number of calls to the encryption scheme for each gate of the circuit is constant.
\end{itemize} All of our protocols are in fact {\em UC-secure} in the OT-hybrid model and can be generalized to {\em multiparty} computation with an arbitrary number of malicious parties.
Category / Keywords: cryptographic protocols / multi-party computation, arithmetic circuits, black-box rings Publication Info: Full version of a paper under submission Date: received 3 Nov 2008, last revised 8 Nov 2008 Contact author: mmp at cs uiuc edu Available formats: PDF | BibTeX Citation Note: more editorial fixes Version: 20081110:135640 (All versions of this report) Discussion forum: Show discussion | Start new discussion