“Breaking the Circuit-Size Barrier for Secure Computation under DDH”, is the collaborative research work of Elette Boyle, a Senior Lecturer in the Efi Arazi School of Computer Science at IDC, Niv Gilboa (Ben Gurion University) and Yuval Ishai (Technion & UCLA). The paper introduces a new approach to a fascinating area of cryptographic applications and was selected for Best Paper of CRYPTO 2016, the flagship annual conference of the international cryptologic research community.

One of the most interesting applications of the paper has to do with what is known as Secure Two Party Computation. In simplified terms, this is when two people each have confidential input data (e.g., their respective salaries) and they want to learn some information about the combined inputs (e.g., whose salary is higher). Breaking the Circuit-Size Barrier focuses on one of the main challenges of this computation: the problem of how much information needs to be passed back and forth between the two parties while maintaining a secure transaction. If security were not a concern, then it suffices to communicate just the size of the input and output: Alice can always send her input x (e.g., her salary) directly to Bob, and Bob can compute and respond with the desired information z = f(x,y) on x together with his input y. However, once security is required, so that Alice and Bob learn only the output f(x,y) and not each other’s inputs, basically all existing techniques of the Two Party Computation are limited by the fact that secure computation grows in size relative to the complexity of the function f being computed, which can be drastically larger for more complex computations. The research of the past few decades has only been able to circumvent this requirement (that the amount of information sent grows with the size of the function), by one approach which requires strong tools and a rather heavy work load for the computer. Breaking the Circuit-Size Barrier veers away from the existing approach and offers the first alternative path, using entirely different mathematical tools. This opens the door to a whole new direction of research that could yield significantly more efficient secure computation solutions.

Boyle was recently awarded a $360,000 grant by the United States Air Force Office of Scientific Research (AFOSR) for a continued research project related to this work here at IDC. An emphasis of the project is on how to use these new techniques to enable efficient queries and manipulation of databases while hiding the requests themselves.