姚期智
Andrew Chi-Chih Yao

第36回(2021)受賞

先端技術部門

情報科学

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

/  コンピュータ科学者

1946 -

清華大学 学際情報学研究院 院長

業績ダイジェスト

計算と通信の新たな計算理論とそれに基づく安全性の基礎理論への先駆的貢献

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

業績

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

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

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

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

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

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

プロフィール

略歴
1946年
中国上海生まれ
1972年
ハーバード大学 物理学博士
1975年
イリノイ大学アーバナ・シャンペーン校 コンピュータ科学博士
1975–1976年
マサチューセッツ工科大学 数学科 助教
1976–1981年
スタンフォード大学 コンピュータ科学科 助教
1981–1982年
カリフォルニア大学バークレー校 コンピュータ科学部 教授
1982–1986年
スタンフォード大学 コンピュータ科学科 教授
1986–2004年
プリンストン大学 コンピュータ科学科 教授
2004年–
清華大学 高等研究センター(現 高等研究院) 教授
2005年–
香港中文大学 博文講座教授
2011年–
清華大学 学際情報学研究院 院長
主な受賞・栄誉
1987年
ジョージ・ポリア賞
1996年
ドナルド・E・クヌース賞
2000年
ACM A・M・チューリング賞
会員
計算機協会、国際暗号学会、台湾中央研究院、中国科学院、 米国科学アカデミー、米国科学振興協会、米国芸術科学アカデミー

プロフィールは受賞時のものです