Google Research

Michael O. Rabin

Michael O. Rabin got his M.Sc. from the Hebrew University and his PhD from Princeton University, where he had his first academic appointment. Later he was visiting member of the Institute for Advanced Study, interacting with K. Godel. He was Albert Einstein Professor of Mathematics at the Hebrew University, serving as its Rector (Academic Head) from 1972 to 1975.

At various times he held Visiting Professorships at Yale University, the Weizmann Institute, the Israel Technion, UC Berkeley, MIT, University of Paris, the Courant Institute of Mathematics, Caltech, ETH Zurich, Columbia University, and Kings College London. He was Saville Fellow at Merton College, Oxford, and Steward Fellow at Gonville and Caius College, Cambridge. From 82 to 94 he served on the IBM Science Advisory Committee. In Spring 2009 he was Visiting Researcher at Google His contributions were recognized by awards including:

  • The ACM Turing Award in Computer Science
  • The ACM Kanellakis Theory and Practice Award
  • The Rothschild Prize in Mathematics
  • The Weizmann Prize in Exact Sciences
  • The IEEE Charles Babbage Award
  • The Harvey Prize for Science and Technology
  • The Israel Prize in Computer Science
  • The EMET Prize in Computer Science
  • IACR Fellow

Rabin was elected as member or foreign honorary member to academies including the US National Academy of Sciences, the French Academy of Sciences, the American Academy of Arts and Sciences, the American Philosophical Society, the Israel Academy of Sciences and Humanities, and Foreign Member Royal Society. He holds honorary degrees from New York University, Haifa University, the University of Bordeaux I, Israel’s Open University, Ben Gurion University, and the University of Wroclaw.

Rabin’s research interests include complexity of computations, efficient algorithms, randomized algorithms, DNA to DNA Computing, parallel and distributed computation computer security, cryptography and financial cryptography.

In recent years he has created, with Y. Aumann and Y.Z. Ding, Hyper-Encryption, the first ever encryption scheme provably providing everlasting secrecy against a computationally unbounded adversary; invented, with S.Micali and J. Kilian, Zero Knowledge Sets, a new primitive for privacy and security protocols; invented and implemented, with W. Yang and H. Rao, a micro chip for physical generation of a strong stream of truly random bits. Hyper-Encryption has been implemented at Harvard and MT via a novel limited access model. Most recently he has innovated practical ZKPs applicable to auctions and other financial processes.

Interviewed by Leslie Yeh Johnson, University Relations, Google

LYJ: How do you find interesting problems to work on?

MR: The problems that excite me most are those which are at the front line of computer science. The process of finding frontiers is really very mysterious and I cannot explain it. It is inspiration, in some sense – but the excitement and the rewards are great.

Let me give you an example: my interest in computer science began before the existence of computer science as a recognized field, when I read Alan Turing’s works on computability. I realized that computing technology was emerging, mainly at IBM and at the Moore School of Electrical Engineering. I realized there is technology which requires a scientific foundation, so to speak. And that Turing’s work, the Turing Machines, were the abstract model for modern computers. All the features of the von- Neumann architecture are already present in Turing’s work. So one of the first things I did was to say that Turing defined the difference between what is computable and what is non-computable. However, there was no discussion of the so-called difficulty of computation; Turing had no hierarchy of things which are easier to compute, and things which are harder to compute. One of my first works defined the notion of difficulty of computation, and gave examples of computational problems which, while according to the Turing definition are computationally solvable, are very, very difficult and would require very large resources to solve. It was a situation where you had the practical field of computing, but there was a definite need for a more theoretical foundation of study.

LYJ: What would you say are the frontiers you're looking at now?

MR: At Harvard we have a very good team of people who are looking at the interface between e-commerce and computation. About three years ago, Stuart Shieber, David Parkes and Christopher Thorpe were looking at auctions – Shieber came to me and suggested that there ought to be applications of cryptography to this field. Together we wrote the first paper: Parkes, Shieber, Thorpe, and I, which gave one method for implementing secrecy-preserving proofs of correctness, or integrity of announced results of auctions. Why is that useful? In repeated auctions, where the same group of people or commercial entities are bidding for similar items, they don’t want their bidding strategy and the values they assign to the auctioned goods to be divulged, because if competitors know how high you're bidding, then the next time around, they will be able to more efficiently compete against you. So, we have these two conflicting interests. On the one hand, if I was a participant in an auction, I would like to be reassured that the announced results are really in accordance with the bids submitted and with the published rules of the auction. At the same time, everybody wants bids to remain secret. So, in that paper, we were able to suggest one method for doing it. These secrecy-preserving proofs are a special case of so-called “zero-knowledge” proofs, which enabled one to prove the correctness of a certain statement, or to prove knowledge of a solution to a certain problem without revealing anything beyond the claimed correctness; hence its paradoxical name, “zero-knowledge”. However, zero-knowledge proofs are not really applicable in most cases to real-life problems because of their complexity. So, we wrote a paper together with Chris Thorpe and Rocco Servedio with a highly practical way of doing these zero-knowledge proofs for financial processes such as auctions, and other financial transactions. That’s an example of things which are lying at the absolute frontier of computer science.

LYJ: It sounds like some of your inspiration is rooted in what’s happening today in related areas, such as finance.

MR: That is true; that is an interesting observation. My work on complexity of computations, which I called difficulty of computing function, was really rooted in the emergence of computer technology, and a need to define the inherent difficulty involved in computation processes. However, when I was looking at primality testing, the order of events was really the converse of what you describe... Strassen, Solovay and I independently came up with the idea of using randomness to test large integers for being prime, and that was later used, i.e. very large prime numbers were later used and deployed in modern cryptography such as for RSA encryption and all the related developments. So here was a purely, at the time, theoretical contribution, which within a year and half or so bore some very practical fruit.

LYJ: I think that really speaks to approaching research in two directions: one is directly enabling the practical application, and the other is solving an interesting problem and believing that somewhere it will become useful.

MR: So I have a surprising example of that phenomenon. There is a classical theorem by Lagrange that every integer, every natural number, is expressible as a sum of four squares of numbers, of integers; and that was actually announced by Fermat in maybe 1650, and was proved by Lagrange, in the first published proof, in 1770. Now, his proof is purely existential. He proves the existence but gives no practical way of finding their representation. In 1977, I found again a randomized algorithm for efficiently computing the sum of four squares representation. In the work with Chris Thorpe and Rocco Servedio, we found an application of that algorithm to those proofs of correctness of the announced results of an auction. So there, the issue was to prove that a certain number is, say, positive, or that of two numbers, x and y, x is greater than y, which amounts to showing that x minus y is positive, and we did that by showing that the number in question is the sum of four squares, and consequently, is positive. That algorithm, in other words, The of Fermat –Lagrange theorem dates way back, and about 200 years later it was extended by a very practical, very fast algorithm for actually doing the sum of four squares in presentation, which subsequently found an application to this very down-to-earth area of auctions.

LYJ: What did you do at Google, and how might this affect your curriculum?

MR: Google was interested in these applications to auctions; everyone knows that Google is conducting very many auctions every second, selling those slots for ads. Now Google is moving into new areas in selling advertisements by Vickrey auctions. They are considering using the technology of secrecy preserving proofs of the integrity of announced auction results. I came to Google and worked on that. One of the challenges is fitting our technology into the very tight time bounds and storage space bounds that the Google technology must respect. In these new auctions, the auction itself has to be conducted and completed within a fraction of a second. The proof of correctness is going to be given later only upon demand; in other words, not every auction being conducted is going to be accompanied by a proof of integrity, but while the auction is being conducted, sufficient information to allow this new method of proving it – the integrity – has to be supplied and stored. That was a challenge we were able to meet. I worked with really wonderful people; we would discuss these problems very intensely, and we would talk often with the people developing the new ADX (Ad Exchange) system. My close cooperation at Google was with Yishay Mansour, Muthu Muthukrishnan and Moti Yung. I had instructive conversations with Corinna Cortes, Eyal Manor, Alfred Spector, Scott Spencer, and Hal Varian as well as with many other Googlers. Altogether, my stay at Google was an exciting learning and research experience.

Every two or three years I teach a cryptography class, in which I cover the basic material – public key cryptography, digital signatures, and so on – and now I'm going to have a very extensive discussion of financial cryptography, and these new, practical zero-knowledge proofs.

LYJ: What would you challenge Google to do in research?

MR: Google is an incredibly exciting, innovating environment. Among other things, I was very impressed by the enthusiasm there, and the strong sense of identification with the enterprise. This is very, very obvious. Google is deeply immersed in search engines and the commercial aspects of selling advertisements, and the question is: what will be the next big thing for Google? There is no doubt that the coming decade is going to be the decade of communications, information databases, and search engines. There are going to be developments in hardware, software, programming languages... and with regard to communications itself, maybe the internet is going to become ten times or a hundred times faster than it is now – all this is all going to happen, and it’s not going to be that major.

So let me mention a couple of big areas.

One is medical records. The time is going to arrive when our medical records are going to be stored online somewhere and available from anywhere, upon permission, to be used for diagnosis, treatment, and so on. This is going to be enormous. In certain countries, for example in Denmark, there is already such a universal medical record system. In England, it was tried and, for various reasons, was not a full success. The approach in the United States, despite Barack Obama’s announcement that we should aim for computerization, is piecemeal, doesn’t look very uniform, and is going to be cumbersome, but eventually, it is going to be universal. It raises really interesting challenges and interesting commercial opportunities. And this is where I come in: one big issue around these medical records and other personal information is going to be the maintenance and protection of privacy. So some of these technologies that we were talking about – accessing information and, at the same time, maintaining privacy – are going to be very prominent.

Another big area is going to be online and remote education. I'm talking about higher education, university education. Several universities have tried it, and do actually offer courses, but it is not really online in most cases. I taught a course on cryptography twice at Columbia University, and they have a very profitable system of remote learning, but my lectures were videotaped and even the tape was physically sent, or maybe people got it online and then they listened to the lecture and they solved the problem sets, sent those solutions in, and we had teaching assistants who graded those problems. The existing technology of online conferences, which is very extensively and successfully used within Google, is still not completely satisfactory. Somehow it doesn’t give you that natural feeling that you and I have as we sit here and converse. Online, you are acutely aware that you are not really together. Now, I'm sure that with advances in image processing, in communications, and with much higher bandwidth, you will be able to create a distributed classroom so some of the students can sit here at Harvard or at MIT with the teacher, and other students can sit in Philadelphia, but they’ll all experience it as if they are sitting among their fellow students. There are many technological challenges involved in getting to that point, but in view of the high value of higher education, and the high value of high-quality higher education, this is going to be a very worthwhile project to pursue.

LYJ: What advice would you give to young computer science students?

MR: My advice is, of course, colored by my interests and also by my experience. I'd say the same thing to a young person getting into music, or medicine: “Practice, practice, practice.” For young students, especially undergraduates, and even graduate students, another piece of advice is: “Algorithms, algorithms, algorithms,” because at the foundation of every successful computing application and technology, a suite of very efficient and powerful algorithms will be the enabling substructure for everything. And then, I come back to what I consider to be the exciting avenues for the future and they have to do with this world of the internet, of enormous databases, searches, and their application.

LYJ: Can you share with us some surprising information about yourself that people might not know?

MR: Everyone who broached that subject with me in the past was sorry for asking! I became interested in mathematics almost by accident when I was eleven or twelve years old. Until then, I imagined myself going into microbiology. But one day I was kicked out of class, and I saw two fellows who were in ninth grade who had a free hour and were sitting in the corridor solving geometry problems. So I asked them, “What are you doing?” and they said they had to prove such and such a statement in Euclidean geometry. They contemptuously asked me: “Well? Can you do it?” so I looked at the problem – lo and behold, I was able to prove what they had to prove! The fact that by pure thought you can prove statements about circles and distances struck me. It was so beautiful, and at that moment I decided I wanted to be a mathematician. The surprising fact is that now, many, many years later, I still maintain that enjoyment and enthusiasm for the fields of mathematics and computer science.