第43卷   第9 期  计  算  机  学  报  Vol. 43  No. 9 2020年9 月  CHINESE  JOURNAL   OF  COMPUTERS Sep. 2020                        收稿日期：2018-09-25 ；在线发布日期：2020-02-07. 本课题得到国家自然科学基金(61972225, 61902164, 61601358, 61672426, 61902300, 61902303, 11847101) 、国家科技支撑计划子课题(2018YFB1004501) 、西安工程大学博士科研启动基金(107020331) 、陕西省教育厅重点科学研究计划项目(20JS052)、陕西省2020年技术创新引导专项计划(2020CGXNG-012) 资助.  巩林明( 通信作者) ，博士，讲师，主要研究领域为密码学与信息安全. E-mail: glmxinjing@163.com.  王道顺( 通信作者) ，博士，副教授，主要研究领域为密码算法、视频智能行为分析、多媒体安全与取证，E-mail: daoshun@mail.tsinghua.edu.cn. 刘沫萌，博士，讲师，主要研究领域为密码学与信息安全.  高全力，博士，讲师，主要研究领域为网络与信息安全.  邵连合，博士，副教授，主要研究领域为信息安全与量子智能信息计算.  王明明，博士，副教授，主要研究领域为密码学与信息安全.   基于无匹配差错的PSI 计算 巩林明1,2)   王道顺3)   刘沫萌1)   高全力1)   邵连合1)   王明明1) 1)(西安工程大学计算机科学学院陕西省服装设计智能化重点实验室/新型网络智能信息服务国家地方联合工程研究中心   西安  710048) 2)(西安工程大学陕西省功能性服装面料重点实验室   西安  710048) 3)(清华大学计算机科学与技术系   北京  100084) 摘  要  分布式计算有很多应用需要参与各方协同执行集合的一些计算但不泄露各自数据集的信息.  保密集合交集(private set intersection, PSI) 计算已经成为数据匹配、数据挖掘、推荐系统等应用中保护用户隐私的一个重要工具.  本文的主要工作是构造无匹配差错的安全两方保密集合交集运算协议.  着重探讨三个问题：（1 ）开发构造无匹配差错的两方保密集合交集计算所需要的工具（①面向有理数且具有语义安全性的加密方案，②便于集合匹配计算的称之为集合的定长向量编码方法）；（ 2 ）无匹配差错的两方保密集合交集计算问题；（3 ）元素为有理数的保密集合交集计算问题.  首先在标准模型下设计了一个能够加密有理数的方案，并证明了该方案能抗自适应性地选择明文攻击；而后又提出了一种便于集合匹配计算的，称之为集合的定长向量编码方法；最后基于有理数加密方案和集合的定长向量编码方法构造了两个面向有理数的、无匹配差错的两方保密集合交集协议.  与先前的两方保密集合交集协议相较之，这两个协议不仅解决了无匹配差错的两方保密集合交集计算，还拓展了保密集合交集问题中隐私保护的范畴：除了可以保护各参与方的隐私数据外，还可以保护各参与方隐私数据的数量.   关键词  保密集合交集；有理数加密；语义安全；安全两方计算；集合的定长向量编码 中图法分类号  TP301       DOI 号  10.11897/SP.J.1016.2020.01769 PSI Computation Based on No Matching Errors GONG Lin-Ming1,2)  WANG Dao-Shun3)  LIU Mo-Meng1)  GAO Quan-Li1) SHAO Lian-He1)  WANG Ming- Ming1) 1) ( 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)  2) ( Shaanxi Key Laboratory on Functional Cloths , Xi'an Polytechnic University, Xi'an   710048) 3)( Department of Computer Science and Technology, Tsinghua University, Beijing  100084)  Abstract   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 se t 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 1770  计  算  机  学  报 2020年   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 participan ts 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 colla borative 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 re sults 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 intersectio n 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 ad dition to protecting the private data of each party, the amount of private data of each participant can also be protected.  Keywords  private set intersection; encryption with rational numbers; semantic security; two-party secure computation; set encoding with fix-length vector  1   引   言 随着分布式计算在各领域的深入发展，越来越多的应用需要参与各方利用他们的私有数据集合协同执行一些集合运算，协同运算结束后，除了运算结果( 等于明文运算的结果) 外，参与各方不会得到有关其它各方的私有信息，这种分布式协同计算被称为保密集合计算.  保密集合交集计算是保密集合计算领域的一个重要研究方向.  它在保密服务预约、保密信息匹配[1]、保密数据挖掘[2]、保密推荐系统[3]，保密计算广告转化率[4]等领域有着广泛应用，已经成为这些领域保护用户隐私的一个重要工具.  从可计算的角度来讲，基于“多项式验根”法、“多个函数间提取公因式”方法、集合元素用数字签名技术实施认证以及“不经意伪随机函数(Pseu-Dorandom Function, PRF)计算”思想构造的PSI 协议，例如协议[1,5-7] 分别为分布式环境下的保密集合计算问题开辟了一种可以解决问题的新方法. 然而采用前三种方法设计的保密集合交集计算协议，协议执行结束计算结果可能存在差错，且差错的范围难以界定；基于不经意伪随机函数计算的保密集合交集计算协议虽然不会泄露双方集合中的私密数据，但会泄露拥有PRF 密钥prf 一方集合的势.    较基于“多项式验根”法、“多个函数间提取公因式”方法、数字签名技术所构造的保密集合交集计算协议，采用协同计算结果必定等于交集思想所9 期  巩林明等：基于无匹配差错的PSI 计算 1771    构造的保密集合交集计算( 被称为保密集合交集的精确计算) 协议更具有研究价值、更具有应用价值：从安全方面讲，保密集合交集的精确计算可以为分布式用户提供更安全的隐私保护( 既保护参与方的数据元素又保护参与方的数据元素个数) ；从效率方面讲，保密集合交集的精确计算因为协同计算无差错，一次协同计算结束后参与各方必定会实现协同计算的目的.   本文着手于解决安全两方集合交集的精确计算问题：参与双方1P 和2P 分别拥有集合1S 与2S ，在执行保密计算12 SS 的协议后他们要实现: (1)  协同计算的结果百分百等于 12 SS ，不再像先前诸如协议[1,5,8-10] 等一些保密两方交集协议那样，协同计算的结果可能存在差错，且差错的范围难于界定；(2)  在协同完成计算12 SS 后，双方在不泄露各自集合元素的同时，也不泄露各自集合的势.  也就说，1P 和2P 协同完成保密计算12 SS 后，二者的计算结果一定正确，他们除了得到12 SS 外，再也得不到有关对方的任何其它信息( 集合的元素、集合的势). 近些年来，因保密集合交集计算问题在保密服务预约、保密信息匹配[1]、保密数据挖掘[2]、保密推荐系统[3]、安全事件信息的安全共享[4]等领域有着广泛应用，得到了学者们的广泛关注，产出了相当丰硕的成果.  这些成果按照协议构造时所采用的保密工具大致可以分成五类：基于某个数学难解问题构造的协议[5,6,12-22]，基于对称密码方案构造的协议[23,24]，基于混淆电路构造的协议[23-26]，基于不经意传输构造的协议[27-30]，基于不经意函数计算构造的协议[1,4,8,11,31]. 其中，基于某个数学难解问题构造的一类协议大都采用保密验证元素的方法实现交集的计算.  保密验证元素的方法大致可以分为四类：多项式验根，函数间提取公因式，不经意函数计算法，用数字签名认证元素法.  1. 采用“多项式验根”法构造协议[1,8].  两方保密集合交集运算最初由Freedman等人提出[1].  此协议采用如下方式实现保密集合运算( 不失一般性，我们假定Alice和Bob 为参与保密计算的两个互不信任的协作方) ： (1) Alice 运行Paillier同态加密方案密钥生成算法(1 )k ，获取公私密钥对(K ,K )pub pri； (2) Alice 将集合中的元素作为多项式的根构造一个多项式： 12 () ( )( ) ( )=akfx xa xa xa      110 ˆ ˆ ˆaakk kk ax a x a ，然后将多项式的系数10 ˆˆ ˆ ,,, aa kk aa a  用Paillier 同态加密方案加密： 10 ˆ ˆˆ ( ),( ), ,( )aa kk Ea Ea Ea  ，并按序传送给Bob ； (3) Bob 收到10 ˆ ˆˆ ( ),( ), ,( )aa kk Ea Ea Ea  后，在密文上执行同态运算，进而求得·( )ii rf b b   ( 其中r 是Bob 随机选取的，ib 是Bob 集合中的元素) 对应的密文 (()) iii cErfb b  ，并将密文1, ,()bii kCc发送给Alice； (4) Alice 收到1, ,()bii kCc后进行解密；如果解密结果落在自己的集合中，则认为解密结果为保密集合交集的元素之一.  此后该协议被拓展成高效的协议[17,32]、对外包数据可验证的协议[18]和抗恶意敌手的协议[8-10,12,13].  2.   采用“多个函数间提取公因式”方法构造协议[5,19,33]. Kissner ，Song采用多项式间提取公因式法设计了一个适应于多方环境的保密集合交集计算协议[5].  该协议的朴素思想如下： (1) Alice( 假定Alice拥有Paillier解密密钥) 和Bob 分别将各自的集合A 与B 表示成多项式 ()AQ 和 ()BQ  ； (2)  如果令 ()Ar  和 ()Br  分别是Alice和Bob 选择的随机多项式，则多项式 () () ()AAB rQ r    ()BQ  的根所构成的集合等于A B  的概率很大.  这是因为如果 1,,, ii ij x xx  ( 1 j ≥) 是 ()AQ  和()BQ  的公共零点， ()AQ  和 ()BQ  提取因式( x   1)( ) ( )i ii j xxx xx    ( ij≤) 后的剩余多项式分别记作 ()RQA 和 ()RQB ，则 () () () ()AABB rQ rQ    可以表示成 1()( )( )(()() ii ijAR xxxx xx r QA      () ())BR rQB  。 2011 年，Kim M等人将该协议拓展成服务器与客户都可以得到保密交集的协议[19]；2013 年，Dan Boneh 等人将该协议拓展成三方协议[34]；2018 年Zhou 等人采用多项式间提取公因式法设计了一个适应于多方环境、具有信息论安全的保密集合交集计算协议[33].  此协议的朴素思想如下：①  n 个参与者i1{} inP≤≤分别将各自集合表示成保密多项式 ()if x   22( ) 22 2 12 0()( )( ) iiqlll qiq i i ilqax x x x x x x x    ，其 中ill≤， {1, 2 , , } in  ；②   参与者iP , 11in ≤≤按照如下方式执行：1) 将各自的保密多项式随机地分成非零的k 份12(), (), ,ii fxf x ()ikf x 满足 ()if x   1()kijjf x ，为每一份加入随机数后发送给n 个参与 者中的k 个；2) 将各自收到的多项式相加，组成新的多项式 (), 1, , 1igxi n    ，并分别发送给nP ；3) nP 计算交集.  1772  计  算  机  学  报 2020年   3. 采用“不经意伪随机函数计算”思想构造协议[7,14,15,35]. Michael  借助不经意伪随机函数计算实现了保密集合交集计算[7].  其思想如下( 此处仍假定Alice和Bob 为协议的两个参与方，他们分别持有集合X 与Y ) ： (1) Alice 选取一个PRF 密钥prf 并计算集合{()}prfXxXPRF PRF x； (2) Alice 和Bob 联合执行不经意随机函数计算协议，其中Alice在协议中的输入为prf ，Bob 的输入为其私有集合Y ，协议执行完后，Bob 得到集合 {()}prfYyYPRF PRF x； (3) Alice 将集合 {()}prfXxXPRF PRF x发给Bob ，Bob 计算XY P RF PRF  并据此提取XY .  此后，该协议被拓展成一些高效的协议[14,15,35]. 近年来，有些学者在该方法的基础上结合其他方法实现了满足某些实际应用需求的协议[16,25,27,28,36].   4.  采用数字签名技术构造带认证的协议[6,20,37-39]. 2009年，De Cristofaro[6] 采用数字签名技术设计了一个带认证的保密集合交集计算协议.  其思想如下( 此处仍假定Alice和Bob 为协议的两个参与方，他们分别持有集合 1={ }aiil Xx≤≤与1={y }biil Y≤≤，1 ≤ ,ab ll n ≤，分别表示Alice和Bob 各自集合中元素的数目) ： (1) Alice 运行加密方案密钥生成算法，获取公私密钥对(,,) pub priKKg； (2) Alice 为集合中的所有元素计算一个指纹() ii hc H x  ，并对指纹进行签名： ()p ubKiihc     mod  n ，然后随机选取一个/4 ci nRZ 并计算：i   2() mod  ciRig n   ，最后将1{}iin ≤≤传送给Bob ； (3) Bob 收到1{}iin ≤≤后按照如下方式执行：①随机选取一个 /4 s nRZ 并计算 modpri sKRZ gn ；②对于 ,llab iZ jZ   计算 ,,()p ri sK Rsi j iK  2(()) mod sRiHy n，,,,() ij sijtHK  ；③将1,1,{ , , Zt  ,}ijt 发送给Alice； (4) Alice  收到1,1 ,,{ , , }ijZ tt 后按照如下方式执行：①对于laj Z 计算 ,() modcjRcjKZ n  ，,() j cjtHK  ；②  计算11,1, {,,}{,, }aabllltt t t  .  2010年，De Cristofaro 对上述协议的安全性进行了改良，提出了一个能够抗恶意敌手攻击的保密集合交集协议[20]；随后，De Cristofaro 对上述协议的隐私保护条件做了进一步约束( 协议应在在保护双方数据集元素的同时还不泄露客户数据集的大小，即客户数据集的势) ，提出了两个快速保密集合交集计算协议[37,38]. 2017 ，Kiss Á 对上述协议进行了改进，提出了一个面向移动应用的轻量级保密集合交集协议[39].  综上所述，协议虽然都很漂亮地解决了保密集合交集问题.  但是我们发现保密集合交集计算领域依然存在如下一些尚未彻底解决的问题： (1)  集合交集元素的无差错匹配问题依然没有得到解决，具体体现在如下两个方面： ①采用“多项式验根”法所构造的保密集合交集计算协议，其匹配计算结果可能存在差错，且差错的范围难以界定.  这是因为这些协议只关注了() 0 ifb  时·( )iii rf b b b   这一合理性，而忽略了利用同态加密运算获得密文() 2mod  ii rf b bg n  () mod 2mod  ii rb b ng nc( 1 g kn   , kZ ) 过程中，指数上所隐含的模n 运算：·( ) modii rf b b n  .  ()ifb   0 时，·( ) modii rf b b n  很可能是Alice集合中不等于ib 的元素ja ( 只属于用户数据库而不是服务器数据库中的元素) ，即·( ) modii j rf b b n a  ( 如图1所示).  如果·( ) modii j rf b b n a   这种情况发生了，即用户Alice 所求结果中包含了两方数据交集中本应该没有的元素( 此元素只属于 Alice 而不属于Bob)，即Alice(用户) 所求结果是错误的.  遗憾的是Alice无法发现这种匹配错误.  事实上，只有匹配正确的PSI 计算才有意义，这违背了保密集合交集计算的初衷( 计算结果正确且能保证参与双方的隐私数据).  特别是用户数据库集合包含的元素越多时，则用户数据库集合中本来不属于交集的元素ja ，即·( ) modii j rf b b n a   出现在交集中的概率就越大，即保密信息匹配结果出现错误的概率就越大.   图1   不可忽略的误差 ②在采用多个函数间提取公因式方法所构造的保密集合交集计算协议中， () ()AR rQA   与 ()Br    ()RQB 很可能还存在公共因式 1()( ) ii xx xx  ()ijxx   ( ij  ≤ ). 显然，这很可能出现 1{, , iix x 11 ,}{ , }{,,,} ,ij i i ij i i ijxxxxxxx     的情形，并且这种情形发生的概率是无法界定的.  而{,ix  111 ,, }{ , }{, ,, ,} iijiiijiiij xx xxx xxx       意味着产生匹配计算差错，即 1{, , , } ii ij AB xx x    . 从而导致实际计算出的交集A B  中存在元素要么只属于Alice，要么只属于Bob. 在该方法的拓展 协议[33]中，nP 在计算1()niig x 时，除了可以提取完 9 期  巩林明等：基于无匹配差错的PSI 计算 1773    全平方构成的公因式外还很可能引入公共因式1()( )( ) ii ij xx xx xx      ( ij≤ ) ，例如，( x   22 6) ( 21) x  与( x 222 6) ( 21) ( 2) xx相加的结果中不仅有公因式22 (6)(21) xx还有公因式( x   5)(x  4) .  这显然会导致保密计算结果产生错误.  (2)  基于不经意函数计算的保密集合交集计算协议虽然不会泄露双方集合中的私密数据，但会泄露拥有PRF 密钥prf 一方集合的势.  为了丰富保密集合交集计算的研究方法，同时实现无匹配差错且保密范畴更广的( 既不会泄露参与双方集合中的私密数据，也不会泄露参与双方私密数据的数量) 保密集合交集计算.  在两方参与的环境下，构建了无匹配差错的保密集合交集计算协议. 该协议在保证保密交集计算100%正确的前提下，能够用于保密计算元素为有理数集合的交集，且不泄露各参与方私有集合的势.  除此之外，本文还做了如下三个工作： (1)  提出一个称之为二元组型高阶剩余类判定性(Decisional Tuple Composite Residuosity) 问题的难解问题，并证明了其难解性； (2)  基于二元组型高阶剩余类判定性问题，设计了一个高效的有理数加密方案，该方案既可以用于解决集合元素为整数域上的保密集合交集问题也可以用于解决集合元素为有理数域上的保密集合交集问题，拓展了解决问题的范围； (3)  提出了一种适用于无匹配差错的保密集合交集计算的集合编码方法：集合的定长向量编码.  2   预备知识 2.1  非对称加密系统安全性定义[40,41] 非对称加密系统具有不可区分安全性的充分必要条件.  加密语义安全的概念通常由一个系统构建者和一个敌手参与的思维实验来刻画[40]，该思维实验通常被称作不可区分安全游戏.  对于任意一个安全参数为k 的公钥加密系统 ，任何攻击系统 的敌手 ( 在多项时间可被执行完的算法) ，它参与不可区分游戏时，能够获胜的优势函数记作,() Adv k，其用选择性明文攻击方法攻击 的事件记作,()cpaP ubK k.   具有选择明文不可区分(indisting-uishability under chosen-p laintext attack, IND-CPA)安全性，当且仅当存在一个可忽略的函数 ，满足： ,,1() [ () 1] ().2cpa cpaA dv k Pr PubK k k   ≤  其中，IND-CPA 安全性游戏在文献[40,41]被定义为： (1)  系统构建者生成系统 ，并产生公私钥对( , Pub PriKK) ，敌手 获得公钥P ubK ； (2)   生成若干明文消息，并得到它们对应的密文； (3)   输出两个等长的消息 , {0,1}bmb ，系统构建者随机选取 {0,1} b  ，将 bm 加密成挑战密文C，并将C发送给 ； (4)   输出 {0,1} b   ，如果 bb  ，则敌手攻击 成功.  在该游戏中，敌手的优势被定义成关于安全参数k 的函数： ,1() [ ] .2cpaAdv k Pr b b    2.2  抗半诚实敌手的安全多方计算模型 我们采用文献[42,43] 给出的半诚实模型下两方计算协议的安全性定义：设分别拥有1x 与2x 的两个参与者采用协议 协同计算确定性概率多项式函数1(, ): {0,1 ,} ii i fff    ， . 如果存在多项式时间的敌手，记作1 和2 ，分别控制着参与者1P 和2P 并满足 12 1212 1211112 1 12,{0,1} ,{0,1}22112 2 12, {0,1} , {0,1}{ ( , ( , ))} {view ( , ) }(1a){ ( , ( , ))} {view ( , ) }(1b).cxx xxcxx xxx fxx xxxfxx xx 则称协议 在半诚实模型下能够安全计算函数1(, ) 1 ,{0,} iii fff  .  其中1211112 ,{0,1}{ ( , ( , ))}xxxfxx 与1222112 ,{0,1}{ ( , ( , ))}xxxfxx  分别代表参与方 1P 和 2P 的视图，“c ”表示计算上不可区分.  敌手视图包 括相应参与者的输入、模拟协议时的模拟抛硬币结果和模拟协议时收到的消息.   Goldreich采用比特承诺与零知识证明理论构造了一个编译器，如有必要，就可以借助该编译器将抗半诚实敌手攻击的协议自动转换成抗恶意敌手攻击的协议.  其核心思想是迫使恶意的参与者以半诚实方式参与协议的执行，否则就会被发现.  如果我们需要一个抗恶意敌手攻击的协议，只要将事先设计好的抗半诚实敌手攻击的协议 作为编译器的输入，编译器就可以为我们输出一个抗恶意敌手攻击的协议   .  出于工程实际的需要，文中假定保密集合交集计算协议的参与者都是半诚实的.  2.3  Paillier 同态加密方案 Paillier加密方案[44] ( 如图2 所示) 具有良好的加法同态性： 0 101 0 101 0 1( ) ( ) ( )                                  (2a).()(())   ( (( )) 2b)M MEM M EM EMEM M EM EM     1774  计  算  机  学  报 2020年   加密:  明文  M n  ，npq ，p 、q 是等长的大素数   选择随机数  rn    密文 2modnMCgr n  ， 1  ( )ng kn k Z   解密:  密文 2Cn   明文 22(mod)mod(mod)LC nM nLg n ;   ()1Ln；lcm( 1, 1) pq   图2  Paillier 加密方案 该方案在高阶剩余类判定性困难假设下具有语义安全性，即任意两个明文 0M 、1M (01 |||| M M  )用此方案加密后所得的对应消息0C 、1C 是两个计算 不可区分的量：01cCC .   2.4  高阶剩余类判定性问题 高阶剩余类判定性(Decisional Composite Resi-duosity, DCR )问题[41,44].  简单地讲，高阶剩余类判定性(Decisional Composite Residuosity, DCR ) 问题[4,8]就是判定是否存在一个y 使得2 modnzy n  ，其中n （合数）与 2nzZ 为事先给定的量.  其形式化语言描述[8]如下： 假定区分算法 D 在区分实验中，能够区分两个分布2{( , R) | R { mod | }}nnDn r nrZ   和ranD   2 {( , R) | R }RnnZ 的优势记作关于系统安全参数的函数(,)()ranDDDAdv .  给定一个随机分布(,R) n   {,} ranD D，区分算法D 能够区分出(,R) n 是ranD 和D中哪一个的优势函数 ()DAdv  可以表示为 (,)()D( , ) D( , ) .ranDDDranAdvPr n R D Pr n R D   事实上，高阶剩余类判定性问题是公认的难解问题，所以必定存在一个可忽略的函数 ()   满足 (,)() (). ≤ ranDDDAdv    二元组型高阶剩余类判定性(Decisional Tuple Composite Residuosity , DTCR) 问题.  现将上面两个分布ranD 和D中的R 分别替换成(,R) R和 22 (mod,mod)nnrnrn ，得到两个新分布 ran D 和D  ： 22(,)2222(, ) (,( , ))| }  (3a){( , ) ( , ( mod , mod )) | .               {( mod , mod ) | , }}      (3{b)RRrannnnnnnnDnRnRRR ZZDnRnr nr nRrnrnrrZ   区分(, ) { , }rannR D D 是 ran D 和D  中哪一个的问题被称作DTCR 问题.  定理1. 如果DCR是多项式时间的难解问题，则DTCR 问题也是多项式时间的难解问题.  证明. 假定区分算法 D  区分出(, ) { ,rannR D   } D是分布 ran D 和D  中哪一个的优势函数记作, ( )()ranDDDAdv  .   显然如果算法D  能够以很大的优势区分出(, ) { , }rannR D D 是分布 ran D 和D  中的哪一个，那么就可以用区分算法D  解决DCR问题.   假定算法D  能以不可忽略的优势解决DCR问题，则用区分算法D  解决DCR问题的成功概率可用贝叶斯全概率公式表示为：  (,)(,) 11 111 ()() .22 222 2ranranDDDD AdvAdv      DD 因此，区分算法D  能够区分出(, ) { , }rannR D D 是ran D 和D  中哪一个的优势函数(,)()ranDDDAdv 满足 (,)(,) 1()1()22 2()                        .2≤ranranDDDD DDAdvAdv    因为()   是可忽略的函数，所以()2 也是可忽 略的.  这与假设“算法D  能以不可忽略的优势解决DCR问题”矛盾，也就说，二元组型高阶剩余类判定性问题是难解的.  证毕. 3    有理数的加密 Paillier加密方案具有同态加的特性，为解决一些保密多方计算问题提供了便利.  但是它只能用于解决nZ 上的函数保密计算问题.  为了拓展解决问题的范围，本文设计了一个基于二元组型高阶剩余类判定性问题的且能用于加密有理数的加密方案.  该方案把一个有理数加密成一个二维向量，其中表示分子和分母的密文分量可以通过密文分量间( 同为分子的密文分量或同为分母的密文分量) 的模乘运算实现同类型密文分量对应的明文分量在指数上的加同态；并且在某些需要保护无密钥一方隐私的计算分布式计算中，作为无密钥的参与方，计算包含隐私的脱敏数据时所用的参数xg ，可以由其根据实际需要适应性地选取.  用于有理数的加密方案及其性能描述如下： 3.1  有理数的加密方案 有理数的加密系统由密钥生成算法(Key- Generation) 、换底算法(Base-Transformation) 、有理9 期  巩林明等：基于无匹配差错的PSI 计算 1775    加密(Encryption) 和有理解密(Decryption) 四个随机算法组成，记作 (Key-Generation, Base-Transfor-mation, Encryption, Decryption)： Key-Generation：生成两个大素数p 、q 使得|||| pq  ( || 表示数“ ”的二进制码长) ，计算npq ，lcm( 1, 1) pq  ， 1  ( )ng kn k Z  ，发布公钥(, )pubKng ;  保留私钥priK   .  Base-Transformation: 随机选择一个k  nZ ，为某一时间段内的加密运算计算新的底数： 21(1)mod. xg kg n     Encryption ：发送者首先将要加密的有理数对应的分 数表示成序偶(, ) M M ( ,nM MZ 分别为分子和分母并且满足gcd( , ) 1 MM ) ，然后随机选择012,,nn rZrrZ ,  对于M n  ，计算： 2222(1 ( 1)) mod mod ,(1 ( 1)) mod . modnn xxnMxMnxrccMg ngrrnMg r ng n        Decryption：接收方执行解密运算： 22(mod )     (mod )(1 ( 1)) 1          = ,(1 ( 1)) 1xxMc nMcnMgMg       2() 1,( 1 ) ( ) x nn        其中 .  3.2  解密正确性验证 证明. 2 2222222(mod) (mod )  (mod) (mod )((1 ) mod )                       ((1 ) mod )((1 ) mod ) 1                       ((1 ) mod ) 1                       MxMxkMkMgn cngn cnkn nkn nkMkn nkMkn n    22modmod                        .kk Mn nkk Mn nMM 证毕. 3.3  有理数加密方案的可计算性 假定本文方案和Paillier 方案选用的模数相同，皆为2n ，并将模2n 意义下的一次自模乘运算的复杂度( O (2log n )) 定义为衡量本文方案和Paillier方案中算法复杂度的基本单位.  将2(1 ) mo , dkkg nn   1 kn ≤ 按照二项式展开计算可得 (1 )kkg n   2mod 1 nkn  ，因此，kg 可以由简单计算“1 kn  ”得到.  因为 1 kn ≤ ，所以1 kn  的计算复杂度为O (2log n ) ；从而可得： 中的加、解密算法的复杂度分别为 O (43log n +2log n ) 和O (23log n ).  而Paillier 方案中的加、解密算法的计算复杂度皆为O (23log n ).  显然，就本文方案与 Paillier 方案在加、解密算法的计算复杂性方面而言，二者属于同一级别.   3.4  有理数加密方案的性质 性质1.  盲化性.  假定有理数AAAMMM 在方案作用下对应的密文序偶为2()mo, (d AMxnA A cgr n  2)mod ) (A MnxA A cgr n ，则任意参与者可对其实施盲化运算： 22() ) mod)mod ,((AAM nA AMxnAcgr ng rn   22() ) mo. )m (dod(AAMnA AMxnAcgr ngr n  或 22()() ))mod, ()((modAAM nnA AMnAxcRg Rr ngR n    22()() ())mod)mod((,AAnM nA AMnxAcRg Rr ngR n    其中,, ,AA nR RR R Z  .  对于解密者而言，解密 (, ) A A cc、(2()mod A cn, 2()mod A cn) 以及(2()()modnA cR n , ()()nA cR  2mod n ) ，结果都是AAAMMM .  这是因为 222mod 1 ( 1) mod mod () xg nkg n n     1776  计  算  机  学  报 2020年   22(1)mod (1 )1( 1)mod,xkg ngng  22 2())mod mod ))m =o(d(= nn AA rnnr n   (  21,mod n 22 22()=( ( )mod mod ))m =1,odmodnn AA rnnr nn  ( 222222()()() ( )mod mod)mod(( ) ) mo (d() ) mod)m)od ,((AAAAM AM nA AM nAMnAxxxMnAxnAcgr n ngr ngr ngr ngr n     222222()()() ( )mod mod)mod(( ) ) mod() ) mod)m (d,()o(AAAAM AxM nA AM nAMnAnxxMnAxAcgr n ngr ngr ngr ngr n   因, AnR rZ ，则()A Rr可以表示成 )(AA Rr R    n   ( 因为, AnR rZ ，所以 ()A Rr不能被n 整除，从而可得 0 A R ) ，其中11n   ≤≤ .  从而有 22202   ))mod()mod()()mo((dmod () ,nAnAnnk kAnAkRr nRn nnRnn kRn  同理可得 22202   ))mod()mod()()mo((dmod () ,nAnAnnk kAnAkRr nRn nnRnn kRn  22 ()() ( )mod ( md )o () AxM nn n A A cR gr nR n      222()(())mod(( ) ) mod)mod (,AAM AMnAMnAxnxAg Rr ng RngR n  22 222() ()() ( )mod ()mod())mod(( ) ) mod)md(((.o)AAAM AM nn n A AMxxnAM nAxnAcR gr nR ngRr ngR ngR n   性质2.   密文对中的两个分量都各自保持了Paillier 加密方案的加法同态性.  假定有理数AAAMMM 与BBBMMM 在方案 作用下对应的密文对分别为2()mo, (d AMxnA A cgr n  2)mod ) (A MnxA A cgr n 与2()mo, (d BMxnB B cgr n  2)mod ) (B MnxB B cgr n .  令AB C rr r kn  ，由已知Z AB nrr ， ，可得A B rr  不能被n 整除且 0 Cr ，进而有 22220(()mod )mod)mod (())mo (( ) d .nnnn AB CnCnCCkrr n rrnkn nnrn  二项式展开定理 所以有 2222(] [)mod[)mod)mod)(]((mod.ABBABAMMnn AB ABMM nABMM nCxxxxcc g r n g r ngrr ngr n     同理，可得 2222(](] [)mod[)mo(d)(.mod)modABABABxxxMn Mn AB ABMM nABMM nCxcc g r n g r ngrr ngr n     所以，由加密方案 产生的密文对中的两个分量都各自保持了Paillier 加密方案的加法同态性.   性质1 与性质2 的应用场景：A 、B 两方各自拥有一个秘密, ab，他们想利用A 方的加密系统通过安全计算1212ra rrb r  或1212rb rra r (12,  rr为B 方在9 期  巩林明等：基于无匹配差错的PSI 计算 1777    协议执行过程随机选取的随机数) 实现安全计算, ab是否相等，而当 ab 时，不能泄露双方的大小关系.  设(, ) CC是对应于 1212 (, ) ra r rb r   或1212 (, ) rb r ra r   的密文对，由B 方利用 的性质1 及性质2 计算而来的.  因B 方利用性质1 将加密底数秘密地变换了，加之不知道B 方发来的密文对(, ) CC对应于1212 (, ) ra r rb r   或121 (,rb rra   2) r 中哪一个，即便拥有密钥，A 方利用解密密钥，除了可以计算出 , ab是否相等外，再也得不到其它任何额外的信息.  3.5  有理数加密系统的安全性 定理2. 如若DTCR 在多项式时间内无法被计算求解，则称  是一个抗IND-CPA 攻击的有理数加密方案.  证明. DTCR 挑战者按照 2.1节中非对称加密系统IND-CPA 安全性游戏执行的操作为： 1.  执行 Key-Generate 算法产生公钥 (,1 ) nkn ； 2. 均匀地选取 )( ) (0nkZ k  ，并计算： 21(1)mod xg kg n    . 3.  {0,1}Rd  ； 4. 如果 0 d  ，则置2(, ) ( mod ,nTTT r n   2mod )nrn，否则置 (, ) TR RR ； 5.  将22 (,1 ,( mod , mod ), )bb MM xx nnTg nTg nT  发送给攻击者.  设 (Key-Generation, Base -Transformation En-cryption, Decryption)为3.1节中构造的加密方案、为攻击 的概率多项式时间内的任意的敌手，并将 在,()cpaP ubK n游戏中获胜的优势函数记作 .  为了将DTCR 问题的难解性与优势函数 联系在一起，下面将在构造性证明框架下，以算法 为基元构建一个拟用于解决DTCR 问题的算法 .  算法 . 1. 作为敌手， 接收由DTCR 挑战者发送的参数(,1 ,(, ), ) nknnRT  ( 它并不知道(, ) nR 具体来自分布 R anD还是分布D) ； 2.     (, 1 )PubKngkn ； 3.     将P ubK 连同系统安全参数1n发给敌手 ； 4.     接收来自 的消息 bM ( 其中 ,bbbbMM MM 0101 {0,1} | | | | | | | | bMMMM   ，，； 5.  {0,1}Rb  ； 6. 22 (mod mod ,) bb MM xx cTg nTg n  并把c转发至敌手 ； 7. 接收 对于参数b 取值的猜测值 {0,1} b   ； 8. 根据 的输出结果，生成一个输出d  如果bb  ，则令 0 d   ；如果bb  ，则令 1 d   ）.   显然，按照上述方式利用算法 构造的算法在多项式时间内可被完成（因为算法 是多项式时间内可被完成的算法），因此算法 在多项式时间内解决DTCR 问题的概率可以用贝叶斯公式计算：     [][0][ 0]                                       [ 1] [ | 1].11[0|0] [1|1]2211[|0] [|1]|22Pr d dPr d Pr d d dPr d Pr d d dPr d d Pr d dPr b b d Pr b b d                (4) 0 d  时，据 DTCR 挑战者工作方式规定，DTCR 挑 战者将置22 (, ) ( mod , mod )nnTTT r nr n   .  此时， 因为在算法 执行过程中，由它向算法 提交的视图(view) 与 在实际安全游戏,cpaPubK中的视图是计算不可区分的，所以在 0 d  的前提下，bb  的条件概率为0.5 与敌手 在安全游戏,cpaPubK中获胜的优势之和，即  1[|0] .2Pr b b d     (5) 1 d  ，据 DTCR 挑战者工作方式规定，DTCR 挑战者将置 (, ) TR RR  .  在 2nZ上，参变量R 服从均匀分布，显然易得：2(mo,dbb M Mx xcRg nRg   2mod ) n 在 22 (, ) nn Z Z 上也是一个服从均匀分布的参变量，且独立于参变量 00 1 ,( , ),( , nM M M 1 ) M与b ，又因 n 、xg 、2modb MxRg n、b MxRg2mod n 和b也是两两相互独立于彼此的随机参变量，所以敌手 无法借助参数 P ubK 与构造变量c推演或计算出任何有关参变量b 取值的信息.  因此，我们可得出结论：事件b (  输送的对参变量b 的猜测值) 与事件b ( 由挑战者随机选择明文的下标) 必为两个相互独立的事件.  又因参变量b 的取值是 猜测的，所以猜测参变量取值 0 b  和 1 b  的概率均等，由此可计算条件概率：  1[|1].2Pr b b d    (6) 由算式(4)、(5)和(6)得  11 1111[] .22 2222Pr d d    (7) 1778  计  算  机  学  报 2020年   因此，算法 在解决DTCR 过程中的成功优势为： ,1[][][ ()1]2.                                                 2cpaPr b b Pr b b Pr PubK n      (8) 事实上，DTCR 问题在第2.4 节中已被证明是一个难解问题，这意味着算法 在解决DTCR 过程 中取得的成功优势是可忽略的，即2是一个可忽略 的量.  这蕴含着 也是一个可忽略量.  这说明敌手 在攻击 的游戏,cpaPubK中获胜的优势 是可忽略的.  因此，方案 具有 IND-CPA 安全性.  如果利用方案 将 00 0(, ) M MM 与1M   11 (, ) M M( 01 |||| M M 并且 01 |||| M M ) 分别为加密成 00 0(, ) ccc 和 11 1(, ) ccc ，那么 00 0(, ) ccc 和1c    11 (, ) cc是两个计算上不可区分的量，即00 (, )ccc   11 (, ) cc.  证毕. 4   无匹配差错的两方PSI 计算思想 为了实现交集元素保密求解差错为“0 ”的目的，同时也为了方便保密集合交集计算，我们在构造无匹配差错的两方PSI 计算协议采用了有理数加密方案 中构造保密比值的思想和一种称之为集合的定长向量编码方法.  4.1  用 构造两个集合对应元素的保密比值 将有理数加密方案 用于构造多方保密计算协议时，参与者可以根据需要，利用性质 1 和性质2改变一个密文的加密底数，这使得本来由参与各方自由选择的加密底数统一变为相同的加密底数，从而使得解密者只有同时拥有底数相同的密文对才可以正确求解出一个有理数.  不失一般性，在此将Alice和Bob 视作安全多方计算协议中的两个参与者.  假定整数1,AB mm n ≤≤分别属于Alice和Bob ，并且Alice拥有公钥加密方案的私钥，Bob 只知道该公钥方案的公钥，则结合上述性质2 ，Alice和Bob按照如下方式可以协同计算(+)x Amm与(+)x Bmm两个量的比值，而不会泄露自己的信息： (1) Alice 计算 Am 对应的密文 AmnA Acgr  2mod n ，计算完成后将其发送给Bob.  (2) Bob 得到Alice 的密文Ac 后，随机选择1 Bn rZ ，nkZ  ( 满足·( 1) kg n  ) ，然后计算： 2222       mod(1 ) mod(          ,1)modmodgxAAAkAAkmxmmcc nkn nkkn ngn  21(1 ( 1) ) modxnmxB ckgmrn    , 2modgxxAA m cc c n    .  (3)  随机选择12,BB n rr Z ，对于Bmn ，计算： 2(1 ( 1) ) modnBBxB ckgmrn m     . 并将(, ) A Bcc 发送给解密方.  (4)  收到(, ) A Bcc 后，Alice通过执行运算： 22(( ) mod )(mod ) BAcncn ， 就可以得到(+)x Amm与(+)x Bmm两个量的比值.  我们注意到：(1)用(+)x Amm与(+)x Bmm两个量的比值可以替代ABmm用于安全比较 Am 与Bm 的大小，并且当+1+ABxxmmmm ，则必有 A Bmm ；(2)若Am A  并且BmB ，则+1+ABxxmmmm 蕴含A Bmm 且Am 为集合A 与B 的公共元素.  4.2  集合的定长向量编码 1. 编码思想.  以全集E 为参照为其子集 iE 构造一个新的映象集合E  ，满足： (1)  ||| | EEm   ； (2)  如果全集中的元素ie 在子集iE 中，则 E  与E 的第i 个元素相同，否则E  中的其他元素映射为一个随机数.  例如：如果 123456 ,,,,, {} iEeeeeee  14 4 2 1 {,,,,,} im m m eeeeee  ，则iE 的定长向量编码如图3 所示.     图3   集合iE 参照全集E 的定长向量编码  2. 区分映射值域的集合定长向量编码.  假定保密集合交集计算协议中两个参与方分别持有保 密集合iE 与jE ，iE 与jE 由两个参与者采用定长向量编码方法编码后的集合分别为E  与E  ，并假定编码时集合编码映射的原象和象值都取自相同的集合{1, 2 , , } n  .  我们注意到：如果两个集合在编码9 期  巩林明等：基于无匹配差错的PSI 计算 1779    时，集合编码映射的原象和象值都取自集合{1, 2 , ,  }n ，则很可能会出现如下情形：()EEEEij即()ij E EEE .  这是因为：一方面，如果iE 与jE 都不具有全集E 中的某个元素，则采用定长向量编码由两个不同的人分别对它们进行编码时可能会映射为同一个 随机数，即两方所选择的随机数也会以21n的概率发 生碰撞.  另一方面，如果iE 与jE 只有一方具有全集E 中的某个元素，则采用定长向量编码由两个不同的人分别对它们进行编码时，选择随机数映射的一 方所选择的随机数会以1n的概率撞上另一方的某个元素.  为了避免在两方保密集合交集计算中产生上述碰撞，达到无匹配差错的保密集合交集计算目的，我们将 nZ 分成三段：3nZ   、5263()nn ZZ    23()nn ZZ     和2526 3()()n nn n ZZ ZZ       ，其中3nZ表示集合E 及其子集E i 中元素( 或者数据库中数据项) 的取值范围， 0 5263 2()(nn n AZ Z Z        3)nZ，1 232 65()()n nn n AZ Z ZZ         为编码时可供参与方选取随机数的集合，简称编码随机可选集合.  设1, ,{} m iiXEe   并且规定： （1 ）||3nE≤ 或3nm   ≤ ，其中为下取整函数； （2 ）3i neZ ； （3 ）1, ,{}i im e 中的元素互不相同.  以集合E 为参照，为集合1, ,{}i ik Xx( km )构造定长的向量编码12 (,,, )mx xx   x ： (1)  若集合的元素都为整数，则按照如下方式对集合1, ,{}i ik Xx编码 ( {0,1}),       ,                                          id i diiirA Ad e XxeeX    或； (2)  若集合的元素为有理数，则按照如下方式编码： ①将元素ie 表示成(, ) ii ee  使其满足：iiieee ，gcd( , ) 1 ii ee ； ②  按照如下方式对集合 1, ,{}i ik Xx ( k ≤ m )  构造定长的向量编码12 (,,, )mx xx   x ： , ({0,1}),             (( ) (gcd( , ) 1)) ( , ),                                        ii d diii ii iii irr A A dxrr rr eXee e X   或 4.3  无匹配差错的PSI计算思路 我们采用区分映射值域的集合定长向量编码方法和有理数加密方案 实现无匹配差错的 PSI 计算，其中区分映射值域的集合定长向量编码方法的主要作用是避免匹配过程中的数值碰撞问题，有理数加密方案 主要作用是无匹配差错的 PSI 计算. 实现无匹配差错的PSI 计算思路如下： (1) Alice 和Bob 分别先将各自的私有集合采用定长向量编码方法编码成 12 (,,, )mx xx   x 与12 (, , , )myy y   y ； (2)  双方采用有理数加密方案 ，并按照如下方式将 12 (, , , )mx xx   x 与12 (, , , )myy y   y 构造成密文对 (, ) ii iccc  ，其中(, ) ii cc是(ii x   , iy   i ) 或者(ii y   ,ii x   ) 对应的密文： ①Alice用自己的公钥为每个ix 计算： ()iEnc x   2modin xAig rn，并按序发送给Bob ； ②Bob 得到 ()iEnc x 后，随机选择 ,Bi Binrr Z ，i ,in kZ  ( 满足·( 1) kg n    ) ，然后通过计算： ()ii Enc x     2(1(1))( mo )),d (inii ikB E nc x k g r n  2((1(1)()(mo)d ))nii ii BiiEnc y k g y r n      随机选择(, ){( ( ( ), , ( )) ii ii ii c c Enc x Enc y Enc     ), (})) (ii ii yEncx     并按序发送给Alice.  ③Bob 执行解密运算 ()iD ec c ，如果 ()iDec c   1 ，则表示ii x y  ，即ie 为Alice和Bob 私有集合交集的元素，否则，ie 不是Alice和Bob 私有集合交集的元素.  5   无匹配差错的两方PSI 计算 5.1  集合交集的相关计算问题 我们研究两类情形下的保密集合交集计算问题( 不失一般性，本文假定Alice和Bob 是两方保密协议的参与方) ： 情形A ：Alice和Bob 分别拥有一个集合aS 和1780  计  算  机  学  报 2020年   bS ，他们想知道他们所持有的集合中有哪些元素是相同的，但不泄露其他任何信息，即Alice和Bob  在不泄漏aS 、bS 的前提下，协同计算： ab SS . 情形B ：Alice和Bob 分别拥有一个集合aS 和bS ，二人只想测试集合 aS 和bS 是否有交集，如果有交集则求交集的势，但不泄露其他任何信息，即Alice和Bob 在不泄漏aS 、bS 的前提下协同计算： ?,        | |ab ab SS SS   . 5.2  针对情形A 和情形B 的PSI协议 5.2.1   针对情形A 、面向整数元素的PSI 计算协议1  1. 具体协议 输入：Alice和Bob 各自的保密集合aS 和bS 、编码随机可选集合标识码{, } dd ( {0,1} d  ).  输出：ab SS .  (1) Alice 先运行方案 的密钥生成算法产生公私钥：公钥为(,1 ) nn ，私钥为 ；并按照集合的定长向量编码方法将自己的集合 aS 编码成m 长的向量12 (, , , )maa a   a ； (2) Alice 对向量 12 (, , , )maa a   a 各分量 ia  ( 1, 2, , im  )  做如下计算：  2). (1 modiiia naa cknrn   (9) 并将得到的密文向量1(,, )maa cc AC  连同自己的随机可选集的标识符 {0,1} d  发送给Bob ； (3) Bob 收到AC 与 {0,1} d  后按照如下方式工作： ①  利用集合的定长编码方法1 ，借助集合dA 将自己的集合 bS 编码成m 长的向量 12 (, , , bb   b  )mb ； ②  随机选择4 m 个不等的随机数12,,, bb kk  mbn kZ ，12,,,mbb b n rr r Z  ，12 ˆˆ ˆ,,,mbx bx bx nrr r Z  ， 12,,,mnbx bx bxrr r Z    ，利用有理数加密方案 加密性质计算： 2()22()           (10a) ,         (1(( ) mod )             (1 ( 1) ) mod(1 ( 1) ) m ) od 0bbibi i iii ibiiii ikra anbb bxnrb bbbxcc ngkrnr ncgkrnrn  得到m 个密文对； ③  将m 个密文对 ()() (,),1 bi bi ii ra rb cc im ≤≤ 分别做对内分量随机置换得到密文对序列：(,iLc  ),  1iRcim≤≤ ，并发给Alice.  (4) Alice  收到(, ), 1ii LR cc i m ≤≤ 后计算：  22modmodiiLiRcncn  (11) 记录 1i  的下标i ，并将它们发送给Bob.  2. 协议1 的正确性 因为集合11, ,{} aiik Sx与212 {, , , } bk Sxx x    对应的定长编码向量分别为 12 (, , , )maa a   a 和12 (, , , )mbb b   b ，其中         ,                  ,idia iiiarA eSeeS a  ,                        ,      ,   iib diiibrA eSeS be  ， 又因为01 AA  ，所以 12 {, , , ab SS aa   12 }{,,, } mm abbb   ，即如果ie 是集合aS 和bS 的公共元素，则集合aS 和bS 的定长编码向量对应的第i个元素都为ie .  下面从元素ie ，ia 与ib 三者的关系论证 12 12 {, , , } {, , , } ab m mSS aa a bb b  的正确性： (1)  当iaib eS eS   时，因为Alice  和Bob  编码时选用到的随机数i r和i r选自两个不同的编码随机可选集合，所以ii ab ，从而必有： 1iiab ,  1iiba ( ,nZ  ) ； (2)  当iaib eS eS     或者iaib eS eS  时，因为Alice和Bob 编码时选用的随机数i r、i r以及ie分别选自三个不同的编码随机可选集合，所以 ii ab ，从而必有： 1iiae ,  1iiea , 1iibe ,  1iieb ； (3)  因为当iaib eS eS  时元素ie ，ia 与ib 两两彼此相等，所以必有： 1iiiiaebe   .  显然 1iiab 必然有 ie 在交集 12 {, , , aa  12 }{,,, } mm abbb   中，并且协议中Bob 利用同态操作和Alice 的密文向量 AC 构造的密文对向量11 2 2 ()()( )( ) ( )( ) (( , ),( , ), ,( , ))bb b b bmbm mm ra rb r a r b r a r b cc c c c c      的下标与编码向量集合 1, ,{}i im a 和1, ,{}i im b 完全一致，因此，通过记录 9 期  巩林明等：基于无匹配差错的PSI 计算 1781    22mod1modiiLiRcncn   的下标i ，Alice和Bob 就能够精确地计算出两个集合11, ,{} aikiSx、212 {, , , } bk Sxx x     的交集aS   bS .  因为 1i 时，集合aS 对应的定长向量编码向量的第i 个分量和bS 对应的定长向量编码向量的第i 个分量相等，并且等于集合1, ,E{}im ie中第i 元素ie .  3. 协议1 的安全性 定理3. Alice和Bob 采用协议1 可以安全地实现保密计算ab SS ，其中aS 与bS 都是由整型元素组成的.  证明.  协议 1 能否实现保密计算 ab SS 的关键是协议执行后有没有造成Alice与Bob 私有信息的泄露.  下面将严格按照2.2 节中抗半诚实敌手攻击安全多方计算模型声明的安全标准和方法证明：在保密计算ab SS 的过程中，Alice与Bob 都不会得到除计算结果 ab SS 外任何有关对方的其他私有信息.  对于Bob 私有信息的安全性：如果在Alice受控于模拟器11 的情形下，多项式时间内的敌手11 获得的信息并不多于Alice 在实际执行协议中的视图内容，则称协议1 完成后Bob 私有信息依然是安全的.  构造一个控制Alice、能够在多项式时间内模拟协议 1 整个执行过程的模拟器11 ，11 的输入为：根据 Alice的私有输入1, ,{}aaikiSa和ab SS构造的利于攻击Bob 的集合 12 {, , , }aak Saa a   , Bob 随机选择的4 m 个不等的随机数12,,, bb kk  mbn kZ ，12,,,mbb b n rr r Z  ，12 ˆˆ ˆ ,,,mbx bx bxrr r    nZ， 12,,,mnbx bx bxrr r Z    ，以及Bob 的私有集合 bS   1, ,{}i ik b .  作为敌手，模拟器11 产生的视图为( {,i  21(1 ( 1) ) mod , )} ,(iiiiia naaLRim cgnrncc    ≤≤) ；而保密集合交集协议1 的实际执行中，Alice的实际视图为(21{, (1 ( 1) ) mod ( ) ,,} iiiii a naaLRim ic g n r n c c   ≤≤). 因为密文1(, )iiR Lim cc ≤≤是Bob 经过下述方式构造的： (1)  由密文( 1 im ≤≤ ) 利用方案 的性质1 和性质2 经运算(10a)与(10b)计算得到m 个密文对()() (,) bi bi ii ra rb cc 2(1 ( 1) ) modiiia naa cgnrn  ； (2)  对m 个密文对 ()() (,) bi bi ii ra rb cc分别做对内分量随机置换得到密文对序列1(, )ii BL im RCcc ≤≤.  对于1 im ≤≤ ，Alice  获得BC  后通过解密运算后最多只能得到由两个方程( 其中每个方程各包含3个不同的未知数) 组成的方程组，不可能通过联立方程组计算出具体的 ib .  同理对于1 i ≤≤m ，Alice获得(, )ii LR cc 也不可能通过联立方程组计算出具体的ib .  这也就是说11 满足安全定义关系式(1a).  对于Alice私有信息的安全性：假定控制Bob的敌手12 在Bob 不参与的情况下，能够在多项时间内模拟出协议 1 的执行过程.  如果在该假定条件下，多项式时间内的敌手12 获得的信息并不多于Bob  在实际执行协议中的视图内容，则Alice的私有信息是安全的.  首先构造一个控制Bob 且能在多项式时间内模拟执行协议1 的模拟器12 .  该模拟器的输入为：Alice 的私有集合1, ,{}aaikiSa、模拟器12 根据Bob 的私有集合1, ,{}bbikiSb和ab SS 构造的有利于获取Alice 私有信息的集合12 {, , , }bbk Sbb b   . 作为敌手，模拟器12 产生的视图为( (1 )iiaacn  2modinarn,2()(( ) mod ) (1 )bibi i ii ikra a bbccnkrn     2ˆmodinbxrn,ˇ2()(1 ) mo , dbi ii iinrb bbbxckrnrn  i ) ，其中1 im ≤≤ ；而Bob 在协议1 的实际执行中产生的视图为(2(1 ( 1) ) modiiia naa cgnrn   ,()(( )bibi i ikra a cc  22 mod ) (1 ) modii inbb ankrnrn  ,()(1bi ii irb bb ckr 2)modinbnr n, i ) ，其中 1 im ≤≤ .  无论在模拟协议还是实际协议中 Bob 接收到的皆为另一个参与者(Alice 或12 ) 私有信息在 作用下的密文，因为Bob 没有 的解密密钥，并且方案 已被证明在选择明文攻击下具有语义不可区分安全性，因此，对于Bob 或者控制着Bob 的敌手而言， (1 (iacg  21) ) modiia nanr n 与 (1iac  2(1)) mod iia nag nr n  是计算不可区分的，并且2()(( ) mod ) (1 )bibi i ii ikra a bbccnkrn     2ˆmodinbxrn 与2ˆ ()(( ) mod ) (1 )bibi i ii i iknra a bb bxccnkrnr    2mod n 也是计算不可区分的.  从而可得： 2 (iac  2(1 ( 1) ) modiia nag nr n , (1 ( 1) ) modiiia naa cgnr    2n ,22ˆ ()(( ) mod ) (1 ) modbibi i ii i iknra a bb bxcc nkrnrn    , 2()(1 ) modbi iiiinrb bbbxckrnrn , 1 im ≤≤ ) 与真实协议中视图 View1B(2(1 ( 1) ) modiiia naa cgnrn   , 22ˆ ()(( ) mod ) (1 ) modbibi i ii i iknra a bb bx cc nkrnrn  ,()(1 )bi ii irb bb ckrn  2modinbxrn, 1 im ≤≤ )  计算不可区分，即12 符合式(1b) 定义的安全条件.  综上可得：Alice和Bob 在协议执行中无信息泄1782  计  算  机  学  报 2020年   漏，即协议1 满足两方保密计算定义.  证毕. 5.2.2   针对情形B 的、面向整数的保密集合交集测试和交集势的计算协议2  1. 具体协议 输入：Alice和Bob 各自的保密集合aS 和bS 、编码随机可选集合标识码{, } dd ( {0,1} d  ).  输出：如果ab a SS，输出0 ；如果aS   ba S  ，输出||ab SS .  (1)  准备阶段：Alice先运行方案 的密钥生成算法产生公私钥：公布公钥(,1 ) nn ，保留私钥(,1 ) nn ；Alice和Bob 按照集合的定长向量编码方法，将各自的集合 aS 和bS 分别编码成m 长的向量12 (, , , )maa a   a 和12 (, , , )mbb b   b ； (2)  保密集合交集测试和交集势的计算： ①Alice 采用方案 对向量12 (, , , )maa a   a 的各分量ia ( 1, 2, , im  ) 进行加密得到向量a 对应的密文向量1, ,()iai mc AC ，并将它发送给Bob ； ②收到1, ,()iai mc AC 后, Bob 随机选择4 m 个不等的随机数12,,,mbb b n kk k Z  ，12,,,mbb b rr r   nZ，12 ˆˆ ˆ ,,,mbx bx bx nrr r Z  ，12,,,mnbx bx bxrr r Z    ，按照下式 2()2ˆ2()             (12a)     (( ) mod )            (1 ( 1) ) mod(1 (      (12b) 1) ) modbibi i iiii ibi ii ikra anbb bxnrb bbbxccngkrnr ncgkrnrn   计算出m 个密文对()() (,),1 bi bi ii ra rb cc im ≤≤ 后，先将这m 个密文对做对内分量间的随机置换，然后再对这m 个密文对做对间的随机置换，将随机置换后的密文对序列记作：11 2 2( , ), ( , ), , ( , )mm LR L R L R cc cc c c  ，并把它发给Alice.   ③ Alice 收到11 2 2( , ), ( , ), , ( , )mm LR L R L R cc cc c c   后计算： 221mod 1, 1, ( )0,        1.mod      其中iimLi Rcn yPPyy cn    (13) 然后将 发送给Bob.  2. 协议2 的正确性 因为集合11, ,{} aikiSx与212 {, , , } bk Sxx x      对应的定长编码向量分别为 12 (, , , )maa a   a 和12 (, , , )mbb b   b ，其中                       ,     ,idia iiiarA eSeSae  ,                       ,      ,   iib diiibrA eSeS be  ， 又因为 01 AA  ，所以 12 {, , , ab SS aa   12 }{,,, } mm abbb   ，即如果ie 为集合aS 和bS 的公共元素，则集合aS 和bS 的定长编码向量对应的第i个元素都为ie .  下面从元素ie ，ia 与ib 三者的关系论证12 12 {, , , } {, , , } ab m mSS aa a bb b  的正确性： (1)  当iaib eS eS   时，因为Alice和Bob 编码时选用到的随机数i r和i r选自两个不同的编码随机可选集合，所以ii ab ，从而必有： 1iiab ， 1iiba ( ,nZ  ) ； (2)  当iaib eS eS    或者iaib eS eS  时，因为Alice  和Bob  编码时选用到的随机数i r、i r以及ie 分别选自三个不同的编码随机可选集合，所以 ii ab ，从而必有： 1iiae ， 1iiea ，1iibe ， 1iieb ； (3)  因为当iaib eS eS  时元素ie ，ia 与ib 两 两彼此相等，所以必有 1iiiiaebe   .  如果 1iiab ，则ie 必在交集12 {, , , aa  12 }{,,, } mm abbb   中，其中i 用于指示集合 {1, 2, , } m  的一个随机置换集合的第i 个元素，因此通过统计结果为1 的个数： 221mod 1, 1, ( )0,  .       1 mod   其中iimLi Rcn yyyPPcn    (14) 能够精确地计算出集合 12 12 {, , , } {, , , maa a bb   }mb 的势，即||ab SS .  3. 协议2 的安全性 定理4. Alice和Bob 采用协议2 可以安全地实现保密计算||ab SS ，其中aS 与bS 都是由整型元素组成的.  证明. Alice 和Bob 能否利用2 安全地实现保密计算||ab SS 的关键是协议完成后有没有造成Alice与Bob 私有信息的泄露.  而Alice与Bob 私有信息有无泄露重点是协议完成后拥有私钥的Alice能否得到||ab SS 中的元素.  下面将严格按照2.2节中抗半诚实敌手攻击安全多方计算模型声明的安全标准和方法进行证明：在安全计算交集势的过程9 期  巩林明等：基于无匹配差错的PSI 计算 1783    中，Alice与Bob 都不会得到除协议输出||ab SS 外的、有关对方的其他任何私有信息.  对于Bob 私有信息的保密性：如果在完全控制Alice的情形下，多项式时间内的敌手21 获得的信息并不多于Alice 在实际执行协议中的视图内容，则称协议2 完成后Bob 私有信息依然是保密的.  构造一个控制Alice、能够在多项式时间内模拟协议 2 整个执行过程的模拟器21 ，21 的输入为：根据Alice 的私有输入1, ,{}aaikiSa和|aS   |bS 构造的利于攻击 Bob 的集合 12 {, , , aSaa   }aka  ,Bob 随机选择的4 m 个不等的随机数12,, bb kk  ,mbn kZ  ，12,,,mbb b n rr r Z  ，12 ˆˆ ˆ ,,,mbx bx bxrr r    nZ，12,,,mnbx bx bxrr r Z    ，以及Bob 的私有集合 1, ,{}bbikiSb.  作为敌手， 21 产生的视图为{2(1 ( 1) ) modiiia naa cgnrn  , 1, ,(, )ii LRi m cc  , i } ( 1 im ≤≤ ) ，其中1, ,(, )ii LRi m cc  是Bob 按照如下方式产生的： (1)  通过计算 2()2ˆ2()       (15a)  (( ) mod )            (1 ( 1) ) mod(1 ( 1) ) m   (15 d b) obibi i iii ibi iiiikra anbb bxnrb bbbxccngkrnr ncgkrnrn    得到m 个密文对()() (,), 1 bi bi ii ra rb cc im  ≤≤ ； (2)  先对这m 个密文对做对内分量间的随机置换，然后再对这m 个密文对做对间的随机置换，将随机置换后的密文对序列记作：11 2 2( , ), ( , ),LR L R cc cc    ,( , )mm LR cc  .  而在实际保密计算协议2 的执行中，Alice 的实际视图为(2(1 ( 1) ) modiiia naa cgnrn   , 1, ,(, )ii LRi m cc  , i ) ，其中 1 im ≤≤ .  因为密文(,iLc  1, ,)iRi m c 是Bob 经过下述方式构造的： ①由密文2(1 ( 1) ) modiiia naa cgnrn   ( 1 i ≤≤ m ) 利用方案 的性质1 和性质2 经运算(12a)与(12b)计算得到m 个密文对()() (,) bi bi ii ra rb cc； ②先对这m 个密文对做对内分量间的随机置换，然后再对这m 个密文对做对间的随机置换，将随机置换后的密文对序列记作：11 2(, ),(, LR L cc c 2), , ( , )mm RLR ccc .  对于 1 im ≤≤ ，即便模拟器21 通过控制Alice获得了解密密钥，在得到1, ,(, )ii LRi m cc  后，它通过解密运算后最多也只能得到由两个方程( 其中每个方程各包含3 个不同的未知数) 组成的方程组，不可能通过联立方程组计算出具体的 ib .  因为1, ,(, )ii LRi m cc  的下标是集合定长向量 12 (, , , aa   a  )ma 和12 (, , , )mbb b   b 中的下标构成集合的一个随 机置换，因此解密者无法再根据22(mod1(mo)d)iiLRcncn 的下标确定交集元素.  同理对于 1 im ≤≤ ，Alice获得(, ), 1ii LR cc i m ≤≤ 后，想通过联立方程组计 算出具体的ib ，根据22) (mod(mod)iiLRcncn的下标确定交集 元素也都是不可行的.  这也就说21 满足安全定义关系式(1a).  对于Alice私有信息的安全性：假定Bob 完全在敌手22 控制下，即使 Bob 不参与协议2 ，22也能够在多项时间内模拟出 2 的执行过程.  如果在该假设下，多项式时间内的敌手22 所得信息并不多于Bob 在实际执行 2 中的视图内容，则称Alice私有信息是安全的.  首先构造一个完全控制Bob 且能在多项式时间内模拟执行2 的模拟器22 .  该模拟器的输入为：Alice 的私有集合1, ,{}aaikiSa、模拟器22 根据Bob 的私有集合 1, ,{}bbikiSb和协议输出结果||ab SS 构造的有利于获取Alice 私有信息的集合12 {, , , }bbk Sbb b      .  作为敌手，22 产生的视图为(2(1 ) modiiia naa cnrn , 2()(( ) mod )bibi i ikra a ccn   2ˆ(1 ) modii inbb bxkrnr n  ,()(1 ) modbi iiiinrb bbbxckrnr   2n , i ) ，其中 1 im ≤≤ ；而 Bob 在协议2 的实际执行中产生的视图为( (1 ( 1) ) modiiia naa cgnr     2n ,2()(( ) mod ) (1 )bibi i ii i iknra a bb a ccnkrnr  2mod n , 2()(1 ) modbi ii i inrb bb b ckrnrn  , i ) ，其中1 im ≤≤ .  一方面，Bob 没有加密方案 的解密密钥，并且他从Alice 或者模拟器22 接收的经加密方案 作用后的密文信息；另一方面，方案 已被证明在选择明文攻击下具有语义不可区分安全性，即由加密方案 产生的密文是语义不可区分的.  因此对于Bob 或者控制着Bob 的敌手而言， (1 ( 1) )iiia naa cgnr   2mod n 与2(1 ( 1) ) modiiia naa cgnrn   是计算不可区分的；并且2()(( ) mod ) (1 )bibi i ii ikra a bb ccnkrn    2ˆmodinbxrn 与2()(( ) mod ) (1 )bibi i ii ikra a bb cc nkrn   2ˆmodinbxrn也是计算不可区分的.  从而可得结论：2 (2(1 ( 1) ) modiiia naa cgnrn  ,()(( )bibi i ikra a cc 2mod ) (1 )iibbnkrn   2ˆmodinbxrn,()(1bi ii irb bb ckr 2)modinbxnr n , i ) 与真实协议执行中视图View B (2(1 ( 1) ) modiiia naa cgnrn   , ()(( )bibi i ikra a cc  22ˆmod ) (1 ) modii inbb bxnkrnrn  ，()(1bi ii irb bb ckr   1784  计  算  机  学  报 2020年   2)modinbxnr n , i )  计算不可区分，即22 符合式(1b)定义的安全条件.  综上可得出：Alice和Bob 的私密性满足安全定义的形式化等式(1a) 与(1b).  所以协议 2 满足两方保密计算||ab SS 的定义.  证毕. 5.2.3   针对情形A 、面向有理数的保密集合交集计算协议3   1. 具体协议 输入：Alice和Bob 各自的保密集合aS 和bS 、编码随机可选集合标识码{, } dd ( {0,1} d  ).  输出：ab SS .  (1) Alice 先运行方案 的密钥生成算法产生公私钥：公钥为(,1 ) nkn ，私钥为 ；并按照集合的定长向量编码方法将自己的集合 aS 编码成m 长的有理向量12 (, , , )maa a   a ； (2)  将m 长的有理向量 12 (, , , )maa a   a   中的每个分量ia 表示成有序整数对(, )ii aa，其中i a与i a分别表示分子与分母； (3)  对于 1, 2, , im  和 11 2 2 (( , ), ( , ), , aa a a  (, )) mm aaAlice做如下计算： ˆ 22(1 ) mod(1 ) mo(16a)(16b d)iiiiiia naaanaacknrncknrn  . 并向Bob 发送 11 2 2 (( , ), ( , ), , ( , )) mm aa a a a a    ； (4) Bob 获得 11 2 2 (( , ), ( , ), , ( , )) mm aa a a a a    后，执行下述工作： ①  利用集合的定长编码方法1 ，将自己的集合bS 编码成m 长的有理向量12 (, , , )mbb b   b ； ②将m 长的有理向量 12 (, , , )mbb b   b 中的每个分量ib 表示成有序整数对(, )ii bb，其中 i a与i a分别表示分子与分母； ③  随机选择4 m 个不等的随机数12,,, bb kk  mbn kZ ，12,,,mbb b n rr r Z  ，12 ˆˆ ˆ ,,,mbx bx bx nrr r Z  ， 12,,,mnbx bx bxrr r Z    ，利用有理数加密方案 加密及其同态性通过计算： 2ˆˆ ()2ˆˆ2ˆ()2(( ) mod )(1 ( 1) ) mod(( ) mod )(1 (      (17a).      (17b )d ) 1) moibiiibiiii iibiii biiiiibkarbanbb bxbkrba anbbbxccngkrnr nccngkrnr n  得到m 个密文对； ④  将m 个密文对 ˆ()()(,) ii ibbiii rb r aba cc 做对内分 量随机置换得到密文对序列：11 2 2(( , ), ( , ),LR L R cc cc  ,( , ))mm LR cc  ，并发给Alice.  (5) Alice 收到11 2 2(( , ),( , ), , ( , ))mm LR L R L R cc cc c c 后计算： 22mod 1X1P,   P(X   )0     X 1 m    .odiiLiRcncn    其中  (18) 然后将 1i  的下标i 发送给Bob.  2. 协议3 的正确性 因为集合11, ,{} aiik Sx与212 {, , , } bk Sxx x     对应的定长编码向量分别为 11 2 2 (( , ), ( , ), , aa a a   a  (, )) mm aa和 11 2 2 (( , ), ( , ), ,( , )) mm bb b b b b     b ，其中 ,  (( ) (gcd( , ) 1)),(, )( , ),                                                       ii i i ii diiiiiiaa A a a aaeXaaeeeX       , ,  (( ) (gcd( , ) 1)),  (, )( , ),                                                     ii i i ii diiiiiibb A b b bbeXbbeeeX       ，{0,1} d  ，又因为d dAA  ，所以如果(, ) ii ee  11 2 2 11 2 2 {(,),(, ),,( , )}{(,),(,),, mm aa a a a a bb bb       (, )} mm bb则必有 () iab eSS   ，即如果 (ia eS   )bS   则集合aS 和bS 的定长编码向量对应的第i 个元组都为ie .  下面从元素 ,( , ),( , ) ii ii ieaa bb 三者的关系论证用 11 2 2 11 2 {( , ), ( , ), , ( , )} {( , ), ( , mm aa a a a a bb b      2 ), , ( , )} mm bbb 计算ab SS 的正确性： 关系1. 当iaib eS eS   时，因为Alice  和Bob编码时，元组(, )ii aa和(, )ii bb的分量分别取自两个不同的编码随机可选集合{, } d dA A  ( {0,1} d  ) ， 所以ii rr  ，从而必有： 1iiiiabab、 1iiiiabab ( ,nZ  ) ； 关系2. 当iaib eS eS    或者iaib eS eS 9 期  巩林明等：基于无匹配差错的PSI 计算 1785    时，因为ie ， ,ii aa与 ,ii bb分别取自三个不同的域，所以必有ii ea ，ii eb ，ii ea ，ii eb .   从而 必有 1iiiiaeae， 1iiiiaeae， 1iiiibebe，1iiiiaeae； 关系3.   当iaib eS eS 时，因为 ii ea  ，ii eb ，ii ea ，ii eb ，所以有iiiiabab   1iiiiabab.  综上所述，协议3 利用集合的定长向量编码方法，通过计算 11 2 211 2 2{( , ), ( , ), , ( , )}{( , ), ( , ), , ( , )}mmmmaa a a a abb b b b b        能够精确地计算出集合11,{} aiik Sx与1{, bSx   22,, }kx x  的交集ab SS .  从而在协议3 中，如果  22(mod)1 .(mod)iiLiRcncn  (19) 时，则集合1,E{}i im e中对应的第i 元素ie 必为交集ab SS 的元素.  3. 协议3 的安全性 定理5. Alice和Bob 利用协议3 可以安全地实现保密计算ab SS ，其中aS 与bS 中的元素都是有理数.  证明.  关于3 的安全性需要考量如下两种情况： (1) Alice 完全受控于敌手时Bob 私有信息的安全性，如果多项式时间内的敌手31 在完全控制Alice情形下，它在代替Alice模拟执行协议3 过程中所能获取的信息并不多于Alice 在实际执行协议中的视图内容，则称协议3 能够保证Bob 私有信息的安全性； (2) Bob 完全受控于敌手时Alice私有信息的安全性，如果多项式时间内的敌手31 在完全控制Bob 情形下，它在代替 Bob 模拟执行协议3 过程中所能获取的信息并不多于Bob 在实际执行协议中的视图内容，则称协议3 能够保证Alice私有信息的安全性.  构造模拟Alice视图的模拟器31 ：假设31 能够在多项式时间内模拟协议3 的执行过程，并令它的输入为：根据Alice的私有输入aS   1,{}aik ia 和ab SS 构造的利于攻击Bob 的集合12 {, , , aSaa   }aka  、Bob 选择的4 m 个随机数1,bk  2,,mbbn kkZ  ， 12,,,mbb b n rr r Z  ，12ˆˆ,,, bx bxrr  ˆmbx nrZ ，12,,bx bxrr ,mnbxrZ  ，以及Bob 的私有集合1,{}bi ik bSb. 作为敌手， 31 模拟产生的视图为( {( ,i ac   1,2, ,)}iim ac , 1,2, ,{( , )}ii LRi m cc  , i ) ；而协议3 的实 际执行中，Alice 的实际视图为( {( ,i ac 1,2, ,)}iim ac  , 1,2, ,{( , )}ii LRi m cc  , i ).  因为密文 1,(, )ii LRi m cc   ( 1 im ≤≤ )  是Bob 经过下述方式构造的： (1)  由密文对(, )ii aacc  ( 其中ˆˆ(1 )iiia naacknr     2mod , n  2(1 ) modiiianaa cknrn ) 利用方案 的性质1 和性质2 经运算:  ˆ ()22 ˆ ˆˆ()ˆ22(( ) mod ) (1 ( 1) ) mod(( ) mod ) (1 ( 1) ) modibiiibiiiii ibiiibiiiiirbabk nabbbx rbabknbbabxccngkrnrnccngkrnrn  . 计算得到m 个密文对()() (,) bi bi ii ra rb cc   ； (2)  对m 个密文对1,(, )ii LRi m cc  分别做对内分量随机置换得到密文对序列 1,2, ,{( , )}ii LRi m cc  .  对于1 im ≤≤ ，Alice  获得1,(, )ii LRi m cc  后通过解密运算后最多只能得到由两个方程( 其中每个方程各包含3 个不同的未知数) 组成的方程组，不可能通过联立方程组计算出具体的(, )ii bb.  同理在实际协议3 中，对于 1, 2, , im  ，Alice 获得(, )ii LR cc 后也 不可能通过联立方程组计算出具体的(, )ii bb.  这也 就说敌手在模拟协议和Alice 在实际协议中一样无法通过额外的计算推算出比协议 3 的实际输出ab SS 更多的信息.  因此，模拟器31 满足定义关系式(1a).  构造模拟Bob 视图的模拟器32 ：假定敌手32   完全控制着Bob 且能在多项式时间内模拟执行协议3 .  其中该模拟器的输入为：Alice  的私有集合i1 ,{}ai ak Sa ,、模拟器32 根据Bob 的私有集合1, ,{}abikiSb和ab SS 构造的有利于获取Alice 1786  计  算  机  学  报 2020年   私有信息的集合12 {, , , }bbk Sbb b   .  作为敌手，模拟器32 产生的视图为 (1,2, ,{( , )}iiim aacc  ,1,2, ,{( , )}ii LRi m cc  , i ) ， 对于 1, 2, , im  ，(, )ii aacc 是Alice在模拟协议中用 自己的公钥对有理数ia 对应的整型表示元组的重新加密： ˆ 2ˆ2(1 ) mod(1 ) modiiiiiia naaanaacknrncknrn    . 生成的.  而Bob 在实际执行协议3 的过程中产生的视图为 (1,2, ,{( , )}iiim aacc  ,1,2, ,{( , )}ii LRi m cc  , i ) ， 对于 1, 2, , im  ，(, )ii aacc是Alice在实际协议3  中用自己公钥对自己集合元素 对应的整型表示元组的加密： ˆ 2ˆ2(1 ) mod(1 ) modiiiiiia naaanaacknrncknrn . 无论在模拟协议还是实际协议中 Bob 接收到的信息都是另一个参与者(Alice 或32 ) 私有信息在作用下的密文，一方面因为 Bob 没有 的解密密钥；另一方面又因方案 已被证明在选择明文攻击下具有语义不可区分安全，即由加密方案 产生的密文 是语义不可区分的，也就说(, )ii aacc 与(, )ii aacc是计算不可区分的并且1,(, )ii LRi m cc  与1, ,(, )ii LRi m cc  也 是计算不可区分的.  从而可得：模拟视图( {( ,i ac   1,2, ,)}iim ac ,1,2, ,{( , )}ii LRi m cc  , i ) 与真实视图( {( ,i ac  1,2, ,)}iim ac  ,1,2, ,{( , )}ii LRi m cc  , i ) 是计算不可区分的.  因此模拟器32 满足安全定义关系式(1b).  综上得出：Alice和Bob 在协议执行中无信息泄漏，即协议 3 满足两方保密计算定义条件(1a) 与(1b).  所以任意两方都可以利用协议3 安全地实现两方集合交集的保密计算.  证毕. 5.2.4   针对问题B 、面向有理数的PSI 测试和交集势的计算协议4  1. 具体协议 输入：Alice和Bob 各自的保密集合aS 和bS 、编码随机可选集合标识码{, } dd ( {0,1} d  ).  输出：如果aS 与bS 无公共元素，输出0 ；如果aS 与bS 有公共元素，输出||ab SS .  (1)  准备阶段. Alice 和Bob 按照如下方式进行准备工作： ① Alice 先运行方案 的密钥生成算法产生公私钥：公布公钥(,1 ) nn ，保留私钥 ； ②Alice和Bob 按照集合的定长向量编码方法，将各自的集合 aS 和bS 分别编码成m 长的有理向量12 (, , , )maa a   a 和12 (, , , )mbb b   b ； ③ Alice 和Bob 分别将各自的有理向量  a  12 (,,, )maa a  和12 (, , , )mbb b   b 表示成分量为整型 有序对的向量 11 2 2 (( , ), ( , ), , ( , )) mm aa a a a a    和 1 (( ,b 122 ), ( , ), , ( , )) mm bbb bb   Alice 先运行方案 的密钥生成算法产生公私钥：公布公钥(,1 ) nn ，保留私钥 ；Alice和Bob按照集合的定长向量编码方法，将各自的集合aS 和bS 分别编码成m 长的有理向量 1(,a  a  2,, )maa和12 (, , , )mbb b   b ； (2)  保密集合交集测试和交集势的计算： ① Alice 采用方案 对向量 11 2 (( , ), ( , aa a  a  2 ), ,( , )) mm aaa 的各分量(, )ii aa ( 1, 2, , im  ) 进 行加密得到向量a 对应的密文向量11 2(( , ), ( ,aa acc c   2), , ( , )mm aaa ccc   ，并将它发送给Bob ； ②  收到11 2 2(( , ), ( , ), , ( , )mm aa a a a acc cc c c      后, Bob 随机选择4 m 个不等的随机数12,,,mbb b n kk k Z  ， 12,,,mbb b n rr r Z  ，12 ˆˆ ˆ ,,,mbx bx bx nrr r Z  ，12,,,bx bxrr mnbxrZ ，按照式(17a)、(17b)计算出m 个密文对()()(, )(1 )bii bii ii rba rbacc im  ≤≤ 后，先将这m 个密文对做对内分量间的随机置换，然后再对这m 个密文对做对间的随机置换，将随机置换后的密文对序列记作：11 2 2( , ), ( , ), , ( , )mm LR L R L R cc cc c c  ，并把它发给Alice.  ③ Alice 收到11 2 2( , ), ( , ), , ( , )mm LR L R L R cc cc c c  后计算： 122() 1,    1, ( )0, 1 () mod  mod   iimLi Rnnc yPPyy c     其中(20) 并将 发送给Bob.  2. 协议4 的正确性 因为集合11, ,{} aikiSx与212 {, , , } bk Sxx x      9 期  巩林明等：基于无匹配差错的PSI 计算 1787    对应的定长编码向量分别为 11 2 2 (( , ),( , ), , aa a a   a  (, )) mm aa和 11 2 2 (( , ), ( , ), ,( , )) mm bb b b b b    b  ，其中 , (()(gcd(,)1)), (, )( , ),                                                        ii i i ii diiiiiiaa A a a aaeXaaeeeX       , , (()(gcd(,)1)), (, )( , ),                                                      ii i i ii diiiiiibb A b b bbeXbbeeeX       ， {0,1} d  ，又因为d dAA，所以如果(, ) ii ee  11 2 2 11 2 2 {(,),(, ),,( , )}{(,),(,),, mm aa a a a a bb bb       (, )} mm bb则ie 必为aS 和bS 的公共元素，即如果ie 为aS 和bS 的公共元素，则集合aS 和bS 的定长编码向量对应的第i 个元组都为 ie .  下面从元素 (, ,iiea ), ( , ) iii abb三者的关系论证 11 2 211 2 2|{( , ), ( , ), , ( , )}{( , ), ( , ), , ( , )} | | |mmmm abaa a a a abb b b b b S S       的正确性： 关系4. 当iaib eS eS  时，因为Alice和Bob编码时，元组(, )ii aa和(, )ii bb的分量分别取自两个不同的编码随机可选集合{, } d dA A  ( {0,1} d  ) ，所 以ii rr  ，从而必有 1iiiiabab， 1iiiiabab ( ,nZ  ) ； 关系5. 当iaib eS eS   或者iaib eS eS 时，因为ie ， ,ii aa与 ,ii bb分别取自三个不同的域，所以必有ii ea ，ii eb ，ii ea ，ii eb .  从而必 有 1iiiiaeae， 1iiiiaeae， 1iiiibebe，1iiiiaeae； 关系6. 当iaib eS eS 时，因为 ii ea  ， ii eb ， ii ea ， ii eb 所以有iiiiabab   1iiiiabab.  综上所述，如果 1iiiiabab或iiiiabab   1 ，即22mod1modiiLRcncn ，则ii ii iiiab ea bab  必在交集12 12 {, , , } {, , , } mm aa a bb b  中，其中i 用于指示集合{1, 2 , , } m  的一个随机置换集合的第i 个元素，因此通过统计计算结果为1 的个数： 221 mod    mod1,    1, ( ) .0    ,1  iimLi Rnnc yPPyy c      其中  能够精确地计算出集合 11 2 2 {( , ), ( , ), , ( , m aa a a a    11 2 2 )} {( , ), ( , ), , ( , )} mmm abbbbbb    的势，即|aS   |bS .  3. 协议4 的安全性 定理6 . Alice 和Bob 利用协议4 可以安全地实现保密计算||ab SS ，其中aS 和bS 中的元素都是有理数.  证明.  协议 4 和2 在安全性证明方面与保密计算||ab SS 的机理完全一样，只是集合构成元素的数据类型不同( 前者针对集合元素是有理数的集合，后者针对集合元素是整数的集合) ，因此该定理的证明与定理3 的证明完全一样.  为了节省篇幅在此不再赘述.  证毕. 6    性能分析 计算复杂度方面( 为了公平地比较，在此只对模数都采用2n 的协议进行比较分析) ，协议1 、2 、3 、4 和基于多项式验根法构造的协议[9,10]属于同一级别：在协议1 和2 中，Alice和Bob  都需要运行2 m 次加密、m 次解密、m 次同态运算；在协议3 和4 中，Alice和Bob  都需要运行2 m 次加密、m 次解密、2 m 次同态运算；而 2016  年，Freedman等基于Paillier  加密方案设计的保密集合交协议，该协议运行一次总计需要执行ab kk 次加 密、bk 次解密、1akBbik    次同态运算.  如果把衡量算 法复杂度的基础单位定义成两个量的一次自模乘运算(222 ( mod mod ) mod nny x n  ，, x  2yn ) 所消耗的1788  计  算  机  学  报 2020年   计算资源，记作(O(2log n )) ，则协议1 的计算总计需要花费2 ml m l ml  次自模乘运算；而基于多项式验根法构造的协议[1,8]总计需要()ab b kkl kl   1()akBbikl 次自模乘运算.  因为3nm  ，1,ak ≤  bk ≤ n ，所以上述 5 个协议的计算复杂度都属于O(2lg nn) 级别的.  在集合交集计算差错方面，协议1 、2 、3 、4 对于集合交集元素的计算差错为零，而基于多项式验根法构造的协议[1,8]、基于多项式间提取公因式法构造的协议[5,33]、采用数字签名技术构造带元素认证的协议[6]对于集合交元素的计算存在差错并且无法界定差错大小.  在保护隐私的范畴方面，协议1 、2 、3 、4 不仅保护了协议参与双方集合中的数据元素还保护了参与双方私有集合的势，而协议[1,5,8] 中作为服务器一方私有集合的势是公开的信息；基于不经意伪随机函数计算的保密集合交集计算协议[7]虽然不会泄露双方集合中的私密数据，但会泄露拥有PRF 密钥prf 一方集合的势.    表1 是协议1 、2 、3 、4 与协议[1,8] 在协议计算复杂度( 用自模乘运算最大次数作为比较标准) 、集合交集计算是否存在差错以及作为服务器一方私有集合的势是否保密三个方面的比较.  表2 是协议1 、2 、3 、4 与协议[1,5,33] 表1    模数都采用2n 的保密计算协议间的对比分析 类型  计算复杂度 交集( 或交集势) 的计算是否无差错 服务器一方集合的势是否保密 协议[9,10]  O(2lg nn)      协议 1  O(2lg nn) √   √  协议 2  O(2lg nn) √   √  协议 3  O(2lg nn) √   √  协议 4  O(2lg nn) √   √  其中，√ 表示具有某种性能， 表示不具有某种性能 表2    模数不等的保密计算协议间的对比分析 类型 交集( 势) 的计算是否无差错 隐私保护范畴 协议[1,5,33]    √  协议1  √   √  协议2  √   √  协议3  √   √  协议4  √   √  其中，√ 表示具有某种性能， 表示只保护保护双方私有集合元素，不能保护双方私有集合的势 在保密集合交集( 势) 计算是否存在差错方面以及隐私保护范畴方面，除了保护双方私有集合元素外，还保护双方私有集合的势两个方面的比较. 7   结束语 本文首先提出了一个面向有理数的加密方案，并在标准模型下证明了它具有语义安全性.  然后利用该方案和集合的定长向量编码技术设计了两个保密集合交集计算协议和两个保密集合交集势计算协议，协议1 和3 对于相交元素的保密计算不存在差错；协议2 和4 对于相交元素个数的保密计算不存在差错；此外，协议1 、2 、3 、4 在保护隐私的范畴方面，不仅保护了双方的私有集合元素，还保护了双方私有集合的势.  这丰富了保密集合交集计算的研究方法，同时实现无匹配差错且保密范畴更广的( 既不会泄露双方集合中的私密数据，也不会泄露双方私密数据的数量) 保密集合交集计算.  参  考  文  献 [1]  Freedman M J, Nissim K, Pinkas B. Efficient private matching and set intersection//Proceedings of  the International Conference on the Theory and Applications  of Cryptographic Techniques. Interlaken, Switzerland, 2004: 1-19 [2]  Aggarwal C C, Philip S Y. A general survey of privacy- preserving data mining models and algorithms. Privacy- preserving data mining. Berlin Germany: Springer, 2008: 11-52 [3]  Vatsalan D, Sehili Z, Christen P, et al. Privacy-preserving record linkage for big data: Current appr oaches and research challenges. Handbook of Big Data Technologies. Berlin Germany: Springer, 2017: 851-895 [4]  Egert R, Fischlin M, Gens D, et al. Privately computing set-union and set-intersection cardinality via bloom filters//Proceedings of the Australasian Conference on Information Security and Privacy. Brisbane, Australia, 2015: 413-430. [5]  Kissner L, Song D. Privacy-preserving set operations//Procee-dings of the annual international cryptology conference. Santa Barbara, USA, 2005: 241-257 [6]  De Cristofaro E, Tsudik G. Practical private set intersection protocols with linear complex ity//Proceedings of the Interna-tional Conference on Financial Cryp tography and Data Security. Springer, Tenerife, Canary  Islands, Spain, 2010: 143-159 [7]  Michael J. Freedman, Yuval Ishai, Benny Pinkas, and Omer Reingold. Keyword search and oblivious pseudorandom func-tions//Proceedings of the Theory of Cryptography Conference. Cambridge, USA, 2005: 303-324   [8]  Freedman M J, Hazay C, Nissim K, et al. Efficient set inter-section with simulation-based security. Journal of Cryptology, 2016, 29(1): 115-155 [9]  Hazay C, Mikkelsen G L, Rabin T, et al. Efficient RSA Key Generation and Threshold Paillier in the Two-Party Setting. Journal of Cryptology, 2019, 32(2): 265-323 9 期  巩林明等：基于无匹配差错的PSI 计算 1789    [10]   Dong C, Chen L, Camenisch J, et  al. Fair private set intersection with a semi-trusted arbiter//Proceedings of the IFIP Annual Conference on Data and Applications Security and Privacy. Newark, USA, 2013: 128-144 [11]   Bradley T, Faber S, Tsudik G. Bounded size-hiding private set intersection//Proceedings of  the International Conference on Security and Cryptography for Networks.  Amalfi, Italy, 2016: 449-467. [12]   Dachman-Soled D, Malkin T, Raykova M, et al. Efficient robust private set intersection. Interna tional Journal of Applied Crypto-graphy, 2012, 2(4): 289-303 [13]   Hazay C, Nissim K. Efficient set operations in the presence of malicious adversaries. Journal of Cryptology, 2012, 25(3): 383-433 [14]   Carmit Hazay and Yehuda Lindell.  Efficient oblivious polyno-mial evaluation with simulation-based security. IACR Crypto-logy ePrint Archive, 2009:459,  2009. https://eprint. iacr.org/ 2009/459.pdf [15]   Carmit Hazay and Yehuda Lindell. Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries.   Journal of Cryptology, 2010, 23(3): 422-456 [16]   Kolesnikov V, Kumaresan R, Rosulek M, et al. Efficient batched oblivious PRF with applications  to private set intersection// Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security.   Vienna, Austria, 2016: 818-829 [17]   Kerschbaum F. Outsourced private set intersection using homo-morphic encryption//Proceedings of the 7th ACM Symposium on Information, Computer and Co mmunications Security. Seoul Korea, 2012: 85-86 [18]   Abadi A, Terzis S, Dong C. VD-P SI: Verifiable delegated private set intersection on outsourced priv ate datasets//Proceedings of the International Conference on Fi nancial Cryptography and Data Security. Christ Church, Barbados, 2016: 149-168 [19]   Kim M, Lee H T, Cheon J H. Mutual private set intersection with linear complexity//Proceedings of  the International Workshop on Information Security Applications. Jeju Island, Korea, 2011: 219-231 [20]   De Cristofaro E, Kim J, Tsudik G. Linear-complexity private set intersection protocols secure in malicious model//Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security. Singapore, 2010: 213-231 [21]   Hemenway Falk B, Noble D, Ostrovsky R. Private set intersection with linear communication from general assum-ptions//Proceedings of the 18t h ACM Workshop on Privacy in the Electronic Society. London, UK, 2019: 14-25 [22]   Rindal P, Rosulek M. Improved private set intersection against malicious adversaries//Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques. Paris, France, 2017: 235-259 [23]   Kolesnikov V, Matania N, Pinkas B, et al. Practical multi-party private set intersection from symmetric-key techniques//Pro-ceedings of the ACM Conference on Computer and Comm-unications Security. London, UK, 2017: 1257-1272 [24]   Kolesnikov V, Rosulek M, Trieu N, et al. Scalable private set union from symmetric-key techniques//Proceedings of the In-ternational Conference on the Theory and Application of Crypto-logy and Information Security.  Brisbane, Australia, 2019: 636- 666 [25]   Pinkas B, Schneider T, Segev G, et al. Phasing: Private set intersection using permutation-ba sed hashing//Proceedings of the 24th Conference on USENIX Security Symposium. Washington, USA, 2015: 515-530 [26]   Pinkas B, Schneider T, Tkachenko O, et al. Efficient circuit- based psi with linear communication//Proceedings of the Annual International Conference on the  Theory and Applications of Cryptographic Techniques. Zagreb, Croatia, 2019: 122-153 [27]   Pinkas B, Schneider T, Zohner M. Faster private set intersection based on OT extension//Proceedings of the 23th Conference on USENIX Security Symposium. San Diego, USA, 2014: 797-812 [28]   Pinkas B, Schneider T, Zohner M. Scalable private set inter-section based on OT extension. ACM Transactions on Privacy and Security (TOPS), 2018, 21(2): 7 [29]   Orrù M, Orsini E, Scholl P. Actively secure 1-out-of-N OT extension with application to  private set intersection//Procee-dings of the Cryptographers’ Track at the RSA Conference. San Francisco, USA, 2017: 381-396 [30]   Pinkas, Benny & Rosulek, Mike &  Trieu, Ni & Yanai, Avishay. SpOT-Light: Lightweight private set intersection from sparse OT//Proceedings of the CRYPTO 2019 - 39th Annual Interna-tional Cryptology Conference, Santa Barbara, USA, 2019: 401- 431 [31]   Ghosh S, Nilges T. An algebraic approach to maliciously secure private set intersection//Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques. Zagreb, Croatia, 2019: 154-185 [32]   D. Many, M. Burkhart, and X. Dimitropoulos. Fast private set operations with sepia. Zurich, Switzerland: Communication Systems Group TIK-Report No. 345, Mar 2012 [33]   Zhou Su-Fang, Li Shun-Dong, Guo Yi-Min, Dou Jia-Wei, Chen Zhen-Hua. Efficient secure set intersection problem computation. Chinese Journal of Computers, 2018, 41(2): 464-480(in Chinese) ( 周素芳,  李顺东,  郭奕旻,  窦家维, 王道顺.  保密集合相交问题的高效计算.  计算机学报, 2018, 41(2): 464-480) [34]   Boneh D, Gentry C, Halevi S, et al. Private database queries using somewhat homomorphic encryption//Proceedings of the International Conference on App lied Cryptography and Network Security. Banff, Canada, 2013: 102-118 [35]   Carmit Hazay and Yehuda Lindell. Efficient Secure Two-Party Protocols-Techniques and Constructions. Berlin, Germany: Springer-Verlag, 2010 [36]   Changyu Dong, Liqun Chen, and Zikai Wen. When private set intersection meets big data: An efcient and scalable protocol// Proceedings of the 2013 ACM SI GSAC conference on computer & communications security. Berlin, Germany, 2013: 789-800 [37]   De Cristofaro E, Gasti P, Tsudik G. Fast and private computation of cardinality of set intersection and union//Proceedings of the International Conference on Cryptology and Network Security. Darmstadt, Germany, 2012: 218-231 [38]   Ateniese G, De Cristofaro E, Tsudik G. (If) size matters: size-hiding private set intersection//Proceedings of the Interna-1790  计  算  机  学  报 2020年   tional Workshop on Public Key Cryptography. Taormina, Italy, 2011: 156-173 [39]   Kiss Á, Liu J, Schneider T, et al. Private set intersection for unequal set sizes with mobile applications//Proceedings of the Privacy Enhancing Technologies. Minneapolis, USA, 2017: 177-197 [40]   Katz J, Lindell Y. Introduction to modern cryptography. Second Edition. Boca Raton: CRC Press, 2014 [41]   Gong Lin-Ming, Li Shun-Dong, D ou Jia-Wei, Guo Yi-Min, Wang Dao-shun. Homomorphic encryption scheme and a protocol on secure computing a line by two private point. Journal of Software, 2017, 28(12) :3274-3292(in Chinese) ( 巩林明,  李顺东,  窦家维,  郭奕旻,  王道顺.  同态加密方案及安全两点直线计算协议.  软件学报, 2017, 28(12) :3274-3292) [42]   Goldreich O. Foundations of cryptography: volume 2, basic applications. Cambridge, UK: Cambridge University press, 2009 [43]   Cramer R, Damgaård I B. Secure multiparty computation. Cambridge, UK: Cambridge University Press, 2015 [44]   Paillier P. Public-key cryptosystems based on composite degree residuosity classes//Proceedings of the International Conference on the Theory and Applications  of Cryptographic Techniques. Prague, Czech Republic, 1999: 223-238 GONG Lin-Ming, Ph.D., lecturer. His current research interests include information security and cryptography.     WANG Dao-Shun, Ph.D., asso-ciate professor. His current research interests include multi-media security and forensics, cryptographic algorithms and video intelligent behavior analysis.  LIU Mo-Meng, Ph.D., lecturer. Her research interests include information security and cryptography. GAO Quan-Li, Ph.D., lecturer. His current research interests include network  and information security. SHAO Lian-He , Ph.D., associate professor. His research interests include information security and quantum intelligence information calculation . WA N G M i n g - M i n g, Ph.D., associate professor. His research interests include information security and crypto-graphy. Background In distributed secure multi-party computation setting, private set intersection is an impor tant tool for protecting users’ privacy in data matching, data mining, recommendation, and so on. Up to now, the existing protocols for evaluating private set intersection can be divided into  four categories according to the construction methods (polynomial root testing, common factor extracting between functions, ob livious function calculating, and set elements authenticating via digital signature): (1) protocols constructed by polynom ial root-checking method, (2) protocols constructed by “extracting Common Factor between multiple functions”, (3) protocols constructed with the idea of “inadvertent pseudorandom function calculation”, and (4) protocols constructed with the id ea of “authentication of set elements with digital signature technology”. From the view of computable point, PSI protocol s constructed using “polynomial root testing”, “common factor extracting among multiple functions”, “set elements authenticating via digital signature technology” and “inadvertent pseudorandom function (pseudo-andom function, PRF) calculating”, such as protocols[1,5-7] have opened up four methods to  solve the problem of PSI in distributed environment. However, for the PSI protocols designed by the first three methods (“polynomial root testing”, “common factor extracting among multiple functions”, “set elements authenticating via digital signature technology”), there may be errors in the calculation results after the execution, and the scope of the errors is difficult to define. The PSI protocol based on oblivious pseudorandom function calculation will not disclose the private data in the two sets, but they will reveal the size of the set of the participant that has PRF keys. In this paper, we aim to solve the problem that constructs precisely private set intersection protocols using an encryption scheme with rational numbers  and set encoding with a fixed-length vector. Assu me that both parties P1 and  P2 have sets  S1 and S2, respectively. After executing the protocol for confidential calculation of 12 SS , they want to implement as follows. (1) The result of the collaborative calculation is 100% equal to 12 SS , unlike some previous private set intersection protocols, such as protocols[1,5,8-10], there may be errors in the results of collaborative computing, and the scope of the errors is difficult to define; (2) After collaborative completion of calculation of12 SS ,  P1 and  P2 do not disclose the elements of their respective sets, nor do they disclose the cardinality of their respective sets. That is, after P1 and P2 complete the calculation of 12 SS  together, the calculation result of 12 SS   must be correct, they cannot get any other information about each other except 12 SS   (the elements of the sets, the cardinality of the sets). This work is supported by  the National Nature Science Foundation of China (Nso. 61972225, 61902164,  61601358, 61672426, 61902300, 61902303, 11847101), the National Science and Technology Support Plan (2018YFB1004501), the Key Scientific Research Program Project of Department of Education of Shaanxi Province(No.20JS052), the Special Plan for technological Innovation guidan ce of Shaanxi Province in 2020 (2020CGXNG-012) and the Research Fund for the Doctoral Program of Xi'an Polytechnic University (No. 107020331).