Thirty years have passed since the concept of ‘secure computation’, now known as ‘secure multiparty computation’, first appeared in the computing literature. The proposal that any function which involves inputs held privately by different parties can be computed securely without revealing much about the inputs, must have seemed unlikely or even paradoxical to some. One of the examples given, nick-named the ‘millionaires’ problem', where two rich people wish to find out who is richer without giving out clues on their actual worth, stood as a faithful representative whose solution still seems to bemuse newcomers to the field today.
In the three decades since, many brilliant scientists have contributed to the development of secure multiparty computation, turning it into an active research area and often an important showcase for modern cryptography and complexity theory, with no sign of abating anytime soon.
The current book, edited by two leading researchers Manoj Prabhakaran and Amit Sahai, does a wonderful job of weaving a compelling story out of the subject matter. The collection features writings by a galaxy of intellectual luminaries who have made landmark contributions in moving this field forward. The eight chapters cover foundational material in multiparty computation and related topics, leading to more advanced discussions on selected topics and special techniques, culminating in some novel approaches at the current frontier. There is no doubt that this monograph will become a definitive work which will prove equally valuable as a textbook for the novices and as a reference for the experts.
Nothing lives in a vacuum. The birth and development of secure multiparty computation was influenced heavily by two revolutionary trends which emerged in the late 1970's. The first was the transition from single stand-alone computing hardware to the networked computing paradigm. The second was the realization that cryptography would play a vital role in the future networked world and, to meet this challenge, cryptography must suitably integrate the dual pillars of information science – Shannon's information theory and Turing's complexity theory. These two trends powered the tremendous developments in a multitude of information sciences and technologies, both theoretical and practical. Indeed, one can sense that the intellectual depth and breadth of these trends have provided the fertile soil from which secure multiparty computation has blossomed as a scientific field.
Despite all the impressive advances, we are still far from having a complete understanding of cryptography in general, and secure multiparty computation in particular. We comprehend secure computation very well in the case of standalone computation, but the highly interactive environments still remains somewhat elusive. To get a complete grasp on the latter may require a thorough scientific understanding of the concept of information and how it is transmitted and propagated. In this regard, the phenomenal successes achieved by Shannon's information theory may have inadvertently left information scientists more complacent than justified. Great challenges still await the ambitious. I believe that future great sciences will flow from various sources such as a fuller integration of information theory and complexity theory, further expeditions of highly interactive environments, and from new frontiers such as quantum information theory. The present book serves very well as a great starting point for an adventure into this wonderful world.
Finally, I would like to thank the editors Manoj Prabhakaran and Amit Sahai for inviting me to write this Foreword. Grateful to be regarded by some as the initiator of the secure multiparty computation area, I have taken great pleasure in reading through this book and finding inspirations chapter after chapter. I trust that many readers will be similarly enlightened by this outstanding book.
Andrew Chi-Chih Yao
July 2012, Beijing