アンドリュー・チーチー・ヤオ

計算と通信の革新的な基礎理論の構築により、情報科学における新たな潮流を作り出し、暗号や  量子計算などの最先端研究にも多大な貢献を果たすとともに、セキュリティ、秘密計算やビッグデータ処理などの現代社会における実問題にまで影響を与え続けている。

アンドリュー・チーチー・ヤオは、計算と通信の革新的な理論モデルを発案し、現代の計算理論の潮流を築き、通信の観点から計算理論の体系を革新し、セキュリティ、プライバシー、並列計算、量子計算など、情報科学に大きな波及効果を与えた。

ヤオは、1977年、計算アルゴリズムによる問題解決を、敵対関係にある競合的2人ゲームとする解析モデルを提案し、乱数を用いる計算のアルゴリズム性能限界に関するヤオの最小最大原理を確立した(1)。1979年、2人の計算者が通信して協調計算するモデルを考察し、計算問題の難しさを通信量で測る「通信複雑度」を提唱し、その解析法を与えた(2)。この新概念は、独創的で、回路計算量、並列・分散計算、ストリーム計算など、多くの重要なモデルの理論基盤を与え、近年の計算量理論の飛躍的発展の多くがこの理論による。

ヤオの研究は、その後、通信の安全性やプライバシーに関する理論に展開し、1981年、公開鍵暗号による情報通信システムに対し、理論的な安全性を定義し（ドレフ-ヤオのモデル）、通信手法の安全性の判定における基準理論を与えた(3)。また、1982年、シャノンの通信量の理論や通信の安全性の理論を拡張し、計算量的エントロピーの概念を導入して一方向性関数 を用いたセキュリティの安全性を定量化し、暗号理論や擬似乱数生成における計算論的な検定法（ヤオの検定）を与えた(4)。

さらに、通信による安全な計算プロトコルモデルを考察し、個々の情報のプライバシーを保ちつつ、敵対者を含む多人数で安全に計算を行う秘密計算法を提唱した(5)。ここでは「2人の富豪が財産を開示せずに、どちらがより大きな財産を所有しているかを判定する」、いわゆる、ヤオのミリオネア問題を設定し、情報プライバシーと安全性に対する厳密なモデルを構築し、セキュリティ分野の金字塔となっている。

ヤオは、これらの研究で、電子商取引や暗号資産など、現代社会にとって必須の概念やモデルを提供した。さらに、ヤオが提案した量子通信複雑度の概念とそれに基づく新原理は、量子コンピュータ の能力の定量評価を可能としている(6)。ヤオによるこれら一連の業績は、情報科学分野に多大な影響と波及効果を与えており、京都賞の授賞に誠に相応しいものである。

以上の理由により、アンドリュー・チーチー・ヤオに先端技術部門における第36回（2021）京都賞を贈呈する。

参考文献
(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.