布尔电路上保护隐私集合并集运算的研究与实现

《布尔电路上保护隐私集合并集运算的研究与实现》由会员分享，可在线阅读，更多相关《布尔电路上保护隐私集合并集运算的研究与实现（7页珍藏版）》请在金锄头文库上搜索。

1、第 38 卷第 6 期 电 子 与 信 息 学 报 Vol.38No.6 2016 年 6 月 Journal of Electronics YAOs garbled circuit technology; Private set operation 1 引言 保护隐私的集合运算是安全多方计算的一个重 要研究分支，是近几年来国内外的研究热点。保护 隐私集合运算的函数表现形式有算术电路和布尔电 路两种。根据数据结构的不同，算术电路上保护隐 私的集合运算分为基于茫然多项式估值的方案、基 于茫然伪随机函数评估的方案和基于布隆过滤器的 方案。例如，2005 年 CRYPTO 大会上，文献1收稿日期：

2、2015-08-05； 改回日期： 2016-02-29； 网络出版： 2016-05-05 *通信作者：孙茂华 基金项目：首都经济贸易大学 2014 年青年科研启动基金，首都经济贸 易 大 学 青 年 科 学 基 金 (2014XJQ016) ， 国 家 自 然 科 学 基 金(61302087)，2016 年北京市教委科研水平提高基金 Foundation Items: Young Scientific Research Starting Foundation of CUEB 2014, Young Scientists Program of CUEB (2014XJQ016), The

3、 National Natural Science Foundation of China (61302087), Improve Scientific Rescarch Foundation of Beijing Education 2016 使用茫然多项式估值实现了半诚实模型下保护隐私 的集合并集运算协议(Private Set Union, PSU)，但 是该协议会泄漏交集信息；2007 年 ACNS 大会上， 文献2提出了恶意模型下保护隐私的并集运算协 议，该协议的计算复杂度为2nk模乘操作，通信复 杂度为222()O knk n+；2012 年 PKC 大会上，文献 3使用茫然有理函

4、数表示集合并借助逆向罗伦级数 实现了保护隐私的并集运算，其恶意模型下协议的 计算复杂度为24k n次模乘操作，通信复杂度为23()O k n。 文献4将布隆过滤器引入到保护隐私的交 集运算(Private Set Intersection, PSI)中，使用安全 多方乘法协议得到参与者布隆过滤器向量的交集， 进而得到输入集合的交集； 但是该算法是不安全的， 因为交集布隆过滤器向量泄漏了输入信息。此后， 文献5使用布隆过滤器和 GM 同态加密方案设计了 保护隐私的交集运算协议，其半诚实模型下的协议第 6 期 孙茂华等： 布尔电路上保护隐私集合并集运算的研究与实现 1413 需要kn次 Hash

5、操作和2( logkekl+2 )kl n+ +次模 乘操作。文献6使用 XOR-秘密共享和茫然传输设 计了基于布隆过滤器的保护隐私交集运算协议，该 协议需要22(log)kke n+次 Hash 操作和数百次公钥 操作。文献7研究了 Server-aided 模式下数亿级集 合上的保护隐私集合并集运算。文献8基于 El-Gamal 同态加密方案和茫然多项式估值技术实 现了保护隐私的集合并集运算。文献9使用茫然传 输扩展协议设计了随机混淆布隆过滤器，进而优化 了文献6协议的效率。 文献10基于代数伪随机函数 的陷门高效性设计了恶意模型下保护隐私集合交集 协议。上述保护隐私的集合运算协议假设输入

6、集合 的大小信息是公开的， 文献11研究了如何同时保护 输入集合的内容和大小信息。此外，文献12-14探 讨了算术电路上保护隐私交集外包运算，将协议的 计算模型由传统模型转换到外包模型。 文献15基于 LWE 困难性假设提出了格上的保护隐私集合交集 运算协议。布尔电路上保护隐私的集合运算协议主 要借助通用混淆电路估值技术实现隐私保护。 例如， 2005 年 ASIACRYPT 大会上，文献16使用比特向 量表示参与者的秘密集合， 利用 YAO 氏通用混淆电 路估值协议在 OR 门组成的电路上实现了保护隐私 集合并集运算协议。 2012 年 NDSS 大会上， 文献17 在布尔电路上设计并实现了

7、保护隐私的集合交集运 算协议；其研究成果表明，通过合理地设计专用电 路，布尔电路上安全多方计算协议的效率在某些情 况下高于基于算术电路的协议效率。文献9基于 GMW 电路估值协议提出了更加高效的保护隐私的 集合交集协议。文献18提出了基于置换 Hash 的保 护隐私集合交集协议， 该协议比文献17的方案提速 约 5 倍。 虽然保护隐私并集运算在近几年取得了一定的 研究成果，但是现有研究仍然存在如下问题：(1)布 尔电路上保护隐私的并集协议16在处理稀疏集合时 效率较低；(2)目前的多数文献主要集中在理论研 究，即通过对渐进计算复杂度表达式和渐进通信复 杂度表达式的对比得到效率分析结果，并没有实

8、现 实验模型的开发。鉴于实验模型设计和开发是近几 年来安全多方计算研究的一种重要方法，设计并开 发保护隐私并集运算的实验模型显得十分必要。由 此，本文主要致力于提高布尔电路上针对稀疏集合 并集运算协议的效率和开发对应的实验模型。具体 地，本文基于 YAO 氏混淆电路估值技术，通过设 计并集运算的专用电路来实现布尔电路上保护隐私 的并集运算协议。输入信息的数据结构采用双调排 序序列。专用电路包括预处理、合并电路、去重电路、混淆电路 4 个部分。为了将理论研究成果转换 为实际应用，本文借助于 MightBeEvil 应用程序框 架实现了应用模型的开发。实验结果表明，当计算 稀疏集合的并集时，本文提

9、出方案的效率较高。 2 保护隐私集合并集运算协议 本节按照预处理-集合合并-去重-混淆 4 个阶段 设计保护隐私的集合并集运算电路。 2.1 预处理 预处理阶段，预处理协议如表 1 所示。参与者 首先通过协商得到集合大小N，然后，参与者在本 地对各自的秘密集合进行排序。接下来，参与者在 自己的排序集合中插入若干个扰乱因子，从而形成 大小为N的集合。通过加入扰乱因子，参与者将无 法通过攻击获得双方集合交集的大小。 表 1 预处理协议 参与者：1P和2P 输入数据：1P 输入集合1S ,2P 输入集合2S 步骤 1 iP 随机产生数据iN ， 要求iinS。iP 将in发送给1iP，其中1,2i=

10、。 步骤 2 1P和2P在本地计算12max(,)Nn n=。 步骤3 1P在本地对1S按照单调递增的顺序排序，得到集合1S。2P在本地对2S按照单调递减的顺序排序，得到集合2S。 步骤4 iP随机挑选 iS中的iNS个数据，并在集合 iS 相应数据的后面插入一个备份，得到集合iG。 2.2 保护隐私的集合合并协议 本文使用双调排序网络实现集合1G和2G的合并。由于1G中的元素按照单调递增的顺序排列，2G中的元素按照单调递减的顺序排列， 因此1G和2G构成双调序列，可以使用双调排序完成集合的合并。双调排序网络算法控制数据比较的顺序，而基本的运算单元为数据比较器 Sorter。Sorter 输入

11、为数据,x y，输出为min( , ),max( , )x yx y。当 Sorter 的一个输出数据为x时，另一个数据必为y。因此，只需要调用一次 Kolesnikov 数据比较器19，然后通过异或门组成的电路可以得到另一个输出数据，如图 1所示。通过保护隐私的集合合并协议，两个参与者的秘密集合被合并为一个多重集合S。 性能比较：使用双调排序网络对参与者的私有集 合 进 行 合 并 时 ， 共 需 要 调 用 Sorter 电 路2log (2)NN次。表 2 对保护隐私的集合合并协议所需的门数进行了对比。可以看出，本文方案在门电路消耗上优于文献17方案。 1414 电 子 与 信 息 学

12、报 第 38 卷 图1 数据比较器方案 表 2 保护隐私的集合合并协议中门数量对比 方案 总门数 异或门数 其他门数 文献17 211log (2)NN 28log (2)NN 23log (2)NN本文方案 29log (2)NN 27log (2)NN 22log (2)NN2.3 去重 由于多重集合S中重复元素都是相邻的，因此 本文对比S中两两相邻的元素实现重复元素的过 滤。当两个元素相等，输出无效元素(暂且认为 0 元 素为无效元素)，否则输出第 1 个元素。去重电路如 图 2 所示。去重电路中包含两类过滤器1F和2F，如 图 3 所示。 对于过滤器1F， 当输入元素1iimm+=时，

13、10niizmm+=，即im和1im+的异或值为 0； 当输入元素1iimm+时，10niizmm+=，即im和1im+的异或值中至少有一位不为 0。通过对z 中各比特执行或操作，可以判断z的各比特是否全 为 0，进而判断出im和1im+是否相等。如果im= 1im+则输出 0，否则输出im。接下来，再对1im+和2im+使用过滤器1F进行过滤。对于多重集合S中最 后的两个元素21nm和2nm，如果212nnmm=，则 输出2nm和 0；否则需要将21nm和2nm都输出，因 此对于S中最后的两个元素21nm和2nm使用过滤 器2F进行过滤。 过滤器1F和2F中的多路复合选择器 MUX 仍然选用

14、文献20的设计方案。 2.4 混淆 合并后的集合S经过去重电路后得到集合F= 122 ,Nf ff?。事实上，F中的元素是由并集元素 和若干个零元素组成。 零元素是由去重电路引入的， 当某个位置0if =且10if+， 则说明集合S中im = 图2 去重电路顶图 1im+。 导致1iimm+=的原因可能是由于参与者在预 处理阶段插入的干扰因子，也可能是由于im是交集 元素。如果直接将F作为协议的最终输出公布，在 极端情况下参与者可能会得知集合交集中某些元素 的信息。考虑如下情况：假设参与者iP通过某些社 会学方法提前得知了对方集合的大小1 iS。 对于iP 私有集合中的元素im,iP在预处理阶

15、段插入了1t 个im的副本。 如果集合F中元素xifm=， 且集合F 中xf前面的1 iNSt+个元素均为 0， 则iP可以判 断出im必为集合交集中的元素。 为了抵抗上述攻击方法，本文将对去重电路的 输出集合进行混淆，打乱集合中元素的位置，从而 保护参与者的私有信息。使用通用电路估值方案对 上述预处理、合并和去重电路进行安全计算后，参 与者iP将得到集合F的一个秘密份额1 ,i iFf= 22,ii Nff?，且满足1ii xxxfff=。表 3 是本文设计 的混淆协议。 表 3 保护隐私的集合混淆协议 参与者：1P和2P 输入数据：1P输入秘密份额1F,2P输入秘密份额2F 输出数据：1P得到集合并集，2P无输出数据 步骤1 1P产生长度是nbit的随机数10,1nr =， 并在本地计算111 112121,NAfr frfr=?。1P将集合A发送给2P。 步骤2 2P在本地计算 1222121212 112121 ,NxxNxBb bbAFfrffrffrf=