Introduce

同态加密的历史可以追溯到1970年代末。就在RSA公钥密码体制公布的第二年，Ron Rivest、Len Adleman 和 Michael Dertouzos 发表了题为《论数据库与隐私同态》的报告。文中详细介绍了金融公司如何运用云提供商(当时的叫法是商用分时服务)存储和计算加密数据。这篇影响力巨大的论文催生了“同态加密”这一术语。

同态加密是一种加密形式，它允许人们对密文进行特定形式的代数运算得到仍然是加密的结果，将其解密所得到的结果与对明文进行同样的运算结果一样。换言之，这项技术令人们可以在加密的数据中进行诸如检索、比较等操作，得出正确的结果，而在整个处理过程中无需对数据进行解密。其意义在于，真正从根本上解决将数据及其操作委托给第三方时的保密问题，例如对于各种云计算的应用。

如果我们有一个加密函数 $$$f$$$ , 把明文A变成密文 $$$A'$$$, 把明文B变成密文 $$$B'$$$，也就是说 $$$f(A) = A'$$$ ， $$$f(B) = B'$$$ 。另外我们还有一个解密函数 $$$f^{−1}$$$ 能够将 $$$f$$$ 加密后的密文解密成加密前的明文。

如果 $$$f$$$ 是个可以进行同态加密的加密函数， 我们对$$$C'$$$使用 $$$f^{−1}$$$ 进行解密得到结果$$$C$$$， 这时候的$$$C = A + B$$$。这样，数据处理权与数据所有权可以分离。

如果满足 $$$f(A)+f(B)=f(A+B)$$$ ， 我们将这种加密函数叫做加法同态
如果满足 $$$f(A)×f(B)=f(A×B)$$$ ，我们将这种加密函数叫做乘法同态。

如果一个加密函数同时满足加法同态和乘法同态，称为全同态加密。那么这个使用这个加密函数完成各种加密后的运算(加减乘除、多项式求值、指数、对数、三角函数)。

Algebra

同态加密之所以被称为同态加密是因为这种加密方法跟抽象代数中的同态很像。在抽象代数中，如果 $$$G$$$和$$$H$$$ 是两个交换环，如果函数 $$$f:G \to H$$$ 使得:

$$$f(e_G) = e_H$$$ , 其中 $$$e_G$$$ , $$$e_H$$$ 分别是$$$G$$$和$$$H$$$中的幺元
$$$\forall x,y \in G,\ f(x \times y) = f(x) \times f(y)$$$
$$$\forall x,y \in G,\ f(x + y) = f(x) + f(y)$$$
均成立，那么我们把 $$$f$$$ 称为一个同态(Homomorphism)。一般的加密函数都是双射的，双射的同态又称为同构(Isomorphism)。所以这么说来，同态加密被称为同构加密更加贴切。

Short board

同态加密会严重拖慢数据运算速度

毫不夸张地说，最开始的时候性能可以慢上100万亿倍。后来性能影响不断改善，但最新的数据是一定时间段内能执行5万次端到端交易。在今天这个快速发展的世界，这样的处理速度还是太慢了。

同态加密需要修改应用

你得事先知道要执行哪种类型的计算(加法、乘法等等)。不太好预测的业务或者自由度高的操作就不得不重写或修改应用才能用上同态加密。这一点就不适用于大规模业务了。

同态加密的整体加密强度(加密熵)也留有疑问

同态加密在不解密数据不访问密钥的情况下实现此机制会暴露出重要属性。采用这样一种方案，其加密强度还有一些悬而未决的问题。

Library

https://github.com/shaih/HElib - An Implementation of homomorphic encryption
https://github.com/diegode/thep - The Homomorphic Encryption Project
https://github.com/mhe/jspaillier - Javascript proof-of-concept implementation of the Paillier cryptosystem
https://github.com/Microsoft/SEAL - Simple Encrypted Arithmetic Library (SEAL) is an easy-to-use but powerful homomorphic encryption library written in C++
https://github.com/tfhe/tfhe - TFHE: Fast Fully Homomorphic Encryption Library over the Torus
https://github.com/vernamlab/cuFHE - CUDA-accelerated Fully Homomorphic Encryption Library
https://github.com/nucypher/nufhe - NuCypher fully homomorphic encryption (nuFHE) library implemented in Python

Virtual Machine

https://github.com/f-prime/arcanevm - A Fully Homomorphic Encryption Brainfuck virtual machine
ArcaneVM is a virtual machine that can execute instructions encrypted with Fully Homomorphic Encryption. Basically, it's a Brainfuck interpreter that can execute encrypted brainfuck code.

Demo

https://webencrypt.org/jspaillierdemo/

Reference

  1. https://www.cs.cmu.edu/~odonnell/hits09/gentry-homomorphic-encryption.pdf - Fully Homomorphic Encryption Using Ideal Lattices
  2. https://blog.csdn.net/jason_cuijiahui/article/details/79121702 - 同态加密算法简述
  3. https://zh.wikipedia.org/wiki/同态加密
  4. https://zhuanlan.zhihu.com/p/31822335 - 同态加密——如何让帮你干活的人不知道自己都干了些什么
  5. https://yeasy.gitbooks.io/blockchain_guide/content/crypto/homoencryption.html - 同态加密
  6. http://slideplayer.com/slide/8488065/ - The Paillier Cryptosystem
  7. http://www.tcnj.edu/~hagedorn/papers/CapstonePapers/OKeeffe/CapstoneOKeeffeCryptography.pdf - The Paillier Cryptosystem
  8. https://mp.weixin.qq.com/s/Oil1BVCGqZo2HyPfXe6_0g - 同态加密的现实与虚幻
  9. https://mp.weixin.qq.com/s/XPHcaKNsdz9zhZAnTWHKDg - IBM 重写了其 C++ 同态加密库，速度提高 75 倍 ！（附论文）