基于阈值的向量保密计算*

王颖囡, 窦家维, 葛 雪

陕西师范大学 数学与信息科学学院, 西安710119

1 引言

在实际生活中, 很多问题都可以抽象为向量比较问题从而得以解决. 例如公司A 要找寻商业合作伙伴, 但希望合作公司在某些方面能达到一定的条件(例如总资产、信誉值等), 对这些条件进行一定的标准化即可表示为向量x= (x1,··· ,xn), 而B 公司的数据也可表示成对应的向量y= (y1,··· ,yn), 要判定公司A 与公司B 是否能达成合作就转化为判定xi ＞yi的分量个数是否达到了公司A 自己的设定值t.此外, 在进行样本特征匹配检测时, 仅需要判定两特征串相同字符个数是否达到某个阈值, 若达到设定的阈值, 就说明两者匹配, 否则不匹配, 将两特征串表示成向量x= (x1,··· ,xn),y= (y1,··· ,yn), 则问题就转化为判定xi=yi的分量个数是否达到了阈值t. 由此可见, 向量为解决一些实际问题提供了基本方法. 但在很多情况下, 向量中的数据涉及到人们的隐私, 人们不希望在计算的过程中泄露信息. 因此在保护隐私的前提下进行向量计算有很大的实际意义. 安全多方计算作为密码学的一个重要研究方向, 可以很好地解决这一问题.

安全多方计算是一种保护隐私数据的计算方式, 是指参与者利用其私有数据进行合作计算, 并得到所需结果, 同时在计算结束后, 每个参与者不能获得其他参与者隐私数据的任何额外信息. Yao 在文献[1]中最早提出两方安全计算问题, 随后, Goldreich 等人提出了安全多方计算问题, 并对其进行了深入的研究[2,3], 他们证明了……