同态加密的原理详解与go实践

类别：乘法同态加密算法

困难：离散对数问题

ELGamal密码是除了RSA之外最有代表性的公开密钥密码之一，是一种公认安全的公钥密码。

设p为素数，若存在一个正整数α，使得 a , a 2 , a 3 , … , a p − 1 a,a^2,a^3,…,a^{p-1} a,a2,a3,…,ap−1 关于模p互不同余，则称α为模p的一个原根。于是有如下运算：

a的幂乘运算： y = a x m o d p , 1 ⩽ x ⩽ p − 1 y = a^xmod p , 1 \leqslant x \leqslant{p-1} y=axmodp,1⩽x⩽p−1

a的对数运算： x = l o g a y ,   1 ⩽ y ⩽ p − 1 x = log_a^y, \ 1 \leqslant y \leqslant {p-1} x=logay​, 1⩽y⩽p−1

只要p足够大，求解离散对数问题时相当复杂的。离散对数问题具有较好的单向性。

对于待加密明文M，随机地选取一个整数k（1＜k＜p-1）。

计算 U = a k m o d p 、 C 1 = a k m o d p 、 C 2 = U ∗ M m o d p U= a^kmodp 、C_1=a^kmodp 、C_2=U*Mmodp U=akmodp、C1​=akmodp、C2​=U∗Mmodp

取(C1,C2)作为密文。

计算 V = C 1 d m o d p V = C_1^dmodp V=C1d​modp

解密结果: M = C 2 V − 1 m o d p M = C_2V^{-1}modp M=C2​V−1modp

代码库：https://github.com/Roasbeef/go-go-gadget-paillier

采用Go语言实现的加法同态加密算法Paillier

其主要可以实现以下 *** 作：

可以将加密的整数加在一起

加密的整数可以与未加密的整数相乘

加密的整数和未加密的整数可以加在一起

go get github.com/roasbeef/go-go-gadget-paillier

func Test_homomorphicCrypto(t *testing.T)  {

	// 生成一个128位的私钥
	privKey, _ := paillier.GenerateKey(rand.Reader, 128)

	// 公钥加密明文：数字15
	m15 := new(big.Int).SetInt64(15)
	c15, _ := paillier.Encrypt(&privKey.PublicKey, m15.Bytes())

	// 私钥解密密文：15
	d, _ := paillier.Decrypt(privKey, c15)
	plainText := new(big.Int).SetBytes(d)
	fmt.Println("Decryption Result of 15: ", plainText.String()) // 15


	// 公钥加密数字20
	m20 := new(big.Int).SetInt64(20)
	c20, _ := paillier.Encrypt(&privKey.PublicKey, m20.Bytes())

	// 将15的密文与20的密文相加（注意都是同一公钥）
	plusM16M20 := paillier.AddCipher(&privKey.PublicKey, c15, c20)
	// 使用私钥解密和的明文结果
	decryptedAddition, _ := paillier.Decrypt(privKey, plusM16M20)
	fmt.Println("Result of 15+20 after decryption: ",
		new(big.Int).SetBytes(decryptedAddition).String()) // 35!

	// 将15密文与10明文常数相加
	plusE15and10 := paillier.Add(&privKey.PublicKey, c15, new(big.Int).SetInt64(10).Bytes())
	decryptedAddition, _ = paillier.Decrypt(privKey, plusE15and10)
	fmt.Println("Result of 15+10 after decryption: ",
		new(big.Int).SetBytes(decryptedAddition).String()) // 25!

	// 将15密文与10明文常数相乘
	mulE15and10 := paillier.Mul(&privKey.PublicKey, c15, new(big.Int).SetInt64(10).Bytes())
	decryptedMul, _ := paillier.Decrypt(privKey, mulE15and10)
	fmt.Println("Result of 15*10 after decryption: ",
		new(big.Int).SetBytes(decryptedMul).String()) // 150!
}

# 结果显示
=== RUN   Test_homomorphicCrypto
Decryption Result of 15:  15
Result of 15+20 after decryption:  35
Result of 15+10 after decryption:  25
Result of 15*10 after decryption:  150
--- PASS: Test_homomorphicCrypto (0.00s)
PASS

值得注意的是该包的作者说其用于课程教学，实际的生产环境则不太适合

同态加密最大的问题是效率

效率。效率一词包含两个方面，一个是加密数据的处理速度，一个是这个加密方案的数据存储量。

工人戴着手套加工金子，肯定没有直接加工来得快嘛~ 也就是说，隔着手套处理，精准度会变差（现有构造会有误差传递问题），加工的时间也会变得更长（密文的 *** 作花费更长的时间），工人需要隔着 *** 作，因此也需要更专业（会正确调用算法）。

金子放在盒子里面，为了 *** 作，总得做一个稍微大一点的盒子吧，要不然手 *** 作不开啊（存储空间问题）。里面也要放各种工具吧，什么电钻啦，锉刀啦，也需要空间吧？

2011年，Gentry和Halevi在IBM尝试实现了两个HE方案：Smart-Vercauteren的SWHE方案[SV10]以及Gentry的FHE方案[Gen09]，并公布了效率。结果如何呢？我们给出Gentry公布的数据（原始数据可以在2nd Bar-Ilan Winter School on Cryptography找到）Smart-Vercauteren的SWHE方案效率如下：

看着好像还行，不过这Dimension有点夸张啊…也就是说公钥很长…那么，Gentry的FHE方案如何呢？效率如下：