笔记分享 | 组队学习密码学（2）——密码学在联邦学习中的应用
本次笔记是对2023年4月23日组队学习密码学第二期：密码学在联邦学习中的应用的内容整理，讲座分为两部分，分享老师是来自于昇思MindSpore的安全可信专家金老师和张老师，两位老师的讲座题目分别是：
基于Diffe-Hellman密钥协商以及Shamir’s Secret Sharing协商的安全聚合算法
基于抗碰撞的安全哈希以及椭圆曲线数乘的PSI算法
本文有不正确的地方欢迎在留言区指出纠正~
基础概念
在主题内容开始之前，金老师先介绍了联邦学习的基本概念和分类。
基本概念
通俗来讲，每一个客户端拥有自己的数据集，但是出于隐私考虑，他们不想暴露自己的数据集，又想要共同训练一个模型，这时就可以利用联邦学习，每个客户端在本地训练模型，再上传参数至一个中心服务器进行聚合，中心服务器更新模型参数后，发送给各个客户端继续训练，重复这个过程，最终中心服务器的模型就是共同训练好的模型，在这个过程中每个参与方的数据集都是保留在本地的。
分类
联邦学习算法可以根据不同的角度进行不同的分类，参考联邦学习算法分类总结。本次讲座金老师主要介绍横向联邦学习和纵向联邦学习。
横向联邦学习表示各个客户端数据集的特征重合度高，但是数据id不同，在应用基本的联邦学习算法时，虽然每个客户端没有直接暴露自己的数据集但是已有工作表明通过其上传的模型参数或者梯度信息可以反推出训练集的信息，同样破坏了隐私。因此，采用差分隐私或安全聚合的方法才能进一步保护好数据集的隐私。金老师稍后将对安全聚合的方法进行讲解。
在纵向联邦学习中，各个客户端数据集的数据id重合度高，但是特征差别较大。所以在训练模型时，要进行重要的一步——数据对齐，也就是要各个客户端利用他们相同数据id的数据进行训练。这个过程各个客户端不能直接暴露自己数据集的数据id，因此可以采用PSI的方法进行解决，这部分由张老师进行讲解。
安全聚合方法
2.1 算法基本组件
Diffie-Hellman密钥协商
加密算法分为对称加密和非对称加密，在利用对称加密时，通信双方需要拥有相同的密钥进行加解密。但是，除了口头约定好密钥外，如何在非安全信道传输加密密钥呢？这个过程如果导致密钥泄露了，那谁都可以解密密文，这样是极其不安全的。
利用Diffie-Hellman密钥协商方法可以让双方安全地协商一个密钥，首先看一下方法利用的数学基础——离散对数困难问题：
下面具体看一下DH算法的过程：
在这个过程中，如果攻击者获得了，但是他也无法得到Alice的私钥（离散对数困难问题），同理。可以看到Alice和Bob最后就协商出了一个相同的密钥。
上述的DH算法稍加改动还可以变形为非对称加密算法：
Shamir’s Secret sharing
通过上图所示的算法，可以将秘密值分为个份额，其中至少个份额才能恢复出秘密值，更多的秘密分享方法可以参考笔记分享 | 冯登国院士MPC讲座（2）——基于秘密分享方法的安全多方计算协议。
2.2 安全聚合算法
金老师本次分享的安全聚合方法是参考了17年CCS的论文《Practical Secure Aggregation for Privacy-Preserving Machine》：
思路：
通过DH密钥协商算法，客户端两两之间协商出密钥，然后利用协商的密钥生成自己的噪声扰动，最后将所有的噪声扰动添加到秘密值上，这样服务器在收到时并不会知道的值，同时由于聚合会导致噪声扰动消除，最后得到的结果也是正确的。
存在的问题：
上述方法依赖于两两成对的噪声消除，考虑现实场景下客户端容易掉线的情况（移动设备），这时噪声扰动并不能消除，导致最终的聚合结果错误，如何解决呢？
防止掉线的方法：
可以看到上述方法考虑了很多实际场景中掉线的情况，最终的聚合结果也是针对于最终没有掉线的客户端上传的数据。主要思想就是通过秘密分享的方式解决客户端掉线的问题（即使他掉线了，他引入的扰动也可以通过其他客户端拥有的份额恢复出来进而消除掉）。
存在的问题：
上述过程中的中心服务器都是诚实工作的，但是当中心服务器欺骗客户端说某一个客户端掉线了需要恢复他的扰动时，服务器就可以利用恢复出的扰动抵消该客户端上传的扰动从而得到了真实上传数据，破坏了隐私。
论文里提到了double masking的方法处理这种情况：
考虑到实际场景中客户端上传的数据维度可能是很大的，这样加入的扰动维度也很大，会导致通信开销很大。所以可以利用伪随机数生成器，降低通信开销：
如果服务器不诚实，他还可以做中间人攻击，通过发送服务器自己产生的公私钥对给客户端，这样服务器就可以计算出客户端加入的扰动值，从而获得客户端上传的真实数据。
针对这种情况可以采用数字签名的方法解决：
更详细的内容可以阅读论文原文：
https://dl.acm.org/doi/10.1145/3133956.3133982
PSI算法
张老师首先介绍了一下方法用到的基本组件PSI：
这里只要了解PSI的功能即可，其主要应用在纵向联邦学习中的数据对齐、计算广告转化率、私有联系人发现等。
张老师从工程的角度讲解了如何进行方案的选择：
1. 首先在选择采用PSI的哪种协议时，应分析应用场景的特点和客户需求：
数据量大：原始数据集合上有上亿甚至十亿的数据量
数据量级不平衡：一方数据量是另一方的十倍或百倍
求交方为两个服务器：算力资源充足
不需要恶意安全性：攻击者是半诚实的
双方均要获得交集
2. 再调研已有方案：
3. 最终确定了基于椭圆曲线上的DH密钥协商协议的PSI（ECDH-PSI）方法。
该方法具有以下特点：
实现简单：只需要进行哈希到曲线、椭圆曲线点的数乘两种操作
性能符合要求：通信开销小，计算量虽然较大但服务器性能可以支持
能够较好地应对数据量不平衡的场景
算法提出时间久，可靠性较高
具体的技术流程：
第一步：采用抗碰撞的安全哈希将参与方的原始数据映射到椭圆曲线。
其中抗碰撞意味着：对于任意, 的概率是一个可忽略函数。
老师提到如果发生了碰撞，那么会导致数据对齐出现问题（本来并不是交集的数据出现在了结果集合中），导致后续的联邦学习训练发生错误。
后续步骤：
有了上述的基础，就可以进行PSI的步骤，如下图所示：
优化方法：
当两方数据量不平衡时，应该让数据量大的那方作为Alice（因为只需要对大数据集进行点乘1次）通过布隆过滤器可以优化上述算法（不仅仅可以用布隆过滤器，也可以用其他的数据压缩算法，例如布谷鸟过滤器，根据应用不同方法实际的效率选择）。
布隆过滤器是一种数据结构，可以压缩表示数据：
可以看出，由于hash函数的碰撞，布隆过滤器的结果并不是完全准确的，会有假正例的情况，但是如果参数选择恰当，可以设定假正例率为：，通信开销可降低，匹配复杂度从降低至。
最终流程为：
这里在Bob求完交集后会发送结果给Alice，Alice还会进行一步FindWrong的操作，确定最后的结果。
张老师提到上述流程参与方内部还可以进行并行计算，利用多线程同时处理多个相同任务：
哈希到椭圆曲线；
椭圆曲线数乘；
布隆过滤器插入、查找；
查找错误数据；
张老师介绍的知识参考了论文《Faster Unbalanced Private Set Intersection》
感兴趣的小伙伴可以阅读论文原文：
https://eprint.iacr.org/2017/677
以上就是组队学习密码学第二期的笔记分享，笔记中有错误的地方还请各位小伙伴在留言区批评指正，大家互相交流，共同进步！另外感兴趣的小伙伴可以点击笔记分享 | 组队学习密码学（1）——密码学与MPC基础复习一下上一期的内容~
往期推荐
1.一文搞懂分组密码——DES、AES、IDEA
2.笔记分享 | 冯登国院士MPC讲座（3）——基于混淆电路方法的安全多方计算协议会议信息 | 2023年6月截稿的密码学与信息安全会议整理4.论文分享 | Endemic Oblivious Transfer via Random Oracles, Revisited