同态加密使用体验

Posted on Edited on

什么是同态加密

虽然同态加密即使现在听起来也很陌生，但是其实这个概念来自 1978 年，由 RSA 算法的发明者的 R 和 A 以及 Dertouzos 提出。具体的定义如下：

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

翻译成人话就是传统的加密方法和数据处理方法是互斥的，比如我需要计算两个数字的和（1 和 2），如果加密了之后，就无法对密文进行计算；如果想要进行计算，就必须知道这两个数字是 1 和 2。如果数据拥有方和计算方是同一方，那么知道 1 和 2 没啥问题；但如果数据拥有方和计算方并非同一方，并且数据拥有方还不想让计算方知道这两个数字是 1 和 2，这个时候就是同态加密发挥作用的时候了。

同态加密将数据的处理和数据本身解耦了：计算方拿到的是加密之后的密文，但是依然可以相加，相加之后把结果告诉数据拥有方，最终数据拥有方解密就可以知道最终的计算结果。

同态加密的这个特点使得云服务厂商非常在意，因为这一举解决了用户担心云服务厂商窃取数据的担心（因为加密了除了计算没法做其他事情），并且因为加密计算本身耗费更多计算资源，还可以变相提高营收。

总结一下：同态加密使得数据可以在加密的状态下进行计算，至于支持什么计算，如何进行计算，我们接下来继续讲。

同态加密步骤

  1. 在本地生成用来加密数据的 Key
  2. 用 Key 和 Encrypt 算法加密本地的数据，记为 EncData = Encrypt(Key, Data)
  3. 告诉云平台/区块链平台需要如何计算数据，记为函数 F()
  4. 云平台/区块链平台进行计算 Evaluate，即 Evaluate(F(), EncData) = Encrypt(Key, F(Data))，记为 ProEncData
  5. 平台将 ProEncData 发回给到我
  6. 我用密钥进行解密 Decrypt，得到 F(Data) = Decrypt(Key, ProEncData)，也就是最终结果

在以上六个步骤中，至少有四个函数是必须的：

  1. 生成密钥的函数：本地执行，生成密钥
  2. Encrypt 函数：本地执行，加密数据，加密之后的数据不会暴露源数据的信息
  3. Evaluate 函数：用来执行用户给定的计算函数 F()，是唯一由云平台运行的函数
  4. Decrypt 函数：本地执行，解密数据

根据支持的 F() 的不同，同态加密分成了两类：

  1. Fully Homomorphic Encryption, FHE：这种方式下，任何 F() 都可以，只要这个算法能够被计算机实现即可。不过这个计算开销非常大，目前暂无实际应用。
  2. Somewhat Homomorphic Encryption, SWHE：这种方式下，只支持某些特定的F() （比如只支持加法/乘法，并且只能执行有限次数）。这个方案有比较大的限制，但也因此计算开销较小，已经可以在实际中使用
    1. 乘法：RSA, Elgamal
    2. 加法：Paillier

接下来我们会详细看看 Paillier 算法和 RSA 算法，对加法同态和乘法同态有更加深入的理解。

Paillier 算法

总共有如下几个步骤：

  1. 随机选择两个质数 p 和 q 满足 |p|=|q|=τ，这个条件保证了 p 和 q 的长度相等。
  2. 计算 N=pq 和 λ=lcm(p−1,q−1)，注：lcm 表示最小公倍数
  3. 随机选择 g∈Z∗,N2，满足 gcd(L(gλmodN2),N)=1gcd(L(gλmodN2),N)=1，注：gcd 表示最大公约数；Z 表示整数，下标表示该整数集合里有多少个元素；L(x)=x−1NL(x)=x−1N
  4. 公钥为 (N,g)(N,g)
  5. 私钥为 λ

参考项目：
https://github.com/apple/swift-homomorphic-encryption
苹果公司表示，它正在使用同态加密技术进行实时来电者身份验证查询，用以支持来电者识别和垃圾电话拦截服务。这项技术允许苹果通过向服务器发送加密的查询，请求获取电话号码的相关信息，而服务器无需知道或存储电话号码。
苹果公司表示，典型的同态加密工作流可能是这样的：

  • 客户端加密敏感数据，并将结果发送给服务器。
  • 服务器在不了解任何解密内容的情况下，对收到的密文进行必要的计算，可能还会结合服务器自身的明文输入。
  • 服务器将计算后的密文响应发送给客户端。
  • 客户端对收到的响应进行解密。
    Swift 实现集成了 Brakerski-Fan-Vercauteren（BFV）同态加密方案，这一方案具备抵御量子计算攻击的能力。

https://github.com/homenc/HElib
IBM 提供的 HElib目前不再进行积极的开发，尽管还有一些未解决的问题，它现在处于“维护模式”，主要的工作是修复安全漏洞。

https://github.com/microsoft/SEAL
至于微软的 SEAL 库，自 2018 年以来也都没有与发布相关的新闻，尽管其 GitHub 代码库偶尔还会有一些更新。