Secure Arithmetic Computation with No Honest Majority

Details Secure Arithmetic Computation with No Honest Majority Secure Arithmetic Computation with No Honest Majority

2008-11-04

arxiv.org/abs/0811.0475v3

Computer Science

Cryptography and Security

minor editorial changes

Scientific paper

We study the complexity of securely evaluating arithmetic circuits over finite rings. This question is motivated by natural secure computation tasks. Focusing mainly on the case of two-party protocols with security against malicious parties, our main goals are to: (1) only make black-box calls to the ring operations and standard cryptographic primitives, and (2) minimize the number of such black-box calls as well as the communication overhead. We present several solutions which differ in their efficiency, generality, and underlying intractability assumptions. These include: 1. An 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|$. 2. Computationally secure protocols in the OT-hybrid model which make a black-box use of an underlying ring, and in which the number of ring operations does not grow with the ring size. These results extend a previous approach of Naor and Pinkas for secure polynomial evaluation (SIAM J. Comput., 35(5), 2006). 3. 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. All of our protocols are in fact UC-secure in the OT-hybrid model and can be generalized to multiparty computation with an arbitrary number of malicious parties.

Affiliated with

Also associated with

No associations

Rating

Secure Arithmetic Computation with No Honest Majority does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Secure Arithmetic Computation with No Honest Majority, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Secure Arithmetic Computation with No Honest Majority will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-184051