同态加密

本文转自“雨夜随笔”公众号，欢迎关注。



之所以要开始写《数据价值》这一系列文章，是最近学习和工作中逐渐感觉目前随着数据的爆发，如何去挖掘数据的价值正成为目前的主流话题，所以希望不断记录相关的信息和和知识，来探寻如何去挖掘数据价值和目前的一些尝试。



在《数据价值-联邦学习篇》：初识 中我们在说联邦学习时提到过联邦学习使用同态加密技术来保证数据的安全。并简单介绍了一下同态加密，今天我们来详细说一下同态加密是什么，并以一个同态加密方案来说明。





什么是同态加密



同态加密并不是新的概念，早在1978年，RSA算法中的R(Ron Rivest) 和A(Leonard Adleman)和另一个人Michael L. Dertouzos就以银行作为应用背景提出了这个概念。对于同态加密的概念，这里引用同态加密大牛Craig Genty的话：



A way to delegate processing of your data, without giving a way access to it.



也就是使用者可以在不接触原有数据的情况下进行数据处理，这个是什么意思呢？就是说使用者直接处理密文，然后解密密文结果就是明文的预期计算结果。



这里举个简单的例子，用户拥有大量的统计数据，而个人电脑无法执行这么大的计算或者耗时很长，所以他找了个云厂商，希望利用云端的计算能力来处理。但是这些数据都是非常敏感的，不能直接在云端跑。这时就可以利用同态加密，用户首先加密好自己的数据，提交到云端，并同时提交根据同态加密接口写好的算式，让电脑利用这个算式来处理加密数据，然后把结果传回给用户。用户拿到这个结果后，只需要进行解密就可以得到自己想要的结果。





神奇的地方就在这里，同态加密在这个例子中扮演的角色是提供一个方法，将信息加密后在平台上面进行密文运算。对于平台方，他并不知道处理的数据明文是什么，但是却能够得到用户想要的结果。而用户对这种方法也很放心，因为是他自己对数据进行的加密，而且也没有泄露任何的密钥信息。





听起来很神奇，但是细细想一下，我们其实从小到大早就学过同态加密的概念，比如有一个函数f(x)=3x,则f(x)可以在某种程度上看成是一种支持加法的同态加密算法（当然密文相加不代表明文也是相加，可能是别的运算），因为：





那么现在我们对数据x,y加密后变成了f(x),f(y)。然后告诉云端计算公式

$f(x)+f(y)$ ,然后云端返回这个结果，我们再进行解密，就得到了我们想要的结果 。





但是仅仅是这样并不能称为同态加密算法，假设你发给你朋友一个密文是15，而你朋友恰好知道你加密的方式，那么他就知道你的原文是5。你可能会想这算是什么问题？我连密文和加密机制都知道了，知道原文不应该很正常的么。这就涉及到同态加密和其他密码学加密方式都必须拥有的一个特性：当没有一些关键信息时，经过加密的密文是很难回推出明文的。在《数据价值-密码学篇》：初识中我们说过非对称加密都是建立在“某些数学问题很难解”的情况下设立的。同态加密也不例外，不过为了方便解密，同态加密会针对所应用的数学问题设立一些窍门，使得在特定条件下，这些问题会变得好解，也就是很容易得到明文。





semantic security



那么什么是好的同态加密呢？好的同态加密除了上面的内容外，还具有一个特性，也就是语义安全(semantic security)。拥有这个特性的同态加密可以抵抗选择明文攻击，这个概念我们在《数据价值-密码学篇》：初识简单介绍过了，不了解的可以看我的这篇文章。这里为了让大家里面同态加密中的语义安全，我们来简单说明一下，比如现在有一个明文x,那么我们用同样的加密方法f(x)计算x100次，会发现什么现象呢？你会发现这一百次的结果不一样，但是呢，如果对着100个结果进行解密，却会得到同一个值。这就满足语义安全，也就是密文不含任何的明文信息。即使拿到一个密文和一堆明文，也不知道对应的是哪一个。而如何达到这个效果呢？你可能会想到在加密阶段加上一个随机数，事实上大部分也都是这么做的，这样就造成了密文的多样性。而在解密的时候平衡掉或者去除随机数，再去解密，这样就可以保证解密后的值是一样的了。



而在上面的例子中，我们介绍了支持加法的同态加密类型，其实按照实现程度分为两种：SWHE(SomewhatHomomorphic Encryption) 和 FHE(Fully HomomorphicEncryption)。这两个区别在于：



• SWHE：这种类型的同态加密只支持特定的函数，比如加法，或者乘法，或者加乘法等。

• FHE：这种类型的同态加密支持任意的函数，只要这种函数可以通过算法描述，并用计算机能够实现。



为什么会出现这两种同态加密类型，源于可用性和安全性之间的衡量，SWHE较弱，但是实现起来较为容易，使用起来也较为方便，同时加密和解密的开销比较小，目前已经有很多可用用于生产的方案了。而FHE则是同态加密的终极目标，现在也有一些方案，但是开销极大，还不能在实际中使用，可以说一旦有可用于生成环境的FHE方案，对于密码学来说是一个极大的进步。



经过上面的例子我们可以直观的看出一个同态加密方案应该具有以下的函数：



• KeyGen：即密钥生成函数。主要是生成数据加解密所需的密钥。

• Encrypt：加密函数，主要是使用密钥对数据进行加密。

• Decrypt：解密函数，主要是使用密钥对数据进行解密。

• Evaluate：这个主要是对加密后的数据进行计算，一般用于用户编写自己的处理方法。





Paillier cryptosystem 同态加密方案



那么我们就根据目前最为常用的同态加密方案Paillier cryptosystem来讲解同态加密的细节。



首先Pailliercryptosystem是一种非对称加密，并且使用的是RSA模组，也就是公钥是由两个参数决定的。在开始之前我们简单描述一下RSA算法：



RSA算法



如果我们想要使用RSA算法进行加密通信，一般按照下面的步骤：



1. 随机选择两个不同的素数p,q

2. 取p,q的乘积n，即$n=p\times q$

3. 根据欧拉函数，当p,q为不同的素数时，有$\phi \left(n\right)=\left(p-1\right)\left(q-1\right)$

4. 然后随机选择一个整数e，满足两个条件：$\phi \left(n\right)$与e互质，并且1<e<$\phi \left(n\right)$

5. 计算e对于$\phi \left(n\right)$ 的模反元素d，也就是满足ed-1=k$\phi \left(n\right)$ ,一般写作$ed=1mod\phi (n)。$

6. 最终(e, n)为公钥，(d,n)为私钥

7. 加密数据m的方式是：$m^{e}modn=c$

8. 解密的方式是：



推导公式如下：



费马定理中$m^{\phi (n)}modn\equiv 1$，所以有$m^{k\phi (n)}modn\equiv 1$，两边同时乘上m, 上面的等式正好等于m。也就是我们的明文数据。



那么RSA是如何保证安全性的呢，我们在《数据价值-密码学篇》：初识提到密码学的算法难度依赖于一个很难得额数学难题。而RSA算法也是。我们来看一下这个难题：



1. 我们现在有公钥(e, n)，如果我们能够计算出d，就能拿到私钥。

2. 因为$ed=1mod\phi (n)$ ，我们已经知道了e，所以只要知道$\phi (n)$就可以了。而$\phi \left(n\right)=\left(p-1\right)\left(q-1\right)$，所以我们需要知道p,q的值。而$n=p\times q$，所以我们要做的其实是分解n。但是n一般都很大，大数分解就是RSA所依赖的数学难题。目前可以破解的最大整数是768位（二进制）整数。所以大于768位的RSA算法目前可以认为是安全的。

Paillier cryptosystem



好了，现在了解了RSA算法后，我们再回过头来看一下Paillier cryptosystem。下面的代码用Go写的，不懂可以直接看注释。这个算法的步骤如下：



• 首先是密钥生成函数KeyGen



1. 选取两个不同的素数p,q

2. 取两个数的乘积$n=p\times q$

3. 据欧拉函数，当p,q为不同的素数时，有$\phi \left(n\right)=\left(p-1\right)\left(q-1\right)$,这里记为$\lambda$

4. 然后随机选择一个整数g，${2<g<n}^2$, 并且和n互质

5. 然后取${\mu =(L(g^{\lambda }mod{n}^2))}^{-1}modn$ , 这里的$L\left(x\right)=\frac{x-1}{n}$

6. 然后取(n,g )为公钥，（λ，μ）为私钥



// KeyGen 秘钥生成函数 random是随机生成源， 用于生成随机数。bits是生成随机数的大小
func KeyGen(random io.Reader, bits int) (*PubKey, *PrivKey, error) {
  // 随机素数 p
  p, err := rand.Prime(random, bits/2)
  if err != nil {
    return nil, nil, err
  }
  // 随机素数 q
  q, err := rand.Prime(random, bits/2)
  if err != nil {
    return nil, nil, err
  }
  // N = p*q
  n := new(big.Int).Mul(p, q)
  // 这里为了计算方便，保存 n * n
  nSquared := new(big.Int).Mul(n, n)
  // 随机整数g，这里问了方便为 n+1
  g := new(big.Int).Add(n, one)
  // p-1
  pMin := new(big.Int).Sub(p, one)
  // q-1
  qMin := new(big.Int).Sub(q, one)
  // (p-1)*(q-1)
  l := new(big.Int).Mul(pMin, qMin)
  // l^-1 mod n
  u := new(big.Int).ModInverse(l, n)
  // 公钥保存n, g, n*n
  pub := &PubKey{Len: bits, N: n, Nsq: nSquared, G: g}
  // 私钥保存l, u, n, g, n*n
  return pub, &PrivKey{PubKey: *pub, Len: bits, L: l, U: u}, nil
}



• 然后是加密函数Encrypt，待加密数据是m, r为选择的随机数，0 < r < n，并且和n互质



// Encrypt函数， 加密数据
// c = g^m * r^n mod n^2
// 0 <= r <= n
// message是待加密的数据
func Encrypt(pubkey *PubKey, message []byte) ([]byte, error) {
  // r是随机素数
  r, err := rand.Prime(rand.Reader, pubkey.Len)
  if err != nil {
    return nil, err
  }
  // 将信息转换成整数，方便计算
  m := new(big.Int).SetBytes(message)
  if pubkey.N.Cmp(m) < 1 {
    return nil, errors.New("ras算法要求对加密的信息有要求，要求不能大于大于n，否则会发生mod n会发生回绕，是的解密发生错误")
  }
  //g^m
  gm := new(big.Int).Exp(pubkey.G, m, pubkey.Nsq)
  //r^n
  rn := new(big.Int).Exp(r, pubkey.N, pubkey.Nsq)
  // prod = g^m * r^n
  prod := new(big.Int).Mul(gm, rn)
  c := new(big.Int).Mod(prod, pubkey.Nsq)
  return c.Bytes(), nil
}



• 解密函数Decrypt



// Decrypt函数， 解密数据
// m = L(c^lamda mod n^2).mu mod n
func Decrypt(privkey *PrivKey, cipher []byte) ([]byte, error) {
  // 将带解密的密文转换成整数，进行计算
  c := new(big.Int).SetBytes(cipher)
  // 如果 n*n < c
  if privkey.Nsq.Cmp(c) < 1 {
    return nil, errors.New("ras算法要求对加密的信息有要求，要求不能大于大于n，则密文不能大于n*n")
  }
  //c^lamda mod n^2
  a := new(big.Int).Exp(c, privkey.L, privkey.Nsq)
  //L(x) = x-1 / n
  l := new(big.Int).Div(new(big.Int).Sub(a, one), privkey.N)
  //computing m
  m := new(big.Int).Mod(new(big.Int).Mul(l, privkey.U), privkey.N)
  return m.Bytes(), nil
}



• 计算函数Evaluate



加法：



// 加法1
func Add(pubkey *PubKey, c1, c2 []byte) []byte {
  a := new(big.Int).SetBytes(c1)
  b := new(big.Int).SetBytes(c2)
  // a * b mod n^2
  res := new(big.Int).Mod(new(big.Int).Mul(a, b), pubkey.Nsq)
  return res.Bytes()
}





//加法2
func AddConstant(pubkey *PubKey, cipher, constant []byte) []byte {
  c := new(big.Int).SetBytes(cipher)
  k := new(big.Int).SetBytes(constant)
  // c * g^k mod n^2
  res := new(big.Int).Mod(
    new(big.Int).Mul(c, new(big.Int).Exp(pubkey.G, k, pubkey.Nsq)), pubkey.Nsq)
  return res.Bytes()
}



乘法：





//乘法
func Mul(pubkey *PubKey, cipher, constant []byte) []byte {
  c := new(big.Int).SetBytes(cipher)
  k := new(big.Int).SetBytes(constant)
  // c^k mod n^2
  res := new(big.Int).Exp(c, k, pubkey.Nsq)
  return res.Bytes()
}



上面就是Pailliercryptosystem的具体实现。当然因为Paillier cryptosystem基于RSA模组，现在可用的SWHE算法大部分也都是基于RSA模组的，所以和RSA算法有一样的问题，那就是一旦整数分解问题被解决，那么算法将变得不安全。而且现在已经证明，量子计算机已经可以解决整数分解问题。所以随着量子计算机的普及，这些算法都会有很大的破解风险。所以目前主流的加密算法已经开始研究格密码学等方向，格密码学已经被证明是量子计算安全的算法。



应用背景



同态加密目前最为热门的领域应该就是云计算，因为云计算拥有大量的数据，同时AI的加持，使得对于数据的操作变得越来越频繁，越来越多样化。如何对数据进行加密一直是比较关心的问题。如果目前FHE的方案能够实现，那么不仅数据得以保护，对于数据的操作也得到了保护。



同样，对于医疗，政府等领域，对数据的隐私性要求非常高。行业内也有各种严格的规定和要求。比如每个谈联邦学习的背景的都或多或少的会提到GDPR，也就是欧盟对数据保护的规定。那么面对这么严格的规定，这些领域想要利用数据，要么搭建自己的私有云计算平台，让数据不出自己内部的局域网。要么就是利用经过认证的公有云计算平台，而对于这类平台最大的要求就是隐私信息不能被暴露，所以要么就是数据进行脱敏后发送到云计算平台，要么就是数据根本就不出局域网。所以目前来看同态加密有着很大的应用市场。



全同态加密（FHE）



对于全同态加密，最重要的是支持各种函数。所以要构造FHE，目前有两种方式：



• 从计算机原理考虑：因为在计算机中，所有的运算最终都是位运算，而对于计算机，如果可以支持逻辑与(AND)和异或（XOR）运算，那么这个计算机就可以实现其他所有的运算（这种被称为图灵完备性）

• 从抽象代数考虑：事实上对于代数来说，只要支持加法和乘法，就可以完成全部运算，当然这个还涉及到效率和易用性的问题，不能只构造出加法和乘法，其他的让用户自己造轮子。



目前全同态加密也有相应的解决方案，比如格密码学中的LWE(Learning with error)问题就是在针对1 bit进行加密。但是全同态加密方案目前的效率都不能达到全状态下的高效，即使格密码学在某些方面可以达到和RSA算法一样的效率。不过这些仍然非常值得学习和研究，因为一方面是新技术最难的是从0到1的过程，对于格密码学接下来的发展，肯定会越来越适合作为新的加密方案。另一方面是量子计算机的到来，现有的加密方案基于的数学难题基本都会被破解，代表着现有的加密方案开始变得不安全了。那么学习格密码学等下一代加密方案，这些被证明即使是量子计算也是很困难的难题，对于密码学都有着很大的意义。



总结



那么最后，让我们简单回顾一下我们这篇的内容，首先我们介绍了什么是同态加密，然后通过对比RSA来介绍了同态加密方案Paillier cryptosystem。通过数学和代码的分析，让我们对于如何实现一个同态加密方案有了更深层次的理解。然后我们简单说了一下同态加密的应用背景和同态加密的未来--全同态加密的现状和未来。当然，同态加密的方案现在还有很多的问题没有解决，对于这方面感兴趣的同学可以尝试着去学习和研究。



欢迎关注