Chat with Shafi Goldwasser ACM Turing Award recipient in 2013 (Nobel Prize of Computing); World-renowned distinguished researcher and professor MIT and Weismann Institute — Part 1

Professors Shafi Goldwasser (r) and Silvio Micali (l) Turing Award Recipients in 2013.
Photo by Jason Dorfman, CSAIL/MIT

This week, Stephen Ibaraki has an exclusive interview with Shafi Goldwasser.

Shafi Goldwasser is the RSA Professor of Electrical Engineering and Computer Science at MIT, and Principal Investigator at the MIT Computer Science and Artificial Intelligence Lab (CSAIL), as well as a professor of Computer Science and Applied Mathematics at the Weizmann Institute of Science in Israel. A recipient of the National Science Foundation Presidential Young Investigator Award, she also won the ACM Grace Murray Hopper Award for outstanding young computer professionals. She has twice won the Gödel Prize presented jointly by the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) and the European Association for Theoretical Computer Science (EATCS). She leads the Theory of Computation Group and co-leads the Cryptography and Information Security Group at MIT CSAIL.

She was elected to the American Academy of Arts and Science, the National Academy of Sciences, and the National Academy of Engineering. She was recognized by the ACM Council on Women in Computing (ACM-W) as the Athena Lecturer, and received the IEEE Piore Award and the Franklin Institute's Benjamin Franklin Medal in Computer and Cognitive Science.

A graduate of Carnegie Mellon University with a B.A. degree in mathematics, she received M.S. and Ph.D. degrees in computer science from the University of California, Berkeley.

ACM Turing Awards announcement: http://www.acm.org/press-room/awards/turing-award-12

To listen to the interview, click on this MP3 file link

The latest blog on the interview can be found in the IT Managers Connection (IMC) forum where you can provide your comments in an interactive dialogue.
http://blogs.technet.com/b/cdnitmanagers/

DISCUSSION:

Interview Time Index (MM:SS) and Topic
:00:44:		When did you hear of this extraordinary honour, recipient of what is widely considered the Nobel Prize in Computing, the 2012 ACM Turing Award? How did you feel at the time? The reaction from your colleagues? From your family? "....I was extremely happy that Silvio and I had won the award together because we work quite a bit together (especially in the early days), and I was very happy that we were recognized for the work and especially the work together....My ex-students, colleagues around the world and my friends, everybody was extremely well-wishing....My family, of course, are proud...."
:02:35:		How will the Turing Award impact your work, your influence, your thinking? "....I have received awards in the past and I'm not sure they had a direct impact on how I do research and in some sense it will continue the way it was. I assume it will affect my influence on directions of computer science and in particular theoretical computer science...."
:03:34:		What are your life goals you want to achieve and how will you achieve them? "....In a sense I think I've achieved my life goals already, but this is not going to change my passion for science and the kind of problems I've been working on....There's something about writing and communicating that's important to me and I think that will definitely be in my future, having impact through writing rather than just doing research in the confines of my office...."
:04:39:		What led you to co-write one of the most influential papers in computer science, "Probabilistic Encryption," as a graduate student in 1983? What were your thought processes in introducing the question, "What is a secret"? "....I was a graduate student at Berkley. There were many courses offered on different areas of theoretical computer science and one of them was a course by Manuel Blum who was Silvio's and my advisor and the course was on Computational Number Theory....Throughout the course I loved the material and at the end of the course he told us about the RSA part, the algorithm or public encryption and he asked the question: 'How would you toss a coin over the telephone?'....This question about the combination of randomness and interaction between 2 people and how to leverage number theory or the complexity of number theory problems in order to emulate this kind of simultaneous coin toss even though we sit remotely — this whole combination of how you could utilize all of these ingredients to solve a real life problem. It was a very exciting question and from that point on I was really sold on that this is an area I wanted to work on.....How would you define secrecy? If you put the question of what were the thought processes the main thing is that we considered this question from a computational point of view...."
:11:33:		Can you provide details behind your approach, the simulation paradigm? "....When people say the simulation paradigm I think they mean two things. The simulation paradigm is a method and also a definition....The encryption system has some functionality to it and some security....What I described as a simulation paradigm is how you prove security by simulation, but the simulation paradigm has become not only a way to prove theorems but also a way to define security...."
:15:46:		How did your work lead to the construction of a secure encryption scheme? "....By way of coming up with the mental poker protocol we actually hit on a way to encrypt bits in a way that was extremely secure and in a way that satisfied the property that no partial information was leaked...."
:17:00:		Can you describe your notions of encryption security, for example semantic security and indistinguishability, and how these measures must be met for schemes to provide security across the wide range of cryptographic applications? "....These are two different definitions, but they turn out to be equivalent to each other....Why that provides security across a wide range of cryptographic applications is because it says that if you use this kind of encryption and it's indistinguishable regardless of whether you put in the encryption of M1 or encryption of M2 (since there's no way to distinguish), there would be no way to distinguish even in the context of plugging it into a cryptographic application. In a sense it's like an opaque envelope, you really can't tell apart its contents regardless of what the two different contents may be. Therefore even in the context of application you wouldn't be able to tell that apart...."
:20:25:		Overall, how did your work revolutionize the study of cryptography and lay the foundation for the theory of cryptographic security? "....It's much more exciting to talk about constructs. You can encrypt in a way that's secure — you can have identification protocols, multi-party protocols — but in order to do all that we really need new notions, new theory or what you call foundation. That is, you have to define things, like secrecy that we already talked about, you have to talk about randomness or pseudo-randomness, about knowledge, about fairness — all of these are notions which existed in the context of information theory....So we have to somehow define simultaneity in a different way in the physical world so we have to capture a mathematical definition for it and that is another part of the thing we do as part of the foundation of the theory of cryptography...."
:23:14:		Can you talk about your work with knowledge complexity, "zero-knowledge" proofs? "....It's kind of weird because usually when you think about mathematics and proofs you are trying to teach someone something; you want them to learn something. In the context of cryptography you want to convince parties of correctness of statement, but you don't want them to know anything else. You want them to believe you but you don't want to give them any extra information so it has the zero knowledge term. This interactive proof mechanism allows you to do that...."
:28:30:		What are the implications of this work? How does it extend to other domains and how does it impact us when we do things on the internet? "....One way to think about this work: as enabling secure communication in the sense of privacy....More generally, a lot of this work (the early work), has led to what's called the multi-party secure protocol....So we enable, not only to protect the privacy of communication between two people, but to compute on this information. (Highly non-trivial computations on information even though the information lies in the hands of different parties in different places on the internet in such a way that you are assured the information was computed correctly even though you were unable to see the information of the other people.) So we can compute on data without revealing it and that has wide-reaching applications. Most of them are not utilized yet but it really enables looking forward to the future for us to communicate better using the internet as a platform for further communication and further interaction without risk...."
:31:59:		What is the impact of your work on computational complexity? "....A few years ago I gave a talk and I entitled it "Cryptography and Complexity Theory, a match made in Heaven" - I really think it is a Match Made in Heaven. There's been a lot of transfer-over from cryptography to complexity theory....There are some notions that come up from cryptography that have become some of the bread and butter of a lot of theory of cryptography. The two compelling examples are interactive proofs and pseudo-randomness...."
:36:46:		Earlier in our discussion on the internet you talked about multi-party issues. Can you talk more about multi-party secure protocol, for example impact and scalability issues? "....The multi-party protocol essentially allows 'n' people with 'n' private inputs to compute any function that they desire on these inputs in such a way that in the end the functions are computed correctly, but the inputs are maintained private....There is some assurance of privacy and correctness of your data and has lots and lots of applications. There is question of scalability as you mentioned. When you talked about two people or small numbers this protocol is also very efficient and it can be used without any problem, but if you talk about the internet and large scale the efficiency degrades....It turns out that one of the most important scalability issues is how many people do I have to communicate with? This is the subject of current work actually, taking previous protocols and making them scalable...."
:39:47:		What can be done regarding one-time programs and obfuscation? "....These are two different problems. Obfuscation, I give you the program (you can run it forever), but I don't want you to be able to reverse engineer it. One-time program I give you a program and I only want to give you the ability to run it once or a limited number of times and then it should disappear. These are fascinating problems...."
:43:09:		Can you share your thoughts on probabilistically checkable proofs and how they were motivated by a cryptographic protocol having great impact on complexity proofs? "....As I said, interactive proofs can be generalized....What you want really to guarantee is that if there is a bug anywhere then with very high probability you will find it if you check enough locations. In fact what one can show is you only have to check a constant number of locations regardless of the size of the original proof in order to find a mistake. That's a probabilistically checkable proof...."
:46:07:		Can you talk about pseudodeterministic algorithms? "....Around the late 70s there were well-known algorithms by Solovay-Strassen and Rabin-Miller. They talked about how to use coins, tossing coins in order to solve problems quickly. The standing question is how to take advantage of coin-tossing. In fact we have a whole bunch of problems where we know how to solve them quickly if we can toss coins (if we can use randomized algorithms), but we don't know how to solve them quickly without randomization. The question is are these randomized algorithms as good as deterministic algorithms? One of the concerns is when you use randomized algorithms it could be that two different times you run it you get different answers. Both answers might be good but they're different....Pseudodeterministic algorithms are randomized (they are tossing coins so they might be able to run faster), but they have the guarantee at the end that they will come up with the same solution. They are pseudodeterministic but they look like they are deterministic because as far as you can tell you have no idea what is happening inside the program. All you can tell is that if you give it the same input, with very high chance it's going to give the same output...."
:49:12:		What are your current and future research interests? "....I am very interested in this pseudodeterministic algorithms right now, but in terms of the future another project that I'm engaged in and very interested in and more generally a lot of the work that we've done is about the power of interaction....Most of my work has this cryptographic setting. So what is it that you could do, how could you interact, how could you collaborate while maintaining privacy? I'm more interested in this question in a more fundamental sense....So I'm interested in studying this question and try it from a computational point of view. How can you argue mathematically and give evidence from the fact that collaboration and interaction are absolutely fundamental for making progress?...."
:50:46:		What do you see as the practical applications of this work — past, present and future? "....It's enhancing the ability to interact over the internet. To interact we need to collaborate remotely. It's putting forth new questions into this realm of research theoretical complexity theory or theoretical computer science. It's the best kind of research, at least from my point of view. It has clear implications and applications but it is also intellectually intriguing regardless of what technological platform you are working with...."
:51:37:		From a broader sense, can you forecast and describe the types of research being created or updated that will drive our experiences in ten years? What will this experience be like — paint a picture for our audience? "....The question of systems security....The whole question of quantum computations versus classical computations....Today since there are so many more challenges with the explosion of computers and the internet, people are going to get more and more ability so there will be more and more problems that are posed and therefore they are willing to assume a lot more about the hardness of problems, and the question is how far can that go? How do we trust the kind of assumptions we make?....The scalability question, we made these systems to work in practice on a large scale. We need new methods of computing on large data, which essentially won't touch the whole data but will just sample it....We aren't going to get something that is absolutely correct, but we are going to get something that is approximately correct and we need to trade-off the correctness with how much efficiency we can get...."
:55:16:		This is a somewhat related question. Shafi, you laid many of the foundational pillars in your pioneering work. Distilling from your experiences, what are the greater burning challenges and research problems for today's youth to solve to inspire them to go into computing? "....Data-driven research — that's fascinating. The whole question about can the data drive what we are going to ask is a fascinating question for young researchers....We have so much more data to make the world a better, more interesting place and a more scientifically richer place — we need to capitalize on that. Somehow we need to make it possible to capitalize on all this fantastic new ability in terms of who we can communicate with and what data we can reach without compromising our own individual security. I think that's a fascinating question for someone getting in the field....The question of scalability, the question of how to ensure that whatever we can do with this data can be done securely...."
:58:03:		What specific qualities make you excel and why? "....Both these properties are useful for me and probably useful for everybody and that is....not to be too narrow in your thinking....and to be persistent...."
:58:19:		Past, present, and future — who inspires you and why is this so? "....I would say I was inspired by my mentors, my colleagues and my students....Historical figures speak less to me — who inspired me are people who I was in contact with...."
:01:01:05:		Shafi had an amazing time in terms of her educational history for example, at Carnegie Mellon and then Berkeley and then at MIT and the Weizmann Institute. She talks about points of interest throughout that educational experience that were catalysts to inflection points in her lifetime of contributions.
:01:03:10:		Are there any additional insights that you would like to give to the audience in regards to your research or your personal life or some of the inspirations in your life or any broader questions or controversies? Any closing comments? "....I guess one of my conclusions is not allowing yourself to be restricted by the current rules of science or by the current dogma of which problems to work on and how to solve them is the right way to go. It was the right way for me and I would encourage people when they are graduate students, before they have selected their research program, to put some time into thinking what it is that they want to study and what’s interesting to them. It doesn't necessarily have to be what their advisor is doing or what all the other graduate students are doing, but really what they like and then give themselves that freedom of pursuing it...."
:01:04:46:		Shafi, with your demanding schedule, we are indeed fortunate to have you come in to do this interview. Thank you for sharing your substantial wisdom with our audience.