Benny Pinkas

Cloud computing infrastructures offer many advantages to users, including large storage and high computation power. However, offloading workloads to hosting environments raises trust and privacy concerns. Algorithms that address these concerns require multiple network transactions and have low performance.

Private set intersection (PSI) is a cryptographic technique that is applicable to many privacy-sensitive scenarios. For decades, researchers have been focusing on improving its efficiency in both communication and computation. However, most of the existing solutions are inefficient for an unequal number of inputs, which is common in conventional client-server settings. In this paper, we analyze and optimize the efficiency of existing PSI protocols to support precomputation so that they can efficiently deal with such input sets. We transform four existing PSI protocols into the precomputation form such that in the setup phase the communication is linear only in the size of the larger input set, while in the online phase the communication is linear in the size of the smaller input set. We implement all four protocols and run experiments between two PCs and between a PC and a smartphone and give a systematic comparison of their performance. Our experiments show that a protocol based on securely evaluating a garbled AES circuit achieves the fastest setup time by several orders of magnitudes, and the fastest online time in the PC setting where AES-NI acceleration is available. In the mobile setting, the fastest online time is achieved by a protocol based on the Diffie-Hellman assumption.

Consider a server offering risk assessment services and potential clients of these services. The risk assessment model that is run by the server is based on current and historical data of the clients. However, the clients might prefer not sharing such sensitive data with external parties such as the server, and the server might consider the possession of this data as a liability rather than an asset. Secure multi-party computation (MPC) enables one, in principle, to compute any function while hiding the inputs to the function, and would thus enable the computation of the risk assessment model while hiding the client’s data from the server. However, a direct application of a generic MPC solution to this problem is rather inefficient due to the large scale of the data and the complexity of the function. We examine a specific case of risk assessment—the ground speed model. In this model, the geographical locations of successive user-authentication attempts are compared, and a warning flag is raised if the physical speed required to move between these locations is greater than some threshold, and some other conditions, such as authentication from two related networks, do not hold. We describe a very efficient secure computation solution that is tailored for this problem. This solution demonstrates that a risk model can be applied over encrypted data with sufficient efficiency to fit the requirements of commercial systems.