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

  1. 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