Michael O. Rabin

Thomas J. Watson, Sr. Professor of Computer Science

Professor Rabin studies the theory and application of computer algorithms. His special interests are the applications of randomization in computations, cryptography, computer security, and parallel systems.

Parallel computing has become an indispensable tool for the solution of very large scientific-engineering and dataprocessing problems. The availability of mass-produced and very powerful microprocessors has made the realization of massive computing power and data-storage capabilities through harnessing together many workstation boards or personal computer boards a feasible and economic possibility. Professor Rabin and associates have buit, in the years 1995-1998, the MCB system, a software environment for enabling the execution of large dataprocessing tasks on a cluster of workstations or personal computers. With MCB, the cluster provides the user with an image of a single, super-large computer on which the user can run standard database and transaction-processing programs without any change. In addition to massive computing power and data storage and transfer facilities, MCB provides for work-load balancing and high fault-tolerance.

Currently used encryption methods are based for their security on unproven assumptions such as the intractability of the factorization of large integers into prime factors. In recent years Rabin, with Y. Aumann and Y.Z. Ding, have produced Hyper-Encryption, the first ever provably unbreakable encryption method ensuring everlasting secrecy against a computationally unbounded adversary. This was done within U. Maurer's bounded storage model which postulates the availability of a public stream of random bits too copious to be stored in its entirety by the adversary. We continue at Harvard work on reducing the size of the Hyper-Encryption keys and creating useful cryptographic protocols based on Hyper-Encryption.

In the past two years we have developed a new model for the implementation of Hyper-Encryption. A p2p network or some community of users creates a Virual Satellite. Each node stores and updates a large number of random bytes pages. A Sender S and Receiver R initially share a random key which they employ to access a randomly chosen node and request a randomly selected random page from that node. S and thus create a trove of common random pages which they employ to create common random one-time pads. These pads are later used for secure encryption. The system has been implemented in Java and is ready for deployment..

Truly random bits have myriad applications to cryptography, monte-carlo computational methods, and network routing. Togther with W. Yang and H. Rao, we have developed a micro-chip employing particle radiation to generate copious streams of physically random bits.

Professor Rabin continues to work on creating efficient algorithms for problems in algebra, number theory, data structures, and combinatorics. In addition to their theoretical interest, many of these algorithms have practical significance.

See also: CV + publications