可计算加密技术是一种加密方法,它通过加密保证数据安全,同时加密后的数据能够支持某些计算,目前已有的可计算加密技术可分为两类:支持检索的加密技术和支持运算的加密技术。

一、支持检索的加密技术

常见的支持检索的加密技术有基于对称加密的密文检索方法和基于非对称加密的密文检索方法、基于Bloom Filter的密文检索方法。

这些方法只支持精确的字符串匹配,即两字符串是否相等。然而,在许多实际的情况下,错别字和格式不一致是不可避免的,因此,又有专家设计了一个支持加密字符串模糊检索的方案,它使用编辑距离来量化字符串的相似度,并为每个字符串附加一个基于通配符的模糊字符串组,用多个精确匹配来实现模糊检索。该方法的不足是它不能对满足检索条件的字符串进行相似度排序,而且计算、存储通信负载很大。对于一个长度为l的字符串,为了能处理d位的错别字和格式不一致,需要进行O(ld)次Hash运算并产生O(ld×160)位的存储/通信负载。

还有专家提出一个基于保序加密技术OPSE的分级字符串检索方案,能够根据某一指标对检索的关键字分级,并按用户的要求返回前N个符合要求的结果。该方案要求数据拥有者在外包文件前对每个文件进行全文扫描,计算出每个关键字在该文件中的出现频率,这对于数据拥有者来说是一件非常麻烦的事情。

另外还有基于同态加密技术的密文聚集查询方案,但是要求数据拥有者自己建立一个加密的索引表。

二、支持运算的加密技术

支持运算的加密技术常见的有以下两种:

基于桶划分和分布概率映射思想的保序对称加密算法OPES,支持对加密数值数据的各种比较操作。

基于折半查找和超几何概率分布的保序对称加密算法OPES,支持对加密数据的各种比较操作,但是由于在计算超几何概率时需要进行多次组合运算,其计算负载较大。以上两种保序加密算法都是确定性的加密方案,这使得它们不具有语义安全性。

于是有专家设计了一个基于向量标量积的对称加密方案,该方案支持对加密数据库进行KNN计算。除此之外,目前已有一些同态加密算法,例如unpadded_RSA、ElGamal、Goldwasser_Micali、Benaloh和Paillier等,但它们只支持加法同态和乘法同态运算中的一种。

三、可计算加密技术的缺点

根据以上分析,我们发现可计算加密技术存在以下缺点:

(1)目前还没有一种加密方案能够同时支持字符串的检索和数值数据(包括整数和浮点数)的算术运算;

(2)目前对加密字符串的模糊检索还没有一个实际可行的方案;

(3)目前还没有一种支持密文运算的方案能轻松地同时解决整数和浮点数的加、减、乘、除法运算;

(4)已有的一些方案往往要求数据拥有者在数据外包前做大量的准备工作,这会使用户的使用体验大打折扣。

小知识之同态加密:

同态加密是基于数学难题的计算复杂性理论的密码学技术。对经过同态加密的数据进行处理得到一个输出,将这一输出进行解密,其结果与用同一方法处理未加密的原始数据得到的输出结果是一样的。