联邦学习样本对齐之隐私集合交集RSA加盲

联邦学习样本对齐之隐私集合交集RSA加盲

1 联邦学习背景

鉴于数据隐私的重要性，国内外对于数据的保护意识逐步加强。2018年欧盟发布了《通用数据保护条例》（GDPR），我国国家互联网信息办公室起草的《数据安全管理办法(征求意见稿)》因此数据在安全合规的前提下自由流动，成了大势所趋。这些法律法规的出台，不同程度的对人工智能传统处理数据的方式提出更多的挑战。
AI高度发展的今天，多维度高质量的是制约其进一步发展的瓶颈。随着各个组织对于数据的重视程度的不断提升，跨组织以及组织内部不同部门之间的数据合作将变得越来越谨慎，造成了数据大量的以孤岛的形式存在。

2 样本对齐概念

联邦学习的本质是基于数据隐私保护一种分布式机器学习技术或机器学习框架。它的目标是在保证数据隐私安全及合法合规的基础上，在模型无损的前提实现共同建模，提升AI模型的效果，进行业务的赋能。 联邦学习分为横向联邦学习与纵向联邦学习，本章针对纵向联邦学习的场景进行分析。相对于传统的机器学习算法训练，纵向联邦学习的样本分属于不同的组织（如下图所示），各个组织的样本的覆盖范围各有差异，所以在进行联邦模型训练的第一步就是要进行跨域的样本对齐，找出交集，交集的方式一般是通过Join健（比如下图的ID证件号），ID可以是手机号、身份证号这种非常敏感的信息，这些敏感信息不适合直接进行交集的计算，需要进行签名处理，并且要保障不被破解。有些联邦平台使用MD5，但是MD5存在撞库造假的风险，所以需要一种隐私计算发方案，比较庆幸的是，关于集合隐私交集PSI的方案还是比较多，下面就给大家分享一下。 

                            图2 样本隐私对齐

3 隐私PSI方案介绍

目前集合隐私交集PSI的方案较多，大致有以下集中方案：

1. Blind RSA-based PSI Protocol with linear complexity。
2. 基于Diffie-Hellman的方案。
3. 基于不经意传输（oblivious transfer，OT）的方案。

4. Freedman安全求交协议。

   本章主要讲解基于Blind RSA-based PSI Protocol with linear complexity。由于该协议使用到RSA加密方案，如果不对RSA进行讲解的话，对于整个方案的推导会造成一些不便之处，所以本文先对RSA加密算法进行一些描述与讲解。 

4 RSA加密方案介绍

首先讲解下基础的数论里面的知识，对于后续的RSA以及隐私求交协议的理解有比较大的帮助。

4.1 数学基础-RSA

以下内容来自维基百科。
RSA加密算法是一种非对称加密算法，在公开密钥加密和电子商业中被广泛使用。RSA是由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）在1977年一起提出的。当时他们三人都在麻省理工学院工作。RSA 就是他们三人姓氏开头字母拼在一起组成的。[1]
1973年，在英国政府通讯总部工作的数学家克利福德·柯克斯（Clifford Cocks）在一个内部文件中提出了一个与之等效的算法，但该算法被列入机密，直到1997年才得到公开。[2]
对极大整数做因数分解的难度决定了 RSA 算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA 算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用 RSA 加密的信息的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的 RSA 钥匙才可能被强力方式破解。到目前为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被破解的。
1983年9月12日麻省理工学院在美国为RSA算法申请了专利。[3]这个专利于2000年9月21日失效。[4]由于该算法在申请专利前就已经被发表了[5]，在世界上大多数其它地区这个专利权不被承认。

4.1.1 质数（素数）

质数（Prime number），又称素数，指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个正因数的数）。大于1的自然数若不是素数，则称之为合数（也称为合成数）。例如，5是个素数，因为其正约数只有1与5。而6则是个合数，因为除了1与6外，2与3也是其正约数。
算术基本定理确立了素数于数论里的核心地位：任何大于1的整数均可被表示成一串唯一素数之乘积。为了确保该定理的唯一性，1被定义为不是素数，因为在因式分解中可以有任意多个1（如3、1×3、1×1×3等都是3的有效约数分解）。

4.1.2 互质

互质是公约数只有1的两个整数，叫做互质整数。公约数只有1的两个自然数，叫做互质自然数，后者是前者的特殊情形。
例如8,10的最大公因数是2，不是1，因此不是整数互质。
7,11,13的最大公因数是1，因此这是整数互质。
5和5不互质，因为5和5的公因数有1、5。
1和任何数都成倍数关系，但和任何数都互质。因为1的因数只有1，而互质数的原则是：只要两数的公因数只有1时，就说两数是互质数。因为1只有一个因数所以1既不是质数（素数），也不是合数，无法再找到1和其他数的别的公因数了。1和-1与所有整数互素，而且它们是唯一与0互素的整数。

4.1.3 欧拉函数

在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目。例如在1到8之中，与8形成互质关系的是1、3、5、7，所以 φ(n) = 4。
特殊情况（后面RSA会有到）：如果n可以分解成两个互质的整数之积，n = p1 × p2，则n的欧拉函数计算为：φ(n) = φ(p1p2) = φ(p1)φ(p2)。上述公式的证明需要用到“中国剩余定理”，有兴趣的读者可以自行查找资料研究，这里就不过多介绍了。

4.1.4 欧拉定理

前面介绍了欧拉函数，现在介绍下欧拉定理，欧拉定理里面使用了欧拉函数。欧拉定理定义：如果两个正整数a和n互质，则n的欧拉函数 φ(n) 可以让下面的等式成立，可以理解为a的φ(n)次方被n除的余数为1。

特例：费马小定理，
定义：假设正整数a与质数p互质，因为质数p的φ(p)等于p-1，则欧拉定理可以写成

也可以表示为：

欧拉定理是RSA算法的核心。理解了这个定理，就可以理解RSA。

4.1.5 模逆运算（模反元素）

模逆运算也叫做模反元素，定义如下：如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。这时，b就叫做a的“模反元素”。

模拟预算在Blind RSA-based PSI Protocol with linear complexity中最后Client侧的签名的推导过程中，将会起到非常大的作用，大家到时候可以仔细体会。

4.2 RSA加密解密

4.2.1 RSA秘钥生成流程

1. 随机选择生成两个不想动的素数P和Q。
2. 计算P和Q的成绩N。（N的二进制的位数就是RSA秘钥的长度，从安全性来说建议1024以上，比较稳妥的选择是2048）。
3. 计算N的欧拉函数φ(N)。
4. 随机选择一个整数E，条件：1 < E < φ(N)，且E与φ(N)互质。
5. 计算E对于φ(N)的模反元素D。

至此，RSA算法需要的五大元素已经生产，E与N作为公钥的成员。其余都保留在私钥侧。

4.2.2 RSA加密解密流程

1. Bob要发送的原始数据是n，加密要传输的数据c，这个计算过程并不复杂，并且将n传输给Alice，如下图：

2. Alice得到Bob的消息c后，就可以利用她的密钥d来解码，计算出原始的数据n

4.2.3 RSA加密解密证明

5 Blind RSA-based PSI Protocol with linear complexity

5.1 方案介绍

        Blind RSA-based PSI Protocol with linear complexity

5.2 协议详细推导流程

本节将针对上一节的图进行数学公式的分析与推导，推导过程尽量详细，本章节的推导基本用到了上面介绍RSA方案中的公式，另外有兴趣的同学也可以自行看下数论里面的知识，进而完成整个PSI协议的推导。
准备工作：

1. Server侧的样本ID集合{hc1, hc2, …,hcv}，Client侧的样本ID集合{hs1, hs2, hsw}
2. Server产生RSA加密的公钥与秘钥，秘钥保留在Server端，公钥（e，n）下发到Client端。
3. Full-Domain Hash H。（小于n，并且与n互质，数据量特别大的情况下要考虑空间问题）。

4. Client随机数R。（小于n，并且与n互质）
   下面详细描述下交互的流程，针对上图进行讲解。

   5.2.1第一步

   Server侧计算样本对齐ID（手机号、身份证号等）的最终签名。计算方式如下： 

5.2.2 第二步

Client侧生成一个随机数Rc（大于1小于n，并且与n互质），并且针对要对齐的ID进行公钥加密处理，然后乘以Rc进行加盲扰动。 

5.2.3 第三步

Client侧将上述加盲扰动的乘积值传递给Server侧。

5.2.4 第四步

Server侧接受Client侧发送的数据，并且进行使用私钥进行签名的初步计算。  

5.2.5 第五步

Server侧将初步计算的签名传输给Client侧继续完成去盲的操作，生产最后的Client ID的签名工作，并且发送Server侧的ID的签名，与Client的ID签名进行样本对齐。 

5.2.6 第六步

这样Client侧的ID也进行了签名，可以与Server侧的ID进行对齐了。

5.3 总结

上面已经完成了整个方案的推导过程，在推导过程中，都是根据自己的理解进行的分析，如果有不恰当的地方欢迎大家指出。 另外这个协议如果直接用到工程领域，如果数据量在可控，单机内存可以可以容纳的情况下，是没有问题的，但是基于超大数据规模的隐私对齐的时候，会有问题，笔者在京东联邦学习平台9N-FL的系统里面对协议进行了相关的改造与优化，使之适用于超大规模的样本隐私对齐，在项目中支撑千亿量级的样本的隐私对齐工作。

6 参考资料

1. Calderbank, Michael. The RSA Cryptosystem: History, Algorithm, Primes (PDF). 2007-08-20. （原始内容 (PDF)存档于2016-12-13）.
2. ^ Cocks, C.C. A Note on Non-Secret Encryption (PDF). www.gchq.gov.uk. 1973-11-20 [2017-05-30]. （原始内容存档 (PDF)于2017-02-16）.
3. ^ Cryptographic communications system and method, 1977-12-14 [2018-04-09], （原始内容存档于2019-02-17）
4. ^ RSA Security Releases RSA Encryption Algorithm into Public Domain. [2010-03-03]. （原始内容存档于2007-06-21）.
5. ^ Robinson, Sara. Still Guarding Secrets after Years of Attacks, RSA Earns Accolades for its Founders (PDF). SIAM News. June 2003, 36 (5) [2018-04-09]. （原始内容 (PDF)存档于2017-01-16）.
6. RSA加密算法：https://zh.wikipedia.org/wiki…
7. Emiliano De Cristofaro and Gene Tsudik. Practical Private Set Intersection Protocols with Linear Computational and Bandwidth Complexity. Jan. 2009. Available: https://eprint.iacr.org/2009/…
8. Gang Liang and Sudarshan S. Chawathe. Privacy-Preserving Inter-Database Operations. Jun. 2004. Available: https:// https://drum.lib.umd.edu/bits…;sequence=1

9. 崔泓睿, 刘天怡等，隐私保护集合求交技术 (PSI) 分析研究报告，https://anquan.baidu.com/uplo…

   7 番外篇

   个人介绍：杜宝坤，从0到1带领团队构建了京东的联邦学习解决方案，实现了电商营销领域支持超大规模的工业化联邦学习解决方案，支持超大规模样本PSI隐私对齐、安全的树模型与神经网络模型等众多模型支持，并且实现了业务侧的落地，开创了新的业务增长点，产生了显著的业务经济效益。
   个人喜欢研究技术。基于从全链路思考与决策技术规划的考量，研究的领域比较多，从架构、数据到算法与算法框架均有涉及。欢迎喜欢技术的同学和我交流，邮箱：baokun06@163.com

[温馨提示：高防服务器能助您降低 IT 成本，提升运维效率，使您更专注于核心业务创新。]

[图文来源于网络，不代表本站立场，如有侵权，请联系高防服务器网删除]