安全求交集(PSI)基本原理

安全求交集（PSI）

1、安全求交集（PSI）界说

Alice 有集合 X，Bob 有集合 Y，经 PSI 计算后，Alice 得到X 和 Y 的交集，且无其他信息。
要求：

• Alice 无法知晓不属于 X ∩ Y 的 Bob 的元素。
  
• 若 Alice 试图获取 Bob 的非匹配数据，她不会成功。
  
• 可证安全。
  

2、PSI功能和分类

Two-Party Semi-Honest PSl

Two-Party Semi-Honest PSl，即两方半老实安全求交集，是最常用基础的PSI。

• 仅针对求交集：交集被披露，非交集部门被保密。
  
• 仅适用于两方：如 Alice 和 Bob
  
• 仅具备半老实安全性：攻击者严酷遵循协议，但对另一方的秘密信息感到好奇 。
  

Two-Party Semi-Honest PSl 应满足的要求：
（1）隐蔽非交集元素（隐蔽）

• 采用暗码学安全的 “隐蔽” 方式。
  
• 当两个元素不相等时，必须添加某种 “干扰信息”，使得无法穷举计算出不匹配的元素。
  

（2）计算交集元素（比较）

• 当两个元素相等时，应能以高效的方式揭示它们相等。
  

（3）效率

• 安全求交集（PSI）协议需适用于大规模应用 。
  

Method1：A Naive PSI based on Hash

A Naive PSI based on Hash，即基于哈希的简朴安全求交集（PSI）

• 基本思绪：先哈希，再匹配
  
  
  
  • 暗码学哈希：单向性、抗碰撞性
    
  
  
• 隐蔽：利用单向暗码学哈希函数
  
• 比较：相同输入的哈希输出是一样的
  
• 效率：哈希计算速度快
  
• 题目：高熵输入数据集是可行的，比如长度不限的随机字符串；然而，在大多数现实应用中，输入数据集是低熵的，比如身份标识、电话号码等；容易受到暴力破解攻击 。
  

Method 2：Based on Diffie-Hellman Key Exchange

Based on Diffie-Hellman Key Exchange，即基于 Diffie-Hellman 的安全求交集（PSI）[3]

• 基本思绪：利用交换律特性举行 “双重加密”。
  
• 隐蔽：通过 “加密” 隐蔽元素。
  
• 比较：借助交换律特性。
  
• 效率：通信成本呈线性关系；还是安全求交集（PSI）的主流实现方式；在椭圆曲线等暗码原语上有许多改进 。
  

Diffie-Hellman Key Exchange
   Diffie-Hellman 密钥交换是一种安全的密钥协商方法，基于该方法的 PSI 利用其特性实现数据隐私掩护下的交集计算。双重加密结合交换律可在隐蔽数据的同时判断交集，线性的通信成本使其在现实应用中较为高效，且随着暗码技能发展，在基础原语上的改进让其安全性和性能不断提拔，常用于多方数据隐私交互场景 。
  

• 离散对数题目（DLP）：给定 p、g、x 和 y 四个大正整数，假设，其中 p 是一个大质数。给定 y、g、p，怎样求出 x 是一个 “难题”。基于DH的安全求交集所基于的真实假设就是离散对数题目。
  
• 效率：计算是高效的
  
• 隐蔽性：给定 y、g、p，很难求出 x
  
• 比较：加密的先后顺序不影响效果，即
  
  
  
  
• g、x、p 和 y 必要满足一系列暗码学条件，才能让这个难题在暗码学范畴真正难以破解。
  

Method 3：OPRF-based PSI

OPRF-based PSI，即基于不经意伪随机函数（OPRF）的安全求交集（PSI）

• 协议 [5]
  
  
  
  • 发送方对本身的数据集合计算一个 “秘密” 函数，然后将效果发送给接收方。
    
  • 接收方通过与发送方交互，对本身的数据集合也计算这个 “秘密” 函数。
    
  • 接收方将从发送方收到的效果与本身计算的效果举行比较。
    
  
  
• 隐蔽性：“秘密” 函数，发送方无法知晓接收方的数据，接收方也无法知晓这个 “秘密” 函数。
  
• 比较：颠末 “秘密” 函数处理后的数据可以举行比较。
  
• 效率：大多数操作是如哈希和对称密钥加密这样的高效暗码学操作，仅涉及少量公钥基础设施（PKI）操作。
  

Oblivious Pseudo-Random Functions (OPRF)
Oblivious Pseudo-Random Functions，即不经意伪随机函数（OPRF）

• OPRF：给定发送方的密钥 k 和接收方的输入元素 e
  
  
  
  • 计算  
    
    
    
  • 接收方知道 
    
     的输出，但不知道 k。
    
  • 发送方对输出或输入元素 e 一无所知。
    
  
  
• 用于安全求交集（PSI）的 OPRF
  
  
  
  • 接收方利用发送方提供的密钥 k，对本身的数据集合计算 OPRF。
    
    
    
    • 接收方不知道发送方的密钥 k。
      
    • 发送方不知道接收方的数据集合。
      
    
    
  • 发送方对本身的数据集合计算 OPRF，然后将效果发送给接收方。
    
  • 接收方通过比较发送方的效果和本身计算的 OPRF 效果，找出交集。
    
  
  

提高效率：Cuckoo Hashing 和 Simple Hashing思想

• 接收方利用 Cuckoo Hashing 将其元素插入哈希表中。
  
• 发送方利用 Simple Hashing 将其元素插入哈希表中。
  
• 不经意伪随机函数（OPRF）的计算次数和比较次数均有所减少。
  

3、PSI 应用

交集利用

• 动机：安全求交集（PSI）的参与方之间，交集信息可能并非 “共享知识”。交集中的数据属于其他方。比方：爱丽丝在 A 银行和 B 银行都有账户，且均利用她的唯一身份标识注册。A 银行和 B 银行通过安全求交集（PSI）来找出爱丽丝这个共同客户，这样做是否合适？
  
• 挑战：交集 “可用不可见”
  

环境 1：交集内容需保密，但交集元素基数可利用

• 基数指的是交集中元素的数量，仅向授权方披露基数。
  
• 方法
  
  
  
  • 全同态加密（PHE）+ 多项式求值 [8]
    
  • 基于 D 密钥交换并带有肴杂操作的安全求交集（PSI）[20]
    
  
  

环境 2：交集内容需保密，且必要对保密的交集举行后续计算 [9]

• 对交集举行 “加密” 处理，与 “加密” 交集相干的数据用于后续的安全计算。比方，在带有负载的安全求交集（PSI）中，交集本身作为中心效果被隐蔽起来 。
  
• 方法
  
  
  
  • 基于电路的安全求交集（PSI）[9]
    
  • 结合置换和全同态加密（PHE）的基于迪菲 - 赫尔曼（DH）的安全求交集（PSI）[20]
    
  
  

环境 3：交集内容需保密，但仍需利用该交集数据

• 方法
  
  
  
  • 全同态加密安全求交集（FHE-PSI）+ 差分隐私 [10]
    
  • 基于 DH 的安全求交集（DH-PSI）+ 差分隐私
    
  
  

---

多方 PSI

   多方 PSI 旨在多个参与方之间计算数据交集，同时掩护数据隐私。在现实应用中，比如多个机构联合分析数据时，既想得到共同的数据部门，又不渴望自身数据以及与其他方的部门交集被泄漏。全同态加密结合多项式表示，可在密文状态下处理数据以计算交集；不经意三方伪随机函数则通过特殊的函数计算机制，在多方交互中保障数据隐私，防止任意两方间交集信息泄漏 。
  常规多方 PSI

• 动机：必要计算 N 个参与方的数据交集。
  
• 挑战：任意两方之间的交集不能被披露。
  
• 方法：
  
  
  
  • 全同态加密（PHE）+ 多项式表示 [8]
    
  • 不经意三方伪随机函数（OPPRF）[11]
    
  
  

特殊多方 PSI
   特殊多方 PSI 处理的是在多方数据交互场景中，存在部门两方交集需特定披露的环境。比如在不同机构的联合数据处理中，某些特定相助方之间的数据交集要分享给第三方监管机构或其他指定方。由于每种环境的披露要求和参与方需求不同，以是不能利用通用的 PSI 协议，而是要依据详细需求定制协议，以保障数据隐私的同时满足信息披露的特定要求。
  

• 动机：某些两方之间的交集可能必要被计算出来，并披露给特定的一方。
  
• 挑战：详细要求因环境而异；必要定制办理方案。
  
• 方法：根据需求举行定制的 PSI 协议 。
  

---

计算模型

单向模型 [1][2][5]

• 动机：仅一方应获知交集。比方，客户端向新的社交媒体服务提交联系人列表；客户端获知集合交集，而服务器除了客户端输入数据的大小外，无法获取其他信息。
  
• 方法：基于不经意伪随机函数（OPRF）的安全求交集（PSI）等。
  

双向模型 [3]

• 动机：两方都应获知交集；比方，找出两家银行之间的共同用户。
  
• 方法：基于 DH 的安全求交集（PSI）等。
  

外包 / 委托 / 服务器辅助的安全求交集（PSI）：两个客户端在不可信的第三方帮助下，对其外包的数据执行安全求交集计算。

• 动机：参与方无法独立完成安全求交集计算，比方资源受限的设备。
  
• 挑战：第三方仅帮助计算，不能获取终极效果；第三方可能由大型云服务提供商充当（通常假设云服务提供商不会与客户端勾结）；第三方不应获知安全求交集的效果。通常的模式是云服务辅助安全求交集计算，获取加密的匹配效果，并将其发送给客户端，然后客户端对匹配效果举行解密。
  
• 方法：多项式表示 + 全同态加密（PHE）+ 伪随机函数（PRF）[12]
  

---

安全模型

半老实安全的安全求交集（PSI）

• 动机：简朴、高效；大多数已实现的安全求交集（PSI）协议都是半老实的。
  
• 挑战：安全假设过强，仅考虑被动攻击者，即使是攻击者也严酷遵循协议。
  
• 方法：基于 DH、OPRF 等的安全求交集（PSI）[1][2][3][5]。
  

恶意安全的安全求交集（PSI）

• 动机：增强安全性；更符合现实的安全假设，考虑恶意攻击者 。
  
• 挑战：会产生更多的计算和通信开销。
  
• 方法：带有额外验证的安全求交集（PSI）协议 [7][13] 。
  

---

非对称 PSI

   在现实的隐私计算场景中，数据分布往往是不均衡的，如客户端与服务器之间，服务器可能拥有海量数据，而客户端数据量较少。非对称 PSI 针对这种环境设计，常规 PSI 方法在处理数据量差异大的环境时效率低下。基于 ECC - OPRF 的 PSI 通过优化计算计谋，减少不必要的计算；FHE PSI 则利用全同态加密特性，在密文上举行计算，以适应非对称的数据分布，提高计算效率和隐私掩护程度，适用于多种数据规模差异较大的应用场景。
  

• 动机：一方拥有的元素数量远多于另一方。比方，客户端 - 服务器场景，大多数现实应用场景可能必要非对称的安全求交集（PSI） 。
  
• 挑战：常规的安全求交集（PSI）对于非对称的环境效率不高。
  
• 方法：
  
  
  
  • 基于椭圆曲线暗码学（ECC）和不经意伪随机函数（OPRF）的安全求交集（PSI）[21]（思想：缓存较大的集合，在匹配前仅对较小的集合举行 “计算”）
    
  • 全同态加密（FHE）的安全求交集（PSI）[14][15]。
    
  
  

4、PSI和其他隐私计算技能结合

安全求交集 + 差分隐私

   差分隐私是一种严酷的隐私掩护模型，在安全求交集（PSI）中引入差分隐私，可以进一步增强对数据隐私的掩护。在交集利用场景中，添加噪声能防止对手推断出个体数据信息。
  什么是差分隐私（DP）？
通俗地说，差分隐私是一种通过添加噪声的方法，使得很难判断某个元素是否在一个集合中。
环境 1：安全求交集（PSI）的交集利用

• 动机：向交集中添加差分隐私噪声，使得从统计上看交集是 “正确的”，但交集中的任何单个元素都难以通过差分隐私判断是否为两边共有。交集中的单个元素受到差分隐私的掩护；应用于联合营销场景。
  
• 挑战：交集是加密的，一方必要在不破坏保密性的条件下，向交集中正确添加误报（假阳性）和漏报（假阴性）元素。
  
• 方法：
  
  
  
  • 全同态加密安全求交集（FHE-PSI）+ 差分隐私（DP）[10]（效率非常低）
    
  • 基于DH-PSI+ 差分隐私（DP）。
    
  
  

环境 2：提拔性能 [18]

• 通过差分隐私减少填充长度 。
  

安全求交集 + 可信执行环境

   可信执行环境（TEE）是一种硬件和软件技能，能创建一个安全的执行空间，掩护其中的代码和数据免受外部攻击和恶意软件的侵扰。MesaTEE 利用 TEE 的特性，为安全求交集提供了一种开源实现方式。通过生成盐值对数据哈希，在隔离的 TEE 环境中计算交集，保障数据隐私和计算效果的安全性。
  MesaTEE[19]

• 基于可信执行环境（TEE）的安全求交集（PSI）开源办理方案。
  
  
  
  • TEE 生成随机盐值（salt）。
    
  • 各方利用该盐值对数据举行哈希处理，以用于安全求交集计算。
    
  • 在 TEE 中完成安全求交集计算。
    
  • 将效果发送回各方。
    
  
  
• 简朴、高效且灵活。
  
• 与暗码学办理方案不同，其信任根在于可信执行环境（TEE）。
  

5、References

   [1] Benny Pinkas, Thomas Schneider, Michael Zohner. Faster Private Set lntersection based on OT Extension, USENIXSecurity 2014
[2] Benny Pinkas, Thomas Schneider, Michael Zohner, scalable Private Set Intersection Based on OT Extension, ACMTransactions on Privacy and Security,2018
[3] Rakesh Agrawal, Alexandre V. Evfimievski, and Ramakrishnan Srikant, Information sharing across privatedatabases. Proceedings of the 2003 ACM SIGMOD lnternational Conference on Management of Data, 2003
  [4] Emiliano De Cristofaro and Gene Tsudik, Practical private set intersection protocols with linear computationaland bandwidth complexity,lACR Cryptology ePrint Archive,2009:491,2009
  [5] Vladimir Kolesnikov, Ranjit Kumaresan, Mike Rosulek, and Ni Trieu. Efficient batched oblivious PRf withapplications to private set intersection, Proceedings of the 2016 ACM SlGSAC Conference on Computer andCommunications Security,2016
[6] Peter Rindal and phillipp Schoppmann. VOLE-PSl: fast OPRF and circuit-psi from vector-ole, Advances inCryptology-EUROCRYPT2021.2021
[7] Peter Rindal and Srinivasan Raghuraman, Blazing fast PSl from improyed OKVs and subfield VOLE. IACRCryptologyePrintArchive,2022:320.2022
[8] Lea Kissner and Dawn Song, Privacy-Preserving Set Operations, Crypto 2005.[9] Benny Pinkas, Thomas schneider, Oleksandr Tkachenko, and Avishav Yanai., Efficient circuit-based psl withlinear communication.Advances in Cryptology-EUROCRYPT 2019
[10] Bailey Kacsmar , Basit Khurram , Nils Lukas , Alexander Norton , Masoumeh Shafieineiad , Zhiwei Shang, YaseiBaseri , Maryam Sepehri, Simon Ova, florian Kerschbaum, Diferentialy Private Two-Party Set Operations, 2020lEEE European symposium on security and Privacy.
  [11] Vladimir Kolesnikov, Naor Matania, Benny Pinkas, Mike Rosulek, and Ni Trieu. Practical multi-party private setintersection from symmetric-key techniques, Proceedings of the 2017 ACM SIGSAC Conference on Computer andcommunications security,2017
[12] Abadi, Aydin, Sotirios Terzis, Roberto Metere, and changyu Dong. Efficient Delegated Private Set Intersectionon Outsourced Private Datasets, lEEE Transactions on Dependable and Secure Computing, 2017
  [13] Benny Pinkas, Mike Rosulek, Ni Trieu, and Avishay Yanai. PSl from paxos: Fast, malicious private setintersection.Advances in cryptology-EUROCRYPT 2020
  [14] Hao Chen, Kim Laine, Peter Rindal, Fast Private Set intersection from Homomorphic Encryption, ACM CCS 2017
  [15] Hao chen, Zhicong Huang, Kim Laine, Peter Rindal, Labeled psl from Fully Homomorphic Encryption withMalicious security,CCs 2018
[16] Giuseppe Ateniese, Emiliano De Cristofaro, Gene Tsudik. (lf) size Matters: Size-Hiding Private Set IntersectionPKC 2011
[17] Benny Pinkas, Mike Rosulek, Ni Trieu, and Avishay Yanai, Spot-light: Lightweiaht private set intersection fromsparse OT extension.Advances in Cryptology-CRYPTO 2019
  [18] Adam Groce, Peter Rindal, and Mike Rosulek, cheaper Private Set intersection via Differentially PrivateLeakage,POPETS 2019
  [19] MesaTEE,https://github.com/zishen14/mesatee
[20] Mihaela lon, Ben Kreuter, Ahmet Erhan Nergiz, Sarvar Patel, Shobhit saxena, Karn Seth, Mariana Ravkova.D avid Shanahan, Moti Yung, On Deploying Secure Computing: Private intersection-Sum-with-Cardinality, EuroS&2020
[21] Amanda Cristina Davi Resende and Diego de Freitas Aranha, Faster Unbalanced Private Set Intersection,FC2018
  后续更新：利用Poseidon同态加密库 实现 基于全同态加密的安全求交集（FHE-PSI）

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。