​​​​Eran Omri

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.

​