基于无匹配差错的PSI计算  

PSI Computation Based on No Matching Errors

作　　者：巩林明 王道顺[3] 刘沫萌 高全力 邵连合 王明明 GONG Lin-Ming;WANG Dao-Shun;LIU Mo-Meng;GAO Quan-Li;SHAO Lian-He;WANG Ming-Ming(The National and Local Joint Engineering Research Center for Advanced Networking&Intelligent Information Service/Shaanxi Key Laboratory of Clothing Intelligence,School of Computer Science,Xi'an Polytechnic University,Xi'an 710048;Shaanxi Key Laboratory on Functional Cloths,Xi'an Polytechnic University,Xi'an 710048;Department of Computer Science and Technology,Tsinghua University,Beijing 100084)

机构地区：[1]西安工程大学计算机科学学院陕西省服装设计智能化重点实验室/新型网络智能信息服务国家地方联合工程研究中心,西安710048 [2]西安工程大学陕西省功能性服装面料重点实验室,西安710048 [3]清华大学计算机科学与技术系,北京100084

出　　处：《计算机学报》2020年第9期1769-1790,共22页Chinese Journal of Computers

基　　金：国家自然科学基金(61972225,61902164,61601358,61672426,61902300,61902303,11847101);国家科技支撑计划子课题(2018YFB1004501);西安工程大学博士科研启动基金(107020331);陕西省教育厅重点科学研究计划项目(20JS052);陕西省2020年技术创新引导专项计划(2020CGXNG-012)资助.

摘　　要：分布式计算有很多应用需要参与各方协同执行集合的一些计算但不泄露各自数据集的信息.保密集合交集(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)ex

关 键 词：保密集合交集 有理数加密 语义安全 安全两方计算 集合的定长向量编码 

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