Dan Boneh密码学笔记1

哔哩哔哩课程链接：

https://www.bilibili.com/video/av1269426

斯坦福官方课程链接：

https://crypto.stanford.edu/~dabo/courses/OnlineCrypto/

每一个信息安全专业的学生都知道，密码学几乎是所有专业课里面最难的。除了复杂的密码算法，你还必须掌握一定的数学工具，所以密码学也是有的数学专业的课程。

暑假在家呆了两个礼拜，思考自己下一阶段该如何发展。最终放弃了计算机视觉，选择了信息安全，放弃了硕士就业，选择了攻读博士，放弃了CTF，选择了密码学科研。

翻遍了学院的官网，终于找到了一位中意的密码学副教授。最终跟随了这位导师。这个课程就是老师推荐的。尽快好好把这门课刷完。装备好密码学工具箱。干！

一、密码学应用：安全多方计算、私有外包计算、零知识证明

二、发展历史：凯撒替换密码、vigener cipher、Rotor machines、Enigma machine、DES

三、离散概率：概率分布、事件、并集上界、随机变量、均匀随机变量 、随机算法、独立性、异或、生日悖论

四、番外：安全多方计算

1.What is cryptography?

密码学神奇应用

2.History

3.Discrete Probability

(crash course, cont.)

离散概率

参考资料：

https://en.wikibooks.org/wiki/High_School_Mathematics_Extensions/Discrete_Probability

番外：关于安全多方计算，摘录自以下文章

一文了解安全多方计算（Secure Muti-party Computation）

大多数企业考虑到数据安全和个人隐私等问题，对数据共享都非常谨慎。在现实生活中，我们时常会受到下列问题的困扰：

· 医院需要共享医疗信息，但是又不想泄露单个患者的隐私；

· 政府机构需要统计选举数据，但是又不想公开投票选民的选举记录；

· 一家制造厂商想要以行业标准检验产品水准，但又不想让竞争对手知道他们真实的生产数据。

针对这种“数据孤岛”现象，安全多方计算（Secure Muti-party Computation）提供了一种解决方案，为实现数据的可控共享做出了重大贡献。

安全多方计算理论的提出

安全多方计算（Secure Muti-party Computation，简称MPC，亦可简称SMC或SMPC）问题首先由华裔计算机科学家、图领奖获得者姚期智教授于1982年提出，也就是为人熟知的百万富翁问题：两个争强好胜的富翁Alice和Bob在街头相遇，如何在不暴露各自财富的前提下比较出谁更富有？

【姚期智教授】

姚氏“百万富翁问题”后经O Goldreich、Micali以及Wigderson等人的发展，成为现代密码学中非常活跃的研究领域，即安全多方计算，其数学描述为，“ 有n个参与者P1,P2，…Pn，要以一种安全的方式共同计算一个函数，这里的安全是指输出结果的正确性和输入信息、输出信息的保密性。具体地讲，每个参与者P1，有一个自己的保密输入信息X1，n个参与者要共同计算一个函数f(X1,X2, … ,Xn)=(Y1,Y2, … ,Yn),计算结束时，每个参与者Pi只能了解Yi,不能了解其他方的任何信息。”

简单来说，安全多方计算协议作为密码学的一个子领域，其允许多个数据所有者在互不信任的情况下进行协同计算，输出计算结果，并保证任何一方均无法得到除应得的计算结果之外的其他任何信息。换句话说，MPC技术可以获取数据使用价值，却不泄露原始数据内容。

安全多方计算的技术架构如下图所示：

【MPC技术框架图 | 中国信息通信研究院《数据流通关键技术包皮书》】

当一个MPC计算任务发起时，枢纽节点传输网络及信令控制。每个数据持有方可发起协同计算任务。通过枢纽节点进行路由寻址，选择相似数据类型的其余数据持有方进行安全的协同计算。参与协同计算的多个数据持有方的MPC节点根据计算逻辑，从本地数据库中查询所需数据，共同就MPC计算任务在数据流间进行协同计算。在保证输入隐私性的前提下，各方得到正确的数据反馈，整个过程中本地数据没有泄露给其他任何参与方。

安全多方计算的主要特点

安全多方计算理论主要研究参与者间协同计算及隐私信息保护问题，其特点包括输入隐私性、计算正确性及去中心化等特性。

安全多方计算的关键技术

安全多方计算技术可以从参与方个数和计算场景来描述：

1. 参与方个数区分

根据参与方个数不同，可分为两方计算（two party computation，简称2PC）和多方计算（multi-party computation），这两者间存在本质的区别。

主流的两方计算框架的核心是用了混淆电路（Garbled Circuit，简称GC）和不经意传输（Oblivious Transfer）这两种密码学技术：一方将需要计算的逻辑转换为布尔电路，再将布尔电路中的每一个门进行加密的过程。在完成该操作后，该参与方将加密电路以及与其输入相关的标签发送给另一参与方，而另一方无法从标签中反推输入的信息。另一方（作为接收方）通过不经意传输按照其输入选取标签，并在此基础上对加密电路进行解密获取计算结果。

通用的多方安全计算框架可以让多方安全地计算任何函数或某类函数的结果。自1986年姚期智提出第一个通用的多方安全计算框架（常被称为Yao’s GC，即姚氏加密电路）以来，30多年间已经有BMR、GMW、BGW、SPDZ等多个多方安全计算框架陆续提出。至今，每年仍有大量的研究工作在改进和优化这些多方安全计算框架。这些框架涉及混淆电路、秘密共享（Secret Sharing，由Adi Shamir最先提出，秘密分享的原理是将每个参与者的输入分割为若干分片，散布在所有参与者当中，并通过这些分片来进行电路计算）、同态加密、不经意传输等多种密码学技术。

2. 计算场景区分

根据计算场景不同，可分为特定场景和通用场景。特定场景是指针对特定的计算逻辑，例如比较大小，确定双方交集等。具体场景可以采用多种不同的密码学技术设计协议。通用场景是指安全多方协议的设计要具有完备性，可以理论上支持任何计算场景，目前采用的方法主要是混淆电路，不经意传输以及同态加密。

目前，通用的两方计算（2PC）已经具备了商用的条件。多方计算在某些特定场景下也已经没有太多的性能瓶颈；而通用计算协议在可扩展性层面依然不够成熟，这也是学术界一直在探索的方向。

安全多方计算的适用场景

· 数据可信交换

· 数据安全查询

· 联合数据分析

安全多方计算技术的优势

安全多方计算是密码学研究的核心领域，解决一组互不信任的参与方之间保护隐私的协同计算问题，能为数据需求方提供不泄露原始数据前提下的多方协同计算能力，为需求方提供经各方数据计算后的整体数据画像，因此能够在数据不离开数据持有节点的前提下，完成数据的分析、处理和结果发布，并提供数据访问权限控制和数据交换的一致性保障。

安全多方计算拓展了传统分布式计算以及信息安全范畴，为网络协作计算提供了一种新的计算模式，对解决网络环境下的信息安全具有重要价值。利用安全多方计算协议，一方面可以充分实现数据持有节点间互联合作，另一方面又可以保证秘密的安全性。

安全多方计算与区块链技术的结合

区块链技术发展至今，特别是对于共有链而言，面临着两大困扰：一是公开数据带来的隐私问题；二是链上无法进行高效计算处理的性能问题。

隐私问题不但包括区块链上记录的交易信息的隐私，还包括区块链上记录以及传递的其他数据的隐私，这一点在大数据时代尤为重要。而高性能的计算一直都是区块链发展的一个瓶颈，在公有网络中，大量节点需要全部对计算任务进行处理，以保证计算任务处理结果的准确性和不可修改性。但这样做造成了严重的资源浪费和低效，同时，为了取得去中心化的效果，搭建节点的要求又不能太高，这一点又进一步影响了单个节点处理任务的能力。

这时候，安全多方计算的输入隐私性、计算正确性、去中心化等优点就可以很好地帮助解决这些问题。

安全多方计算技术与区块链技术对比如下所示：

【来源：中国信息通信研究院《数据流通关键技术包皮书1.0版》】

区块链的数字签名、不可篡改、可追溯、去中心化等优点，结合安全多方计算的输入隐私性、计算正确性、去中心化等特征，构成了下一代通用计算服务平台，实现了去中心化、数据保护、联合计算等综合特点，对上层业务形成新的技术支撑。