Search
E-mail
RSS

Journal of Cybersecurity >

2025 , Vol. 3 >Issue 5: 114 - 124

DOI: https://doi.org/10.20172/j.issn.2097-3136.250328

Academic Research

Verifiable private set intersection protocols in semi-trusted cloud environments

  • Ouyang Yuxuan ,
  • Hu Ronghua , *
Expand
  • school of Computer Science, Yangtze University, Jingzhou 434022, China

Online published: 2026-04-01

Copyright

Copyright ©2025 Journal of Aeronautical Materials. All rights reserved.
Fold

Abstract

Private Set Intersection (PSI) is an important privacy-preserving technique in the field of Secure Multi-Party Computation (SMPC), which enables the intersection to be computed by two parties without disclosing their respective datasets. However, high computational power is required from participants by existing PSI protocols, and low efficiency is achieved in large-scale data processing when participants have limited local computing power. To address the problem of limited client resources, a cloud-assisted verifiable privacy set intersection protocol is constructed based on the Oblivious Pseudo-Random Function (OPRF) and homomorphic Brakerski/Fan-Vercauteren (BFV) algorithm. The protocol can detect and resist the malicious tampering behavior of cloud servers, while ensuring the data security and privacy of participants. The security of the protocol is proved under the semi-honest model. Through experimental comparison with existing protocols, high efficiency is achieved by the protocol when the data volumes of the two parties differ greatly, and both computational complexity and communication complexity are linearly correlated with the set size, making it suitable for client-server application scenarios.

Key words： private set intersection; cloud-assisted; verifiable computation; homomorphic encryption; oblivious pseudo-random function

Cite this article

Ouyang Yuxuan , Hu Ronghua . Verifiable private set intersection protocols in semi-trusted cloud environments[J]. Journal of Cybersecurity, 2025 , 3(5) : 114 -124 . DOI: 10.20172/j.issn.2097-3136.250328

0 引言

隐私集合求交（Private Set Intersection， PSI）[1-2]是安全多方计算领域中应用广泛、协议成熟的隐私保护技术，也是当前隐私计算研究的热点课题。PSI 协议允许双方或多方在不泄露各自数据集的前提下计算交集，且任何参与方均无法推断出对方数据集的其他信息。
最早的 PSI 协议可追溯至 20 世纪 80 年代，当时的研究主要集中于安全多方计算（Secure Multi-Party Computation，SMPC）领域[3]。SMPC 允许多个参与方在不泄露各自输入数据的前提下，共同完成数据的计算与分析。当时的 PSI 协议大多基于公钥加密技术[4-5]，计算开销较高且效率较低。但随着密码学技术的不断发展，PSI 协议也得到了进一步研究与改进，研究人员针对不同应用场景及性能需求，提出了多种改进方案。当前，PSI 已得到广泛应用，如医疗数据分析[6]、计算广告转化效率[7-8]、私人联系人发现[9]等场景，可有效保护个人隐私及企业机密。
PSI 作为隐私计算的核心技术，已在数据协作场景中体现出重要价值。传统两方 PSI 虽在计算效率上表现优异，但在一方客户端资源受限的前提下，其局限性逐渐凸显。大数据时代的到来为 PSI 带来了新的机遇与挑战。在参与方本地算力有限的前提下，大规模数据集的处理效率显著下降，严重制约了其在实际场景中的应用。为突破本地资源瓶颈，学术界提出了将计算任务外包至云端的解决思路[10-15]。云服务商凭借其弹性可扩展的算力资源，理论上可显著提升 PSI 协议的执行效率。然而，该方案也带来了隐私安全隐患，若直接采用传统 PSI 协议并将计算迁移至云端，云服务商可能通过中间计算结果推断出敏感数据信息，甚至恶意篡改计算结果。现有云辅助 PSI 方案多基于半诚实云服务商假设，即默认云服务器严格遵循协议流程，但可能被动窃取隐私信息，该假设在商业云环境中往往过于理想化。研究表明，现有协议在抵御主动攻击时存在验证机制缺失的问题，且无法在保护数据隐私的同时，实现计算过程的可审计性。
本文针对客户端一方资源受限且与服务端交互的应用场景，引入云服务器来承担算力，采用不经意伪随机函数盲化数据、布谷鸟哈希降低计算开销、多项式插值与评估及同态加密（Homomorphic Encryption，HE）技术构建安全计算框架，提出了一种可验证的云辅助隐私集合求交（Verifiable Cloud-Assisted PSI，VC-PSI）协议。该协议可解决参与方计算资源不足的问题，将计算任务委托给云服务器，并引入 Merkle 树对计算结果进行验证，从而解决恶意云服务器篡改结果的问题。本文的主要贡献如下。
1）提出云辅助可验证隐私集合求交协议，通过云服务器承担核心计算任务，显著降低资源受限设备的负载；该协议适用于服务器—客户端模式，在两方数据量不平衡时效率较优。
2）实现轻量级正确性与完整性检测，设计通过秘密共享扩展外包数据集以有效验证交集结果的正确性，引入 Merkle 树实现高效完整性验证，同时支持选择性检验，进一步降低计算开销。
3）搭建实验仿真环境，在不同数量级数据场景下，对比分析各参与方的性能表现，并与现有高效隐私集合求交协议进行性能对比。

1 相关工作

PSI 作为安全多方计算的重要分支，近年来在隐私保护数据共享场景中受到广泛关注。现有方案大致可分为传统 PSI 协议和基于云辅助的 PSI 协议两类。

1.1 传统PSI协议

PSI 协议的性能优化主要依托其底层密码原语的发展，根据密码原语的差异，主要可划分为3种不同的计算框架。
早期的 PSI 协议以公钥加密技术为核心，根据底层密码机制的不同，可分为基于 Diffie-Hellman 密钥交换[16-19]与基于 RSA（Rivest-Shamir-Adleman）盲签名[20-21]两类方案。这类协议思想简单、易于实现，且通信开销较小，但计算复杂度偏高，更适用于数据规模较小的应用场景。为降低计算开销，Dong 等[22]首次将乱码布隆过滤器与不经意传输（Oblivious Transfer，OT）技术相结合，提出的协议在半诚实模型下可证明安全，具备线性复杂度，且依托高效的对称密钥操作，即便在输入数据集规模较大时，仍能保持良好性能。Pinkas 等[23]对文献[22]提出的基于乱码布隆过滤器的 PSI 协议进行改进，核心思路是使参与方协作生成随机布隆过滤器，并引入随机 OT 扩展与并行化操作，进一步提升了计算效率。
Kolesnikov 等[24]提出一种高效的批处理不经意伪随机函数（Oblivious Pseudo-Random Function，OPRF）协议，并将其应用于半诚实安全模型下的 PSI 协议设计。该方案是目前高带宽场景下计算效率最优的 PSI 协议，但存在通信开销较大的问题。为实现通信与计算开销的平衡，Pinkas 等[25]提出基于稀疏 OT 扩展的轻量级 PSI 协议，与文献 [24] 的方案相比，该协议通信开销更低，在低带宽网络环境中运行速度优势更为显著。
针对两方数据量差距较大的非平衡场景，研究人员通常采用同态加密技术[26-28] 构造 PSI 协议。Freedman 等[29]首次将同态加密技术引入隐私集合求交领域，但所提协议计算效率较低。Freedman 等[30]对文献 [29] 的协议进行优化，引入布谷鸟哈希技术，使协议在输入数据集规模较大时的效率得到明显提升。Chen 等[31]提出一种基于 BFV（Brakerski/Fan-Vercauteren）全同态加密的非平衡场景 PSI 方案，该方案计算效率高但通信效率较低，且对数据持有方的计算资源要求较低，适用于资源受限的设备。Chen等[32]对文献 [31] 方案的性能与安全性进行了优化改进。

1.2 基于云辅助的PSI协议

云计算技术的兴起为 PSI 协议的研究开辟了新方向，目前已有多种云辅助 PSI 协议被提出，但云计算的引入也引发了新的安全问题。Kerschbaum 等[33]将同态加密技术与布隆过滤器相结合，提出可外包的 PSI 协议，该协议安全性较弱，云服务器可从计算过程中直接获取交集信息。Zheng 等[13]提出一种基于双线性映射累加器的求交协议，采用代理重加密和多累加器等技术实现可验证委托求交功能，但该方案存在遭受不可信云服务器明文猜测攻击的风险。Abadi等 [15]提出两种新型委托 PSI 协议：O-PSI 和 EO-PSI。其中， O-PSI 基于加法同态加密与点值多项式表示法构建协议，EO-PSI 则通过哈希表与伪随机函数进一步提升效率，且避免了公钥加密的使用。两种协议均能保障数据隐私与计算安全性，但客户端计算开销较高，不适用于计算资源受限的场景。Wang 等[34]提出一种基于标签的可验证委托集合交集协议，该协议将每个子集与一个标签相关联，标签隐式嵌入加密数据中，使云端无法获知哪些数据属于同一子集。协议支持多子集处理、动态更新与计数查询，并通过重加密技术和多项式表示保障数据隐私与计算结果的正确性，但存在子集规模及数据访问模式泄露的问题。Jiang 等[35]基于秘密共享、多项式表示、哈希表及伪随机函数等技术，构造了可验证委托求交协议。该协议使客户能够以可忽略的错误概率验证交集的正确性，有效解决了恶意云模型下私有集合交集计算的隐私保护与结果验证问题。综上所述，现有云辅助 PSI 协议大多仅限于诚实或半诚实场景，针对恶意云服务器，仍缺乏高效且可验证的协议方案。

2 系统架构与安全模型

2.1 系统架构

半可信云环境下的 PSI 协议涉及三方参与实体，包括服务端 A、客户端 B 与云服务器 C。服务端 A 与客户端 B 分别持有私有数据集，且希望在不泄露各自数据集隐私的前提下计算交集。A、B 两方负责对数据集进行预处理，并将加密后的数据外包给云服务器 C 执行计算。云服务器 C 提供计算资源，负责执行 PSI 计算任务，并将结果返回给客户端 B。客户端 B 对返回的加密结果进行解密，并验证结果的正确性。系统模型如图1 所示。
图 1 系统模型

Fig.1 System model

2.2 安全模型

2.2.1 攻击模型

攻击模型用于界定敌手可能采取的行为模式与策略，在分析 PSI 协议安全性时，需明确协议维持安全所需抵御的敌手能力边界。本文设定服务端 A 与客户端 B 为半诚实参与者。隐私计算领域常见的攻击模型主要分为两类：半诚实模型与恶意模型。
半诚实模型：协议参与方严格遵循协议执行流程，但可能试图从获取的中间数据中推测其他参与方的隐私信息。
恶意模型：被腐化的协议参与方会恶意偏离协议执行流程，通过篡改数据、伪造结果等方式获取额外利益或破坏协议安全性。

2.2.2 敌手模型

本协议的安全性基于理想—现实模型（Ideal-Real Model）进行严格证明。
现实模型：现实模型种包括服务端A、客户端B、云服务器C以及半诚实敌手$ \mathcal{A} $。本模型假设敌手$ \mathcal{A} $每次只能破坏一个实体，敌手$ \mathcal{A} $在控制服务端A和客户端B时是半诚实行为，而控制云服务器C时是恶意行为，同时设定云服务器C不会与任意参与方合谋。协议初始化阶段，服务端A和客户端B分别持有私有集合$ {S}_{\rm A}=\{{a}_{1}，{a}_{2}，\ldots ，{a}_{n}\} $和$ {S}_{\rm B}=\{{b}_{1}，{b}_{2}，\ldots ，{b}_{m}\}\mathrm{。}\pi $是PSI协议，$ \mathcal{F} $是PSI功能函数，$ \mathcal{F}\colon \Lambda \times {2}^{u}\times {2}^{u}\rightarrow \Lambda \times \Lambda \times {f}_{n} $，其中，$ \Lambda $表示空字符串，$ {2}^{u} $表示一个集合，$ {f}_{n} $表示两方交集。协议执行结束后，诚实参与方输出协议预设结果，而敌手$ \mathcal{A} $ 输出其在协议执行过程中获取的视图信息。现实模型中协议$ \pi $的联合输出被定义为$ {\mathrm{REAL}}_{\mathcal{A}}^{\pi }(\Lambda ，{S}_{\rm A}，{S}_{\rm B}) $。
理想模型：理想模型种包括服务端A、客户端B、云服务器C以及模拟器$ S $。本模型设定敌手通过模拟器S实施攻击，且每次仅能破坏一个参与实体。各参与方的输入与现实模型保持一致。诚实参与方将私有输入发送至可信第三方（Trusted Third Party, TTP），被敌手破坏的参与方则可能终止协议，或向 TTP 发送任意伪造输入。最终由 TTP 根据各方合法输入计算集合交集，并将结果发送给客户端B。理想模型的联合输出定义为$ {\mathrm{IDEAL}}_{S}^{F}(\Lambda ，{S}_{\rm A}，{S}_{\rm B}) $。
安全性：若$ {\mathrm{REAL}}_{\alpha }^{\pi }(\Lambda ，{S}_{\rm A}，{S}_{\rm B}) $ 和$ {\mathrm{IDEAL}}_{S}^{F}(\Lambda ， {S}_{\rm A}，{S}_{\rm B}) $不可区分，则判定协议$ \pi $可以安全地实现功能函数$ \mathcal{F} $，即
$ {\mathrm{IDEAL}}_{S}^{F}(\Lambda \text{，}{S}_{\rm A}\text{，}{S}_{\rm B})\overset{C}={\mathrm{REAL}}_{\mathcal{A}}^{\pi }(\Lambda \text{，}{S}_{\rm A}\text{，}{S}_{\rm B}) $

3 基础知识

3.1 不经意伪随机函数

不经意伪随机函数是密码学协议与隐私保护技术领域中广泛应用的密码原语。OPRF 是一类特殊的伪随机函数，协议交互过程中，服务器持有密钥 k，客户端持有输入 x。协议的核心目标是使客户端获取伪随机函数输出 f(k,x)，而服务器无法获知客户端输入 x 的任何隐私信息。OPRF 的安全性需满足正确性、隐私性及可验证性等核心属性。OPRF 的构造通常基于伪随机函数，伪随机函数是一类可通过密钥与输入生成伪随机输出的函数，具备伪随机性与不可区分性等核心特点。OPRF 的交互流程如图2 所示。
图 2 OPRF的交互流程

Fig.2 Interaction flow of OPRF

OPRF 的核心特性是：即便交互双方互不掌握对方的私有集合信息，仍可实现安全高效的协同计算与数据交互。PSI 协议可依托 OPRF 的上述特性进行构造，支持两方在不泄露各自集合隐私信息的前提下计算交集，协议流程如图3 所示。OPRF 协议通常基于OT构造，但 OT 的实现通常依赖公钥密码学技术，存在计算开销较大的问题。Ishai 等[36]提出一种基于少量基础 OT 实现大量 OT 实例高效扩展的方法。Kolesnikov 等[37]基于文献 [36] 的方法，将 1-out-of-2 OT 扩展至 1-out-of-n OT 场景，单次扩展可生成 logn 个 1-out-of-2 OT 实例，显著减少基础 OT 实例的调用次数。文献[24]采用伪随机码（Pseudo-Random Code, PRC）替代传统纠错码，通过少量公钥加密与大量对称密钥加密操作的结合，实现了批量 OPRF 实例的高效生成，并以此构造了目前高带宽场景下计算效率较优的 PSI 协议。
图 3 基于OPRF的PSI协议流程

Fig.3 PSI protocol flow based on OPRF

3.2 布谷鸟哈希

布谷鸟哈希是一种解决哈希冲突的高效方法，其核心目标是通过简单哈希函数提升哈希表的空间利用率，同时保证平均查询时间复杂度。该方法的基本思想是采用多个哈希函数处理冲突，典型的布谷鸟哈希方案即使用两个不同的哈希函数 H1 和 H2，并配合一个哈希表 T 完成数据存储。插入元素 x 时，首先通过 H1(x) 计算其存储地址，若该地址空闲，则将 x 存入该地址。否则，将新元素 x 置于该地址，并将原本存储在该地址的元素 y 通过 H2(y) 重新映射到哈希表 T 的对应地址。
哈希技术是 PSI 协议中优化通信复杂度与计算复杂度的重要工具之一，本文采用布谷鸟哈希与朴素哈希相结合的方式，降低协议的计算复杂度。具体方案为服务器端采用朴素哈希，客户端采用布谷鸟哈希，以此减少 PSI 协议中隐私数据的安全对比次数。

3.3 同态加密

同态加密是一类特殊的加密技术，支持用户直接对加密数据进行计算，且计算结果解密后与原始数据的计算结果一致。这意味着数据处理方无需知晓数据明文内容即可执行计算操作，从而实现数据的 “可算不可见”。同态加密既能保障数据机密性，又允许对加密数据进行处理，这对于云计算、隐私保护性数据分析及其他需第三方处理敏感信息的应用场景至关重要。
同态加密根据其支持的运算类型，可划分为以下几类：
若加密函数满足$ f(x)+f(y)=f(x+y) $，则称其具备加法同态特性;
若加密函数满足 f (x)+f (y)=f (x+y)，则称其具备加法同态特性；
若加密函数满足 f (x)×f (y)=f (x×y)，则称其具备乘法同态特性；
若加密函数同时支持任意次数的加法同态与乘法同态运算，则称其为全同态加密。
因此，根据上述特性，可将同态加密分为半同态加密（Partially Homomorphic Encryption，PHE）、分级同态加密与全同态加密（Fully Homomorphic Encryption，FHE）三类。
半同态加密仅支持单一类型的同态运算，包括以下3类。
乘法同态加密：以 RSA[38]算法和 ElGamal [39]算法为代表，仅支持加密数据的乘法运算。
加法同态加密：以 Paillier[40]算法为代表，仅支持加密数据的加法运算。
分级同态加密：以 BGN[41]方案为代表，支持加法同态与限定次数的乘法同态运算。
全同态加密支持任意次数的加法与乘法同态运算，主要包括以下方案。
第一代方案：以 Gentry[42]方案为代表，首次在理论上实现了全同态加密，但实际执行效率较低。
第二代方案：以文献[26]中的 BGV 方案为代表，基于环学习同态加密问题的困难性构建，无需压缩解密电路，方案的效率与安全性均大幅提升，但同态计算过程仍需计算密钥辅助。
第三代方案：以文献[27]中的 GSW 方案为代表，基于近似特征向量技术，设计了无需计算密钥的全同态加密方案。
CKKS 方案：以文献[28]中的方案为代表，支持对浮点数进行近似同态计算，计算结果为近似值，显著拓展了全同态加密的应用范围。

3.4 透明多项式评估

不经意多项式评估（Oblivious Polynomial Evaluation，OPE）是一种安全多方计算协议，支持两方（Alice 与 Bob）在不泄露各自私有输入信息的前提下，协同计算一个多项式在指定点的函数值。具体而言：Alice 持有多项式 $ {p}(x)=\sum \limits_{{i}=0}^{{N}}{{p}}_{{i}}{{x}}^{{i}} $，Bob 持有输入值 y，双方通过协议协同计算得到 p(y)，且交互过程中 Alice 不会泄露多项式的具体参数，Bob 也不会泄露输入值 y。

3.5 Merkle树

Merkle树是一种用于高效验证数据完整性的树状数据结构。该结构由 Ralph Merkle 于 1979 年提出，广泛应用于密码学、区块链及分布式系统等领域。
Merkle树是一种二叉树结构，每个叶子节点存储对应数据块的哈希值，每个非叶子节点存储其子节点哈希值的拼接哈希。树的根节点称为默克尔根（Merkle Root），是表征整个数据集内容的唯一哈希摘要。该结构通过密码学哈希函数（如 SHA-256）生成各节点哈希值，以此保障数据的不可伪造性与抗篡改性。

4 云辅助下可验证隐私集合求交协议

4.1 协议设计

本协议涉及三方参与实体，各参与方的角色定义如下。
服务端$ {\mathrm{A}} $:持有私有集合$ {U}_{{\mathrm{A}}}=\{{{x}}_{1}，{{x}}_{2}，\cdots ，{{x}}_{{n}}\} $;
客户端$ {\mathrm{B}} $:持有私有集合$ {U}_{{\mathrm{B}}}=\{{{y}}_{1}，{{y}}_{2}，\cdots ，{{y}}_{{m}}\} $;
云服务器C: 负责执行协议计算任务，且无法获取参与方的原始数据明文。

4.1.1 云服务器初始化

在协议执行前，云服务器 C 需完成以下参数的初始化工作。
（1）哈希表构建
选择3个抗碰撞哈希函数$ {H}_{1}，{H}_{2}，{H}_{3} $，构造哈希表，其中，$ h $为哈希桶数量，$ B $为每个桶的容量，需满足:
$ h\cdot B\geqslant \max (|{S}_{\rm A}|\text{，}|{S}_{\rm B}|)+\kappa $
其中，$ \kappa $为安全参数。
（2）伪随机函数选择
选取基于 FourQ 椭圆曲线的 Diffie-Hellman 伪随机函数，其安全性基于 OMGDH （One-More Gap Diffie-Hellman）困难性假设。
（3）Merkle树构建
选择密码学哈希函数$ {H}_{M}\colon \{0，1{\}}^{*}\rightarrow \{0，1{\}}^{2\kappa } $，用于生成数据完整性的认证路径，并基于该函数对数据集 D 构建Merkle树。

4.1.2 扩展原始数据集和完整性验证

（1）哈希值绑定
对数据集$ {{{{U}}_{\mathrm{A}}}，{U}}_{\mathrm{B}} $每个原始元素$ {{x}}_{{i}} $与其哈希值$ {{h}}_{{i}}={{H}}_{{M}}\left({{x}}_{{i}}\right)\text{进行} $拼接，形成增强元素$ {x}_{{i}}^{{*}}={{x}}_{{i}}||{{h}}_{{i}} $。以此确保解密后可以验证数据完整性。
（2）数据集扩展
按照算法 1 所述流程，生成共享扩展因子z，对每个增强元素$ {x}_{{i}}^{\mathrm{*}} $计算其扩展元素$ {z}\cdot {x}_{{i}}^{\mathrm{*}} $，结合原始增强元素构建扩展数据集 SA（服务端 A）、SB（客户端 B）。
算法1　数据集扩展
输入　元素集合$ {{U}}_{{{\mathrm{A}}}}=\{{{x}}_{1}，{{x}}_{2}，\cdots ，{{x}}_{{n}}\} $、$ {{U}}_{{{\mathrm{B}}}}=\{{{y}}_{1}， {{y}}_{2}，\cdots ， {{y}}_{{m}}\} $
输出　共享扩展因子z
1. 计算元素比值
　　 $ {{a}}_{1}=\left[\dfrac{\max ({{S}}_{\mathrm{A}})}{\min ({{S}}_{\mathrm{A}})}\right]， {{a}}_{2}=\left[\dfrac{\max ({{S}}_{\mathrm{B}})}{\min ({{S}}_{\mathrm{B}})}\right] $
2. 秘密共享
　　服务端A和客户端B通过算术秘密共享比较$ {a}_{1} $和$ {a}_{2}\text{大小} $。计算差值$ \langle {a}\rangle =\langle {{a}}_{2}\rangle -\langle {{a}}_{1}\rangle $，提取最高有效位$ \langle {b}\rangle =\mathrm{MSB}(\langle {a}\rangle ) $。双方生成随机盲化因子${\epsilon }={{\epsilon }}_{\mathrm{A}}+{{\epsilon }}_{\mathrm{B}} $，计算共享扩展因子
　　 $ \langle {z}\rangle =\langle {b}\rangle \cdot \langle {{a}}_{1}\rangle +(1-\langle {b}\rangle )\cdot \langle {{a}}_{2}\rangle +\langle \mathrm{\epsilon }\rangle $

4.1.3 服务端A数据预处理

服务端 A 对自身扩展数据集 SA 进行预处理，核心是通过 OPRF、哈希映射、多项式插值及Merkle树构造，生成可外包计算的多项式系数及数据完整性验证所需的认证信息，具体流程如算法 2 所示。
算法2　服务端A数据预处理
输入　扩展元素集合$ {S}_{\rm A} $
输出　多项式系数$ f_{v，j}^{(r)} $及Merkle树认证信息
1. OPRF预处理：生成OPRF密钥$ S $，对每个$ {x}_{i}\in {S}_{\rm A} $计算$ {x}_{i}'={\text{PRF}}_{S}({x}_{i}) $，得到集合$ X'=\{{x}_{1}'，{x}_{2}'，\cdots ，{x}_{2n}'\} $;
2. 哈希处理：使用哈希函数$ {H}_{1}、{H}_{2}、{H}_{3} $将$ \text{集合}X' $映射到哈希表$ {H}_{\rm A} $中（分桶数$ h $，桶容量$ B $），对空桶填充冗余元素以保证哈希表结构一致性;
3. 分区处理：将$ {H}_{\rm A} $垂直划分为$ a $个子表$ {H}_{\rm A}\left[1\right],\cdots, {H}_{\rm A}[a] $，每个子表大小$ \mathrm{为}B'=B/a $;
4. 多项式插值：对每个子表$ {H}_{\rm A}[v] $构造多项式:
$ p_{v}^{(r)}(x)=\mu \prod \limits_{s\in [B]}(x-{V}_{s}) $
其中$ ，\mu $为随机数，${V}_{s} $为子表 $ {H}_{\rm A}[v] $中的元素，生成多项式系数集合$ f_{v，j}^{(r)} $;
5. 构造Merkle树：为每个子表$ {H}_{\rm A}[v] $生成Merkle树$ {{\mathrm{MT}}}_{\rm A}[v] $，记录其根哈希$ {{\mathrm{Root}}}_{\rm A}[v] $;
6. 数据上传云服务器：将多项式系数集合、各子表对应的Merkle树$ {{\mathrm{MT}}}_{\rm A}[v] $和根哈希$ {{\mathrm{Root}}}_{\rm A}[v] $上传至云服务器$ {\mathrm{C}} $。

4.1.4 客户端B数据预处理

客户端 B 对自身扩展数据集 SB 进行预处理，核心是通过 OPRF、布谷鸟哈希、窗口化处理及同态加密，生成可发送至云服务器的密文集合，具体流程如算法 3 所示。
算法3　客户端B数据预处理
输入　扩展元素集合$ {S}_{\rm B} $
输出　同态加密结果$ {\mathrm{Enc}}(y'') $
1. OPRF预处理：从服务端$ {\mathrm{A}} $获取OPRF密钥$ S $，对每个$ {y}_{i}\in {S}_{\rm B} $计算:
　　 $ {y}_{i}'={{\mathrm{PRF}}}_{S}({y}_{i})，Y\mathrm{'}=\{{y}_{1}\mathrm{'}，{y}_{2}\mathrm{'},\cdots, {y}_{2{m}}\mathrm{'}\} $
2. 哈希处理：使用布谷鸟哈希算法，通过哈希函数集$ \{{H}_{1}，{H}_{2}，{H}_{3}\} $，将$ 集合Y' $映射到哈希表$ {{\mathrm{H}}}_{{\mathrm{B}}} $中;
3. 窗口化处理：对于哈希表$ {\mathrm{H}}_{\mathrm{B}} $中的每个非空元素$ {y}_{i}' $，计算其二次幂序列：
　　 $ \left\{({y}_{i}{)}^{{{2}^{1}}}，({y}_{i}{)}^{{{2}^{2}}}，\cdots ，({y}_{i}{)}^{{{2}^{k}}}\right\} $
其中，$ {k}=\log \log 2{n} $。
4. SIMD编码及同态加密：采用BFV方案的SIMD编码技术，将$ {H}_{\rm B} $中对应的幂次打包成一个明文向量，对每个打包后的明文向量进行加密，得到密文集合$ {\{{c}}_{{i}}\} $并发送至云服务器$ {\mathrm{C}} $。

4.1.5 云服务器计算

云服务器 C 接收服务端 A 上传的多项式系数及客户端 B 发送的密文集合后，核心执行多项式同态评估任务，计算得到对应密文结果，具体流程如算法 4 所示。
算法4　云服务器计算
输入　多项式系数$ f_{v，j}^{(r)} $、密文集合$ {\{{c}}_{{i}}\} $
输出　同态计算结果集合$ {{c}}_{v}={\mathrm{Enc}}({p}_{v}({y}^{'})) $
多项式评估：对每个分桶$ v\in \left[a\right]，执行以下操作： $
1. 加载多项式$ {p}_{v}(x)=\sum \limits_{j=0}^{N}f_{v，j}^{(r)}{x}^{j} $的系数；
利用Horner法则对密文集合$ {\{{c}}_{{i}}\} $进行同态计算
2. 输出密文结果$ {\boldsymbol{c}}_{v}={\mathrm{Enc}}({p}_{v}({y}^{'})) $。

4.1.6 客户端B进行解密

客户端 B 接收云服务器 C 返回的密文集合后，核心执行解密操作获取交集初步结果，并通过完整性验证，确保结果未被篡改，具体流程如算法 5 所示。
算法5　客户端B进行解密
输入　云服务器返回的密文集合$ \{{\boldsymbol{c}}_{v}={\mathrm{Enc}}({p}_{v}({y}^{'}))\}_{v=1}^{a} $
输出　交集结果$ U $及验证哈希$ \{{h}_{i}\}_{i=1}^{t} $
1. 解密处理：对每个密文$ {\boldsymbol{c}}_{v} $执行解密:
　　 $ {d}_{v}\leftarrow {\mathrm{Dec}}({\boldsymbol{c}}_{v}) $
若$ {d}_{v}=0 $，则对应元素$ y\in {S}_{\rm A}\cap {S}_{\rm B} $，构成交集$ U $;
2. 结果验证：通过检查元素与其扩展元素的倍数关系检测结果是否被篡改。对于正确计算的交集结果，原始元素与其对应的扩展元素应同步存在或同步不存在；若云服务器 C 篡改部分结果，将破坏该倍数关系，从而被检测到。
3. 完整性验证：随机选择$ t $个元素$ {u}_{i}\in U $，对其进行OPRF处理后映射到哈希表$ {H}_{y}' $，计算:
　　 $ {h}_{i}={H}_{{\mathrm{M}}}({H}_{y}'[{u}_{i}])，\forall i\in [t] $
其中，$ {H}_{{\mathrm{M}}} $为Merkle树哈希函数;
4. 验证请求：将$ \{{h}_{i}\}_{i=1}^{t} $发送至云服务器$ {\mathrm{C}} $请求获取对应的Merkle树验证路径。

4.1.7 生成Merkle路径及验证

云服务器$ {\mathrm{C}} $根据客户端$ \mathrm{B} $提供的哈希值生成路径证明$ {\text{π} }_{\mathrm{v}} $，并将该路径证明发送至客户端$ \mathrm{B} $。
客户端$ \mathrm{B} $使用云服务器$ {\mathrm{C}} $提供的路径证明$ {\pi }_{v} $和服务器$ {\mathrm{A}} $上传的Merkle树根哈希$ {{\mathrm{Root}}}_{\rm A}[v] $进行对比，若比对一致，则可确保云服务器C未篡改结果。验证过程通过以下函数实现:
$ {\mathrm{VerifyMerklePath}}({h}_{i}\text{，}{\pi }_{v}\text{，}{{\mathrm{Root}}}_{\rm A}[v])\rightarrow \{{\mathrm{True}}\text{，}{\mathrm{False}}\} $

4.2 协议安全性证明

本节首先证明客户端可以检测云服务器计算过程中的恶意行为，接着基于现实—理想模型证明本协议的安全性。
定理 1　本协议中，客户端能够检测云服务器计算过程中的恶意行为。
客户端 B 解密云服务器发送的交集密文，其检测概率接近 1。
证明　若云服务器正确返回交集密文，客户端 B 解密后，可利用交集结果与其扩展元素的倍数关系及Merkle树进行检测，若Merkle树认证路径匹配，则可判定对应元素为交集元素。同时，客户端 B 可在Merkle树中找到任意一个交集元素对应的认证路径。若云服务器篡改交集密文或计算结果，客户端 B 解密得到的结果将为随机值，无法通过验证。
定理2　基于现实—理想模型的不可区分性，本协议是安全的。
本定理的安全证明基于现实—理想不可区分性，针对协议中3种可能的敌手行为，分别构造对应的模拟器。
证明（1）　敌手攻击云服务器情形。对于在现实模型中操作的任意攻击者$ \mathcal{A} $，理想模型中存在一个模拟器$ \text{Sim}_{{\mathrm{PSI}}}^{{\mathrm{C}}} $，可控制云服务器C。模拟器$ \text{Sim}_{{\mathrm{PSI}}}^{{\mathrm{C}}} $在理想模型中的输出，与攻击者$ \mathcal{A} $在现实模型中的输出是不可区分的。
1）模拟器$ \text{Sim}_{{\mathrm{PSI}}}^{{\mathrm{C}}} $获取服务端A处获取多项式系数$ f_{v，j}^{(r)} $和Merkle树$ {{\mathrm{MT}}}_{{\mathrm{A}}}[v] $以及客户端B处获取密文集合$ {{c}}_{{i}}=\{\mathrm{Enc}({y}^{{{\mathrm{'}}^{2\mathrm{i}}}})\}_{{i}=1}^{\log {N}} $。
2）模拟器$ \text{Sim}_{{\mathrm{PSI}}}^{{\mathrm{C}}} $生成虚拟多项式系数{$ {{f_{v，j}^{(r)}}}^{*} $} 和虚拟Merkle树$ {{{{\mathrm{MT}}}_{{\mathrm{A}}}}[v]}^{*} $，并将其上传至云服务器C。由于真实多项式系数$ f_{v，j}^{(r)} $由随机数$ \mu 加密 $隐藏，因此其与虚拟项式系数{$ {{f_{v，j}^{(r)}}}^{*} $}在统计上无法区分；虚拟Merkle树$ {{{{\mathrm{MT}}}_{{\mathrm{A}}}}[v]}^{*} $通过抗碰撞哈希生成，与真实Merkle树$ {{\mathrm{MT}}}_{{\mathrm{A}}}\left[v\right]计算上不可 $区分；虚拟密文$ {c}^{*} $ 与真实计算结果密文$ c $因RLWE问题的困难性假设，在计算上不可区分。因此$ \text{Sim}_{{\mathrm{PSI}}}^{{\mathrm{C}}}的输出 $和$ \mathrm{V}\text{iew}_{{\mathrm{PSI}}}^{\mathrm{{C}}} $不可区分（攻击者$ \mathcal{A} $在现实模型中获取的云服务器视图）。
证明（2）　敌手攻击服务端A情形。对于在现实模型中操作的任意攻击者$ \mathcal{A} $，理想模型中存在一个模拟器$ \text{Sim}_{{\mathrm{PSI}}}^{\mathrm{A}} $，可控制服务端A。模拟器$ \text{Sim}_{{\mathrm{PSI}}}^{\mathrm{A}} $在理想模型中的输出，与攻击者$ \mathcal{A} $在现实模型中的输出是不可区分的。
1）模拟器$ \text{Sim}_{\text{PSI}}^{\mathrm{A}} $获取哈希参数$ ({H}_{1}，{H}_{2}， {H}_{3}， h，B) $、分区参数$ a $、构建Merkle树的哈希函数$ {H}_{{\mathrm{M}}} $。
2）模拟器$ \text{Sim}_{\text{PSI}}^{\mathrm{A}} $模拟OPRF协议，输入伪造集合$ {S}_{\rm A}' $，得到输出$ {x}_{{\mathrm{im}}}'={\mathrm{PR}}{{\mathrm{F}}}_{s}({x}_{{\mathrm{im}}}) $，基于OPRF的伪随机性和离散对数假设的不可预测性，可保证${\mathrm{ PR{F}}}_{s}\left({x}_{{\mathrm{im}}}\right)在统计上 $均匀分布且不可区分。对$ {x}_{{\mathrm{im}}}' $进行哈希、分区处理后获得的多项式$ P_{v}^{(r)}({x}_{{\mathrm{im}}}) $，在服务端A的视角中均匀分布且计算上不可区分。对于没有密钥PRF密钥S和随机值$ \mu $的云服务器C来说，该多项式同样均匀分布且计算上无法区分。因此$ \text{Sim}_{\text{PSI}}^{\mathrm{A}}的输出 $和$ \mathrm{Vi}\text{ew}_{\text{PSI}}^{\mathrm{A}} $不可区分。
3）若模拟器$ \text{Sim}_{\text{PSI}}^{\mathrm{A}} $生成虚假的多项式系数$ f_{v，j}^{(r)} $，客户端B解密后获得的结果为随机值，进而导致验证失败，客户端B将拒绝接收该结果。
4）若模拟器$ \text{Sim}_{\text{PSI}}^{\mathrm{A}} $生成虚假的Merkle树根，客户端B解密后无法匹配正确Merkle认证路径，导致验证失败，进而拒绝接收该结果。
证明（3）　敌手攻击客户端B情形。对于在现实模型中操作的任何攻击者$ \mathcal{A} $，理想模型中存在一个模拟器$ \text{Sim}_{\text{PSI}}^{\mathrm{B}} $，可控制客户端B。模拟器$ \text{Sim}_{\text{PSI}}^{\mathrm{B}} $在理想模型中的输出，与攻击者$ \mathcal{A} $在现实模型中的输出是不可区分的。
1）模拟器$ \text{Sim}_{\text{PSI}}^{\mathrm{B}} $获取哈希参数$ ({H}_{1}，{H}_{2}， {H}_{3}， h，B) $、OPRF密钥$ S $、全同态加密参数、服务端A的根哈希$ {{\mathrm{Root}}}_{\rm A}[v] $。
2）模拟器$ \text{Sim}_{\text{PSI}}^{\mathrm{B}} $模拟OPRF协议，输入伪造集合$ {S}_{\rm B}' $，得到输出$ {y}_{{\mathrm{im}}}'={\mathrm{PR{F}}}_{S}({y}_{{\mathrm{im}}}) $，由于OPRF协议的伪随机性与不可预测性，可保证$ {\mathrm{PR{F}}}_{S}\left({y}_{{\mathrm{im}}}\right)在统计上 $均匀分布且不可区分。对$ {y}_{{\mathrm{im}}}' $进行哈希、批处理、同态加密后获得的$ {\mathrm{Enc}}(y_{{\mathrm{im}}}^{*}) $，在客户端B视角中均匀分布且计算中不可区分。对于没有密钥PRF密钥$ S $和同态解密密钥的云服务器C，基于FHE的语义安全性，$ \text{Sim}_{\text{PSI}}^{\mathrm{B}} $生成的密文同样均匀分布且计算上无法区分的。因此$ \text{Sim}_{\text{PSI}}^{\mathrm{B}} $的输出和$ \mathrm{Vi}\text{ew}_{\text{PSI}}^{\mathrm{B}} $不可区分。

5 效率分析

5.1 理论分析

（1）通信复杂度
服务端 A 需要上传多项式系数和Merkle树根哈希。上传多项式系数的总复杂度为O(a⋅B′)；对哈希表分区得到a个子表，上传Merkle树根哈希的通信复杂度为O(a)，即常数级复杂度。a⋅B′与服务端 A 的集合大小n呈线性正相关，故其通信复杂度可简化为O(n)。客户端 B 对加密数据采用单指令多数据编码后，发送给云服务器 C 的通信复杂度为O(m)。云服务器 C 返回加密结果的通信复杂度亦可简化为O(n)。在验证阶段，客户端 B 对k个交集元素求哈希值并上传，通信复杂度为O(k)；云服务器 C 返回Merkle树路径证明的通信复杂度为O(k⋅logN)。因此，本协议的总通信复杂度为O(n)（k远小于n、m，可忽略），整体呈线性复杂度。
（2）计算复杂度
令$ |{S}_{{\mathrm{A}}}|=n，|{S}_{{\mathrm{B}}}|=m $，在预处理阶段，服务器A中每个元素进行一次PRF运算，时间复杂度为$ O(n) $，对元素进行哈希分桶与冗余填充，将n个元素映射到对应哈希桶中，时间复杂度为$ O(n) $，利用拉格朗日插值法进行多项式插值计算的时间复杂度为$ O({B}^{2}/a) $，构建Merkle树的计算复杂度为$ O(\log B/a) $，合计计算复杂度为$ O(n+{B}^{2}/a) $。客户端B在进行OPRE预处理阶段的时间复杂度为$ O(m) $，采用布谷鸟哈希插入将元素插入哈希表的时间复杂度为$ O(m) $，若SIMD的并行参数设置为$ t $，可将时间计算复杂度降低到$ O((m/t)\cdot {\mathrm{PK}}) $($ {\mathrm{PK}} $表示公钥密码原语)。客户端B解密与验证阶段，若解密n个密文，验证$ t $个元素的Merkle路径，时间复杂度为$ O(n+t\cdot \log B') $，解密与验算的时间复杂度远低于同态加密的过程，因此，客户端B的总时间复杂度为$ O((m/t)\cdot {\mathrm{PK}}) $。云服务器C对每个分桶进行多项式求值的复杂度为$ O(B\cdot \log N) $(其中同态乘法深度为$ \log N $)，默克尔数路径生成的总时间复杂度为$ O(t\cdot \log B') $，因此，其总时间复杂度为$ O(n) $。本协议在n > > m时，效率达到最优，适用于服务器—客户端模式。

5.2 实验分析

5.2.1 实验性能评估

本文实验环境为：Ubuntu 22.04.3 LTS，Intel (R) Core i5-8265U CPU @ 1.60GHz，4GB RAM。本文基于 C++ 语言实现了半可信云辅助环境下可验证隐私集合求交协议，其中同态加密部分通过微软 SEAL 库的 BFV 加密方案实现，多项式计算基于 NTL 库实现。实验测试数据集由长度为 64 byte的随机大小写字母组成的字符串构成，大数据集的集合大小为216~220，小数据集集合大小固定为212。本协议的布谷鸟哈希算法参照 Pinkas 等[43] 的参数选择，计算安全参数κ=128，统计安全参数λ=40。实验评估分别统计了协议3个参与方的计算开销和通信开销，结果如表1 所示。表2 列出了云辅助隐私集合求交协议的性能对比。
表 1 性能评估结果

Table 1 Result of performance evaluation

数据集大小 计算开销/s 总计算开销/s 通信开销/KB
服务端A 客户端B 云计算
216 1.08 0.72 0.447 2.26 20.1
217 2.5 0.81 0.473 3.78 36.34
218 4.1 0.849 0.516 5.46 68.7
219 7.04 0.976 0.585 8.56 133.62
220 13.8 1.2 0.76 15.76 263.5
表 2 云辅助隐私集合求交协议性能对比

Table 2 Performance comparison of cloud-assisted PSI protocols

协议 抗半
可信云		 数据
外包		 可验证 计算
复杂度		 通信
复杂度
Liu等[11] 否 是 否 ${O}({c}^{2}) $ ${O}(c) $
Qiu等[14] 否 是 否 ${O}(c) $ ${O}(c) $
Kerschbaum等[33] 否 否 否 ${O}({c}^{2}) $ ${O}({c}^{2}) $
Zheng等[13] 否 是 是 ${O}(c) $ ${O}(c) $
O-PSI[15] 是 是 否 ${O}({c}^{2}) $ ${O}(c) $
EO-PSI[15] 是 是 否 ${O}(c) $ ${O}(c) $
Jiang等[35] 是 是 是 ${O}({c}{\mathrm{log}}c ) $ ${O}(c) $
本文协议 是 是 是 ${O}(c) $ ${O}(c) $

5.2.2 实验性能对比

将本文方案与 Abadi等[15]的 EO-PSI 方案和 Pinkas 等[44]的 OPPRF-PSI 方案进行了对比，其中客户端数据集大小固定为212服务端规模从216扩展至220。由图4 可知，本文提出的 PSI 协议在两方数据量不平衡的场景下，运行时间具有绝对优势；在一方数据量达到220时，运行时间仅需 15.76 s，相较 EO-PSI 方案有了显著提升。
图 4 不同数据规模下各方案运行时间对比

Fig.4 Comparison of running time of each scheme under different data scales

6 结束语

隐私集合求交是安全多方计算领域的研究热点，具有广泛的实际应用场景。本文将OPRF与同态加密相结合，设计了一种半可信云环境下可验证隐私集合求交协议。本协议尤其适用于一方数据量大、另一方数据量较小且计算能力较弱的客户—服务端场景，且客户端可对交集元素进行验证，确保云服务器未篡改计算结果。在未来的工作中，可进一步研究多参与方隐私集合求交协议，并探索抵抗恶意云服务器攻击的优化方案。

References

Publishing order | Descend order by publishing year | Descend order by cited within
1
Morales D, Agudo I, Lopez J. Private set intersection: a systematic literature review[J]. Computer Science Review, 2023, 49, 100567.

DOI

2
Cui H R, Liu T Y, Yu Y A. survey on private set intersection[J]. Information Security and Communications Privacy, 2019, (3): 48- 67.

3
Yao A C. How to generate and exchange secrets[C]//Proceedings of the 27th Annual Symposium on Foundations of Computer Science (SFCS 1986). Piscataway: IEEE Press, 1986: 162-167.

4
Meadows C. A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party[C]//Proceedings of the 1986 IEEE Symposium on Security and Privacy. Piscataway: IEEE Press, 1986: 134.

5
Huberman B A, Franklin M, Hogg T. Enhancing privacy and trust in electronic communities[C]//Proceedings of the 1st ACM Conference on Electronic Commerce. New York: ACM, 1999: 78-86.

6
Miyaji A, Nakasho K, Nishida S. Privacy-preserving integration of medical data: a practical multiparty private set intersection[J]. Journal of Medical Systems, 2017, 41 (3): 37.

DOI

7
Ion M, Kreuter B, Nergiz E, et al. Private intersection-sum protocol with applications to attributing aggregate ad conversions[R]. Tech. Rep. 738, 2017.

8
Lv S Y, Ye J H, Yin S J, et al. Unbalanced private set intersection cardinality protocol with low communication cost[J]. Future Generation Computer Systems, 2020, 102, 1054- 1061.

DOI

9
Kales D, Rechberger C, Schneider T, et al. Mobile private contact discovery at scale[C]//Proceedings of the 28th USENIX Security Symposium. Santa Clara, CA, USA: USENIX Association, 2019: 1447-1464.

10
Kerschbaum F. Collusion-resistant outsourcing of private set intersection[C]//Proceedings of the 27th Annual ACM Symposium on Applied Computing. New York: ACM, 2012: 1451-1456.

11
Liu F, Ng W K, Zhang W, et al. Encrypted set intersection protocol for outsourced datasets[C]//Proceedings of the 2014 IEEE International Conference on Cloud Engineering. Piscataway: IEEE Press, 2014: 135-140.

12
Kamara S, Mohassel P, Raykova M, et al. Scaling private set intersection to billion-element sets[M]//Financial Cryptography and Data Security. Berlin, HeidelbergSpringer2014: 195-215.

13
Zheng Q J, Xu S H. Verifiable delegated set intersection operations on outsourced encrypted data[C]//Proceedings of the 2015 IEEE International Conference on Cloud Engineering. Piscataway: IEEE Press, 2015: 175-184.

14
Qiu S, Liu J Q, Shi Y F, et al. Identity-based private matching over outsourced encrypted datasets[J]. IEEE Transactions on Cloud Computing, 2018, 6 (3): 747- 759.

DOI

15
Abadi A, Terzis S, Metere R, et al. Efficient delegated private set intersection on outsourced private datasets[J]. IEEE Transactions on Dependable and Secure Computing, 2019, 16 (4): 608- 624.

DOI

16
Agrawal R, Evfimievski A, Srikant R. Information sharing across private databases[C]//Proceedings of the 2003 ACM SIGMOD International Conference on on Management of Data - SIGMOD '03. New York: ACM, 2003: 86.

17
Cho C, Dachman-Soled D, Jarecki S. Efficient concurrent covert computation of string equality and set intersection[M]//Topics in Cryptology - CT-RSA 2016. ChamSpringer International Publishing, 2016: 164-179.

18
Manulis M, Pinkas B, Poettering B. Privacy-preserving group discovery with linear complexity[M]//Applied Cryptography and Network Security. Berlin, HeidelbergSpringer, 2010: 420-437.

19
Rosulek M, Trieu N. Compact and malicious private set intersection for small sets[C]//Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2021: 1166-1181.

20
De cristofaro E, Kim J, Tsudik G. Linear-complexity private set intersection protocols secure in malicious model[M]//Advances in Cryptology - ASIACRYPT 2010. Berlin, HeidelbergSpringer, 2010: 213-231.

21
Ateniese G, De Cristofaro E, Tsudik G. (if) size matters: size-hiding private set intersection[M]//Public Key Cryptography – PKC 2011. Berlin, HeidelbergSpringer2011: 156-173.

22
Dong C Y, Chen L Q, Wen Z K. When private set intersection meets big data: an efficient and scalable protocol[C]//Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security - CCS '13. New York: ACM, 2013: 789-800.

23
Pinkas B, Schneider T, Zohner M. Scalable private set intersection based on OT extension[J]. ACM Transactions on Privacy and Security, 2018, 21(2): 1-35

24
Kolesnikov V, Kumaresan R, Rosulek M, et al. Efficient batched oblivious PRF with applications to private set intersection[C]//Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2016: 818-829.

25
Pinkas B, Rosulek M, Trieu N, et al. SpOT-light: lightweight private set intersection from sparse OT extension[M]//Advances in Cryptology – CRYPTO 2019. ChamSpringer International Publishing, 2019: 401-431.

26
Brakerski Z, Gentry C, Vaikuntanathan V. （leveled） fully homomorphic encryption without bootstrapping[J]. ACM Transactions on Computation Theory, 2014, 6 (3): 1- 3.

DOI

27
Gentry C, Sahai A, Waters B. Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based[M]//Advances in Cryptology – CRYPTO 2013. Berlin, HeidelbergSpringer, 2013: 75-92.

28
Cheon J H, Kim A, Kim M, et al. Homomorphic encryption for arithmetic of approximate numbers[M]//Advances in Cryptology – ASIACRYPT 2017. ChamSpringer International Publishing, 2017: 409-437.

29
Freedman M J, Nissim K, Pinkas B. Efficient private matching and set intersection[M]//Advances in Cryptology - EUROCRYPT 2004. Berlin, Heidelberg: Springer, 2004: 1-19.

30
Freedman M J, Hazay C, Nissim K, et al. Efficient set intersection with simulation-based security[J]. Journal of Cryptology, 2016, 29 (1): 115- 155.

DOI

31
Chen H, Laine K, Rindal P. Fast private set intersection from homomorphic encryption[C]//Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. Dallas, TX, USA: ACM, 2017: 1243-1255.

32
Chen H, Huang Z C, Laine K, et al. Labeled PSI from fully homomorphic encryption with malicious security[C]//Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2018: 1223-1237.

33
Kerschbaum F. Outsourced private set intersection using homomorphic encryption[C]//Proceedings of the 7th ACM Symposium on Information, Computer and Communications Security. New York: ACM, 2012: 85-86.

34
Wang Q, Zhou F C, Xu J, et al. Tag-based verifiable delegated set intersection over outsourced private datasets[J]. IEEE Transactions on Cloud Computing, 2022, 10 (2): 1201- 1214.

DOI

35
Jiang G S, Zhang H L, Lin J, et al. Optimized verifiable delegated private set intersection on outsourced private datasets[J]. Computers & Security, 2024, 141, 103822.

DOI

36
Ishai Y, Kilian J, Nissim K, et al. Extending oblivious transfers efficiently[M]//Advances in Cryptology - CRYPTO 2003. Berlin, HeidelbergSpringer2003: 145-161.

37
Kolesnikov V, Kumaresan R. Improved OT extension for transferring short secrets[M]//Advances in Cryptology – CRYPTO 2013. Berlin, HeidelbergSpringer, 2013: 54-70

38
Rivest R L, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems[J]. Communications of the ACM, 1978, 21 (2): 120- 126.

DOI

39
Elgamal T. A public key cryptosystem and a signature scheme based on discrete logarithms[J]. IEEE Transactions on Information Theory, 1985, 31 (4): 469- 472.

DOI

40
Paillier P. Public-key cryptosystems based on composite degree residuosity classes[M]//Advances in Cryptology — EUROCRYPT ’99. Berlin, HeidelbergSpringer, 2007: 223-238.

41
Boneh D, Goh E J, Nissim K. Evaluating 2-DNF formulas on ciphertexts[M]//Theory of Cryptography. Berlin, HeidelbergSpringer, 2005: 325-341.

42
Gentry C. Fully homomorphic encryption using ideal lattices[C]//Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing. New York: ACM, 2009: 169-178.

43
Pinkas B, Schneider T, Segev G, et al. Phasing: private set intersection using permutation-based hashing[C].Proceedings of the 24th USENIX Security Symposium. Washington, USA, 2015: 515-530.

44
Pinkas B, Schneider T, Tkachenko O, et al. Efficient circuit-based PSI with linear communication//Proceedings of the Public Key Cryptography - PKC 2019. Beijing, China, 2019: 122-153.

Options
Outlines

/

〈 〉

Website Copyright © Editorial Office of Journal of Cybersecurity.
Tel: 010-89061756/89061778　
E-mail：wlkjaqkxxb@caasse.cn
Powered by Beijing Magtech Co. Ltd,.

京ICP备16032046号-20