| Secure Computation enables non-trusting parties to jointly perform computations, while guaranteeing both the privacy of their private inputs and the correctness of the computation.First introduced by Yao for the two party case, and later extended to the multi party case, and against stronger classed of attacks by Goldreich, Micali and Wigderson, secure computation has been extensively researched since, with great progress, giving polynomial time protocols for secure computation in various settings of assumptions on the parties involved, different attackers and attacks, and with various cryptographic assumptions.Despite these protocols being polynomial time and asymptotically efficient, there are still obstacles to a widespread adoption of secure computation in general use. Among the reasons one can count the additional communication and round complexity required for secure computation. While the overhead is usually only a small polynomial in the circuit size, this is still prohibitively high for practical purposes. For example, even a fairly small constant round complexity can result in very high latency, which makes the protocol impractical for distributed computing.In this thesis we focus on efficient secure computation protocols, and concentrate on reducing the round and/or communication complexity. In particular we show the following three results: (1) A protocol for general two party secure computation with encrypted data, which requires only a single message from Alice to Bob for each circuit evaluated. This protocol remains secure under arbitrary composition, in the Universal Composition (UC) model of Canetti. (2) A protocol for general multi party secure computation with encrypted data, requiring two rounds for each circuit evaluated, which is also UC-secure (that is, remains secure under arbitrary composition in the UC-model), even when the adversary may corrupt any number of parties. Our model for both protocols is of Computing with Encrypted Data, where inputs are given as ciphertexts in a threshold homomorphic public key encryption scheme. Both protocols can also be used to give general secure computation protocols at the cost of additional rounds. As with any UC-secure protocol, these protocols require preprocessing. We allow general preprocessing, which include any polynomial time interaction that is independent of the circuits evaluated or of the actual inputs. (3) Protocols for efficient two party secure evaluation of kernel functions, and applications of face detection and face recognition in images. These protocols are secure in the honest-but-curious model. |
