×
Używamy ciasteczek, aby ulepszyć LingQ. Odwiedzając stronę wyrażasz zgodę na nasze
polityka Cookie .
李永樂老師, 姚期智百万富翁问题:大数据时代,如何保护个人隐私?
姚期智 百万富翁 问题 :大 数据 时代 ,如何 保护 个人隐私?
各位 同學 大家 好 我 是 李永樂 老師
各位 同學 大家 好 我 是 李永樂 老師
在 上 一回 咱們 講零 知識 證明 的 時候
留 了 一個 思考題
說 有 兩個 百萬富翁 想 比較 彼此 的 財富 誰 多 誰 少
但是 誰 都 不想 公開 自己 的 真實 財產
有沒有 什 麽 辦法 呢
今天 我們 來講 一講 這個 問題
這個 問題 是 一個 計算機科學 的 問題
我們 稱之為 百萬富翁 問題
這個 百萬富翁 問題 呢
在 現在 的 生活 中 已經 越來越 有用 了
我們 來講 一講 這個 問題
它 是 誰 提出 的 呢
它 是 在 這個 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 的 賬號 李永樂 老師 裏 訂閱 我
點擊 小 鈴鐺 可以 第一 時間 獲得 更新 信息
姚期智 百万富翁 问题 :大 数据 时代 ,如何 保护 个人隐私?
|||||||protect|personal privacy
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 的 賬號 李永樂 老師 裏 訂閱 我
點擊 小 鈴鐺 可以 第一 時間 獲得 更新 信息