Paper 2013/013

Efficiently Outsourcing Multiparty Computation under Multiple Keys

Andreas Peter, Erik Tews, and Stefan Katzenbeisser


Secure Multiparty Computation (SMC) enables a set of users to evaluate certain functionalities on their respective inputs while keeping these inputs encrypted throughout the computation. In many scenarios, however, outsourcing these computations to an untrusted server is desirable, so that the server can perform the computation on behalf of the users. Unfortunately, existing solutions are either inefficient, rely heavily on user interaction, or require the inputs to be encrypted under the same key - drawbacks making the employment in practice very limited. We propose the first general-purpose construction that avoids all these drawbacks: it is efficient, it requires no user interaction whatsoever (except for data up- and download), and it allows evaluating any dynamically chosen function on inputs encrypted under different independent public keys. Our solution assumes the existence of two non-colluding but untrusted servers that jointly perform the computation by means of a cryptographic protocol. This protocol is provably secure in the semi-honest model. We demonstrate the applicability of our result in two real-world scenarios from different domains: Privacy-Preserving Face Recognition and Private Smart Metering. Finally, we give a performance analysis of our general-purpose construction to highlight its practicability.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Secure Multiparty ComputationHomomorphic EncryptionOutsourcing ComputationSemi-Honest Model
Contact author(s)
andreas peter @ cantab net
2013-01-12: received
Short URL
Creative Commons Attribution


      author = {Andreas Peter and Erik Tews and Stefan Katzenbeisser},
      title = {Efficiently Outsourcing Multiparty Computation under Multiple Keys},
      howpublished = {Cryptology ePrint Archive, Paper 2013/013},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.