Achievement Digest

Pioneering Contributions to a New Theory of Computation and Communication and a Fundamental Theory for Its Security

Andrew Chi-Chih Yao created new trends in computer science and made a great contribution to cutting-edge research in various areas, especially in security, secure computing, and quantum computation through establishing innovative fundamental theories for computation and communication. His achievements are continuing to influence current real-world problems such as security, secure computing, and big data processing.

Achievement

Andrew Chi-Chih Yao has constructed innovative theoretical models for computation and communication, creating trends in modern computational theory that have revolutionized computational theory from a communications perspective. Further afield, Yao’s research has influenced cutting-edge computer science in multiple fields, including security, privacy, parallel computing, big data processing, and quantum computing.

In 1977, Yao first established a principle in problem solving by a computational algorithm, known as Yao’s minimax principle, as the basis of worst case complexity of randomized algorithms in comparison with deterministic algorithms using von Neumann’s minimax theorem (1). In 1979, Yao presented a model in which two persons perform cooperative computation through communication and introduced the concept of communication complexity, a measure of the difficulty of a computational problem in terms of the communication load (2). Furthermore, he provided a novel method for its analysis. The theory of communication complexity was a highly original, new concept that sent strong ripples through the computational theory research community, providing a theoretical foundation for many important models such as circuit complexity, parallel and distributed computing, data structures and stream computing. As such, Yao’s work has inspired many recent breakthroughs in computational complexity theory.

Subsequently, Yao’s research has evolved into theories that consider the security and privacy of communications. In 1981, he contributed to a theoretical definition of complete security (i.e., the Dolev-Yao model) for information and communication systems using public-key cryptography, which was being increasingly utilized around the early 1980s, and provided the standard model of evaluating the security of communication methods (3). In 1982, building on computational aspects, he introduced computational entropy into Shannon’s theory of communication quantity and the theory of communication security (4). He then applied this concept to quantify the safety of security using unidirectional functions, thereby providing a computational method for testing (Yao’s test) pseudo-random number generation, which bears significance for cryptography and computational theory.

In addition, he examined a mathematically complete model for communication-basedsecure computation protocols, and proposed an innovative secure computational method facilitating secure computation by many individuals, including adversaries, while preserving the privacy of the information pertaining to each individual (5). Here, using insights into so-called Yao’s millionaires’ problem, in which “two wealthy people determine which of them owns the larger fortune without disclosing their wealth to each other,” he presented a rigorous model of the conditions that must be satisfied to ensure information privacy and security. Remarkably, this model illustrated the principles of secure computation with an efficiency approaching that of a single binary circuit. This was a landmark achievement in the field of information security.

Yao’s work has provided essential concepts and models that play a vital role in modern society. These concepts and models are most evident in areas in which many parties collaborate or confront each other to solve social problems over networks, such as in e-commerce and crypto-asset management. Moreover, Yao’s concept and principle of quantum communication complexity enable quantitative performance evaluation of quantum computing (6). These achievements have a great impact and ripple effect on the information science field, and therefore Yao truly deserves the Kyoto Prize.

References

(1)  Yao AC-C (1977) Probabilistic computations: Toward a unified measure of complexity. In Proceedings of IEEE 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), IEEE: 222–227.

(2)  Yao AC-C (1979) Some Complexity Questions Related to Distributive Computing (Preliminary Report) In Proceedings of the 11th Annual ACM Symposium on Theory of Computing (STOC ’79), ACM: 209–213.

(3)  Dolev D & Yao AC-C (1983) On the security of public key protocols. IEEE Transactions on Information Theory 29 (2): 198–208.

(4)  Yao AC-C (1982) Theory and Applications of Trapdoor Functions. In Proceedings of IEEE 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), IEEE: 80–91.

(5)  Yao AC-C (1982) Protocols for Secure Computations. In Proceedings of IEEE 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), IEEE: 160–164.

(6)  Yao AC-C (1993) Quantum Circuit Complexity. In Proceedings of IEEE 34th Annual Symposium on Foundations of Computer Science (FOCS 1993), IEEE: 352–361.