×

Utilizziamo i cookies per contribuire a migliorare LingQ. Visitando il sito, acconsenti alla nostra politica dei cookie.

image

李永乐老师 Youtube, 姚期智百万富翁问题:大数据时代,如何保护个人隐私?

姚期智 百万富翁 问题 :大 数据 时代 ,如何 保护 个人隐私?

各位 同学 大家 好 我 是 李永乐 老师 各位 同学 大家 好 我 是 李永乐 老师 在 上 一回 咱们 讲 零 知识 证明 的 时候 留 了 一个 思考题 说 有 两个 百万富翁 想 比较 彼此 的 财富 谁 多 谁 少 但是 谁 都 不想 公开 自己 的 真实 财产 有没有 什么 办法 呢 今天 我们 来讲 一讲 这个 问题 这个 问题 是 一个 计算机科学 的 问题 我们 称之为 百万富翁 问题 这个 百万富翁 问题 呢 在 现在 的 生活 中 已经 越来越 有用 了 我们 来讲 一讲 这个 问题 它 是 谁 提出 的 呢 它 是 在 这个 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 的 账号 李永乐 老师 里 订阅 我 点击 小 铃铛 可以 第一 时间 获得 更新 信息

Learn languages from TV shows, movies, news, articles and more! Try LingQ for FREE

姚期智 百万富翁 问题 :大 数据 时代 ,如何 保护 个人隐私? Yao Qizhi|millionaire|||big data|||protect|personal privacy Yao Qizhi's millionaire question: How to protect personal privacy in the era of big data? Yao Zhizhi Millionaire Pregunta: ¿Cómo proteger la privacidad personal en la era de los grandes datos? Yao Zhizhi Millionaire Question: Come proteggere la privacy personale nell'era dei big data?

各位 同学 大家 好 我 是 李永乐 老师 ||||||Li Yongle| 各位 同学 大家 好 我 是 李永乐 老师 ||||||Li Yongle| 在 上 一回 咱们 讲 零 知识 证明 的 时候 ||last time|||zero|knowledge|proof|| When we talked about zero-knowledge proof last time 留 了 一个 思考题 |||thought question Left a question 说 有 两个 百万富翁 想 比较 彼此 的 财富 谁 多 谁 少 |||millionaires|||each other||wealth|||| 但是 谁 都 不想 公开 自己 的 真实 财产 ||||disclose|||true assets|assets 有没有 什么 办法 呢 今天 我们 来讲 一讲 这个 问题 ||to talk about|talk about|| 这个 问题 是 一个 计算机科学 的 问题 ||||computer science|| 我们 称之为 百万富翁 问题 |call|millionaire| 这个 百万富翁 问题 呢 |millionaire|| 在 现在 的 生活 中 已经 越来越 有用 了 |||||||useful| 我们 来讲 一讲 这个 问题 |to speak from our perspective|talk about|| 它 是 谁 提出 的 呢 它 是 在 这个 1982 年 的 时候 由 著名 的 计算机 科学家 姚期智 提出 的 by|famous||computer||Yao Qizhi|| 大家 听说 过 姚期智 的 名字 吗 |||Yao Qizhi||| 如果 你 没听说过 的话 有没有 听说 过 清华大学 姚班 呢 |||Tsinghua University|Yao Class| 就是 以 姚期智 的 名字 命名 的 |with|Yao Qizhi|||named after| 姚期智 1946 年 的 时候 出 生于 上海 |||||born in| 后来 在 台湾大学 物理系 获得 了 学士学位 ||National Taiwan University|Department of Physics|obtained a bachelor's degree||bachelor's degree 到 美国 的 哈佛大学 获得 了 物理学 的 博士学位 |||Harvard University|obtained||Physics||PhD degree 再 后来 在 MIT 斯坦福 |||MIT|Stanford 还有 UC 伯克利 教 计算机 |UC Berkeley|UC Berkeley||Computer 在 2000 年 的 时候 由于 姚期智 在 计算机 方面 的 贡献 而 获得 了 |Yao Qizhi||Computer|||contribution||received| Due to Yao Qizhi’s contribution to computers 图灵奖 Turing Award 图灵奖 我们 讲过 Turing Award||talked about 是 这个 计算机 界 的 诺贝尔奖 ||Nobel Prize in Computer Science|field||Nobel Prize 我们 国家 就 只有 一个 人 获得 过 图灵奖 ||||||won||Turing Award 那 就是 姚期智 ||Yao Qizhi 姚期智 也 是 美国科学院 台湾 中央研究院 Yao Qizhi|||National Academy of Sciences||Academia Sinica Yao Qizhi is also the National Academy of Sciences Taiwan 还有 中国科学院 的 院士 |Chinese Academy of Sciences||Academician 好 那么 姚期智 在 1982 年 这篇 论文 里面 ||Yao Qizhi|||this paper|paper| 就 提出 这样 一个 问题 |raise||| 他 说 有 A B 两个 富翁 ||||||rich man 这个 A 和 B 两个 富翁 |||||rich man 他们 的 资产 都 可以 近似 为 一个 整数 ||assets|||approximately equal to|||integer 说 A 他 的 资产 是 i 亿元 这个 i 是 一个 整数 ||||assets|||hundred million|||||integer 然后 这个 B 他 的 资产 是 这 j 亿元 |||||capital|||hundred million| j 亿元 j 也 是 个 整数 |hundred million|||||integer i 和 j 都 介于 0 到 10 之间 ||||between||between 是 一个 0 到 10 之间 的 整数 |||between||integer 然后 他们 两个 就 说 我们 两个 想 比较 一下 ||||||||compare| 谁 钱 多 谁 钱 少 但是 我们 都 不想 让 对方 知道 我们 自己 的 钱 |||don't want||||||| 有没有 什么 办法 呢 这 姚期智 就 提出 了 一种 办法 |Yao Qizhi||||| 我们 先 用 一个 例子 来 打个比方 ||||example||for example 说明 一下 姚期智 的 这个 思路 是 什么 ||Yao Qizhi|||idea|| 说 这 两个 百万富翁 他们 商量 好 |||millionaires||discussed| 说 我们 要 通过 一个 规则 比较 彼此 的 财富 |||||rule||each other||wealth 谁 也 不许 作假 ||not allowed|cheat No one is allowed to cheat 但 在 这个 过程 中 but|||process| 我们 每个 人 都 不 告诉 对方 我们 有 多少钱 |||||tell|||| 怎么办 呢 我们 可以 这样 看 首先 我们 先 拿 10 个 箱子 这 10 个 箱子 带锁 |||take||boxes|||boxes|locked 我 先画 10 个 箱子 |First draw||boxes 好 了 10 个 箱子 画 完 了 |||boxes|paint|| 这 10 个 箱子 都 是 带锁 的 |||||locked| 这个 A 就 我们 刚才 说 的 那个 资产 为 i 亿 的 这个 人 ||just now||||asset|||hundred million||| 他 是 有 钥匙 的 |||key| 所以 他 可以 锁上 这个 箱子 |||lock up|| 也 可以 把 这个 箱子 给 打开 ||||box|| 而 B 这个 百万富翁 这个 B 他 没有 钥匙 |||millionaire|||||key 但是 他 可以 锁上 |||lock it 那个 锁头 你 一扣 不 就 锁上 了 吗 |lock head||a snap|||locked|| Can't you lock the lock as soon as you click it? 所以 他 虽然 没有 钥匙 他 还是 可以 锁上 的 |||||he|||lock| 好 现在 这 两个 人 就 开始 做 这个 事 了 怎么 做 呢 首先 这个 A 他 不是 资产 是 i 亿元 嘛 |||||asset|||hundred million| 他 先 找到 第 i 个 箱子 比如说 这个 吧 这个 就是 第 i 个 箱子 ||||||||box 然后 他 就 把 i 个 箱子 之前 所有 的 箱子 里面 放 一个 纸条 写 的 0 ||boxes||||note|| 所有 的 箱子 都 写 0 ||boxes|| 到 了 第 i 个 箱子 开始 他 就 写 1 |||||box|||| 写 1 1 1 1 放个 纸条 |put a|note 然后 把 箱子 全都 锁上 ||the box|| 全都 锁上 了 之后 他 就 出来 跟 B 说 |locked||after|||||| 说 你 过去 吧 你 去 看吧 这个 B 进来 之后 面对 10 个 箱子 10 个 箱子 全是 锁上 的 |boxes|all|| B 一个 也 打不开 对 不 对 |||can't open||| 所以 B 根本 不 知道 里边 写 的 是 什么 他 如果 打开 的话 一看 前面 是 0 后面 是 1 他 就 明白 了 你 的 资产 就 应该 是 这个 是不是 ||assets||||| 1 2 3 4 5 6 你 应该 就是 6 亿元 |||600 million 现在 我 打不开 我 就 不 知道 那 怎么办 呢 ||can't open||||||| B 说 这样 我 也 找 我 自己 的 资产 ||||||assets 比如说 我 的 资产 是 4 亿元 是 j 是 吧 |||assets||hundred million|||| 我 第 4 个 j 等于 4 是不是 ||||is equal to| 刚才 说 这个 i 等于 6 ||||is equal to 如果 我 的 资产 是 4 亿元 |||||billion 那 这样 我 就 把 这 第 4 个 箱子 给 拿 出来 ||||||||the fourth box||take| 我 把 它 拿 出来 给 A |||take||| 我 打不开 但 我 可以 拿 出来 |||||take| 剩下 这些 个 箱子 我 全都 烧掉 我 全都 烧掉 the rest|||boxes|||burned down|||burned 你 也 不要 管 我 拿 的 是 第几个 箱子 ||don't|mind||take|||which one|box 反正 我 都 烧掉 了 Anyway|||burned it all| 都 烧掉 了 之后 |burned down|| A 面对 这个 B 拿 出来 的 箱子 A 根本 不 知道 这 拿 出来 是 第几个 箱子 |||||take|||which number| 但是 A 有 钥匙 A 可以 把 它 打开 |||key||||| 所以 A 就 把 它 打开 了 打开 了 之后 就 面临 两种 可能 ||after||facing|two possibilities| 第一种 可能 是 什么 呢 第一种 可能 是 这个 箱子 里面 是 0 ||||box|| 箱子 里边 是 0 box|| 这 说明 了 什么 这 不 就 说明 这个 j 它 是 小于 i 的 吗 是不是 ||||||||less than|||| 也 就是 第一个 富翁 他 比较 有钱 |||rich man||| 第二个 富翁 比较 没 钱 对 不 对 |rich man|||||| 但是 也 有 可能 打开 之后 里边 字条 是 1 |||||after||note| 如果 里边 字条 是 1 说明 什么 ||note||| 说明 这个 j 它 出现 在 这些 个 部位 对 不 对 ||||||||parts||| 所以 就 说明 什么 说明 j 是 大于 等于 i 的 |||||||greater than||| 所以 第二个 富翁 可能 更 有钱 一些 或者 是 相等 ||wealthy man|||||||equal 通过 这种 办法 他 就 可以 比较 彼此 财富 的 多少 ||||||relatively|each other|wealth|| 而且 A 不 知道 拿 的 是 第几个 箱子 |||||||which box| 所以 A 不 知道 B 的 财富 而 B 拿出 箱子 之后 ||took out|| 他 也 不 知道 后面 第几个 才 变成 1 的 |||||which one||| 所以 他 也 不 知道 A 的 财富 对 不 对 就 实现 了 姚期智 当时 说 的 这种 方法 |achieved||Yao Qizhi||||| 那 这 里面 只是 一个 比方 |||||example 它 这里 边 的 锁 就是 这个 箱子 是 带锁 的 ||||lock|||box||locked| 锁 是 什么 呢 锁 在 密码学 中叫 公钥 ||||public key||cryptography|called public key|public key 就是 公开 的 这个 密码 就是 公开 的 钥匙 ||||password||public||key 任何人 都 可以 对 数据 用公钥 进行 加密 Anyone||||data|public key|perform|encryption 而 这个 钥匙 是 什么 呢 ||key||| 钥匙 密码学 中 称之为 私钥 |cryptography||called|private key 就是说 只有 那个 拥有者 用 私钥 |||owner||private key 才 能够 把 锁 打开 |can||lock| 才能 看到 里边 的 数据 是 什么 才 能够 解密 ||||data||||can|decrypt 这种 非对称 的 加密 方式 |asymmetric||encryption| 以前 我们 讲过 叫 RSA 加密 ||have talked about||RSA encryption|encryption 这是 一种 典型 的 非对称 加密 ||typical||asymmetric|encryption 好 那么 这是 一个 例子 ||||example 我们 来讲 一讲 具体 的 过程 是 怎么样 的 |to speak from our perspective|talk|specific||process||| 我们 来看 整个 的 这个 具体 的 操作 的 方案 |||||specific||operation plan||plan 我们 还是 说 A B 两个 人 用 更加 数学 化 的 方法 把 这个 问题 解释 出来 |||||||||explain mathematically| 首先 我们 先说 B 第一步 我们 看 B 的 操作 ||||the first step|||||operation B 怎么 操作 呢 我们 知道 B 他 是 没有 私钥 的 ||operate||||||||| 也 就是 他 是 没有 办法 解密 的 就 跟 刚才 这个 B 一样 他 没有 钥匙 对 不 对 但是 他 有 公钥 因为 公钥 是 公开 的 |||public key||public key||| 谁 都 可以 有 他 可以 进行 加密 ||||||can perform|encryption 所以 他 不能 解密 他 只能 加密 |||decrypt|||encryption 于是 B 按照 下面 的 方法 进行 操作 |||||||operation 第一步 B 先 选出 一个 大数 选出 一个 大数 x ||first|Choose a large number||large number|Choose a large number||large number| 这 大数 x 他 不要 告诉 A 他 选出 大数 来 |big number||||||||big number| 然后 用公钥 对 这个 大数 x 进行 加密 ||||large number||perform|encryption 加密 我们 用 字母 E 来 表示 E(x) encryption|||letter|||denote|| 加密 完 了 之后 不是 有个 结果 吗 encryption||||||result| 这个 结果 我们 令 它 等于 k |result||make||equal to| 大家 注意 加密 之后 的 结果 就是 k 那 我 问 你 解密 之后 的 结果 是 什么 ||||decryption||||| 解密 我用 字母 D 来 表示 ||letter||| D(k) 它 就 应该 等于 x 对 不 对 这 就是 个 解密 过程 |||decoding| 但是 问题 是 解密 这个 步骤 B 是 完成 不了 的 |||decryption||step B||||| 因为 他 只是 有公钥 可以 进行 加密 |||public key||perform|encryption 但是 他 没有 私钥 所以 他 没有 办法 进行 解密 |||private key|||||perform| 这 就是 非对称 加密 的 一个 特点 ||asymmetric|encryption|||characteristic 下 一步 这个 B 就 再 计算 一个 数 ||||||calculate|| 计算 一个 什么 数 呢 计算 一个 k-j+1 calculate|||number||||| 大家 注意 |pay attention k 是 他 刚才 通过 加密算法 算 出来 的 一个 数 |||||encryption algorithm|calculated||||number 这个 j 是 什么 j 就是 B 的 财富 值 ||||||||wealth| 他 就 把 这个 自己 的 财富 值 ||||||wealth|value 融入 到 这个 算式 当中 去 了 integrated into|||equation||| 最后 又 加 了 1 这个 数据 我们 管它 叫 m |||||data||call it|| B 就算 出 一个 m 来 |even if|||| 然后 B 就 通过 一定 的 方法 把 这个 m 公开 给 A 他 就 告诉 A 了 |||make public||||||| 他 说 你 看 我 现在 算 出 一个 m 来 ||||||calculate|||| 而且 我 还 可以 告诉 你 这个 m 里边 就 有 我 的 财富 值 j 但是 因为 你 不 知道 我 的 k 是 多少 所以 你 根本 也 没有 办法 算出 j 来 对 不 对 ||||||calculate||||| B 告诉 一个 数据 m 给 A |||data||| 但 A 也 不 知道 B 有 多少钱 好 B 的 操作 暂时 先放 这 ||||temporarily|first put| 然后 我们 再 来看 A A 的 特点 是 什么 呢 A 比 B 多有 一个 东西 A 是 有 公钥 有公钥 |||more than||||||public key|has public key 也 就是 那个 锁头 同时 还有 私钥 |||lock head||| 说 A 为什么 有 私钥 呢 因为 最 开始 生成 的 时候 |||||||||generated|| 就是 这个 A 自己 生成 了 一对 公钥 和 私钥 ||||generated||||| 然后 他 把 这公钥 发给 B 的 |||this public key||| 所以 说 B 是 没有 私钥 的 therefore|||||| 但是 A 有 有公钥 也 有 私钥 既 可以 进行 加密 也 可以 进行 解密 both||||||| A 拿到 B 传过来 的 数据 m |||passed over||| 也 就是 k-j+1 之后 A 要 做 这么 几个 操作 首先 A 要 计算 一系列 的 数据 哪些 数据 呢 ||||a series||||| 第一个 数据 就是 k-j+1 这个 不用 算了 A 还要 算 第二个 数 叫 k-j+2 k-j+3 往 下 一直 写 最后 写 到 多少 呢 写到 k-j+10 |||||write to|| 一共 有 10 个 数据 这 10 个 数据 中 必然 有 一项 是 什么 ||||must be|||| 是 k-j+j 为什么 呢 因为 我们 说 过 i 和 j 都 是 在 0 到 10 之间 对 不 对 而 k-j+j 等于 多少 不 就 等于 k 吗 所以 说 这个 k 是 隐藏 在 这 十个 数 中间 的 这是 一个 自然数 的 数列 ||natural number||sequence 好 计算出来 这件 事 之后 你 看 A 不是 有 私钥 吗 那 可以 解密 所以 A 就 会 对 这些 个 数据 进行 解密 就 加密 的 逆运算 叫 解密 |||inverse operation|| 解密 的 结果 我们 写成 是 y 第 u 个 解密 数据 叫做 D(k-j+u) 我 把 它 解密 出来 解密 出来 了 之后 就 会 获得 十个 数据 叫做 y₁ 这个 y₁ 就是 对 这个 数据 进行 解密 得到 的 然后 y₂ 就是 对 这个 数据 解密 得到 的 y₃ 一直 到 中间 有 一个 yⱼ ||||||y sub j 这个 yⱼ 就是 对 它 解密 得到 的 然后 再 往 最后 叫做 y₁₀ 好 解密 出来 了 咱们 来看 一看 这个 yⱼ 是 什么 这个 yⱼ 是 对 k-j+j 进行 解密 得到 的 对 不 对 也 就是 对 k 进行 解密 得到 的 于是 我们 说 这个 yⱼ 它 其实 是 等于 D(k) 大家 看 一下 x 加密 之后 的 结果 是 k 而 k 解密 之后 的 结果 不 就是 x 吗 所以 这 一项 它 其实 就 等于 最 开始 A 所选 的 那个 数据 |||||||selected||| 因此 它 解密 之后 的 这些 数据 大家 注意 看 它 已经 不再 是 自然 数列 了 因为 我 经过 了 一次 解密 它 不是 自然 数列 了 是 乱七八糟 的 但是 中间 隐藏 了 一个 数 就是 刚才 B 选出 的 那个 大数 x 只不过 A 不 知道 为什么 呢 因为 B 也 没有 告诉 它 哪个 数是 我 大数 x 对 不 对 你 要 知道 哪个 数是 的话 A 就 会 知道 B 的 财富 了 A 不 知道 但是 确实 有 那么 一个 数是 x 好 解密 完 了 之后 下 一步 的 操作 叫做 求模 |||||modulus operation 什么 叫模 呢 |What is a model| 这是 一个 比较 数学 化 的 语言 大概 的 意思 就是 取 余数 就是 我们 算 一个 数列 zᵤ 它 等于 什么 呢 |||||sequence zᵤ|||| 等于 每 一个 数 yᵤ 再模 一个 P ||||each number|mod P|| Equal to every number yᵤ modulo a P 这个 P 是 一个 质数 ||||prime number 什么 意思 呢 就是 除以 一个 质数 取 余数 举个 例子 来讲 我们 这个 质数 取 3 如果 y₁ 是 100 的话 那 100 除以 3 余几 ||||||remainder 是不是 余 1 那 z₁ 就是 1 如果 第二个 数是 10 10 除以 3 还余 1 ||||remainder 那 z₂ 也 是 1 如果 第三个 数是 5 5 除以 3 它 是 余 2 所以 第三个 数 就是 2 就是 我们 找 一个 质数 然后 让 刚才 的 y₁ 到 y₁₀ 这 十个 数 全都 除以 这个 质数 除 完 了 这个 质数 之后 取出 余数 来 这 就 叫做 求模 求模 求 完 了 模 之后 你 又 得到 了 一组 数据 叫 z₁ 它 就是 y₁ 除以 P 余数 z₂ 那 就是 第二个 数 除以 P 的 余数 z₃ 一直 到 有 一个 zⱼ 对 吧 |||||z sub j|| 再 往后 叫 z₁₀ 取 了 十个 余数 好 下 一步 A 的 操作 就是 要 把 自己 的 财富 融到 这些 数据 里边 |||||integrate into||| A 的 财富 是 多少 是 i 亿美元 它 怎么 融 进去 我们 看 它 的 操作 是 这样 的 就是 z₁ z₂ ... zᵢ |||z sub i 这些 个 数据 它 都 不变 它 都 不变 然后 在 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 取 余数 |||||modulus|||| 取完 了 余数 之后 它 正好 等于 zⱼ 这 说明 了 什么 说明 这个 zⱼ 没有 经过 +1 这个 步骤 因为 你 不 +1 我 这么 一除 ||one subtraction I divide like this 你 最后 发现 它 是 相等 的 对 不 对 所以 没有 经过 +1 这个 步骤 说明 什么 说明 zⱼ 是 落到 了 i 之前 的 这个 空间 因此 j 就 小于 等于 i 对 吗 我 再说 一遍 就是说 你 是 对 x 然后 除以 P 取个 余数 ||||||||take a| 因为 x 就 等于 yⱼ yⱼ 对 P 的 余数 就是 zⱼ 如果 它 正好 相等 的话 就 说明 这个 zⱼ 是 没有 +1 的 没有 经过 最后 这 一步 那么 为什么 没有 +1 呢 因为 这个 A 它 只 对 前 i 个 数据 加 了 1 了 后面 的 数据 它 没有 加 对 不 对 所以 说 你 如果 没有 +1 就 表示 zⱼ 是 落 在 i 之前 的 那 于是 j 就 小于 等于 i 对 不 对 反过来说 如果 这个 x 它模 了 P 之后 |||it model||| 它 不 等于 zⱼ 你 把 你 自己 的 那个 数 除以 P 取 余数 取完 了 之后 不 相等 不 相等 的 原因 是 什么 那 因为 就是 zⱼ+1 了 呗 加完 了 1 之后 它 就 不再 是 x 除以 P 的 余数 了 对 不 对 所以 才 会 不 相等 那 就 说明 这个 zⱼ 它 是 在 i 之后 的 因此 j 就 大于 i 于是乎 A 也 不 知道 B 的 财富 therefore||||||| B 也 不 知道 A 的 财富 但是 他们 却 可以 比较 谁 钱 多 谁 钱 少 对 吧 好 这样 就 解决 了 百万富翁 问题 在 我 上 一回 提 这个 思考题 的 时候 有 小朋友 给 我 留言 说 很 简单 两个 富翁 把 自己 的 钱装 袋子 里 |||||money bag|| 放在 一个 天平 上 ||balance scale| 看 谁 重 谁 重 谁 的 钱 就 多 这种 方法 实现 的 前提 是 要 有 一架 公正 的 天平 这个 公正 的 天平 就是 一个 客观 的 第三方 但是 如果 你 在 互联网 的 世界 上 你 没有 这个 客观 的 第三方 又 如何 去 解释 这个 问题 呢 那么 姚期智 先生 提出 的 这种 方法 就是 用来 应对 这种 问题 的 那 这种 问题 被 称之为 多方 安全 计算 问题 现在 我们 是 一个 互联网 大 数据 的 时代 我们 有 许多 数据安全 的 问题 要 处理 举个 例子 来讲 比如说 我 想 找到 跟 我 兴趣爱好 相同 的 人 但是 我 又 不想 向 别人 透露 我 的 兴趣爱好 到底 是 什么 我该 怎么 做 呢 再 比如说 有 一些 学校 机关 和 医院 他们 有 一大堆 的 数据 要 进行 处理 但是 他们 又 不敢 把 这个 数据 给 一些 私人 公司 怕 他们 把 这个 数据 泄露 此时 他 该 怎么办 呢 姚期智 先生 提出 的 这种 方法 就 可以 解决 这个 问题 我 把 加密 之后 的 数据 给 你 然后 你 进行 处理 再 返 给 我 |||||return|| 但 在 这个 过程 中 你 其实 什么 都 没有 获得 姚期智 先生 提出 的 这个 问题 在 计算机 安全 领域 具有 开拓性 的 意义 |||||pioneering significance|| 他 获得 了 图灵奖 也 是 实至名归 ||||||well-deserved 那么 这节 课 再 给 大家 留 一个 思考题 说 你 在 一个 公司 里面 上班 上 了 很多年 之后 找到 老板 说 老板 我要 加薪 我 这么 努力 但是 我 的 工资 却 没有 达到 咱们 公司员工 的 平均水平 老板 说 每 一个 人 的 工资 都 是 保密 的 你 是 怎么 知道 公司员工 的 平均工资 的 呢 ||||||average salary|| 你 就 非常 生气 把 这个 事 跟 小伙伴 们 一 说 小伙伴 们 也 纷纷表示 |||all expressed 希望 算 出 公司 的 平均工资 但是 每 一个 小伙伴 又 不 愿意 告诉 别人 自己 的 工资 到底 是 多少 那么 我们 有没有 一种 办法 能够 算 出 所有 员工 的 平均工资 但是 又 不 透露 出 每个 员工 的 工资 到底 是 多少 呢 我 提示 一下 第一步 依然 是 要 寻找 一个 大数 大家 如果 知道 这个 问题 的 答案 可以 在 评论 区里 留言 大家 如果 喜欢 我 的 视频 可以 在 YouTube 的 账号 李永乐 老师 里 订阅 我 点击 小 铃铛 可以 第一 时间 获得 更新 信息