Page 303 - 《软件学报》2021年第11期

刘旭红:高效安全向量计算及其推广 3629

性.SMC 要确保各参与者输入数据的私密性以及计算结果的正确性.国际著名的计算机科学家、密码学家
[3]
Cramer 提出:若任何函数都可以进行保密计算,将为计算科学提供一个强大的工具.Goldreich 等人 [4,5] 证明了
理论上安全多方计算问题都存在解决方案, 并给出适用于任何安全多方计算问题的通用方案,为安全多方计
算奠定了扎实的理论基础.但对于具体的安全多方计算问题,利用通用方案来解决会导致计算效率低、安全性
低等问题.因此针对具体的安全多方计算问题,需要根据其特点研究具体的解决方案.近年来,许多新的适用于
实际应用场景的安全多方计算问题被不断提出并研究出解决方案,使安全多方计算研究得到进一步发展.目前,
安全多方计算研究的主要问题包括:保密信息比较 [6,7] 、保密数据挖掘 [8−10] 、保密几何计算 [11−13] 、保密数据库
查询 [14−16] 、保密竞拍 [17−19] 等.
向量是一个高度抽象的数学对象,许多问题可以抽象为向量计算问题 [20−23] ,例如:
(1) 在信息检索、数据挖掘、机器翻译、文本复制等领域有着广泛应用的文本相似度计算,通过对涉及
到的文本进行向量化,然后计算向量间的余弦相似度,进而得到文本的相似度.
(2) 在计算几何中,关于图形相似性的保密计算问题、空间位置关系的保密计算问题中,往往需要对原始
数据进预处理,该过程不可避免存在有理数域上的数据.因此,计算几何中的诸多问题可以抽象为有
理数向量计算问题进行解决.
(3) 统计学在金融工程、经济等领域具有重要的基础作用,其中,期望、方差、加权平均值等问题的计算
都可以抽象为向量计算.
因此,利用向量运算可以解决文本相似度问题、自动问答系统、论文抄袭识别以及几何图形检索、经济学
等方面的许多问题.一个向量具有多个分量,各分量可以代表不同的含义,很多情形下,对向量进行某种运算等
价于对其分量分别做相应的运算.正因为向量计算的这种特殊性质,使其成为科学研究中一个基本而且重要的
研究方法 [24] .
目前,关于向量问题的保密计算主要包括保密计算向量点积 [25−34] 、保密判定向量相等 [35] 及保密判定向量
优势 [36−38] 等问题.其中,向量点积问题的研究最为广泛.文献[25]基于一个理想的预处理过程设计了向量点积协
议,但实现预处理阶段需要第三方参与者;文献[26]设计了在多密钥的云环境下进行计算的向量点积协议,计算
复杂性较高;文献[27]基于第三方服务器以及可逆矩阵设计了两个点积协议,在基于可逆矩阵的协议中,每个参
与者会泄露其 n 维向量的 n/2 个线性关系式(当向量维数或数据范围较小时,该协议存在一定的安全隐患),且需
要计算逆矩阵而导致其计算成本较高;文献[28]设计了一个基于多项式共享的点积协议,由于协议需要雇用半
诚实的第三方,协议容易受到合谋攻击;文献[29]在文献[30,31]的基础上设计了一个偶数维点积协议,该协议的
计算复杂性较低,但泄露了私有数据部分和的某些信息,仅适用于偶数维向量点积计算.文献[30−32]利用不同的
公钥加密算法设计了一些点积协议,其中,文献[30]中基于 Paillier 加密算法设计的点积协议是目前应用得较多
的一个经典的点积协议;文献[31]基于 Damgard 等人 [39] 的加密算法设计的点积协议与文献[30]中协议的设计方
案类似,只是将文献[30]中向量数据的正整数范围推广到负整数范围.这些协议的计算复杂性都较高.文献[32]
基于 Goldwasser-Micali 密码体制和不经意过滤器设计了一个有关二进制向量的点积协议,此协议与文献
[30,31]的协议相比,计算效率有所提高,但数据的适用范围却受到很大的限制.文献[33,34]也利用公钥加密体制
设计了一些点积协议,这些协议均需要借助于云服务器进行一些计算,由于应用公钥加密体制而使得计算复杂
性依然较高,且只适用于正整数范围内的向量计算.
关于两个向量相等或向量优势的保密判定问题,普遍的解决方案是将其对应分量分别进行比较,但这样做
显然会泄露很多不应泄露的信息.文献[35]基于字母表与连接运算和散列函数设计了向量相等保密判定协议,
该协议仅适用于向量的分量为正整数的情形,且判定结果可能出现单边错误.文献[36]通过多次调用百万富翁
协议解决向量优势问题,但解决方案效率较低且有信息泄露.为了克服文献[36]的缺陷,文献[37]通过引进茫然
的第三方,将向量优势问题扩展为向量优势统计问题,这样做增加了协议的通信轮数,也会泄露私密向量的部分
信息;文献[38]也设计了一个向量优势统计问题的保密判定协议,与文献[37]相比提高了计算效率,但当向量
X=(x 1 ,…,x n )和 Y=(y 1 ,…,y n )不具有向量优势关系时,会泄露两向量中具有关系 x i >y i 的分量数目,无法获得向量优