The International Association for Cryptologic Research has awarded a “Test of Time” award to a paper co-authored in 2005 by Brent Waters, currently an NTT Research Distinguished Scientist, and Dr. Amit Sahai, professor of computer science at the UCLA Samueli School of Engineering. Titled “Fuzzy Identity-Based Encryption,” this paper introduced attribute-based encryption, a departure from the prevailing model at the time. Dr. Amit, who is also director of the Center for Encrypted Functionalities at UCLA, served as Dr. Waters’ Ph.D. advisor at Princeton University, where they first collaborated. Dr. Waters is also professor of computer science at the University of Texas at Austin.
We recently posed this series of questions to Dr. Sahai about this paper, its significance and his long-standing collaboration with his former student:
Did you think back in 2005 that the “Fuzzy Identity-Based Encryption” paper that you presented at EuroCrypt 2005 would have the impact that it has?
I think it is fair to say that we did not. When we first started to attack it technically, it just looked like a nice natural problem, namely: what if the identity of a party was a fingerprint, and since no two readings of a fingerprint are likely to be the same, it could be that your secret key corresponds to a fingerprint that is slightly different from the fingerprint someone used to encrypt a message to you. The beauty and depth of this line of work was revealed over time by our attempts to generalize both the model and the techniques that we developed. There was first an immediate generalization away from fingerprints to sets of attributes that should overlap, but this seemed like a technical abstraction at the time. However, this move to attributes then naturally led us to consider other access policies over attributes beside set-intersection size – this became Attribute-Based Encryption. And finally, just the process of writing down a formal abstraction for general policies led to the natural question of what if the sets of attributes were not public, but themselves were also private. This led to the powerful notion of Functional Encryption.
The prevailing encryption model at the time was more along the lines of all-or-nothing access, correct? Would you have described your proposal as disruptive, or just an alternative?
Yes, the prevailing encryption model until our work was all-or-nothing access to the message being encrypted, with typically a single recipient, or a broadcasted encrypted message to a set. Our line of work challenged both of these elements. First with Attribute Based Encryption, we considered allowing an encryptor to set at the time of encryption a policy that determines who should be able to decrypt the message, and who should not. Then, with Functional Encryption, we considered the possibility that the recipient does not get the entire message being encrypted, but only a processed version of it. I think both these concepts have proven to be disruptive to how we think about encryption. In general, our thinking has consistently been: What aspects of security that are currently handled by careful software engineering can we move to the realm of mathematics instead?
How does one objectively measure the influence of a scientific paper? Citations, debate, follow-on ideas, etc.? How would you personally measure it?
This is a good question. I am a strong believer in the idea that there is no one way to measure success, whether for people, or for papers. The educational system of the U.S. works so well because it gives students many different ways to distinguish themselves, and I believe the same should be true for papers. Some papers distinguish themselves by directly influencing many follow-up papers; in this case, citation counts are a reasonable measure. Other papers distinguish themselves by introducing new techniques or concepts that are refined later before “taking off.” In such cases, citations may not follow quite as naturally because a follow-up paper may be cited instead. Still other papers distinguish themselves by solving a major open problem; such papers may not get citations because those papers are the “end of the line” for a problem, but they can nevertheless be important and influential.
Functional encryption grew out of this initiative, as well as software obfuscation, correct? Could you summarize those later developments, in a few words?
Yes, I’ve already touched on how Functional Encryption came out earlier. Software obfuscation – where secrets can be embedded and used by public computer programs – on the other hand, was a problem that I fell in love with as a graduate student at MIT back in 1998, and in fact the concept of cryptographically strong software obfuscation dates back all the way to the classic 1976 paper of Diffie and Hellman that introduced public-key cryptography. However, remarkably, we observed in 2012-2013 that the techniques that would enable Functional Encryption would also enable an intriguing form of software obfuscation called Indistinguishability Obfuscation. Later in 2013, Brent and I showed that Indistinguishability Obfuscation was remarkably versatile and powerful. A couple of years later, in 2015, the work of a few groups formally showed that sufficiently secure Functional Encryption actually implies secure Indistinguishability Obfuscation.
You and Dr. Waters have been collaborating since he was in graduate school. How would you describe your academic partnership?
Brent walked into the Introduction to Cryptography class that I was teaching at Princeton, and very obviously fell in love with cryptography while taking the class with me. It was my pleasure to be his research advisor, together with Ed Felten. Over the past 20 years, he has become a colleague and good friend. We have always had a lot of fun together. Last year we explored a castle in Germany while attending Eurocrypt 2019. There has always been something magical about our research cooperation, and the proof of that magic is in the work that has come out of it. I think we bring out the best in each other, and we have a lot of fun doing it.
