SEAL全同态加密库(二)

一.同态加密

如果我们有一个加密函数 f , 把明文A变成密文A’, 把明文B变成密文B’,也就是说f(A) = A’ ,f(B) = B’ 。另外我们还有一个解密函数 ,能够将 f 加密后的密文解密成加密前的明文。
对于一般的加密函数,如果我们将A’和B’相加,得到C’。我们用对C’进行解密得到的结果一般是毫无意义的乱码。
但是,如果 f 是个可以进行同态加密的加密函数, 我们对C’使用进行解密得到结果C, 这时候的C = A + B。这样,数据处理权与数据所有权可以分离,这样企业可以防止自身数据泄露的同时,利用云服务的算力。

二.全同态加密体系

系统性的定义一下全同态系统的正式定义。一个全同态加密系统,一共拥有四个算法:
密钥生成算法:KenGen为了简单表示,我们这里假设这个加密系统是对称的(即加密密钥等于解密密钥)。
加密算法:Enc(sk,m)->ct把原文m加密成密文ct。
解密算法 :Dec(sk,ct)->m把密文 ct还原为原文m。解密算法不仅能对初始密文解密,还能够对计算后的密文解密
运算评估算法 :Eval(F,ct1,ct2…ctn)->ct_把n个密文组合起来,通过一个二进制逻辑电路 F,最后得到组合的密文ct_,通俗理解为将密文输入到函数f里进行计算。满足下面等式

与此同时,FHE系统还需要满足三大属性(properties):
正确性(Correctness):一个FHE系统必须要是正确的。具体来说,也就是加密之后的密文可以被成功解密,并且Eval运算输出的密文也可以成功解密回原文。
语义安全(Semantic Security):FHE系统输出的密文必须要难以分辨。具体来说,如果有一个网络窃听者看到了所有的密文,那么这个窃听者并不能分辨出哪个密文是对应哪个原文的。
简短性(Compactness):FHE的运算算法Eval输出的密文的长度一定要独立于功能F的所对应的电路的大小。这一属性代表就算运算功能复杂,输出的密文仍然在一个可以控制的长度范围内,确保了FHE系统的实用性。
简单来说,FHE要解决的问题是这样的。假设一个用户拥有一个私密的值x,但是他想要委托远程的服务器在不知晓x的情况下计算一个功能f(x)的值。

基于我们定义的四个算法,首先用户需要使用FHE加密算法来加密他的私密输入,得到Enc(S),然后发送给云端。随后,云端将会使用运算算法Eval来计算得到Enc(f(x)),并返回给用户。最后用户使用FHE的密钥来解开密文,得到f(x)。

三.同态分类

a) 如果满足 f(A)*f(B)=f(A+B), 我们将这种加密函数叫做加法同态
b) 如果满足 f(A)×f(B)=f(A×B), 我们将这种加密函数叫做乘法同态。
如果一个加密函数f只满足加法同态,就只能进行加减法运算;
如果一个加密函数f只满足乘法同态,就只能进行乘除法运算;
如果一个加密函数同时满足加法同态和乘法同态,称为全同态加密。那么这个使用这个加密函数完成各种加密后的运算(加减乘除、多项式求值、指数、对数、三角函数)。