is competing for the project. The purchaser of digital content obtains a tag
permitting use of the content. The tag
is not tied to a machine identifier so
that the tag and use of the content can
be moved from machine to machine.
Coupled with robust content-identify-ing software, use of protected content
absent a corresponding tag is stopped.
The deployment of this robust solution to the piracy problem requires
the cooperation of system vendors.
More recently, I have become interested in protecting the privacy and
secrecy of auctions. Working with Stuart Shieber, David Parks, and Chris
Thorpe, we have a methodology that
employs cryptography to ensure honest privacy-preserving auctions. Our
protocols enable an auctioneer to conduct the auction in a way that is clearly
honest, prevents various subversions
of the auction process itself, and later
on, when the auction is completed
and the auctioneer has determined
the winner or winners and how much
they pay and how much they get of
whatever is being auctioned in multi-item auctions, the auctioneer can
publish a privacy-preserving proof for
the correctness of the result. In the initial papers, we used the tool of homomorphic encryption. Later on, I had
an idea that I then eventually implemented with Chris Thorpe and Rocco
Servedio of an entirely new approach
to zero knowledge proofs, which is
computationally very efficient, does
not use heavy-handed and computationally expensive encryption, and
achieves everything very efficiently by
use of just computationally efficient
hash functions.
teachers, teaching, and Research
In the life of every creative scientist,
you will find outstanding teachers
that have influenced him or her and
directly or indirectly played a role in
their success. My first mentor was a
very eminent logician and set theorist, Abraham Halevi Fraenkel. I wrote
a master’s thesis under the direction
of the wonderful algebraist Jacob Lev-itski. He was a student of maybe the
greatest woman mathematician ever,
Emmy Noether, the creator of modern
abstract algebra as we know it. In Jerusalem, I learned applied mathematics from Menachem Schiffer, a great
Powerful algorithms
are enabling
tools for every
computer innovation
and application.
mathematician and a great teacher.
Shasha: Let’s talk a little bit about
the relationship that you’ve mentioned to me often between teaching
and research, because you’ve won
many awards for teaching as well as
for science. How do you think academics should view their teaching responsibilities?
Rabin: This is really a very important
question. There is this misconception
that there is a conflict and maybe even
a contradiction between great teaching and being able to do great science.
I think this is completely incorrect,
and that wonderful teaching, such as
Schiffer’s teaching, flows from a deep
understanding of the subject matter.
This is what enables the person also
to correctly select what to teach. After all, the world of knowledge, even
in specialized subjects, is almost infinite. So one great contribution is to
select the topics, and the other great
contribution is to really understand
the essence, the main motifs, of each
particular topic that the person presents, and to show it to the class in a
way that the class gets these essential
ideas. Great teaching and great science really flow together and are not
mutually contradictory or exclusive of
each other.
the future
Shasha: You have contributed to so
many areas of computer science. Talk
about one or many, and where do you
think it is going?
Rabin: Computer science research
has undergone a number of evolutions
during my research career, and be-
cause of the quick pace, one can even
say revolutions. To begin with, there
was Alan Turing’s model of a comput-
ing machine, leading to the stored-
program computer. Next there was a
great emphasis on the study of vari-
ous mathematical machines. Finite
automata are models for sequential
circuits. Nondeterministic and deter-
ministic so-called pushdown autom-
ata play a pivotal role in the syntactic
compilation of programming languag-
es. For about 20 years or so, there was a
great emphasis in research on autom-
ata, programming languages, and for-
mal languages, also in connection of
course with linguistics. There was also
a considerable emphasis on efficient
algorithms of various kinds. The book
by Alfred Aho, John Hopcroft, and Jeff
Ullman, and Donald Knuth’ classical
books are examples of this strong in-
terest in algorithms. The study of al-
gorithms will always remain centrally
important. Powerful algorithms are
enabling tools for every computer in-
novation and application.
