隐私保护集合交集计算协议

隐私保护集合交集计算属于安全多方计算领域的特定应用问题,具有重要的研究价值和广泛的应用范围。在信息高速发展的时代,对该问题的研究满足了人们在日常生活中享受各种便利的同时隐私得到保护的需求。文章考虑的是两个参与者隐私保护集合交集计算的情形,首先将集合表示成多项式,把求解两个集合的交集问题转化为求解两个多项式的最大公因式问题;在此基础上,根据多项式的数学性质和Pailliar同态加密算法提出一种保护隐私的两方集合交集计算协议,并给出协议的正确性和安全性分析;最后通过与相关文献的比较分析,得出文章协议的计算复杂度和通信复杂度较低的结论,且能够很好地保护参与方集合的元素个数。     

半可信云服务器辅助的高效隐私交集计算协议

隐私集合交集（private set intersection,PSI）是隐私计算中的热点,其允许参与两方在不泄露任何额外信息的要求下计算交集.现有的隐私集合交集计算方案对参与双方的计算能力要求高,且计算能力差的参与方无法在保证集合数据隐私的前提下将计算安全外包给云服务器.设计了一种新的不经意两方分布式伪随机函数,允许半可信的云服务器参与相等性测试,又不泄露参与方任何集合信息.基于该不经意伪随机函数构建了半可信云服务器辅助的隐私集合交集计算协议,将主要计算量外包给云服务器.在半诚实模型下证明了协议的安全性.同时,该协议可保密地计算隐私集合交集的基数.通过与现有协议分析与实验性能比较,该协议效率高,计算复杂度与通信复杂度均与集合大小呈线性关系,适用于客户端设备受限的应用场景.     

基于云服务器的公平多方隐私集合交集协议

隐私集合交集（PSI）是解决隐私信息共享的重要办法。针对现有的协议中参与方不能同时获取计算结果而导致的不公平性问题，提出一种基于云服务器的公平多方PSI协议。首先，利用哈希映射完成隐私信息的子份额在混淆布隆过滤器（GBF）中的存储；其次，为避免交互过程中各参与方集合元素索引值的泄露，协议结合不经意传输（OT）技术完成存储信息的份额置换；最后，通过云服务器进行逐位计算，并将结果同时返回各参与方，保证各参与方获取结果的公平性。协议的正确性和安全性分析表明，所提协议能够实现参与方获得交集结果的公平性，而且协议能够抵抗参与方与云服务器进行的合谋。性能分析表明，所提协议的计算复杂度和通信复杂度与参与方集合包含的元素总数无关；与多方隐私集合交集协议（MPSI）、实用多方恶意安全私有集合交集PSImple和隐私集合交集求和协议（PI-Sum）相比，在同等条件下，所提协议的存储开销、通信开销和运行时间更少。     

双云辅助的超阈值多方隐私集合交集计算协议

超阈值多方隐私集合求交协议(OT-MP-PSI)是PSI协议的变体,允许m个参与方共同计算至少t (t≤m)个参与方中拥有相同元素的超阈值交集,且保证仅拥有超阈值元素的参与方才能知晓该元素是否属于超阈值交集,对于其他信息一无所知. OT-MP-PSI推广了PSI的实际应用场景.现有方案均基于昂贵的公钥密码来构建,其较大的计算量导致运行时间缓慢.首先设计一个基于对称密码的不经意可编程伪随机秘密共享(OPPR-SS)密码组件,并基于OPPR-SS组件设计双云辅助的OT-MP-PSI协议,将秘密分发和重构的任务分别交给不可信云服务器来辅助完成,实现弱计算能力的参与方也能完成OT-MP-PSI协议.在半诚实模型下证明协议安全性.相比现有的OT-MP-PSI协议,所提协议在秘密分发和重构阶段均具有最优运行时间和通信负载,参与方、共享方和重构方的通信复杂度不再与阈值t有关,实现参与方常数轮的通信,通信复杂度仅为O(n),秘密分发方和重构方的计算复杂度仅与对称密码次数有关.     

基于弹性秘密共享的多方门限隐私集合交集协议

$ (t, n) $门限隐私集合交集协议, 指$ N $个参与者各自拥有大小为$ n $的隐私集合, 在不泄露自身隐私信息的前提下, 如果各参与者交集数量大于门限值$ t $, 则参与各方能够获得交集信息, 其有广泛的应用, 如指纹识别、在线拼车、相亲网站等. 然而现有门限隐私集合交集协议大多针对两方参与者进行研究, 对多方门限隐私集合交集协议的研究仍存在许多挑战, 现有的多方门限隐私集合交集协议使用全同态加密等开销较大的公钥算法, 尚没有有效实现. 针对上述问题, 结合弹性秘密共享、布隆过滤器提出两种有效的多方门限隐私集合交集协议, 并首次仿真实现了协议. 首先, 设计一种新的布隆过滤器构造方法, 将弹性秘密共享生成的份额与参与方的集合元素相对应, 通过查询布隆过滤器获取的秘密子份额能否重构出正确秘密来判断各方交集是否达到门限值, 有效防止交集基数的泄露. 设计的第1个协议避免使用开销较大的公钥算法, 当设置安全参数$ \lambda $为128, 集合大小为$ {2^{14}} $, 门限值为$ 0.8n $时, 在三方场景下协议在线阶段的时间成本为191 s. 此外, 为了能在半诚实模型下抵抗至多$ N - 1 $个敌手合谋, 在第1个协议基础上结合不经意传输设计一种该协议的变体, 相同条件下, 在线阶段时间成本为194 s. 最后通过安全证明, 证明上述协议在半诚实模型下是安全的.     

基于理想格的两方隐私集合交集协议

当前大多数现有的隐私集合交集（PSI）协议的安全性都是基于数论假设,而随着量子计算理论的发展,基于数论假设的PSI协议将变得不再安全。针对该问题,利用格上函数加密的函数策略解密特性,并通过二进制分解将参与方元素设计成符合LWE加法同态的向量形式,提出了一种基于理想格的半诚实安全的两方PSI协议。安全性方面,使用基于环上错误学习问题（RLWE）的函数加密系统来构造PSI协议,实现了抗量子的安全性。效率方面,协议的通信复杂度为O（w+v）,与参与方元素成正比,保证了较高的通信效率;并且利用理想格使公钥的大小减少n倍,提高了存储效率,降低了通信成本。     

基于云服务器辅助的多方隐私交集计算协议

隐私集合交集(Private Set Intersection,PSI)技术允许私有集合数据持有方联合计算出集合交集而不泄露交集外的任何隐私信息.作为安全多方计算中的重要密码学工具,该技术已被广泛应用于人工智能和数据挖掘的安全领域.随着多源数据共享时代的到来,大多数PSI协议主要解决两方隐私集合交集问题,一般无法直接推广到多方隐私交集计算场景.文中设计了基于云服务器辅助的多方隐私交集计算协议,能将部分计算和通信外包给不可信云服务器而又不会泄露任何隐私数据,通过使用不经意伪随机函数、秘密共享和键值对打包方法使得协议更高效.通过模拟范例证明了协议在半诚实模型下能够安全地计算多方隐私集合交集,所有参与方和云服务器都无法窃取额外数据.与现有方案相比,所提协议受限制更少,适用范围更广.     

高效且恶意安全的三方小集合隐私交集计算协议

隐私集合交集(private set intersection, PSI)允许持有私有集合的参与方安全地获得集合的交集,而不会泄露除交集之外任何元素的信息.现有的两方/多方PSI协议大多基于不经意传输(oblivious transfer, OT)协议,具有很高计算效率的同时,也带来了巨大通信开销.在很多场景中,扩展网络带宽是非常昂贵甚至不可行的,而目前不依赖于OT设计且计算高效的多方PSI协议仍然较少.基于一轮密钥协商构造了三方参与的PSI计算协议,分别在半诚实模型和恶意安全性模型下,证明了协议的安全性且允许任意两方的合谋攻击.通过实验仿真,在大集合场景,相比现有基于OT的多方PSI协议,所构造的协议具有最优的通信轮数且通信量降低了89%～98%;在小集合场景(500个元素或更少),相比适用弱通信网络的同类PSI协议,具有最优运行时间和通信负载,比依赖于同态加密的PSI协议快10～25倍.     

一类可抵抗恶意攻击的隐私集合交集协议

针对安全两方计算中隐私集合交集计算问题,提出了一种改进的基于Bloom Filter数据结构的隐私集合交集协议。该协议能够保证双方在各自隐私安全的前提下,计算出两者数据集合的交集,其中只有一方能够计算出交集元素,另外一方无法计算得到交集,并且双方都不能获得或推测出对方除交集以外的任何集合元素,确保了参与双方敏感信息的安全保密。所提协议引入了基于身份的密钥协商协议,能够抵抗非法用户的恶意攻击,达到隐私保护和安全防御的目的,抵御了密钥泄露的风险,减少了加解密的运算量,并且具备支持较大规模集合数据的运算能力。     

公平理性委托计算协议

已存在的安全计算集合关系的协议大多基于公钥加密算法,因此很难再嵌入到带有属性关系的公钥加密或密文搜索中.针对该问题,本文给出了非加密方法安全计算集合包含关系和集合交集的2个协议.我们首先利用（n,n）秘密共享的思想分别将原来2个问题转化为集合相等问题.在此基础上,结合离散对数,构造了安全计算集合包含关系的协议1和集合交集的协议2.最后的分析显示：我们的方案没有使用任何公钥加密方法,在保持了较优通信复杂性的同时,便于作为一种子模块嵌入到带有集合操作关系的公钥加密体制或者密文搜索体制中,从而丰富这些方案的功能.     

基于串空间理论的安全协议自动验证

针对目前串空间理论依赖分析人员主观判断、无法使用自动化工具进行验证的问题,提出了基于串空间理论的协议认证属性标准化验证过程。首先为协议消息项定义类型标签,对串空间及认证测试理论进行扩展;然后通过判断测试元素出现位置、检验测试元素参数一致性、确认变换进行边唯一存在性和检验目标串参数一致性,将基于串空间理论的协议验证过程标准化为可程序实现的步骤。该算法的时间复杂度为O(n²),避免了模型检测方法的状态空间爆炸问题,并在此基础上实现了安全协议认证属性的自动化验证工具。以BAN-Yahalom协议和TLS 1.0握手协议为例进行了标准化的分析验证,找到了对BAN-Yahalom协议的一种新攻击形式。该攻击无需限制服务器对随机数的检查,比Syverson发现的攻击更具普遍性。     

A lightweight delegated private set intersection cardinality protocol

Secure multiparty computation (MPC) is an important means to realize privacy computing (PC). Private set intersection cardinality (PSI-CA) is a variant of an important problem in MPC research, that is private set intersection. PSI-CA allows multiple participants jointly compute the size of the common intersection of their private sets through interaction without revealing any other information about their respective sets. Delegated PSI-CA delegates a large number of computing in the protocol to some untrusted cloud servers, which makes the protocol efficient. Delegated PSI-CA is considered to be of great significance for the construction of privacy-preserving contact tracing systems recently. However, the existing work is still not ideal for the resource-limited mobile terminal of clients. In this paper, we propose a lightweight delegated PSI-CA protocol based on multi-point oblivious pseudorandom function and collision-resistant hash function. Our protocol does not need to do additional pre-operations, so the computation complexity and the communication complexity on the client side are further reduced compare to the existing works. In addition, we build a privacy-preserving contact tracing system by utilizing our protocol, which can be publicly checked if necessary, named PC-CONTrace. The experimental results show that our system is more practical and advantageous for densely populated areas.     

Constraint-based structuring of network protocols

Summary. The complexity of designing protocols has led to compositional techniques for designing and verifying protocols. We propose a technique based on the notion of parallel composition of protocols. We view a composite protocol as an interleaved execution of the component protocols subject to a set of constraints. Using the constraints as building blocks, we define several constraint-based structures with each structure combining the properties of the component protocols in a different way. For instance, the component protocols of a multifunction protocol can be structured so that the composite protocol performs all the individual functions concurrently or performs only one of them depending on the order of initiation of the component protocols. We provide inference rules to infer safety and liveness properties of the composite protocol. Some properties are derived from those of the component protocols while others are derived from the structuring mechanism (the set of constraints) used to combine the component protocols. Received: October 1996 / Accepted: August 1998     

How to Choose a Timing Model

When employing a consensus algorithm for state machine replication, should one optimize for the case that all communication links are usually timely, or for fewer timely links? Does optimizing a protocol for better message complexity hamper the time complexity? In this paper, we investigate these types of questions using mathematical analysis as well as experiments over PlanetLab (WAN) and a LAN. We present a new and efficient leader-based consensus protocol that has O(n) stable-state message complexity (in a system with n processes) and requires only O(n) links to be timely at stable times. We compare this protocol with several previously suggested protocols. Our results show that a protocol that requires fewer timely links can achieve better performance, even if it sends fewer messages.     

保护私有信息的两多边形相交面积计算

保护私有信息的计算几何是一类特殊的安全多方计算问题,在军事、商业等领域具有重要的应用前景。在半诚实模型下,利用点线叉积协议设计一个保护私有信息的点包含于多边形判定协议;基于该协议,提出保护私有信息的两多边形相交面积计算协议;分析和证明上述协议的正确性、安全性和复杂性。     

一种高效的百万富翁问题协议及其应用

百万富翁问题是安全多方计算的基础问题,但现有解决方案计算复杂度高且效率较低,在两数相等时无法进行精确比较。针对该问题,提出一种基于0-1编码的百万富翁问题协议。使用改进的0-1保密数据编码规则构建向量,利用ElGamal同态加密变体算法的同态性质,将百万富翁问题转化为向量中两元素求和的问题,同时在半诚实模型下利用模拟范例证明协议的正确性与安全性,并将其应用于安全两方集合交集个数问题的求解。实验结果表明,与采用ElGamal和Paillier同态加密算法的协议相比,该协议计算复杂度更低且效率更高,可在两数相等时进行准确对比。     

Performance analysis of CSMA and BTMA protocols in multihop networks (I). Single channel case

Busy tone multiple access protocols have been used in multihop networks to reduce the effect of the hidden terminal problem. Due to complexity, the performance of these protocols for large networks has not been analyzed. In this paper, using a Markov chain model and an approximation, we are able to analyze and evaluate the throughput performance of the non-persistent CSMA protocol, the conservative busy tone multiple access (C-BTMA) protocol and the ideal destination-based busy tone multiple access (ID-BTMA) protocol for large networks. The throughput comparison of the protocols is given. The results show that in a large multihop network, the BTMA protocols have a better performance than the non-persistent CSMA protocol and the ID-BTMA protocol has a better performance than the C-BTMA protocol at light channel loads.     

Protocol Customization for Improving MPI Performance on RDMA-Enabled Clusters

Optimizing Message Passing Interface (MPI) point-to-point communication for large messages is of paramount importance since most communications in MPI applications are performed by such operations. Remote Direct Memory Access (RDMA) allows one-sided data transfer and provides great flexibility in the design of efficient communication protocols for large messages. However, achieving high point-to-point communication performance on RDMA-enabled clusters is challenging due to both the complexity in communication protocols and the impact of the protocol invocation scenario on the performance of a given protocol. In this work, we analyze existing protocols and show that they are not ideal in many situations, and propose to use protocol customization, that is, different protocols for different situations to improve MPI performance. More specifically, by leveraging the RDMA capability, we develop a set of protocols that can provide high performance for all protocol invocation scenarios. Armed with this set of protocols that can collectively achieve high performance in all situations, we demonstrate the potential of protocol customization by developing a trace-driven toolkit that allows the appropriate protocol to be selected for each communication in an MPI application to maximize performance. We evaluate the performance of the proposed techniques using micro-benchmarks and application benchmarks. The results indicate that protocol customization can out-perform traditional communication schemes by a large degree in many situations.