Secure Computation: Feasibility, Infeasibility, and Applications to Differential Privacy.
![](https://static.wixstatic.com/media/ea0999_e2ba91db07bf42679dff588888bfbf91.jpg/v1/fill/w_236,h_180,al_c,q_80,usm_0.66_1.00_0.01,enc_auto/ea0999_e2ba91db07bf42679dff588888bfbf91.jpg)
Joint project of Ben-Gurion University and Ariel University.
E-mail: omrier@ariel.ac.il , amos.beimel@gmail.com
Overview
In today’s Internet, parties communicate and perform common tasks together, where each party holds some private information; however, parties cannot be trusted and some of them are malicious. Secure multiparty computation ensures that tasks can be performed securely in untrusted environments, and it can be used to model almost any cryptographic task, including coin-tossing, electronic voting, electronic auctions, and distributed private data analysis. It is known that, assuming that trap-door permutations exist, any function can be computed with full security whenever the honest parties form the majority of the participating parties.
When an honest majority cannot be guaranteed, however, even the elementary task of coin-tossing cannot be computed with full security (i.e., with full fairness). This demonstrates that the actual picture of secure computation is much more complex, involving different models of computation and various settings. Specifically, the feasibility of obtaining secure computation depends on the definition of security, the power of the adversary, the existence of honest majority, and the cryptographic hardness assumptions. Even after four decades of intensive and extremely prolific research, much remains unknown and answers to fundamental questions are still missing. We will consider three interrelated subjects:
Security without an honest majority. Full security cannot be obtained in general without an honest majority (Cleve, STOC 86). This poses a problem in the two-party setting and in scenarios where participants are virtual entities, and an adversary can create many malicious entities, causing the honest entities to be a minority. This can be overcome by giving away fairness altogether. In many scenarios, however, some degree of fairness is essential and Cryptography should offer it to honest parties when they are a minority. We will study what types of security can be guaranteed for various secure computation tasks without a honest majority.
Minimal assumptions in secure computation. Identifying minimal assumptions in secure computation is of great value as it explains the nature of these cryptographic tasks and typically allows substantially more efficient cryptographic constructions. Indeed, much of the focus of research in cryptography was directed to understanding the complexity of cryptographic tasks. We will try to understand the necessary and sufficient cryptographic hardness assumptions for fundamental tasks in secure computation, such as coin-tossing with abort, fair coin-tossing, and distributed differentially private protocols.
Distributed differential privacy. Nowadays, huge amounts of sensitive information on individuals are shared on the Internet. Conducting analyses over this information can be highly beneficial in many aspects; however, disclosing the results of such analyses can cause damage to individuals and to the community as a whole, and collecting the information in a single point might be dangerous. The need for distributed differential privacy protocols that compute the analyses is evident. We will explore what analyses can be computed privately in the semi-honest and the malicious models. We are also interested in understanding the complexity of differentially private computation.
Team Members
Jobs
We are looking for excellent graduate students or postdoctorants with interest in the theory of cryptography and privacy. For more details, please contact Eran Omri.
Funding
This research is supported by the Israel Science Foundation (ISF).
Papers
-
Almost-Optimally Fair Multiparty Coin-Tossing with Nearly Three-Quarters Malicious. Bar Alon and Eran Omri. TCC (B1) 2016: 307-335
-
Optimizing Semi-Honest Secure Multiparty Computation for the Internet. Aner Ben-Efraim and Yehuda Lindell and Eran Omri. ACM Conference on Computer and Communications Security 2016: 578-590
-
Characterization of Secure Multiparty Computation Without Broadcast. Ran Cohen and Iftach Haitner and Eran Omri and Lior Rotem. TCC (A1) 2016: 596-616
-
Parallel Hashing via List Recoverability. Iftach Haitner and Yuval Ishai and Eran Omri and Ronen Shaltiel. Crypto (2) 2015: 173-190
-
Characterization of Fairness in Secure Two-Party Computation of Boolean Functions. G. Asharov and A. Beimel and N. Makriyannis and E. Omri. TCC 2015, LNCS Volume 9014, 2015, pages 199-228
-
Limits on the Usefulness of Random Oracles. Iftach Haitner, Eran Omri, and Hila Zarosim. TCC 2013, LNCS Volume 7785, 2013, pages 437-456