本文学习丁老师写的同态加密的文章，做些笔记。
引言
- 同态加密适用于云计算。
- 因为任意计算都可以由加法和乘法构成，全同态意味着计算函数\(f\)可以是任意计算操作（任意次加法和乘法）。
- 同态加密，起源于“隐私同态”的概念，但并未给出具体实现；后续提出一些部分同态性的方案，比如乘法同态（RSA、ElGamal），加法同态（Paillier，GGH），一次乘法和任意次加法（BGN）；全同态的概念和实现是Gentry09中提出。
留个疑问：为什么只能计算一次乘法，多次会解密错误么？
发展
- 评估函数，就是对密文计算的函数，底层实现是通过一系列逻辑门电路（AND门、OR门、NOT门等）。
- 电路深度（乘法次数），就是电路中布尔门的个数，具体讲就是从输入到输出的最长路径上布尔门的个数，能计算任意深度的门电路，就实现了全同态。
- 同态计算最大的问题：随着密文的计算，噪声变大（加法，噪声加倍；乘法，噪声平方），若超过界限则会影响最后的解密结果，为了能正确解密，需要限制密文运算次数依次限制噪声的积累，这也就是Leveled-FHE。
- 如何减少电路胜读的限制？方法：当噪音快到到临界值时，解密数据，再重新加密，这样可以将噪音恢复到初始低水平，这就是自举技术最初构造的思路。但这样解密需要私钥，又不能泄漏私钥，所以解密所需的也需要加密。
- 如果不超过电路深度所能接受的噪音界限，那么评估函数（计算函数）就可以进行人已计算，所以可以利用评估函数调用解密函数，所以这里给评估函数的密钥也是加密的。
- 自举的原理，可以用工匠在箱子中制作宝石的例子来说明，具体的可以分成重加密和刷新密文两步，这样就能实现真正的全同态，这也是目前能实现真正FHE的唯一方法。
- 自举是建立在这样的假设之上：解密电路本身足够浅（解密电路所产生的的噪音不会超过噪音阈值），但在实际中，使用评估函数调用解密函数时，噪音依旧会增加，可能会超过噪音阈值，这里使用“挤压解密（squashing decrypt）”的方法解决，但会使得密钥变长变复杂。
- 设计全同态的架构：先设计Leveled-FHE，再通过自举完成FHE。
- 全同态加密大多是公钥加密，也有对称加密，其中方案的安全性大多依赖于数据难题，其中RSA依赖于大素数难分解问题、Gentry09基于理想格上的困难问题，比如CVP问题和SVP问题等、DGHV10是基于AGCD问题、BV11和GSW等基于LWE问题、BGV和BFV等是基于RLWE问题。
- BGV12方案比较经典的原因在：基于RLWE问题（LWE问题变体）、采用不同的方法降噪，即在每一步计算（乘法）后渐增式的调整系统参数来防止噪音达到阈值，由此实现第一个Leveled-FHE方案。
抗量子攻击
- 全同态加密方案，一般选择尽可能大的参数，来确保方案的安全性。
- 基于LWE问题设计的全同态方案，能抵抗常规计算机的攻击，也能抵抗量子计算机的攻击，前提是选择合适的参数。
- 基于RLWE问题设计的全同态方案，安全性是更加确定的，但基于一个假设：在理想格中求解密钥的格是困难的，该假设只是推测，目前并不能证明。
应用
- 全同态加密缺点：为了保证安全性，1Bit的明文加密后，会膨胀为几KBit甚至几MBit的数据量，且加密时使用的公钥也是“巨大的”，会达到几MB甚至几GB；
- 为了提升效率，提出多比特加密，分组加密，明文打包等技术，提升加密效率，减少开销。
- 同态加密的应用：在线医疗、金融股票、广告投放、邮件垃圾过滤等。
竞争
- 基于LWE问题设计的方案，可以在硬件上优化，提升方案效率。
总结
- 同态加密并不实用，使用昂贵，但具有研究意义，对未来影响很大，就像刚开始的电、电话、计算机等一样，不断优化，普及开就能对社会产生重大影响。