联邦学习样本对齐之隐衷汇合交加 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