有理数域上两方集合的高效保密计算  

Privacy Preserving Two-Party Rational Set Computation

作　　者：窦家维[1] 刘旭红 王文丽 DOU Jia-Wei;LIU Xu-Hong;WANG Wen-Li(School of Mathematics and Information Science,Shaanxi Normal University,Xi’an 710119)

机构地区：[1]陕西师范大学数学与信息科学学院,西安710119

出　　处：《计算机学报》2020年第8期1397-1413,共17页Chinese Journal of Computers

基　　金：国家自然科学基金(61272435)资助.

摘　　要：安全多方计算已经成为密码学的一个重要研究方向,是国际密码学界的一个研究热点.集合运算可以用来描述许多实际问题,因此研究集合的保密计算问题具有重要的理论与实际意义.目前,关于整数集上集合问题的保密计算已有很多重要成果,但在有理数域上集合问题的保密计算尚未见到有关研究报道.本文主要研究有理数域上集合的两方保密计算问题.首先,提出一种新的转化思想,将任意有理数编码为直角坐标系中一条过原点的直线,并结合三角形面积计算公式,将有理数域上元素与集合关系问题转化为整数范围内向量内积问题,进一步结合Paillier加密方案设计了集合运算的保密计算协议.其次,设计了将平面上的有理点编码为有理数的新编码方案,在此基础上设计了判定有理点是否属于有理点集合的保密判定协议.最后,应用模拟范例证明了所设计协议在半诚实模型下是安全的,并通过理论分析和实验测试说明协议是高效的.Secure multiparty computation is an important research area of cryptography and a key privacy-preserving technology in information society.It is also a focus of the international cryptographic community.Secure set operation is an important topic of secure multiparty scientific computation,an important field of secure multiparty computation.As many practical problems can be reduced to set problems,it is of both theoretically and practically important significance to study the secure multiparty computation of the set operation.There are many works to study secure integer set computation.To the best of our knowledge,there is little research investigating the secure rational set computation.The existing solutions to secure integer set computation can hardly be directly applied to solve secure rational set operation problems.This paper focuses on solving secure multiparty rational set operation problems including privately determining whether a rational number belongs to a rational set,privately computing the intersection or the union of two private sets,and privately computing the cardinality of the intersection/union of two private sets.The key to these problems is to privately determine whether a private rational number belongs to a private rational set,which can be reduced to privately determine whether two private numbers are equal.In this paper,we represent a rational number u by the line that passes the origin with slope u,and two rational numbers are equal if and only if the two lines to represent them coincide.Therefore,privately determine whether two rational numbers are equal is transformed into privately determining whether two private lines coincide.To privately determining whether two private lines coincide,we can choose one point on a private line and two different points on another private line;these three points form a triangle;the area of this triangle is zero if and only if the two lines coincide.Then we utilize the Paillier additively homomorphic encryption cryptosystem to design a protocol to priv

关 键 词：保密计算 有理数 集合运算 编码方案 同态加密 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]