2000 Andrew Yao —— 姚期智：偽隨機與百萬富翁的秘密#

「兩位富翁想比誰有錢，卻都不想讓對方知道自己的財產。 這個聽起來像腦筋急轉彎的問題，成為現代密碼學的基石。」

案件檔案#

前因#

1980s 初，密碼學有了公鑰革命（2015 案），但缺兩樣東西： 偽隨機的理論（金鑰從哪來才夠「隨機」？）與 安全計算的一般定義（「安全」到底是什麼意思？）。 Blum（1995 案）已給出不可辨識性的語言，Yao 將其建成 完整大廈。

線索與推理#

線索一：百萬富翁問題（1982）#

姚的開場問題：A、B 各有 x、y，能否在不洩漏數值的前提下 比較 x 與 y 的大小？

姚的電路方案：把比較寫成布林電路，
以加密的「亂碼電路」（garbled circuit）讓對方求值
而看不到中間值
⟹ 安全兩方計算（secure two-party computation）的第一個一般解

一般化後的驚人定理（姚氏 1982/86）：

任何可計算的函數 f，都可以由互不信任的各方安全地 共同計算——只要存在陷門置換。

「比大小、投票、拍賣、訓練模型」全部納入此框架。

線索二：姚氏原理（Yao's Principle, 1977）#

隨機演算法最壞情況期望成本的下界技巧：

確定性最優對隨機分佈的期望成本
  ≥ 最優隨機演算法的最壞情況成本（反了？不，這是 min-max）

  min_R max_x E[cost(R,x)] = max_μ min_x E_μ[cost(D,x)]（近似對偶）

用博弈論的 min–max 定理證明隨機演算法的下界—— 巧妙化簡難題的經典範例（影響所有教科書的下界章節）。

線索三：偽隨機性三部曲#

1. Yao（1982）：若存在單向函數，則存在偽隨機生成器
   PRG：種子 s（n 位）→ 輸出 G(s)（多項式長），與真隨機
       計算上不可辨識
2. 拉長定理：小幅拉長（n → n+1 不可辨識）可複合為任意拉長
3. 隨機性 vs 計算：真隨機可能不存在，但「對多項式時間
   觀察者的隨機」可合成 —— 哲學上意義深遠

線索四：Dolev–Yao 模型（1983）#

把攻擊者建模為「只能攔截、拼接、重加密訊息的多項式 時間程序」——協議安全的形式化模型，成為協議驗證 （model checking 對密碼協議）的標準出發點。

理論評析#

姚氏的統一母題：計算受限的觀察者。物理隨機、 資訊論安全太奢侈；改問「多項式時間的敵人能否區分」， 一切複雜度假設立即兌換為安全保證——與 Blum（1995 案）、 Goldwasser–Micali（2012 案）構成同一學派的三角。

後果#

• 姚班（清華 2004 創立）與姚期智回國任教，重造中國 理論計算機科學人才鏈。
• 安全多方計算（MPC）在 2020s 從理論走向聯邦學習、 隱私計算的實業化。

關聯案件#

→ 1995-Manuel-Blum與計算不可辨識及密碼學、2012-Goldwasser-Micali與零知識證明、1982-Stephen-Cook與NP完全性理論