姚期智 百万富翁 问题 ：大 数据 时代 ，如何 保护 个人隐私？ Yao Qizhi's millionaire question: How to protect personal privacy in the era of big data?

各位 同学 大家 好 我 是 李永乐 老师 各位 同学 大家 好 我 是 李永乐 老师 在 上 一回 咱们 讲 零 知识 证明 的 时候 When we talked about zero-knowledge proof last time 留 了 一个 思考题 Left a question 说 有 两个 百万富翁 想 比较 彼此 的 财富 谁 多 谁 少 但是 谁 都 不想 公开 自己 的 真实 财产 有没有 什么 办法 呢 今天 我们 来讲 一讲 这个 问题 这个 问题 是 一个 计算机科学 的 问题 我们 称之为 百万富翁 问题 这个 百万富翁 问题 呢 在 现在 的 生活 中 已经 越来越 有用 了 我们 来讲 一讲 这个 问题 它 是 谁 提出 的 呢 它 是 在 这个 1982 年 的 时候 由 著名 的 计算机 科学家 姚期智 提出 的 大家 听说 过 姚期智 的 名字 吗 如果 你 没听说过 的话 有没有 听说 过 清华大学 姚班 呢 就是 以 姚期智 的 名字 命名 的 姚期智 1946 年 的 时候 出 生于 上海 后来 在 台湾大学 物理系 获得 了 学士学位 到 美国 的 哈佛大学 获得 了 物理学 的 博士学位 再 后来 在 MIT 斯坦福 还有 UC 伯克利 教 计算机 在 2000 年 的 时候 由于 姚期智 在 计算机 方面 的 贡献 而 获得 了 Due to Yao Qizhi’s contribution to computers 图灵奖 图灵奖 我们 讲过 是 这个 计算机 界 的 诺贝尔奖 我们 国家 就 只有 一个 人 获得 过 图灵奖 那 就是 姚期智 姚期智 也 是 美国科学院 台湾 中央研究院 Yao Qizhi is also the National Academy of Sciences Taiwan 还有 中国科学院 的 院士 好 那么 姚期智 在 1982 年 这篇 论文 里面 就 提出 这样 一个 问题 他 说 有 A B 两个 富翁 这个 A 和 B 两个 富翁 他们 的 资产 都 可以 近似 为 一个 整数 说 A 他 的 资产 是 i 亿元 这个 i 是 一个 整数 然后 这个 B 他 的 资产 是 这 j 亿元 j 亿元 j 也 是 个 整数 i 和 j 都 介于 0 到 10 之间 是 一个 0 到 10 之间 的 整数 然后 他们 两个 就 说 我们 两个 想 比较 一下 谁 钱 多 谁 钱 少 但是 我们 都 不想 让 对方 知道 我们 自己 的 钱 有没有 什么 办法 呢 这 姚期智 就 提出 了 一种 办法 我们 先 用 一个 例子 来 打个比方 说明 一下 姚期智 的 这个 思路 是 什么 说 这 两个 百万富翁 他们 商量 好 说 我们 要 通过 一个 规则 比较 彼此 的 财富 谁 也 不许 作假 No one is allowed to cheat 但 在 这个 过程 中 我们 每个 人 都 不 告诉 对方 我们 有 多少钱 怎么办 呢 我们 可以 这样 看 首先 我们 先 拿 10 个 箱子 这 10 个 箱子 带锁 我 先画 10 个 箱子 好 了 10 个 箱子 画 完 了 这 10 个 箱子 都 是 带锁 的 这个 A 就 我们 刚才 说 的 那个 资产 为 i 亿 的 这个 人 他 是 有 钥匙 的 所以 他 可以 锁上 这个 箱子 也 可以 把 这个 箱子 给 打开 而 B 这个 百万富翁 这个 B 他 没有 钥匙 但是 他 可以 锁上 那个 锁头 你 一扣 不 就 锁上 了 吗 Can't you lock the lock as soon as you click it? 所以 他 虽然 没有 钥匙 他 还是 可以 锁上 的 好 现在 这 两个 人 就 开始 做 这个 事 了 怎么 做 呢 首先 这个 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 Equal to every number yᵤ modulo a 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 我 这么 一除 I divide like this 你 最后 发现 它 是 相等 的 对 不 对 所以 没有 经过 +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 的 账号 李永乐 老师 里 订阅 我 点击 小 铃铛 可以 第一 时间 获得 更新 信息