Application-Scale Secure Multiparty Computation
Secure multiparty computation (MPC) permits a collection of parties to compute a collaborative result without any of the parties or compute servers gaining any knowledge about the inputs provided by other parties, except what can be determined from the ou
- PDF / 1,000,451 Bytes
- 19 Pages / 439.363 x 666.131 pts Page_size
- 73 Downloads / 213 Views
ion
It is scarcely possible to read the news without seeing yet another reason to be able to perform computation on encrypted data. The cryptography community has long known that some kinds of computations on encrypted data are possible—at least in principle. This was notably demonstrated by Yao’s seminal work on secure multiparty computation [Y86], and most radically by Gentry’s work on fully homomorphic encryption (FHE) [G09]. While FHE is very new and still far from practical, there has been significant effort in the last few years to make MPC usable in practice. MPC computations permit a collection of parties to compute a collaborative result, without any of the parties gaining any knowledge about the inputs provided by other parties (other than what is derivable from the final result of the
This material is based upon work supported by the Defense Advanced Research Projects Agency through the U.S. Office of Naval Research under Contract N0001411-C-0333. The views expressed are those of the author and do not reflect the official policy or position of the Department of Defense or the U.S. Government.
Z. Shao (Ed.): ESOP 2014, LNCS 8410, pp. 8–26, 2014. c Springer-Verlag Berlin Heidelberg 2014
Application-Scale Secure Multiparty Computation
9
computation). In recent years, the variant of MPC called linear shared computation has been producing significant performance wins [BLW08, LAD12, DKL+13]. When we say “performance wins”, we should put it in context: on test cases such as securely decrypting AES-encrypted text, we have been seeing linear sharing achieving execution times of around 3–30ms per 128-bit block, which corresponds to a slowdown of around four to five orders of magnitude compared with computation in the clear. Significant though this slowdown is, it compares well with Yao and especially with FHE, whose current slowdowns appear to be respectively around six and nine orders of magnitude in our experience. There are two fundamental reasons why secure computation proceeds more slowly than computation in the clear. First, all secure computations have to be performed generically across all possible input and internal values (otherwise information is revealed), though there are neat algorithms which can sometimes amortize this somewhat across multiple accesses. Second, the multi-party schemes (both Yao and linear sharing) require significant network communication, typically growing linearly with the size of the function being evaluated. MPC protocols can be targeted to different security models, but the performance cost in establishing and maintaining the security for particular models can vary significantly. The simplest security model used for secure computation is honest but curious [G04], where the separate parties are assumed to follow the protocol honestly, but may at the same time attempt to learn secrets by looking at internal values of the computation, including any communications. This security model is appropriate for settings such as preventing information leakage by individuals with administrator ac
Data Loading...
