联邦学习：加密算法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天黑了，对不起，上手了。
