Program Preview: Cryptography, Summer 2015

by Sanjam Garg

Organizations and individuals are now outsourcing data storage and computation to untrusted third-party systems, referred to as “the cloud.” The privacy of outsourced personal information such as medical and financial history is questionable, and the paranoia around it has been at an all-time high. This paradigm shift in how we store and compute on our data has raised many new challenges in cryptography. Departing from the traditional cryptographic goals of secure and authenticated communication, these new systems demand high levels of functionality with very sophisticated security and privacy demands. Furthermore, the large data sizes that these systems need to deal with also place stringent efficiency requirements that have typically not been considered in cryptographic systems previously.

In recent years we have seen dramatic progress in answering many long standing open problems in cryptography. Recent foundational results on fully homomorphic encryption enable arbitrary computation on encrypted data. For example, a cloud provider could use a client’s encrypted financial information to prepare his tax return in encrypted form without learning anything at all about the client’s financial history or the prepared tax return - something that might seem paradoxical, or even impossible. Recent results on program obfuscation take it to the next level, bringing about a dramatic change in our understanding of what is possible in cryptography. Obfuscation enables techniques for hiding secrets inside computer programs. This, for instance, has enabled cryptographic methods allowing parties to learn outputs of specific functions of encrypted data without learning any additional information. Finally we have also seen tremendous progress in development of powerful privacy preserving data-mining techniques based on rigorous foundations. In tandem with these new feasibility results, we now have far more efficient multiparty secure computation protocols, first realized roughly three decades ago. These techniques allow a set of mutually distrustful parties to compute a joint function on their private inputs without revealing anything more than the output of the computation itself. These efficiency improvements have been possible due to a huge body of theoretical results. This includes works on oblivious random access machines (RAM), a technique used for realizing secure computation for RAM programs directly, instead of first converting them to circuits as is typically done in cryptography.

Although many new discoveries have been made, still many challenges remain; both in terms of foundational research, and in translating this foundational progress in to practically viable solutions. The cryptography program at Simons will consist of three workshops and aims to instill discussions that can help overcome these challenges and lead to significant progress in development of new techniques in cryptography.

The program will start with a boot camp which aims to acquaint program participants with the key themes of the program. After setting this foundation, the remainder of the program will consist of two workshops. The first workshop will focus on secure computation – specifically, on the fresh concepts such as fully homomorphic encryption and program obfuscation and the more mature cryptographic techniques such as secure multi-party computation and oblivious RAM. Finally the second workshop will focus on the mathematical aspects of cryptography. Very exciting theoretical advances in cryptography, including many discussed above, have been based on relatively new computational assumptions relating to basic mathematical structures. This workshop will bring together cryptographers, mathematicians and cryptanalysts with the goal of enhancing our understanding of these problems.

Cryptography program page

Related Articles:

Letter from the Director
Through the Computational Lens: Interdisciplinary Collaboration at the Simons Institute
From the Inside: Information Theory
Research Vignette: Faster Algorithms for Linear Programming
Research Vignette: Semialgebraic Geometry of Ranks