同态加密概述

基本概念
同态加密（Homomorphic Encryption,HE）指将原始数据经过同态加密后，对密文进行特定的运算，得到的密文计算结果在进行同态解密后的得到的明文等价于原始明文数据直接进行相同计算所得到的数据结果。

历史与发展

• 1978年，Rivest、Adleman（RSA中的\"R\"和\"A\"）和Dertouzos提出了全同态加密的构想，当时称为“隐私同态”，并于 2009 年由 Craig Gentry 首次构建。目前，同态加密算法主要分为半同态加密，稍微同态加密，全同态加密两大类。
• 半同态加密或部分同态加密（Somewhat Homomorphic Encryption,SWHE 或 Partially Homomorphic Encryption,PHE）：支持对密文进行部分形式的计算，如仅支持加法、仅支持乘法、支持有限次加法和乘法。半同态加密主要包括以RSA算法和ElGamal算法为代表的乘法同态加密、以Paillier算法为代表的加法同态加密
• 稍微同态加密（SHE）：支持有限操作（例如加法、乘法）直到某个复杂的的方案，但是这些操作只能执行一定次数。主要包括以BGN算法为代表的有限次全同态加密。
• 全同态加密（Fully Homomorphic Encryption,FHE）：支持对密文进行任意形式的计算。全同态加密算法起源于2009年Gentry提出的方案，后续的方案大多都是基于格代数结构构造。全同态加密算法只要包括以Gentry方案为代表的第一代方案，以BGV方案和BFV方案为代表的第二代方案，以GSW方案以及支持浮点数近似计算的CKKS方案为代表的第三代方案。目前，BGV方案、BFV方案、CKKS方案均在同态加密开源库中得以实现。
• 

标准化进展

• 半同态加密标准化
  2019年5月，国际标准化组织ISO发布了同态加密标准（ISO/IEC 18033-6:2019）。该标准仅涉及半同态加密，具体包含两种较为成熟的半同态加密机制：ElGamal乘法同态加密和Paillier加法同态加密，并规定了参与实体的参数和密钥生成、数据加密、密文数据解密、密文数据同态运算等步骤的具体过程。

• 全同态加密标准化
  2017年7月，来自学术界、工业界和政界的相关领域研究人员组成了全同态加密标准化开放联盟HomomorphicEncryption.org，在微软研究院举办了首届全同态加密标准化研讨会，开始共同推进全同态加密标准草案的编写工作，并发布了全同态加密安全标准、API标准、应用标准三份白皮书。迄今为止，HomomorphicEncryption.org在三年内已举办五届全同态加密标准化会议，参与成员包括微软、三星SDS、英特尔、IBM、谷歌、万事达卡等企业，以及NIST、ITU等机构的代表和各大高校的学者。在标准化进展方面，HomomorphicEncryption.org已分别于2018年3月和11月发布和更新了全同态加密标准草案。

同态加密的具体过程

1、Alice对数据进行加密，并把加密后的数据发送给Cloud
2、Alice向Cloud提交数据的处理方法，用函数 f 来表示
3、Cloud在函数f下对数据进行处理，并且将处理后的结果发送给Alice
4、Alice对数据进行解密，得到结果

同态加密方案应该拥有的函数

• KeyGen函数：密钥生成函数，这个函数由Alice运行，用于产生加密数据Data所用的密钥Key，应该还有一些公开常数PP
  (Public Parameter)
• Encrypt函数：加密函数，这个函数由Alice运行，用key对用户数据Data进行加密，得到密文CT（Ciphertext）
• Evaluate函数：评估函数，这个函数由Cloud运行，在用户给定的数据处理方法f下，对密文进行操作，使得结果相当于用户用密钥key对Data进行加密
• Decrypt函数：解密函数，这个函数由Alice运行，用于得到cloud处理的结果f（Data）

对于同态加密，其密码套件具备延展性，也就是说无法保证数据的完整性，这并非是缺陷，反而时有意为之的，能够使用户易于操作加密数据
延展性时加密算法的属性之一，用户可利用延展性将密文转换为改变了原始文本含义的另一有效加密文本，而且，转换数据的用户甚至无需知道或推测原始明文数据是什么

主流同态加密算法

1、半同态加密算法

乘法同态加密算法
满足乘法同态特性的典型加密算法包括1977年提出的RSA公钥加密算法和1985年提出的ElGamal公钥加密算法

加法同态加密算法
Paillier加密算法是1999年由paillier提出的一种基于复合剩余类问题的公钥加密算法，同时也是目前最为常用且最具实用性的加法同态加密算法，在具体的应用场景中实现了应用。

2、稍微（特定）同态加密

有限次全同态加密算法
2005年提出的Boneh-Goh-Nissim方案是一种基于双线性映射的公钥密码方案，支持任意加法同态和一次乘法同态运算。方案中的加法同态基于类似paillier算法的思想，而一次乘法同态基于双线性对映射的运算性质。由于双线性对映射算法会使得密文所在的群发生变化，因此只能支持一次乘法同态运算，但是对乘法后的密文支持作加法运算

3、全同态加密

第一代全同态加密方案 – Gentry方案
Gentry方案是一种基于电路模型的全同态加密算法，支持对每个比特进行加法和乘法同态运算。Gentry方案的基本思想是构造支持有限次同态运算的同态加密算法并引入“Bootstrapping”方法控制运算过程中的噪音增长。
“Bootstrapping”方法通过将解密过程本身转化为同态运算电路，并生成新的公私钥对对原私钥和含有噪音的原密文进行加密，然后用原私钥的密文对原密文的密文进行解密过程的同态运算，即可得到不含噪音的新密文。但是，由于解密过程本身的运算十分复杂，运算过程中也会产生大量噪音，为了给必要的同态运算需求至少预留足够进行一次乘法运算的噪音增长空间，需要对预先解密电路进行压缩简化，即将解密过程的一些操作尽量提前到加密时完成

第二代全同态加密方案 – BGV/BFV方案
第二代全同态加密方案通常基于LWR/RLWR假设，其安全性基于代数格上的困难问题，典型方案包括BGV方案和BFV方案。

• BGV方案（Brakerski-Gentry-Vaikuntanathan）是目前主流的全同态加密算法中效率最高的方案。在BGV方案中，密文和密钥均以向量表示，而密文的乘积和对应的密钥乘积则为张量，因此密文乘法运算会造成密文维数的爆炸式增长，导致方案只能进行常数次的乘法运算。BGV方案采用密钥交换技术控制密文向量的维数膨胀，在进行密文计算后通过密钥交换将膨胀的密文维数恢复为原密文的维数。同时，BGV方案可采用模交换技术替代Gentry方案中的“Bootstrapping”过程，用于控制密文同态运算产生的噪声增长，而不需要通过复杂的解密电路实现。因此，在每次进行密文乘法运算后，首先需要通过密钥交换技术降低密文的维数，然后通过模交换技术降低密文的噪声，从而能够继续进行下一次计算。
• BFV（Brakerski/Fan-Vercauteren）方案是与BGV方案类似的另一种第二代全同态加密方案，同样可基于LWE和RLWE构造。BFV方案不需要通过模交换进行密文噪声控制，但同样需要通过密钥交换解决密文乘法带来的密文维数膨胀问题。

第三代全同态加密方案 – GSW方案
GSW（Gentry-Sahai-Waters）方案是一种基于近似特征向量的全同态加密方案。该方案基于LWE并可推广至RLWE，但其的性能不如BGV方案等其他基于RLWE的方案。GSW方案的密文为矩阵的形式，而矩阵相乘并不会导致矩阵维数的改变，因此GSW方案解决了以往方案中密文向量相乘导致的密文维数膨胀问题，无需进行用于降低密文维数的密钥交换过程。

浮点数全同态加密方案 – CKKS方案
CKKS（Cheon-Kim-Kim-Song）方案是2017年提出的一种新方案，支持针对实数或复数的浮点数加法和乘法同态运算，得到的计算结果为近似值，适用于机器学习模型训练等不需要精确结果的场景。由于浮点数同态运算在特定场景的必要性，HElib和SEAL两个全同态加密开源库均支持了CKKS方案。

全同态加密算法开源库

• HElib
• SEAL

同态加密应用场景

同态加密的概念最初提出用于解决云计算等外包计算中的数据机密性保护问题，防止云计算服务提供商获取敏感明文数据。随着区块链、隐私计算等新型领域的发展及其对隐私保护的更高要求，同态加密的应用拓展到了更为丰富的领域。

• 1、云计算
  在云计算或外包计算中，用户为了节约自身的软硬件成本，可将计算和存储需求外包给云服务提供商，利用云服务提供商强大的算力资源实现数据的托管存储和处理。但是，将明文数据直接交给云服务器具有一定的安全风险，而传统的加密存储方式则无法实现对密文数据的直接计算，因此如何同时实现数据的机密性和可计算性成为了一个难题，同态加密的出现为这一场景的实现提供了可能性。
  在传统的云存储与计算解决方案中，用户需要信任云服务器提供商不会窃取甚至用户数据，而基于同态加密的云计算模型可在根本上解决这一矛盾。首先，用户使用同态加密算法和加密密钥对数据进行加密，并将密文发送给云服务器；云服务器在无法获知明文数据的情况下按照用户给定的程序对密文进行计算，并将密文计算结果返回给用户；用户使用同态加密算法和解密密钥对密文计算结果进行解密，所得结果与直接对明文进行相同计算的结果等价。

• 2、在区块链中应用

• 3、在联邦学习中的应用

发展现状

目前，全同态加密算法仍处于以学术界研究为主的发展阶段，现有方案均存在计算和存储开销大等无法规避的性能为题，距离高效的工程应用还有着不小的差距，同时面临国际与国内相关标准的缺失。因此，在尝试同态加密落地应用时，可以考虑利用Paillier加法同态加密算法等较为成熟且性能较好的半同态加密算法，解决只存在加法或者数乘同态运算需求的应用场景，或通过将复杂计算需求转化为只存在加法或数乘运算的形式实现全同态的近似替代
加密算法等较为成熟且性能较好的半同态加密算法，解决只存在加法或者数乘同态运算需求的应用场景，或通过将复杂计算需求转化为只存在加法或数乘运算的形式实现全同态的近似替代