From the Inside: Cryptography

By Guy Rothblum

Historically, the study of cryptography was effectively synonymous with secure encryption. The goal was that if an encrypted message were intercepted by an adversary, it should appear to be nonsense. Encrypted messages could only be decrypted and understood by a recipient who knew the secret decoding method. In modern times, however, cryptography has become an immensely richer field of scientific study. Cryptographers study diverse settings where adversarial behavior might be a concern, and provide solutions that circumvent such behaviors. Beyond the traditional goal of securing communication, modern cryptography studies challenges as diverse as (for example): remote authentication, public-key encryption, protocols that allow distrustful parties to achieve common goals while protecting their private information, obfuscating programs to protect proprietary information, verifying the correctness of remote computations, and statistical analysis that protects individual privacy. The Summer 2015 Cryptography program just completed at the Simons Institute brought together cryptographers from around the world to study new challenges and exciting recent breakthroughs in the field, as well as to lay the groundwork for new research and solutions.

Recently, powerful technological trends have created new challenges and opportunities for cryptographic research. We are witnessing an explosive growth in online data stored by third-party providers in “the cloud”. There are numerous benefits and applications that can be derived from these data and from the “cloud computing” paradigm. Together with these benefits, there are also new threats and opportunities for adversarial interference. The need for solutions that guarantee privacy, security, availability and correctness of data and computations is more acute, and the scale of the challenges is greater than ever.

Hand in hand with these new challenges, the field has also seen thrilling advances, such as the first fully homomorphic encryption schemes, which can be used to run computations on encrypted inputs. These allow a provider to analyze an individual’s encrypted financial data, providing financial advice without learning anything about the sensitive information. Other examples include new techniques for code obfuscation: protecting proprietary secrets in the code, while allowing full access to the program’s functionality. Remarkable advances in our understanding of mathematical objects such as lattices and multilinear maps are changing the underpinnings of modern cryptography. New protocols can be used to outsource complex computations to third parties and verify the correctness of results with minimal overhead. The new field of differential privacy has developed methods that allow aggregate statistical analysis of sensitive data while protecting the privacy of individuals whose data are analyzed.

The Simons Institute program on Cryptography concluded last week. The diverse participants experienced a roller-coaster ride of workshops, discussions, collaborations, and learning. The program was organized around two week-long workshops, each with its own theme, as well as an initial boot camp. The weeks in between these workshops allowed participants more time for research and collaboration.

The first week of the program was devoted to a boot camp (May 18-22). Ten half-day tutorials brought participants up to date on the state of the art in lattice-based cryptography, fully homomorphic encryption, multilinear maps, code obfuscation, delegating computations and verifying their correctness, multi-party computation, garbled circuits, oblivious RAMs and differential privacy. In between these longer tutorials there were also shorter introductory talks from the Simons Institute Research Fellows, a phenomenal group of young researchers in cryptography.

The second workshop (June 8-12) was centered on securing computations: tools, techniques and systems that aim to protect computations from adversarial behavior. This encompassed both the dramatic recent advances in studying cutting-edge notions such as fully-homomorphic encryption, obfuscation and functional encryption, and significant advances that have significantly improved the efficiency of central techniques such as multi-party computation and oblivious RAMs.

The third workshop (July 6-10) focused on the mathematical underpinnings of modern cryptography. Many of the recent developments in cryptography have been based upon relatively new computational problems and assumptions relating to classical mathematical structures. This workshop brought together cryptographers, mathematicians and cryptanalysts to investigate the algorithmic and complexity-theoretic aspects of these new problems, the relations among them, and the cryptographic applications they enable. Topics included, among others: worst-case versus average-case complexity, the use of algebraic structure in cryptographic constructions and cryptanalytic attacks, and the role of quantum computation in security analysis and cryptanalytic attacks.

On top of and in between these workshops, the corridors at the Simons Institute have been buzzing with exciting research activity. During these weeks, the program organized several lecture series and reading groups. The weekly Historical Papers Seminar Series was particularly notable. This series consisted of talks about seminal papers that have had, and continue to have, long-lasting impact in cryptography and beyond. The talks discuss not only the works themselves but also their historical context -- and more broadly how the field has evolved, and where the techniques have found applications both in and out of cryptography.

I would be remiss not to include in this report a special thank you to Tal Rabin for tirelessly and flawlessly chairing the program organization, to all the other organizers, and to the phenomenal Simons Institute staff, who enabled the program to run without a hitch in the delightful setting of the Simons Institute at Berkeley. The workshop lectures and the historical lecture series are all streamed live from program webpage, and preserved in the Institute’s online archive and YouTube channel.

Beyond all of this scientific activity, participants have also followed a bevy of creative and social pursuits: from playback theater to swing dance lessons, weekly movie nights, karaoke and hiking. Even at the conclusion of a day of exciting research, there was hardly a dull moment in the Cryptography summer program at the Simons Institute.

Related Articles:

Research Vignette: Reed, Muller, and Costa: Together at the Simons Institute
Research Vignette: Hard Problems All The Way Up
Looking Ahead: Economics and Computation, Fine-Grained Complexity and Algorithmic Design, Fall 2015