Zvika Brakerski
Krill Prize 2017
Weizmann Institute
Dr. Zvika Brakerski
My Research: Advanced Cryptography via Foundational Study
Can we delegate all of our computational tasks to a remote cloud server without surrendering the privacy of the data, even to the server itself? Can we compile computer programs in a way that completely hides their inner workings, but preserves their functionality? Can we give third parties such as companies or law enforcement access to our personal data while maintaining a mathematical guarantee that they can only use it in accordance with their declared privacy policy or warrant? These questions and similar ones are becoming increasingly pertinent as our society becomes more dependent on data that is being processed by third-party algorithms. In many cases, it might appear that utility or the greater good are at odds with privacy of individuals. My current research is focused on developing new cryptographic tools for mitigating this tension, via foundational investigation of the computational properties of mathematical structures.
State-of-the-art research in cryptography, including my own prior work, suggests that even though the aforementioned wish-list appears to be paradoxical, many of these goals can be achieved using new crypto- graphic structures, in particular relying on the intractability of computational problems on high-dimensional integer lattices. In the past, I was able to make significant progress in the task of fully homomorphic encryption, which allows computation on encrypted data without decrypting it first and without leaking information, and thus addresses the first question above. However, this is merely a gateway to a new world of cryptographic applications.
The grand mission of my research endeavor is to establish cryptographic tools supporting these appli- cations and to explore the mathematical and computational framework that governs the utility/privacy interplay. My exploration is internally motivated by the following two objectives: finding the conceptually simplest structure that provides the required property, and unifying our understanding by explaining various applications as different facets of a single phenomenon. Even though practical usability and improved secu- rity are not direct objectives, I believe, and my experience shows, that orders-of-magnitude improvements in efficiency and security follow from deeper conceptual understanding. Indeed, this has been demonstrated in my work on fully homomorphic encryption, which showed how to construct this strong primitive based on a much simpler mathematical structure than previously conjectured, and in turn led to a leap in the efficiency and security of implementations.
There is still a multitude of open problems in the study of fully homomorphic encryption, as well as in the study of other advanced cryptographic primitives. These include fine-grained access control to encrypted data via attribute based encryption, and the study of program obfuscation which allows to “encrypt” a program such that it is still executable, but hard to reverse engineer. The current level of understanding of these primitives varies, and the existence of some, e.g. program obfuscation, is still in the realm of conjecture (albeit with significant supporting evidence). The study of these problems leads us time and again to the mathematical and computational properties of high-dimension integer lattices, which can be imagined as infinite high-dimensional periodic grids. Information can be embedded in these grids in a way that is computationally hard to retrieve, and yet which enables manipulation of the information in many interesting ways. This translates into cryptographic schemes with extremely rich functionality but with a high level of security (interestingly, at the current state of knowledge, such cryptographic constructions are even immune to attacks using quantum computers, which render older cryptographic primitives insecure). The study of the cryptographic properties of lattices is fairly young, and many important pieces of the puzzle are still missing.
Our horizons are constantly expanded by the de- velopment of new techniques that we are only beginning to master, and technological developments challenge us to provide solutions to new and more intricate problems than we faced before. I feel fortunate to be a part of this great scientific effort and am very excited to see where it leads.