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

3630 Journal of Software 软件学报 Vol.32, No.11, November 2021

势问题的安全解决方案.
目前,已有的向量计算协议大多是在整数集上设计构造的,而实际生活中遇到的很多问题需要转化为有理
数域中的向量问题解决.由于已有的有理数向量的保密计算协议还较少,且计算效率和安全性都不高.为此,本
文对有理数域上的向量问题进行深入研究,并提出安全高效的解决方案.
本文的贡献如下:
(1) 利用基本代数学知识设计了简单、高效的向量点积协议,并以此为基础,设计了向量相等以及向量优
势保密判定协议.
(2) 本文所设计的协议仅需要基本的算术运算,未利用任何公钥加密方案,因而具有很高的计算效率.利
用模拟范例证明了协议在半诚实模型下是安全的.理论分析和实验结果都表明,本文协议与已有相关
协议相比具有较高的安全性和计算效率.
(3) 本文协议适用于计算有理数向量,具有广泛适用性.通过实例说明:对于其他的向量计算问题以及实
际应用问题的保密计算, 利用本文协议的设计思想可以安全高效的解决.
本文第 1 节主要介绍与本文有关的基本概念和记号.第 2 节~第 4 节分别详细描述向量点积保密计算协议、
向量相等保密判定协议和向量优势保密判定协议的具体步骤,以及各协议的正确性和安全性分析.第 5 节详细
分析和比较本文协议的效率.第 6 节介绍以本文协议为基础,可以解决其他安全多方计算问题.第 7 节总结全文.
1 预备知识

[5]
本节介绍一些与本文有关的基本概念和记号 文献[5]中对本部分内容进行了详细介绍..
双方计算.对于一个将任意的输入对映射为输出对的随机过程,用函数 f:(x,y)→(f 1 (x,y),f 2 (x,y))表示,并将此
过程称为双方计算.即:对于每一个输入对(x,y),输出对是随机变量(f 1 (x,y),f 2 (x,y)).记这样的函数为 f=(f 1 ,f 2 ).
理想模型. 假设有一个不会泄露任何私密信息的可信第三者(trusted third party,简称 TTP),两个参与者
P 1 ,P 2 分别将各自的私密数据 x,y 告诉可信的第三者,可信的第三者自己单独计算函数 f(x,y)→(f 1 (x,y),f 2 (x,y)),然
后将计算结果 f 1 (x,y),f 2 (x,y)分别告诉参与者 P 1 ,P 2 .参与者 P 1 ,P 2 最后仅能得到由可信第三者发送的计算结果,其
他任何信息都无法得到.上述通过可信的第三者对函数 f(x,y)进行保密计算的协议称为理想的两方保密计算协
议(简称理想协议或 TTP 协议).任何一个保密计算函数 f(x,y)的协议的安全性都比理想协议的安全性低,且协议
安全性的高低可通过与理想协议相比较得到,理想协议是安全性最高、最简单的保密协议.理想多方保密计算
方案虽然既简单又安全,但在应用中经常受到很大限制,原因是在网络环境中要找到一个可信的第三者一般不
是一件容易的事,利用可信的第三者也可能需要付出经济、时间等代价.
半诚实模型. 在协议执行过程中, 参与者除了按照协议要求诚实地执行协议,还可能将协议执行中的所有
信息记录下来,并在协议执行完毕后对收集到的信息进行推算得到其他参与者的私密信息,这样的参与者称为
半诚实参与者.若一个保密计算中所有的参与者都是半诚实参与者,这样的计算模型就称为半诚实模型.因为在
协议中半诚实参与者不会进行主动攻击,所以这样的计算模型又称为诚实但好奇(honest-but-curious)模型或被
动模型.在本文中,假设所有的参与者都是半诚实的.
模拟范例方法. 对安全多方计算协议的安全性进行证明时, 最常用的证明方法就是模拟范例法.该方法的
具体描述如下.
假设 P 1 和 P 2 分别是参与计算的两个参与者.设一个概率多项式时间函数为 f=(f 1 ,f 2 ),计算函数 f 的两方协议
为π.在协议π的执行过程中,参与者 P i (i=1,2)的输入数据为 x i 时,P i 得到的信息序列记为
i
view i π (, )x x = ( , ,x r m 1 i ,...,m i t , (, ))f x x 2 .
2
i
i
1
1
i
i
其中, f i (x 1 ,x 2 )表示参与者 P i 获得的输出结果,r 和 m 分别表示参与者 P i 产生的随机数和收到的第 j 个消息.
j
定义 1(半诚实模型下协议的安全性). 对于上述函数 f 和协议π,若使