这是我的学习笔记，若有不足和错误之处，欢迎交流和指正，谢谢！
联系方式：lrcgnn@163.com
前言
联邦学习是参与者联合隐私培训的一种新范式，受到了学术界和产业界的关注。然而，一些研究表明，联邦学习传递的中间信息，如水平联邦学习中的梯度信息或垂直联邦学习中的嵌入信息，都表明了隐私泄露的风险。如何对这些中间信息保密是一个重要的研究课题。
[En]
Federal learning is a new paradigm of joint privacy training among participants, which has attracted the attention of academia and industry. However, some studies have shown that the intermediate information transmitted by federation learning, such as gradient information in horizontal federation learning or embedding in vertical federation learning, indicates the risk of privacy disclosure. How to keep these intermediate information confidential is an important research issue.
同态加密技术是一种很好的加密方案，允许对加密数据进行处理，得到的解密结果等价于在原始数据下做运算。例如对明文m m m进行加密，得到密文c c c，满足f ( c ) f(c)f (c )是f ( m ) f(m)f (m )的密文，其中f f f是任意属于某个函数族F F F的函数。半同态加密技术在联邦学习、区块链有很多的现实落地应用。通常来说，全同态加密的存在的问题在于计算成本大，运行效率低、密钥过大以及密文爆炸。
一、同态加密算法
1. 同态加密的类型
1.1 按照运算的类型来分：
加法同态：该加密方案支持的同态函数族为所有可以仅由加法实现的函数。目前使用比较广泛的是paillier加法同态。
乘法同态：该加密方案支持的同态函数族为所有可以仅由乘法实现的函数。比如经典的RSA加密方案。
1.2 按照支持的函数来分：
部分全同态（partially fully homomorphic encryption, somewhat homomorphic encryption or leveled fully homomorphic encryption）：该方案支持的同态函数族为有限次数的加法和有限次乘法能够实现的函数。实际应用中的同态加密算法多选取半同态加密（如加法同态），用于在特定应用场景中实现有限的同态计算功能。
全同态加密：该方案能够支持的同态函数族所有的加法和乘法可以实现的函数。比如BGV、BFV、CKKS。全同态加密仍处于方案探索阶段，现有算法存在运行效率低、密钥过大和密文爆炸等性能问题，在性能方面距离可行工程应用还存在一定的距离。
2.同态加密步骤
看到博客中清晰介绍同态加密的例子，我来分享一下Paillier算法。
2.1 非对称加密步骤
同态加密算法对加密的数据进行运算，非对称加密算法的步骤可分为四个步骤：
[En]
The homomorphic encryption algorithm operates on the encrypted data, and the steps of the asymmetric encryption algorithm can be divided into four steps:
第一步：生成一对密钥，包括一个公钥Pub()和一个私钥Pri()。
第二步：参与方1用公钥加密自己的数据m 1 m_1 m 1 ，获得加密的数据P u b ( m 1 ) Pub(m_1)P u b (m 1 )；参与方2用公钥加密自己的数据m 2 m_2 m 2 ，获得加密的数据P u b ( m 2 ) Pub(m_2)P u b (m 2 )。
第三步：服务器对加密数据P u b ( m 1 ) Pub(m_1)P u b (m 1 )以及加密数据P u b ( m 2 ) Pub(m_2)P u b (m 2 )进行数学运算，例如加法运算，获得计算加密后的数据M M M.
第四步：参与方获得服务器发送的加密数据M M M，可以利用私钥解密数据，即可以获得数据m 1 + m 2 m_1 + m_2 m 1 +m 2 .
上述过程非常适合联邦政府学习。参与者拥有本地数据，上述机制可以保证服务器只能获取加密的数据，从而保证了数据传输过程的安全性。
[En]
The above process is very suitable for federal learning. The participants have local data, and the above mechanism can ensure that the server can only get encrypted data, thus ensuring the security of the data transmission process.
2.2 几个关于同态加密Paillier 算法的问题：
a) 如何生成密钥？
随机选择两个质数 p 和 q 满足 ∣ p ∣ = ∣ q ∣ = τ |p|=|q|=\tau ∣p ∣=∣q ∣=τ，这个条件保证了 p 和 q 的长度相等。
计算 N = p q N=pq N =p q 和 λ = l c m ( p − 1 , q − 1 ) \lambda = lcm(p-1,q-1)λ=l c m (p −1 ,q −1 )
注：lcm 表示最小公倍数。
随机选择 g ∈ Z N 2 ∗ g\in Z_{N^2}^*g ∈Z N 2 ∗，满足 g c d ( L ( g λ m o d N 2 ) , N ) = 1 gcd(L(g^\lambda mod N^2),N)=1 g c d (L (g λm o d N 2 ),N )=1，
注：gcd 表示最大公约数；Z 表示整数，下标表示该整数集合里有多少个元素；L ( x ) = x − 1 N L(x)=\frac{x-1}{N}L (x )=N x −1 ，公钥为 ( N , g ) (N,g)(N ,g )，私钥为 λ \lambda λ。
b) 如何加密？
对于任意整数 m ∈ Z N m\in Z_N m ∈Z N ，任意选择随机数 r ∈ Z N ∗ r\in Z_N^*r ∈Z N ∗，密文 C = E ( m ) = g m r N m o d N 2 C=E(m)=g^mr^N mod N^2 C =E (m )=g m r N m o d N 2
上述解答内容来源地址。
2.3 其他资源
实现同态加密RSA 算法过程中，密钥生成，加密，解密三部曲的python代码：https://github.com/wdxtub/federated-learning-note/blob/main/flt-03/rsa_sample.py
博客中介绍python实现联邦学习中使用同态加密方法。代码链接：https://blog.csdn.net/wutianxu123/article/details/124110931
同态加密介绍引用自：https://blog.csdn.net/watqw/article/details/122648319
二、基于同态加密的联邦学习
下面介绍基于同态加密算法的联邦学习。
正如前言所述，联邦学习中诚实但是好奇的服务器可能从参与方上传的梯度信息中窃取隐私数据，这种威胁最典型的应该就是用20多行代码写的DLG论文吧。解决这个问题的一个办法就是：让服务器拿不到明文梯度信息！当服务器端只能对密文数据进行密文操作时，这种原始梯度信息泄露隐私问题也得到解决。
1.步骤
横向联邦学习中的同态加密算法可以分为三个步骤：
第一步：参与者首先加密本地模型，然后使用本地数据估计有偏的参数，并上传加密模型的梯度。
[En]
Step 1: participants first encrypt the local model, then use the local data to estimate the parameters biased, and upload the gradient of the encryption model.
步骤二：服务器聚合本地的模型梯度，进行密文运算操作。
步骤3：服务器发送加密的模型参数。在参与者解密新一轮全局模型参数后，继续执行步骤1。
[En]
Step 3: the server sends the encrypted model parameters. After the participants decrypt the new round of global model parameters, proceed to step 1.
2.细节
上述的基于同态加密的联邦学习框架中存在一个细节： 谁来生成密钥？参与方的私钥都是一样的吗？
密钥的生成应该由参与者进行，否则服务器在拥有私钥后也可以对明文信息进行解密，带来不安全。一般来说，联邦学习的参与者共享一套公钥和私钥，当这些参与者诚实的时候，一旦他们想用服务器做坏事，就很容易造成新的安全问题。第二种情况可以通过使用门限同态加密算法来缓解，即允许多套公钥和私钥。
[En]
The generation of the key should be carried out by the participants, otherwise the server can also decrypt the plaintext information after it has the private key, which brings insecurity. Generally speaking, participants in federal learning share a set of public and private keys, and when these participants are honest, it is easy to cause new security problems once they want to do bad things with the server. The second case can be alleviated by using * threshold homomorphic encryption algorithm * , that is, multiple sets of public and private keys are allowed.
图片来自于链接
上面的图片来源于：论文
此外，看到一张很漂亮的图：
图片来自论文
在联邦学习中引入同态加密技术后在一定程度保护模型隐私，但是必不可少增加计算时间和内存资源占用。下面的图片中的时间统计是来自于 NVIDIA的同态加密联邦学习框架。
这个开源的同态加密联邦学习开源框架分享给大家，项目内容为：Running FL with secure aggregation using homomorphic encryption。该项目基于两个开源项目：TenSEAL library by OpenMined & a convenient wrapper around Microsoft SEAL.
分享基于同态加密的联邦学习papers:
Zhang, Chengliang, et al. “{BatchCrypt}: Efficient Homomorphic Encryption for {Cross-Silo} Federated Learning.” 2020 USENIX Annual Technical Conference (USENIX ATC 20). 2020.
; 三、同态加密的代码实现(Python版)
1.手写代码
代码参考链接：https://gist.github.com/djego/97db0d1bc3d16a9dcb9bab0930d277ff
import random
'''
Euclid's algorithm for determining the greatest common divisor
Use iteration to make it faster for larger integers
'''
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
'''
Euclid's extended algorithm for finding the multiplicative inverse of two numbers
'''
def multiplicative_inverse(e,r):
for i in range(r):
if((e*i)%r == 1):
return i
def is_prime(num):
if num == 2:
return True
if num < 2 or num % 2 == 0:
return False
for n in range(3, int(num ** 0.5) + 2, 2):
if num % n == 0:
return False
return True
def generate_keypair(p, q):
if not (is_prime(p) and is_prime(q)):
raise ValueError('Both numbers must be prime.')
elif p == q:
raise ValueError('p and q cannot be equal')
n = p * q
phi = (p - 1) * (q - 1)
e = random.randrange(1, phi)
g = gcd(e, phi)
while g != 1:
e = random.randrange(1, phi)
g = gcd(e, phi)
d = multiplicative_inverse(e, phi)
return ((e, n), (d, n))
def encrypt(pk, plaintext):
key, n = pk
cipher = [(ord(char) ** key) % n for char in plaintext]
return cipher
def decrypt(pk1, pk2, ciphertext):
key, n = pk1, pk2
plain = [chr((char ** key) % n) for char in ciphertext]
return ''.join(plain)
if __name__ == '__main__':
p = int(input("输入一个素数: "))
q = int(input("再输入一个素数: "))
public, private = generate_keypair(p, q)
print("为你生成的公钥是：", public)
print("为你生成的私钥是：", private)
message = input("输入需要加密的数据: ")
encrypted_msg = encrypt(public, message)
print("您获得的密文是：", ''.join(map(lambda x: str(x), encrypted_msg)))
privatee = []
privatee.append(int(input('输入您的私钥前排序列')))
privatee.append(int(input('输入您的私钥后排序列')))
print('密文的解密结果为：', decrypt(privatee[0], privatee[1], encrypted_msg))
输出结果：
2.调包实现乘法同态加密
import rsa
(public_key, private_key) = rsa.newkeys(512)
print('公钥为：{} 私钥为：{}。'.format(public_key, private_key))
emessage = 'Hello world!'.encode('utf-8')
crypto = rsa.encrypt(emessage, public_key)
print(crypto)
dmessage = rsa.decrypt(crypto, private_key)
print(dmessage.decode('utf8'))
输出结果为：
公钥为：PublicKey(8095059374219196630454198555684841855555779377170836284535186351217329395948699458601330730050809264266228630028651115426719314399559600212173369081099979, 65537) 私钥为：PrivateKey(8095059374219196630454198555684841855555779377170836284535186351217329395948699458601330730050809264266228630028651115426719314399559600212173369081099979, 65537, 3373672226193584045159154754587791409444970049417383332156027050533270024472236092302389157206342283683740184679587325263536984653117242945602120034664897, 7238673580383412616612813154973643099381838015408521462886068127059748767382973867, 1118307005327131164182883905657023822538740327140066922538214293760080737)。
b'A\x10_\x8cUC\xe2\xaf\xda\x18\x9d\xc7nr1}\xcd3\xdfQ\xa6\x9f\xb2W
Hello world!
此外，对于加法同态加密也有很多包，推荐使用phe。直接pip install phe就可以了。
四、基于同态加密的FL实战(Python版)
2022年5月30日前更新
推荐阅读
[1] 联邦学习|同态加密：实现数据的”可算不可见”
[2] 基于同态加密的横向联邦学习
[3] 联邦学习与密码学
Original: https://blog.csdn.net/qq_42217215/article/details/124889240
Author: lrchang
Title: 【联邦学习邂逅密码学系列】基于同态加密算法python代码实现
相关阅读
Title: Deep Reasoning with Knowledge Graph for Social Relationship Understanding 阅读笔记
0 摘要
任务：社交关系推理
现状：以往的研究忽略了(i)社交关系之间的相互影响，(ii)人周围的场景信息
解决办法：
1 提出了一个端到端的可训练图推理模块，探索人与前后物体的交互关系。
2 引入图注意力机制，促进可区分的物体的识别。
1 引言
图一的目的；想说明推理两个人之间的关系是件不容易的事情。
原因一：不同场合下会有不同的的社交关系，原因二：不同场合会有不同的周边线索（contextual cues）。这里的原因一，二在图中都有所反映。
这个图在introduction的作用，也是一个引子，目的想说明对社交关系与contextual cues的相互作用进行建模的必要性.
继续讲前人工作的缺点：忽略了 semantic of contextual objects，the prior knowledge of their correlations with the social relationships，the interaction between the contextual objects and the persons of interest is oversimplified.
接下来讲做法，贡献。
; 2 相关工作
注意论文调研，故事线的编写，以及论文如何引出来自己的研究点。
[En]
Pay attention to the research of the paper, the compilation of the storyline, and how the paper leads to its own research point.
主要是关于社交关系识别，知识表征方向的调研。
3 图推理模块
（图的设计思路理解（核心图）图为什么这样设计？考虑图与论文提出来的创新点的关系。）
[En]
(understanding of the design idea of the diagram (core diagram) Why is the diagram designed in this way? Consider the relationship between the diagram and the innovation proposed in the paper. )
图推理模块：
○1 按照[Li et al., 2017]提取人的特征，并用这些特征初始化关系节点。
1.1 过程：首先将修剪为三个区域，(i)两个人的联合体（ii）分开的两个人。
1.2 CNN对两个人的几何特征进行编码得到位置信息，将这些信息输入到一个全连接层，输出d维的特征向量。这些特征向量用于初始化社交关系节点。
○2 用Faster-RCNN检测器提取特征，并用这些特征初始化相关物体节点。
2.1用Faster-RCNN检测器检测到图片的物体，比如人，领带，电脑，而后提取这些特征用以初始化相关物体节点。
○3 用GGNN（迭代式）探索人与周边物体的交互关系。
○4最后使用图注意力机制，选出来最有用的节点。
; 4 实验
（主要关注消融实验的设计，注意考虑消融实验是为了证明什么？）
[En]
(mainly focus on the design of the ablation experiment, pay attention to what the ablation experiment is to prove? )
4.1 与最先进的方法对比
在PISC数据集上，将我们的图推理模块与现存的最先进的方法做对比。
结合各种方法的特色，对表进行分析。
比如：1结合Pair CNN + BBox + Union 和Pair CNN + BBox + Global能够提取整张图片的特征信息作为上下文信息的特点，我们推理知，Pair CNN + BBox + Union 和Pair CNN + BBox + Global在本表中表现好是因为这些方法可以用到周边的线索。
Dual-glance 结果更好，是因为它捕捉到了更细层次的局部线索，而非全局线索.
进而分析我们与之不同的地方：我们的方法用的是更高层次的知识图来推理周边信息，这些周边信息是一个很有助于社交关系识别的线索。
[En]
And then analyze the differences between us: our method uses a higher-level knowledge graph to infer the surrounding information, which is a clue that is very helpful to the identification of social relationships.
; 4.2 消融实验
4.2.1 验证知识图的有效性；
方法：随机初始化图的邻接矩阵与不随机初始化图的邻接矩阵。（后者用提取的信息用于初始化图的邻接矩阵）
[En]
Methods: the adjacency matrix of random initialization graph and the adjacency matrix of non-random initialization graph. (the latter uses the extracted information to initialize the adjacency matrix of the graph)
结果表明：用先验知识（prior knowledge）能提高社交关系识别.
; 4.2.2 验证图注意力机制的有效性。
方法：1，不移除图注意力模块，但是将图注意力模块学习到的注意系数用随机选择的分数来替换，2，移除图注意力模块，仅仅整合关系节点和物体节点用于识别。3 我们的full model。
结果表明：3与2 相比表明图注意力模块的有效性，3与1相比可以表明图注意力模块学习到的注意系数有助于社交关系识别。
4.2.3 选择合适的临界值用于侦测器来检测出合适的语义物体。
（低的临界值会检测出无关物体，而高的临界值会漏掉重要的周边线索。）方法：选择不同的临界值来找到最优的临界值。
[En]
(a low threshold will detect irrelevant objects, while a high threshold will miss important peripheral clues. ) method: select different critical values to find the optimal critical value.
; 4.2.4 定性分析。
以一张图来帮助读者理解定性分析。
○1 在第一个例子中电脑，杯子，，书桌，等都被检测出来用以初始化图中的相关节点，
○2但是像书桌，杯子经常发生在社交场景中，几乎不能提供有用的信息，而电脑更容易与职业信息关联。
○3图注意力机制就是这样给有用的节点比较高的分，给没用的节点比较少的分，来助社交关系识别。
○4第二个例子，图注意力机制关注于碗和披萨来助社交关系-朋友识别。
5 总结
论文做了什么事，实验结果表明我们的领先性。
Original: https://blog.csdn.net/qq_43187760/article/details/113663873
Author: 捡贝壳的男孩
Title: Deep Reasoning with Knowledge Graph for Social Relationship Understanding 阅读笔记
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/177247/
转载文章受原作者版权保护。转载请注明原作者出处！
