HomeResearchPublications

Lean and Fast Secure Multi-Party Computation: Minimizing Communication and Local Computation Using A Helper

back to overview

Reference

Schneider, J. (2009). Lean and Fast Secure Multi-Party Computation: Minimizing Communication and Local Computation Using A Helper. Paper presented at the International Conference on Security and Cryptography (SECRYPT).

Publication type

Paper in Conference Proceedings

Abstract

A client wishes to outsource computation on con?dential data to a network of servers. He does not trust a single server, but believes that multiple servers do not collude. To solve this problem we introduce a new scheme called JOS for perfect security in the semi-honest model that naturally requires at least three parties. It differs from clas- sical secure multi-party computation (MPC) through three points: (i) a client-server setting, where all inputs and outputs are only known to the client; (ii) the use of three parties, where one party serves merely as “helper” for computation, but does not store any shares of a secret; (iii) distinct use of the distributive and associative nature of well-known linear encryption schemes to derive our protocols. We improve on the to- tal amount of communication needed to compute both an AND and a multiplication compared to all prior schemes (even two party protocols), while matching round com- plexity or requiring only one more round. For big-data analysis, network bandwidth is often the most severe limitation, thus minimizing the amount of communication is essential. Therefore, we make an important step towards making MPC more practical. We also reduce the total amount of storage needed (eg. in a database setting) compared to all prior schemes using three parties. Our local computation requirements lag be- hind non-encrypted computation by less than an order of magnitude per party, while improving on other schemes, ie. GRR, by several orders of magnitude. We also dis- cuss a trade-off for round complexity and communication for large fan-in gates.

Persons

Organizational Units

  • Institute of Information Systems
  • Hilti Chair of Business Process Management