联邦学习:加密算法Paillier,Affine,IterativeAffine
本文介绍联邦学习中用到的几种加密算法的实现过程,不涉及原理。
1.知识准备
这里要首先介绍加密算法牵扯到的几个基础知识,简单介绍,不讲原理,方便后续理解。
1.1 同态加密
同态加密的概念:对加密后的数据进行特定形式的代数运算,对运算结果进行解密,得到的结果和对原数据进行相同的代数运算得到的结果相同。换言之,用户可以不经过解密,直接对密文进行运算,而不影响最终的结果。
1.2 乘法逆元
不是倒数!
1.2.1 线性同余方程
介绍乘法逆元之前,还要先介绍一下线性同余方程:
a
x
≡
b
(
m
o
d
n
)
\large ax\equiv b\; (\mod n)
ax≡b(modn)
所谓同余,即,
a
x
/
n
ax/n
ax/n得到的余数和
b
/
n
b/n
b/n得到的余数相等。
方程有解的充要条件为,b能够被a与n的最大公约数整除(a与n的最大公约数记为
gcd
(
a
,
n
)
\gcd(a,n)\,
gcd(a,n))
1.2.2 乘法逆元
乘法逆元定义为:
a
x
≡
1
(
m
o
d
n
)
解
x
为
a
的
乘
法
逆
元
,
记
为
a
−
1
,
\large ax \equiv 1\;(\mod n)\\ 解x为a的乘法逆元,记为a^{-1},
ax≡1(modn)解x为a的乘法逆元,记为a−1,
即ax除n的余数为1。
a在模n的条件下,存在乘法逆元的充分必要条件为a与n互质,及
gcd
(
a
,
n
)
=
1
\gcd(a,n)=1
gcd(a,n)=1。
1.2.2.1 乘法逆元的求解
1.循环求解,挨个试。
2.费马小定理。费马小定理定义:a与n为质数,则
a
n
−
1
/
n
=
1
,
所
以
,
a
−
1
=
a
n
−
2
a^{n-1}/n=1,所以,a^{-1}=a^{n-2}
an−1/n=1,所以,a−1=an−2
3.等等。
1.3 剩余系和简化剩余系
- 剩余系:一个数模n所得的余数域,称为剩余系,记为 Z n , 例 如 : Z 6 = { 1 , 2 , 3 , 4 , 5 } \mathbb{Z}_n,例如:\mathbb{Z}_6=\{1,2,3,4,5\} Zn,例如:Z6={1,2,3,4,5}。
- 简化剩余系,一个数模n所得的余数域中与n互质的余数所组成的余数域,称为简化剩余系,记为 Z n ∗ , 例 如 : Z 6 ∗ = { 1 , 5 } \mathbb{Z}_n^*,例如:\mathbb{Z}_6^*=\{1,5\} Zn∗,例如:Z6∗={1,5}。
【注】剩余系和剩余类不同,剩余类是对整数进行的重新归类,这里我们记作 Z n + , 例 如 : Z 6 + = { [ 1 ] 6 , [ 2 ] 6 , [ 3 ] 6 , [ 4 ] 6 , [ 5 ] 6 } , 其 中 [ 1 ] 6 为 所 有 模 6 余 数 为 1 的 数 集 , [ 1 ] 6 = { 1 , 7 , 13... } \mathbb{Z_n^+},例如:\mathbb{Z_6^+}=\{[1]_6,[2]_6,[3]_6,[4]_6,[5]_{6}\},其中[1]_6为所有模6余数为1的数集,[1]_6=\{1,7,13...\} Zn+,例如:Z6+={[1]6,[2]6,[3]6,[4]6,[5]6},其中[1]6为所有模6余数为1的数集,[1]6={1,7,13...}。
2.Paillier encryption
2.1 计算过程
Paillier通过公钥对明文进行加密,使用**对密文进行解密。其运算过程如下:
【注】:我们用
a
m
o
d
b
来
表
示
a
模
b
的
运
算
a\mod b来表示a模b的运算
amodb来表示a模b的运算
①
:
选
取
随
机
大
素
数
p
、
q
,
p
、
q
满
足
条
件
g
c
d
(
p
q
,
(
p
−
1
)
(
q
−
1
)
)
=
1
,
g
c
d
(
)
为
求
最
大
公
约
数
函
数
;
①:选取随机大素数p、q,p、q满足条件gcd(pq,(p-1)(q-1))=1,gcd()为求最大公约数函数;
①:选取随机大素数p、q,p、q满足条件gcd(pq,(p−1)(q−1))=1,gcd()为求最大公约数函数;
②
:
设
n
=
p
q
,
λ
=
l
c
m
(
p
−
1
,
q
−
1
)
,
l
c
m
(
)
为
求
最
小
公
倍
数
函
数
;
②:设n=pq,\lambda=lcm(p-1,q-1),lcm()为求最小公倍数函数;
②:设n=pq,λ=lcm(p−1,q−1),lcm()为求最小公倍数函数;
③
:
设
L
(
x
)
=
x
−
1
n
;
③:设L(x)=\frac{x-1}{n};
③:设L(x)=nx−1;
④
:
选
取
随
机
数
g
,
g
<
n
2
,
g
∈
Z
n
2
∗
,
我
们
选
g
=
n
+
1
,
g
还
要
满
足
L
(
g
λ
m
o
d
(
n
2
)
)
在
模
n
的
条
件
下
存
在
乘
法
逆
元
④:选取随机数g,g<n^2,g\in\mathbb{Z_{n^2}^*},我们选g=n+1,g还要满足L(g^\lambda\mod(n^2))在模n的条件下存在乘法逆元
④:选取随机数g,g<n2,g∈Zn2∗,我们选g=n+1,g还要满足L(gλmod(n2))在模n的条件下存在乘法逆元
⑤
:
μ
=
(
L
(
g
λ
m
o
d
(
n
2
)
)
−
1
m
o
d
n
,
即
μ
为
L
(
g
λ
m
o
d
(
n
2
)
)
在
模
n
条
件
下
的
乘
法
逆
元
。
⑤:\mu=(L(g^\lambda\ mod(n^2))^{-1}\mod n,即\mu为L(g^\lambda\mod(n^2))在模n条件下的乘法逆元。
⑤:μ=(L(gλ mod(n2))−1modn,即μ为L(gλmod(n2))在模n条件下的乘法逆元。
⑥
:
生
成
公
钥
(
n
,
g
)
;
⑥:生成公钥(n,g);
⑥:生成公钥(n,g);
⑦
:
生
成
***************************
(
λ
,
μ
)
;
⑦:生成**(\lambda,\mu);
⑦:生成密钥(λ,μ);
⑧
:
选
取
随
机
数
γ
,
γ
∈
Z
n
2
∗
,
且
γ
<
n
,
即
γ
与
n
互
质
。
⑧:选取随机数\gamma,\gamma\in\mathbb{Z_{n^2}^*},且\gamma<n,即\gamma与n互质。
⑧:选取随机数γ,γ∈Zn2∗,且γ<n,即γ与n互质。
⑨
:
根
据
明
文
m
,
计
算
密
文
c
。
c
=
g
m
γ
n
m
o
d
(
n
2
)
;
⑨:根据明文m,计算密文c\,\text 。c=g^m\gamma^n\mod(n^2);
⑨:根据明文m,计算密文c。c=gmγnmod(n2);
⑩
:
根
据
密
文
c
,
计
算
明
文
m
。
m
=
[
L
(
c
λ
m
o
d
(
n
2
)
)
∗
μ
]
m
o
d
n
。
⑩:根据密文c,计算明文m\, 。m=[L(c^\lambda\mod(n^2))*\mu]\mod n。
⑩:根据密文c,计算明文m。m=[L(cλmod(n2))∗μ]modn。
2.2 示例
我们为了计算方便,就不生成大素数了,假设明文为11,对11进行加密和解密。
- 假 设 随 机 生 成 素 数 p = 5 , q = 7 , 满 足 gcd ( p q , ( p − 1 ) ( q − 1 ) ) = gcd ( 35 , 24 ) = 1 ; 假设随机生成素数p=5,q=7,满足\gcd(pq,(p-1)(q-1))=\gcd(35,24)=1; 假设随机生成素数p=5,q=7,满足gcd(pq,(p−1)(q−1))=gcd(35,24)=1;
- n = p q = 35 , λ = l c m ( 4 , 6 ) = 12 ; n=pq=35,\lambda=lcm(4,6)=12; n=pq=35,λ=lcm(4,6)=12;
- g = 36 ; g=36; g=36;
- L ( g λ m o d ( n 2 ) ) = L ( 3 6 12 m o d ( 3 5 2 ) ) = 421 − 1 35 = 12 ; L(g^\lambda\mod(n^2))=L(36^{12}\mod(35^2))=\frac{421-1}{35}=12; L(gλmod(n2))=L(3612mod(352))=35421−1=12;
- 12 μ ≡ 1 ( m o d 35 ) ⟹ μ = 3 ; 12\mu\equiv1(\mod 35)\implies \mu=3; 12μ≡1(mod35)⟹μ=3;
- 公 钥 ( n , g ) = ( 35 , 36 ) , ****************************** ( λ , μ ) = ( 12 , 3 ) ; 公钥(n,g)=(35,36),**(\lambda,\mu)=(12,3); 公钥(n,g)=(35,36),密钥(λ,μ)=(12,3);
- 选 γ = 3 ; 选\gamma=3; 选γ=3;
- 加密: 密 文 c = g m γ n m o d ( n 2 ) = 3 6 11 3 35 m o d ( 3 5 2 ) = 327 ; 密文c=g^m\gamma^n\mod(n^2)=36^{11}3^{35}\mod(35^2)=327; 密文c=gmγnmod(n2)=3611335mod(352)=327;
- 解密: 明 文 m = [ L ( c λ m o d ( n 2 ) ) ∗ μ ] m o d ( n ) 其 中 , L ( c λ m o d ( n 2 ) ) = [ 32 7 12 m o d ( 3 5 2 ) ] − 1 35 = 27 m = ( 27 × μ ) m o d 35 = 11 。 明文m=[L(c^\lambda\mod(n^2))*\mu]\mod(n)\\ 其中,L(c^\lambda\mod(n^2))=\frac{[327^{12}\mod(35^2)]-1}{35}=27\\ m=(27\times\mu) \mod 35=11。 明文m=[L(cλmod(n2))∗μ]mod(n)其中,L(cλmod(n2))=35[32712mod(352)]−1=27m=(27×μ)mod35=11。
3. Affine Homomorphic Encryption
仿射同态加密(Affine Homomorphic Encryption),通过映射来进行加密,仿射加密是线性变换,对字符型变量,可以将其映射为数值型变量。
3.1 计算过程
①
:
生
成
一
个
大
的
整
数
n
;
①:生成一个大的整数n;
①:生成一个大的整数n;
②
:
生
成
大
整
数
a
、
a
−
1
、
b
,
gcd
(
a
,
n
)
=
1
,
a
−
1
为
a
的
乘
法
逆
元
;
②:生成大整数a、a^{-1}、b,\gcd(a,n)=1,a^{-1}为a的乘法逆元;
②:生成大整数a、a−1、b,gcd(a,n)=1,a−1为a的乘法逆元;
③
:
加
密
算
法
E
(
x
)
=
(
a
x
+
b
)
m
o
d
n
;
③:加密算法E(x)=(ax+b)\mod n;
③:加密算法E(x)=(ax+b)modn;
④
:
解
密
算
法
D
(
x
)
=
[
a
−
1
(
E
(
x
)
−
b
)
]
m
o
d
(
n
)
;
④:解密算法D(x)=[a^{-1}(E(x)-b)]\mod(n);
④:解密算法D(x)=[a−1(E(x)−b)]mod(n);
3.2 示例
为计算方便,这里用简单的示例来演示, 假设明文为 m = { 20 , 20 , 9 , 22 } m=\{20,20,9,22\} m={20,20,9,22}。
- 生 成 大 整 数 n = 100 ; 生成大整数n=100; 生成大整数n=100;
- 生 成 大 整 数 a = 91 , b = 101 , a − 1 = 11 ; 生成大整数a=91,b=101,a^{-1}=11; 生成大整数a=91,b=101,a−1=11;
- 加密: 密 文 c = ( a x + b ) m o d 100 = ( 91 x + 101 ) m o d 100 ∣ x ∈ m = { 21 , 21 , 20 , 3 } 密文c=(ax+b)\mod100=(91x+101)\mod100|_{x\in m}=\{21,21,20,3\} 密文c=(ax+b)mod100=(91x+101)mod100∣x∈m={21,21,20,3}
- 解密: 明 文 m = [ a − 1 ( x _ − b ) ] m o d n = [ 11 × ( x _ − 101 ) ] m o d 100 ∣ x _ ∈ c = { 20 , 20 , 9 , 22 } 明文m=[a^{-1}(x\_-b)]\mod n=[11\times(x\_-101)]\mod 100|_{x\_\in c}=\{20,20,9,22\} 明文m=[a−1(x_−b)]modn=[11×(x_−101)]mod100∣x_∈c={20,20,9,22}
4. IterativeAffine Homomorphic Encryption
迭代仿射同态加密(IterativeAffine Homomorphic Encryption),通过迭代,对数据进行多次仿射加密。
4.1 计算过程
为计算方便,这里用简单的示例来演示, 假设明文为
m
=
{
20
,
20
,
9
,
22
}
m=\{20,20,9,22\}
m={20,20,9,22}。
①
:
生
成
r
个
大
整
数
元
组
(
a
,
a
−
1
,
n
)
①:生成r个大整数元组(a,a^{-1},n)
①:生成r个大整数元组(a,a−1,n)
②
:
加
密
算
法
E
(
x
)
=
E
r
(
E
r
−
1
(
(
.
.
.
(
E
1
(
x
)
.
.
.
)
)
)
②:加密算法E(x)=E_r(E_{r-1}((...(E_1(x)...)))
②:加密算法E(x)=Er(Er−1((...(E1(x)...)))
③
:
解
密
算
法
D
(
x
)
=
D
1
(
D
2
(
(
.
.
.
(
D
r
(
E
(
x
)
)
.
.
.
)
)
)
③:解密算法D(x)=D_1(D_{2}((...(D_r(E(x))...)))
③:解密算法D(x)=D1(D2((...(Dr(E(x))...)))
4.2 示例
emmm天黑了,对不起,上手了。