Efficiently Outsourcing Multiparty Computation under Multiple Keys.

Peter Andreas, Erik Tews, Stefan Katzenbeisser

Published Jan 1, 2013• 2 citations

Abstract

Abstract. 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. Inmanyscenarios, however, outsourcingthesecomputations toanuntrustedserver is desirable, sothattheservercanperform thecomputationonbehalfoftheusers.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.

Related papers

Outsourcing computation for private function evaluation

Henry Carter, Patrick Traynor

Outsourced secure multiparty computation (SMC) protocols allow resource-constrained devices to execute input-private computation with great efficiency. Unfortunately, existing outsourced SMC protocols require that all parties know the function being evaluated, precluding applications where the function itself must remain private. We develop the first linear-complexity protocols for outsourcing private function evaluation (PFE), SMC protocols that provide input and function privacy. Assuming a semi-honest function holder, we build on existing two-party PFE constructions to develop outsourced protocols that are secure against a semi-honest, covert, or malicious outsourcing server and malicious mobile participants. To do this, we develop a garbling technique for combining public and private sub-circuits in a single computation. This allows us to apply auxiliary checks for malicious behaviour using only free-XOR gates. These protocols demonstrate the feasibility of outsourced PFE and provide a first step towards privacy-preserving applications for use in cloud computing.

International Journal of Information and Computer SecurityJan 1, 20191 citation

Protocols for secure multi-party private function evaluation

Feras Aljumah, Andrei Soeanu, Wen Ming Liu +1 more

Secure multi-party computation (SMC) allows multiple parties to jointly and securely compute a function while preserving the privacy of the involved parties. In this regard, homomorphic cryptosystems allow users to perform addition or multiplication operations on encrypted values without having to decrypt the input values. In this paper, we propose both a cryptographic and a non-cryptographic privacy-preserving protocols that allow one party to collaboratively compute a private polynomial function with at least two other parties using semantically secure cryptosystems. In this respect, the function to be evaluated is kept private to the party in question. In addition, we assume that there is no fully trusted party and that all parties are semi-honest. Moreover, we assume that there is no collusion between the different parties. We present the two protocols in question and report on the underlying performance through the presentation of our implementation results. The proposed protocols are relevant in many applications such as evidence sharing in multi-party forensic investigations, situation awareness through the secure sharing in distributed monitoring of plan execution, etc.

International Conference on Anti-Cyber Crimes (ICACC)Nov 1, 20151 citation

A Comparative Study of Available Protocols during Privacy Preservation in Secure Multiparty Computation

Zulfa Shaikh, Poonam Garg, Andrew Chi-Chih Yao +1 more

In this paper, comparative study of different available Secure Multiparty Computation (SMC) protocols have been addressed. In SMC, a set of parties wishes to jointly compute some function on their inputs. This computation must preserve certain security properties, like privacy and correctness. The general approach for such kind of computation is to make use of trusted third party to do the computation and then announce the result publicly. The major problem with this approach is that it is difficult to find a third party which is trusted by all the parties providing the inputs. This implies that the data of parties must be secured. Security is meant to achieve correctness of the result of computation and keeping the party’s input private even if some of the parties are corrupted.

Jan 1, 20111 citation

Two-Cloud-Servers-Assisted Secure Outsourcing Multiparty Computation

Yi Sun, Qiaoyan Wen, Yudong Zhang +3 more

We focus on how to securely outsource computation task to the cloud and propose a secure outsourcing multiparty computation protocol on lattice-based encrypted data in two-cloud-servers scenario. Our main idea is to transform the outsourced data respectively encrypted by different users' public keys to the ones that are encrypted by the same two private keys of the two assisted servers so that it is feasible to operate on the transformed ciphertexts to compute an encrypted result following the function to be computed. In order to keep the privacy of the result, the two servers cooperatively produce a custom-made result for each user that is authorized to get the result so that all authorized users can recover the desired result while other unauthorized ones including the two servers cannot. Compared with previous research, our protocol is completely noninteractive between any users, and both of the computation and the communication complexities of each user in our solution are independent of the computing function.

The Scientific World JOURNALJan 1, 20148 citations

Efficiently secure multiparty computation based on homomorphic encryption

Yuangang Yao, Jinxia Wei, Jianyi Liu +1 more

The existing security multiparty computation (SMC) protocols are either insecure, demand the input information to be encrypted under a public key, or rely heavily on user interaction. These deficiencies limit the protocol to be employed. We put forward a protocol based on homomorphic encryption (HE) that allows the input of function to be encrypted with various public keys. Comparing the methodology with the known technique shows that the communication complexity in our paper is lower.

IEEE International Conference on Cloud Computing and Intelligence Systems (CCIS)Aug 1, 20164 citations

Secure Computation in Heterogeneous Environments: How to Bring Multiparty Computation Closer to Practice?

Raykova, Mariana Petrova

Many services that people use daily require computation that depends on the private data of multiple parties. While the utility of the final result of such interactions outweighs the privacy concerns related to output release, the inputs for such computations are much more sensitive and need to be protected. Secure multiparty computation (MPC) considers the question of constructing computation protocols that reveal nothing more about their inputs than what is inherently leaked by the output. There have been strong theoretical results that demonstrate that every functionality can be computed securely. However, these protocols remain unused in practical solutions since they introduce efficiency overhead prohibitive for most applications. Generic multiparty computation techniques address homogeneous setups with respect to the resources available to the participants and the adversarial model. On the other hand, realistic scenarios present a wide diversity of heterogeneous environments where different participants have different available resources and different incentives to misbehave and collude. In this thesis we introduce techniques for multiparty computation that focus on heterogeneous settings. We present solutions tailored to address different types of asymmetric constraints and improve the efficiency of existing approaches in these scenarios. We tackle the question from three main directions: New Computational Models for MPC - We explore different computational models that enable us to overcome inherent inefficiencies of generic MPC solutions using circuit representation for the evaluated functionality. First, we show how we can use random access machines to construct MPC protocols that add only polylogarithmic overhead to the running time of the insecure version of the underlying functionality. This allows to achieve MPC constructions with computational complexity sublinear in the size for their inputs, which is very important for computations that use large databases. We also consider multivariate polynomials which yield more succinct representations for the functionalities they implement than circuits, and at the same time a large collection of problems are naturally and efficiently expressed as multivariate polynomials. We construct an MPC protocol for multivariate polynomials, which improves the communication complexity of corresponding circuit solutions, and provides currently the most efficient solution for multiparty set intersection in the fully malicious case. Outsourcing Computation - The goal in this setting is to utilize the resources of a single powerful service provider for the work that computationally weak clients need to perform on their data. We present a new paradigm for constructing verifiable computation (VC) schemes, which enables a computationally limited client to verify efficiently the result of a large computation. Our construction is based on attribute-based encryption and avoids expensive primitives such as fully homomorphic encryption andprobabilistically checkable proofs underlying existing VC schemes. Additionally our solution enjoys two new useful properties: public delegation and verification. We further introduce the model of server-aided computation where we utilize the computational power of an outsourcing party to assist the execution and improve the efficiency of MPC protocols. For this purpose we define a new adversarial model of non-collusion, which provides room for more efficient constructions that rely almost completely only on symmetric key operations, and at the same time captures realistic settings for adversarial behavior. In this model we propose protocols for generic secure computation that offload the work of most of the parties to the computation server. We also construct a specialized server-aided two party set intersection protocol that achieves better efficiencies for the two participants than existing solutions. Outsourcing in many cases concerns only data storage and while outsourcing the data of a single party is useful, providing a way for data sharing among different clients of the service is the more interesting and useful setup. However, this scenario brings new challenges for access control since the access control rules and data accesses become private data for the clients with respect to the service provide. We propose an approach that offers trade-offs between the privacy provided for the clients and the communication overhead incurred for each data access. Efficient Private Search in Practice - We consider the question of private search from a different perspective compared to traditional settings for MPC. We start with strict efficiency requirements motivated by speeds of available hardware and what is considered acceptable overhead from practical point of view. Then we adopt relaxed definitions of privacy, which still provide meaningful security guarantees while allowing us to meet the efficiency requirements. In this setting we design a security architecture and implement a system for data sharing based on encrypted search, which achieves only 30% overhead compared to non-secure solutions on realistic workloads.

Jan 1, 20124 citations