同态加密的基本概念

所谓的同态加密（HE,homomorphic encryption）是指：对明文m加密，得到密文c，满足f(c)是f(m)的密文，其中f是任意属于某个函数族F的函数，明文可以是单个明文，也可以是明文向量，对应的为单个密文和密文向量。而对应的函数族F为该方案的同态函数族，即该同态加密方案所支持的能够同态计算的所有函数的集合。比如f(x)=x+2,我们要加密的c为明文m的密文。则f(c)=c+2，是m+2的密文。

同态函数的简单分类

根据加密方案对支持的函数族的不同，可以将同态加密分为多种。

比较主流的同态方案有加法同态、乘法同态、部分全同态和全同态。

加法同态：该加密方案支持的同态函数族为所有可以仅由加法实现的函数。目前使用比较广泛的是paillier加法同态。

乘法同态：该加密方案支持的同态函数族为所有可以仅由乘法实现的函数。比如经典的RSA加密方案。

部分全同态（partially fully homomorphic encryption, somewhat homomorphic encryption or leveled fully homomorphic encryption）：该方案支持的同态函数族为有限次数的加法和有限次乘法能够实现的函数。

全同态：该方案能够支持的同态函数族所有的加法和乘法可以实现的函数。比如BGV、BFV、CKKS。

同态加密一般是非对称加密，当然也有对称加密的同态方案。

下面的描述采用非对称加密，即公钥系统的术语描述。对称加密是公钥和私钥相等的对称加密。

形式化定义

一个完整的同态方案由密钥生成算法，加密算法，解密算法和同态计算算法4部分构成。

1、密钥生成算法（HE.KeyGen）其输入为安全参数和其他描述其他需求的公共参数，输出一个加密密钥pk（公钥），一个解密密钥sk（私钥）和一个同态计算密钥evk。

2、加密算法（HE.Encrypt）输入明文m和加密密钥pk，输出m的密文c。

3、解密算法（HE.Decrypt）输入密文c和解密密钥，输出明文m。

4、同态计算算法（HE.Evaluate）输入密文，同态计算密钥evk和函数f，输出。值得注意的是，这里的c不一定是可以再次参与计算的密文，他只需要能够正确解密即可。所有可能的函数f构成同态函数族F。

同态加密的正确性

同态加密的正确性包括两个方面。首先，跟一般的加密方案一样，密文能够正确地解密，也就是m=HE.Decrypt(HE.Encrypt(m,pk),sk)。其次，同态计算必须要保证正确。

当，其中时：