姚期智 百万富翁 问题 ：大 数据 时代 ，如何 保护 个人隐私？ Yao Zhizhi Millionaire Problem: How to protect personal privacy in the age of big data?

各位 同學 大家 好 我 是 李永樂 老師 各位 同學 大家 好 我 是 李永樂 老師 在 上 一回 咱們 講零 知識 證明 的 時候 留 了 一個 思考題 說 有 兩個 百萬富翁 想 比較 彼此 的 財富 誰 多 誰 少 但是 誰 都 不想 公開 自己 的 真實 財產 有沒有 什 麽 辦法 呢 今天 我們 來講 一講 這個 問題 這個 問題 是 一個 計算機科學 的 問題 我們 稱之為 百萬富翁 問題 這個 百萬富翁 問題 呢 在 現在 的 生活 中 已經 越來越 有用 了 我們 來講 一講 這個 問題 它 是 誰 提出 的 呢 它 是 在 這個 1982 年 的 時候 由 著名 的 計算機 科學家 姚期智 提出 的 大家 聽說 過 姚期智 的 名字 嗎 如果 你 沒聽說過 的話 有沒有 聽說 過 清華大學 姚班 呢 就是 以 姚期智 的 名字 命名 的 姚期智 1946 年 的 時候 出 生於 上海 後來 在 臺灣大學 物理系 獲得 了 學士學位 到 美國 的 哈佛大學 獲得 了 物理學 的 博士學位 再 後來 在 MIT 斯坦福 還有 UC 伯克利 教 計算機 在 2000 年 的 時候 由於 姚期智 在 計算機 方面 的 貢獻 而 獲得 了 圖靈獎 圖靈獎 我們 講過 是 這個 計算機 界 的 諾貝爾獎 我們 國家 就 只有 一個 人 獲得 過 圖靈獎 那 就是 姚期智 姚期智 也 是 美國科學院 臺灣 中央研究院 還有 中國科學院 的 院士 好 那 麽 姚期智 在 1982 年 這篇 論文 裏面 就 提出 這樣 一個 問題 他 說 有 A B 兩個 富翁 這個 A 和 B 兩個 富翁 他們 的 資產 都 可以 近似 為 一個 整數 說 A 他 的 資產 是 i 億元 這個 i 是 一個 整數 然後 這個 B 他 的 資產 是 這 j 億元 j 億元 j 也 是 個 整數 i 和 j 都 介於 0 到 10 之間 是 一個 0 到 10 之間 的 整數 然後 他們 兩個 就 說 我們 兩個 想 比較 一下 誰 錢 多 誰 錢 少 但是 我們 都 不想 讓 對方 知道 我們 自己 的 錢 有沒有 什 麽 辦法 呢 這 姚期智 就 提出 了 一種 辦法 我們 先 用 一個 例子 來 打個比方 說明 一下 姚期智 的 這個 思路 是 什 麽 說 這 兩個 百萬富翁 他們 商量 好 說 我們 要 通過 一個 規則 比較 彼此 的 財富 誰 也 不許 作假 但 在 這個 過程 中 我們 每個 人 都 不 告訴 對方 我們 有 多少錢 怎 麽 辦 呢 我們 可以 這樣 看 首先 我們 先 拿 10 個 箱子 這 10 個 箱子 帶鎖 我 先畫 10 個 箱子 好 了 10 個 箱子 畫完 了 這 10 個 箱子 都 是 帶鎖 的 這個 A 就 我們 剛才 說 的 那個 資產 為 i 億 的 這個 人 他 是 有 鑰匙 的 所以 他 可以 鎖上 這個 箱子 也 可以 把 這個 箱子 給 打開 而 B 這個 百萬富翁 這個 B 他 沒有 鑰匙 但是 他 可以 鎖上 那個 鎖頭 你 一扣 不 就 鎖上 了 嗎 所以 他 雖然 沒有 鑰匙 他 還是 可以 鎖上 的 好 現在 這 兩個 人 就 開始 做 這個 事 了 怎 麽 做 呢 首先 這個 A 他 不是 資產 是 i 億元 嘛 他 先 找到 第 i 個 箱子 比如說 這個 吧 這個 就是 第 i 個 箱子 然後 他 就 把 i 個 箱子 之前 所有 的 箱子 裏面 放 一個 紙條 寫 的 0 所有 的 箱子 都 寫 0 到 了 第 i 個 箱子 開始 他 就 寫 1 寫 1 1 1 1 放個 紙條 然後 把 箱子 全都 鎖上 全都 鎖上 了 之後 他 就 出來 跟 B 說 說 你 過去 吧 你 去 看吧 這個 B 進來 之後 面對 10 個 箱子 10 個 箱子 全是 鎖上 的 B 一個 也 打不開 對 不 對 所以 B 根本 不 知道 裏邊 寫 的 是 什 麽 他 如果 打開 的話 一看 前面 是 0 後面 是 1 他 就 明白 了 你 的 資產 就 應該 是 這個 是不是 1 2 3 4 5 6 你 應該 就是 6 億元 現在 我 打不開 我 就 不 知道 那 怎 麽 辦 呢 B 說 這樣 我 也 找 我 自己 的 資產 比如說 我 的 資產 是 4 億元 是 j 是 吧 我 第 4 個 j 等於 4 是不是 剛才 說 這個 i 等於 6 如果 我 的 資產 是 4 億元 那 這樣 我 就 把 這第 4 個 箱子 給拿 出來 我 把 它 拿 出來 給 A 我 打不開 但 我 可以 拿 出來 剩下 這些 個 箱子 我 全都 燒掉 我 全都 燒掉 你 也 不要 管 我 拿 的 是 第幾個 箱子 反正 我 都 燒掉 了 都 燒掉 了 之後 A 面對 這個 B 拿 出來 的 箱子 A 根本 不 知道 這拿 出來 是 第幾個 箱子 但是 A 有 鑰匙 A 可以 把 它 打開 所以 A 就 把 它 打開 了 打開 了 之後 就 面臨 兩種 可能 第一種 可能 是 什 麽 呢 第一種 可能 是 這個 箱子 裏面 是 0 箱子 裏邊 是 0 這 說明 了 什 麽 這不 就 說明 這個 j 它 是 小於 i 的 嗎 是不是 也 就是 第一個 富翁 他 比較 有錢 第二個 富翁 比較 沒 錢 對 不 對 但是 也 有 可能 打開 之後 裏邊 字條 是 1 如果 裏邊 字條 是 1 說明 什 麽 說明 這個 j 它 出現 在 這些 個 部位 對 不 對 所以 就 說明 什 麽 說明 j 是 大於 等於 i 的 所以 第二個 富翁 可能 更 有錢 一些 或者 是 相等 通過 這種 辦法 他 就 可以 比較 彼此 財富 的 多少 而且 A 不 知道 拿 的 是 第幾個 箱子 所以 A 不 知道 B 的 財富 而 B 拿出 箱子 之後 他 也 不 知道 後面 第幾個 才 變成 1 的 所以 他 也 不 知道 A 的 財富 對 不 對 就 實現 了 姚期智 當 時說 的 這種 方法 那 這裏 面 只是 一個 比方 它 這裏 邊的鎖 就是 這個 箱子 是 帶鎖 的 鎖是 什 麽 呢 鎖在 密碼學 中叫 公鑰 就是 公開 的 這個 密碼 就是 公開 的 鑰匙 任何人 都 可以 對 數據 用公鑰 進行 加密 而 這個 鑰匙 是 什 麽 呢 鑰匙 密碼學 中稱 之 為 私鑰 就是說 只有 那個 擁有者 用 私鑰 才 能夠 把鎖 打開 才能 看到 裏邊 的 數據 是 什 麽 才 能夠 解密 這種 非對稱 的 加密 方式 以前 我們 講過 叫 RSA 加密 這是 一種 典型 的 非對稱 加密 好 那 麽 這是 一個 例子 我們 來講 一講 具體 的 過程 是 怎 麽 樣 的 我們 來看 整個 的 這個 具體 的 操作 的 方案 我們 還是 說 A B 兩個 人 用 更加 數學 化 的 方法 把 這個 問題 解釋 出來 首先 我們 先說 B 第一步 我們 看 B 的 操作 B 怎 麽 操作 呢 我們 知道 B 他 是 沒有 私鑰 的 也 就是 他 是 沒有 辦法 解密 的 就 跟 剛才 這個 B 一樣 他 沒有 鑰匙 對 不 對 但是 他 有 公鑰 因為 公鑰 是 公開 的 誰 都 可以 有 他 可以 進行 加密 所以 他 不能 解密 他 只能 加密 於是 B 按照 下面 的 方法 進行 操作 第一步 B 先 選出 一個 大數 選出 一個 大數 x 這 大數 x 他 不要 告訴 A 他 選出 大數 來 然後 用公鑰 對 這個 大數 x 進行 加密 加密 我們 用 字母 E 來 表示 E(x) 加密 完 了 之後 不是 有個 結果 嗎 這個 結果 我們 令 它 等於 k 大家 註 意 加密 之後 的 結果 就是 k 那 我問 你 解密 之後 的 結果 是 什 麽 解密 我用 字母 D 來 表示 D(k) 它 就 應該 等於 x 對 不 對 這 就是 個 解密 過程 但是 問題 是 解密 這個 步驟 B 是 完成 不了 的 因為 他 只是 有公鑰 可以 進行 加密 但是 他 沒有 私鑰 所以 他 沒有 辦法 進行 解密 這 就是 非對稱 加密 的 一個 特點 下 一步 這個 B 就 再 計算 一 個數 計算 一個 什 麽 數呢 計算 一個 k-j+1 大家 註 意 k 是 他 剛才 通過 加密算法 算 出來 的 一 個數 這個 j 是 什 麽 j 就是 B 的 財富 值 他 就 把 這個 自己 的 財富 值 融入 到 這個 算式 當中 去 了 最後 又 加 了 1 這個 數據 我們 管它 叫 m B 就算 出 一個 m 來 然後 B 就 通過 一定 的 方法 把 這個 m 公開 給 A 他 就 告訴 A 了 他 說 你 看 我 現在 算 出 一個 m 來 而且 我還 可以 告訴 你 這個 m 裏邊 就 有 我 的 財富 值 j 但是 因為 你 不 知道 我 的 k 是 多少 所以 你 根本 也 沒有 辦法 算出 j 來 對 不 對 B 告訴 一個 數據 m 給 A 但 A 也 不 知道 B 有 多少錢 好 B 的 操作 暫時 先放 這 然後 我們 再 來看 A A 的 特點 是 什 麽 呢 A 比 B 多有 一個 東西 A 是 有 公鑰 有公鑰 也 就是 那個 鎖頭 同時 還有 私鑰 說 A 為什 麽 有 私鑰 呢 因為 最 開始 生成 的 時候 就是 這個 A 自己 生成 了 一對 公鑰 和 私鑰 然後 他 把 這公鑰 發給 B 的 所以 說 B 是 沒有 私鑰 的 但是 A 有 有公鑰 也 有 私鑰 既 可以 進行 加密 也 可以 進行 解密 A 拿到 B 傳過來 的 數據 m 也 就是 k-j+1 之後 A 要 做 這 麽 幾個 操作 首先 A 要 計算 一系列 的 數據 哪些 數據 呢 第一個 數據 就是 k-j+1 這個 不用 算了 A 還要 算 第二 個數 叫 k-j+2 k-j+3 往 下 一直 寫 最後 寫到 多少 呢 寫到 k-j+10 一共 有 10 個數 據 這 10 個數 據 中 必然 有 一項 是 什 麽 是 k-j+j 為什 麽 呢 因為 我們 說過 i 和 j 都 是 在 0 到 10 之間 對 不 對 而 k-j+j 等於 多少 不 就 等於 k 嗎 所以 說 這個 k 是 隱藏 在 這十 個數 中間 的 這是 一個 自然數 的 數列 好 計算出來 這件 事 之後 你 看 A 不是 有 私鑰 嗎 那 可以 解密 所以 A 就 會 對 這些 個數 據 進行 解密 就 加密 的 逆運算 叫 解密 解密 的 結果 我們 寫成 是 y 第 u 個 解密 數據 叫做 D(k-j+u) 我 把 它 解密 出來 解密 出來 了 之後 就 會 獲得 十個 數據 叫做 y₁ 這個 y₁ 就是 對 這個 數據 進行 解密 得到 的 然後 y₂ 就是 對 這個 數據 解密 得到 的 y₃ 一直 到 中間 有 一個 yⱼ 這個 yⱼ 就是 對 它 解密 得到 的 然後 再 往 最後 叫做 y₁₀ 好 解密 出來 了 咱們 來看 一看 這個 yⱼ 是 什 麽 這個 yⱼ 是 對 k-j+j 進行 解密 得到 的 對 不 對 也 就是 對 k 進行 解密 得到 的 於是 我們 說 這個 yⱼ 它 其實 是 等於 D(k) 大家 看 一下 x 加密 之後 的 結果 是 k 而 k 解密 之後 的 結果 不 就是 x 嗎 所以 這 一項 它 其實 就 等於 最 開始 A 所選 的 那個 數據 因此 它 解密 之後 的 這些 數據 大家 註 意 看 它 已經 不再 是 自然 數列 了 因為 我 經過 了 一次 解密 它 不是 自然 數列 了 是 亂七八糟 的 但是 中間 隱藏 了 一 個數 就是 剛才 B 選出 的 那個 大數 x 只不過 A 不 知道 為什 麽 呢 因為 B 也 沒有 告訴 它 哪 個數 是 我 大數 x 對 不 對 你 要 知道 哪 個數 是 的話 A 就 會 知道 B 的 財富 了 A 不 知道 但是 確實 有 那 麽 一 個數 是 x 好 解密 完 了 之後 下 一步 的 操作 叫做 求模 什 麽 叫模 呢 這是 一個 比較 數學 化 的 語言 大概 的 意思 就是 取余數 就是 我們 算 一個 數列 zᵤ 它 等於 什 麽 呢 等於 每一 個數 yᵤ 再模 一個 P 這個 P 是 一個 質數 什 麽 意思 呢 就是 除以 一個 質數 取余數 舉 個例 子 來講 我們 這個 質數 取 3 如果 y₁ 是 100 的話 那 100 除以 3 余幾 是不是 余 1 那 z₁ 就是 1 如果 第二 個數 是 10 10 除以 3 還余 1 那 z₂ 也 是 1 如果 第三 個數 是 5 5 除以 3 它 是 余 2 所以 第三 個數 就是 2 就是 我們 找 一個 質數 然後 讓 剛才 的 y₁ 到 y₁₀ 這十 個數 全都 除以 這個 質數 除 完 了 這個 質數 之後 取出 余數 來 這就 叫做 求模 求模 求 完 了 模 之後 你 又 得到 了 一組 數據 叫 z₁ 它 就是 y₁ 除以 P 余數 z₂ 那 就是 第二 個數 除以 P 的 余數 z₃ 一直 到 有 一個 zⱼ 對 吧 再 往後 叫 z₁₀ 取 了 十個 余數 好 下 一步 A 的 操作 就是 要 把 自己 的 財富 融到 這些 數據 裏邊 A 的 財富 是 多少 是 i 億美元 它 怎 麽 融 進去 我們 看 它 的 操作 是 這樣 的 就是 z₁ z₂ ... zᵢ 這些 個數 據 它 都 不變 它 都 不變 然後 在 zᵢ₊₁ zᵢ₊₂ ... z₁₀ 這不 還有 一大堆 數據 嗎 我 都 讓 它 加上 1 也就是說 剛才 你 獲得 一大堆 數據 比如說 這個 z₃ 就是 zᵢ 那 你 前面 幾個 數據 它 就 不變 它 就 不變 完 了 後面 的 這些 數據 你 就 把 它 都 加上 1 都 加上 1 中間 那個 分界線 是 什 麽 就是 第 i 個數 據 這個 i 就 表示 的 是 A 的 財富 值 了 是不是 好 我 獲得 了 這些 數據 之後 再 幹什 麽 呢 再 把 這些 數據 把 它 傳給 B 好 傳給 B 最後 一步 就是 B 的 檢驗 了 B 進行 檢驗 那 麽 B 拿到 這個 數據 之後 關 註 什 麽 呢 它 只會 關 註 第 j 個數 據 zⱼ 它 為 什 麽 關 註 zⱼ 呢 因為 你 看 zⱼ 它 是 什 麽 它 實際上 是 yⱼ 取 P 的 這個 模 得到 的 就是 yⱼ 除以 P 取余數 得到 的 yⱼ 是 什 麽 yⱼ 不 就是 x 嗎 x 是 我 自己 想 的 所以 我 知道 對 不 對 所以 我 就 檢查一下 如果說 我們 用 x 我們 取模 除以 P 取余數 取完 了 余數 之後 它 正好 等於 zⱼ 這 說明 了 什 麽 說明 這個 zⱼ 沒有 經過 +1 這個 步驟 因為 你 不 +1 我 這 麽 一除 你 最後 發現 它 是 相等 的 對 不 對 所以 沒有 經過 +1 這個 步驟 說明 什 麽 說明 zⱼ 是 落到 了 i 之前 的 這個 空間 因此 j 就 小於 等於 i 對 嗎 我 再說 一遍 就是說 你 是 對 x 然後 除以 P 取個 余數 因為 x 就 等於 yⱼ yⱼ 對 P 的 余數 就是 zⱼ 如果 它 正好 相等 的話 就 說明 這個 zⱼ 是 沒有 +1 的 沒有 經過 最後 這 一步 那 麽 為 什 麽 沒有 +1 呢 因為 這個 A 它 只 對 前 i 個數 據加 了 1 了 後面 的 數據 它 沒有 加 對 不 對 所以 說 你 如果 沒有 +1 就 表示 zⱼ 是 落 在 i 之前 的 那 於是 j 就 小於 等於 i 對 不 對 反過來說 如果 這個 x 它模 了 P 之後 它 不 等於 zⱼ 你 把 你 自己 的 那 個數 除以 P 取余數 取完 了 之後 不 相等 不 相等 的 原因 是 什 麽 那 因為 就是 zⱼ+1 了 唄 加完 了 1 之後 它 就 不再 是 x 除以 P 的 余數 了 對 不 對 所以 才 會 不 相等 那 就 說明 這個 zⱼ 它 是 在 i 之後 的 因此 j 就 大於 i 於是乎 A 也 不 知道 B 的 財富 B 也 不 知道 A 的 財富 但是 他們 卻 可以 比較 誰 錢 多 誰 錢 少 對 吧 好 這樣 就 解決 了 百萬富翁 問題 在 我 上 一回 提 這個 思考題 的 時候 有 小朋友 給我 留言 說 很 簡單 兩個 富翁 把 自己 的 錢裝 袋子 裏 放在 一個 天平 上 看 誰 重 誰 重 誰 的 錢 就 多 這種 方法 實現 的 前提 是 要 有 一架 公正 的 天平 這個 公正 的 天平 就是 一個 客觀 的 第三方 但是 如果 你 在 互聯網 的 世界 上 你 沒有 這個 客觀 的 第三方 又 如何 去 解釋 這個 問題 呢 那 麽 姚期智 先生 提出 的 這種 方法 就是 用來 應對 這種 問題 的 那 這種 問題 被 稱 之 為 多方 安全 計算 問題 現在 我們 是 一個 互聯網 大 數據 的 時代 我們 有 許多 數據安全 的 問題 要 處理 舉 個例 子 來講 比如說 我 想 找到 跟 我 興趣愛好 相同 的 人 但是 我 又 不想 向 別人 透露 我 的 興趣愛好 到底 是 什 麽 我 該 怎 麽 做 呢 再 比如說 有 一些 學校 機關 和 醫院 他們 有 一大堆 的 數據 要 進行 處理 但是 他們 又 不敢 把 這個 數據 給 一些 私人 公司 怕 他們 把 這個 數據 泄露 此時 他 該 怎 麽 辦 呢 姚期智 先生 提出 的 這種 方法 就 可以 解決 這個 問題 我 把 加密 之後 的 數據 給你 然後 你 進行 處理 再 返給 我 但 在 這個 過程 中 你 其實 什 麽 都 沒有 獲得 姚期智 先生 提出 的 這個 問題 在 計算機 安全 領域 具有 開拓性 的 意義 他 獲得 了 圖靈獎 也 是 實至名歸 那 麽 這節 課 再給 大家 留 一個 思考題 說 你 在 一個 公司 裏面 上班 上 了 很多年 之後 找到 老板 說 老板 我要 加薪 我 這 麽 努力 但是 我 的 工資 卻 沒有 達到 咱們 公司員工 的 平均水平 老板 說 每 一個 人 的 工資 都 是 保密 的 你 是 怎 麽 知道 公司員工 的 平均工資 的 呢 你 就 非常 生氣 把 這個 事 跟 小夥伴 們 一 說 小夥伴 們 也 紛紛表示 希望 算 出 公司 的 平均工資 但是 每 一個 小夥伴 又 不 願意 告訴 別人 自己 的 工資 到底 是 多少 那 麽 我們 有沒有 一種 辦法 能夠 算 出 所有 員工 的 平均工資 但是 又 不 透露 出 每個 員工 的 工資 到底 是 多少 呢 我 提示 一下 第一步 依然 是 要 尋找 一個 大數 大家 如果 知道 這個 問題 的 答案 可以 在 評論 區裏 留言 大家 如果 喜歡 我 的 視頻 可以 在 YouTube 的 賬號 李永樂 老師 裏 訂閱 我 點擊 小 鈴鐺 可以 第一 時間 獲得 更新 信息