基于无匹配差错的PSI计算

PSI Computation Based on No Matching Errors

分布式计算有很多应用需要参与各方协同执行集合的一些计算但不泄露各自数据集的信息.保密集合交集(private set intersection,PSI)计算已经成为数据匹配、数据挖掘、推荐系统等应用中保护用户隐私的一个重要工具.本文的主要工作是构造无匹配差错的安全两方保密集合交集运算协议.着重探讨三个问题:(1)开发构造无匹配差错的两方保密集合交集计算所需要的工具(①面向有理数且具有语义安全性的加密方案,②便于集合匹配计算的称之为集合的定长向量编码方法);(2)无匹配差错的两方保密集合交集计算问题;(3)元素为有理数的保密集合交集计算问题.首先在标准模型下设计了一个能够加密有理数的方案,并证明了该方案能抗自适应性地选择明文攻击;而后又提出了一种便于集合匹配计算的,称之为集合的定长向量编码方法;最后基于有理数加密方案和集合的定长向量编码方法构造了两个面向有理数的、无匹配差错的两方保密集合交集协议.与先前的两方保密集合交集协议相较之,这两个协议不仅解决了无匹配差错的两方保密集合交集计算,还拓展了保密集合交集问题中隐私保护的范畴:除了可以保护各参与方的隐私数据外,还可以保护各参与方隐私数据的数量.

In a distributed computing,many applications require multi-parties to jointly perform set operations.After the collaborative computing,except the result of the operation(equal to the result of the plaintext operation),the participating parties should not get the private information about other parties.This collaboratively distributed computation is called private set computation.Private set intersection(PSI)is an important research field of private set computation.In recent years,PSI has become an important tool for protecting user privacy in applications such as data matching,data mining,and recommendation systems,etc..In this paper,the goal is to construct private set intersection protocols using encryption scheme with rational numbers.Three specific issues are covered.The first issue is developing tools required to construct the two-party PSI protocols without matching errors(a rational number-oriented encryption scheme with semantic security and a set encoding method called set encoding with a fixed-length vector that is convenient for set matching calculation).The second issue is studying the problem of precise evaluation in the two-party private set intersection.Both participants have a private set respectively.After implementing a protocol for computing private set intersection,they aim to achieve(1)the result of the collaborative computation is 100%equal to the result calculated directly in plaintext.Unlike some previous confidential two-party intersection protocols,the results of collaborative calculation may have errors,and the scope of errors is difficult to be defined;(2)after the collaborative calculation,the two sides do not disclose the elements of their respective sets,nor do they disclose the potential of their respective sets.That is to say,after completing the confidential calculation,the results of the collaborative calculation by these two participants must be correct,and both participants can not get any other information about each other(the elements of the set,the cardinality of the set)except for the common elements of their private set.The third issue is studying the problem of two-party private intersection computing whose elements are rational numbers:Both participants respectively have a private set,in which the elements are rational numbers.By jointly implementing a PSI calculation protocol,they aim to achieve(1)the result of the collaborative calculation is 100%equal to the result calculated directly in plaintext;(2)the two sides do not disclose the elements of their respective sets,nor do they disclose the cardinality of their respective sets.To answer those questions,firstly,a scheme capable of encrypting rational numbers is designed under the standard model,and it is proved that the scheme can resist adaptive selection plaintext attack.Then,a set encoding called set encoding with a fix-length vector is proposed to facilitate set matching calculation.Finally,based on the proposed encryption scheme with rational numbers and the proposed set encoding with a fix-length vector,we present two two-parties private intersection protocols with rational elements without matching errors.Compared with the previous two-party private intersection protocols,these two protocols not only extend the category of privacy protection in the problem of PSI but also solve the precise evaluation of two-party private intersection:in addition to protecting the private data of each party,the amount of private data of each participant can also be protected.