我的隐私计算学习——隐私集合求交(1)

这篇具有很好参考价值的文章主要介绍了我的隐私计算学习——隐私集合求交(1)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

笔记内容来自多本书籍、学术资料、白皮书及ChatGPT等工具,经由自己阅读后整理而成。

(一)PSI的介绍

隐私计算关键技术:隐私集合求交(PSI)原理介绍

隐私计算关键技术:隐私集合求交(PSI)的性能扩展

笔记分享 | 组队学习密码学 —— 隐私求交的关键路径及其应用

笔记分享 | 组队学习密码学 —— 隐私求交之不经意的伪随机函数构造

​ 隐私集合求交( Private Set Intersection,PSI)是多方安全计算领域中的经典问题,它要求参与方在互相不公开本地集合的前提下,共同计算得出多个参与方的集合的交集,且不能向任何参与方泄露交集以外的信息。

​ 在纵向联邦学习场景中,PSI 也被称为样本对齐 ( Sample Alignment ) 或者数据库撞库,即各参与方需要首先求出各自的训练样本 ID 集合之间的交集,基于计算得到的训练样本 ID 交集进行后续的纵向联邦模型训练。

样本对齐概念

​ 样本对齐是纵向联邦学习中不可或缺的一环。纵向联邦学习的样本分属于不同的组织,各个组织的样本的覆盖范围各有差异,所以需要找出参与方 A 与参与方 B 共有的训练样本 ID,且除了A和B双方共有的样本 ID(例如,一家银行和另一家电商共同的客户的 ID,可以用手机设备号的哈希值作为客户的 ID 标识,找出交集,以外,不能泄露其他样本 ID 给彼此。这个过程需要用到加密样本 ID 对齐机制。交集的方式一般是通过 Join 键(比如 ID 证件号),这些敏感信息不适合直接进行交集的计算,需要进行签名处理,并且要保障不被破解。样本对齐的方式有多种,例如基于映射的散列算法、比特承诺,基于RSA加密体系的茫然传输等。

​ 隐私集合求交技术通常是基于 ID 来实现交集的计算,即在计算的过程仅通过样本集的 ID 列参与计算,在求得 ID 集合的交集后,再同步相对应的特征标签列给其他参与方或是仅在节点内同步特征列为后续的其他计算做准备。

我的隐私计算学习——隐私集合求交(1),学习,密码学,安全,人工智能

(二)PSI的方法

    1. 基于 Diffie-Hellman 密钥交换的 DH 算法(公钥)

      我的隐私计算学习——隐私集合求交(1),学习,密码学,安全,人工智能

    1. 基于盲签名的 Blind-RSA 算法(公钥)

      以基于 RSA 盲签名和哈希算法的 PSI 技术为例,简单介绍其工作原理:

      我的隐私计算学习——隐私集合求交(1),学习,密码学,安全,人工智能

RSA 计算复杂度较高,协议中 RSA 的计算次数会随着数据量的增大呈线性增长,使得基于 RSA 的求交方法,在数据量较大时会产生性能问题。由于 RSA 盲签名算法在运行时只对一端的数据进行 RSA 加密,使得在求交数据量级差距较大时,可以把数据量较小的一端作为 Client 端,这样可以获得非常大的性能优势。另外,RSA 算法的流程适合并行处理,方便利用并行计算来提升性能。

RSA 盲签名协议能够在恶意对手模型下,为隐私集合求交提供安全保障,但由于非对称加密的次数随比对的数量量的增加呈线性增长,所以无法处理海量数据的隐私集合求交场景。

    1. 基于同态加密的算法

    ​ 比较适合拥有较小集合的一方将数据加密后发送给另一方进行计算,然后将结果返回给加密方进行解密的场景。但实际上,这种原型协议实现起来效率特别差,因为同态加密密文长度都不算太小。另外,同态加密电路的深度随着集合元素数量增加而快速增加,导致方案性能较差。

我的隐私计算学习——隐私集合求交(1),学习,密码学,安全,人工智能

​ 此协议应用相同元素的差为0的原理进行交集判断,使用 HE 算法来完成密文求差操作。为了防止差不为 0 的元素值泄露,每一次求差操作后会乘一个随机数 r。为了提高协议的实际性能,Chen 等人使用了一些优化方法。包括 PSI 领域的 hash、切分技术,还使用了 HE 领域的批处理、分窗、模数转换技术。上面的过程简化下来就是:

我的隐私计算学习——隐私集合求交(1),学习,密码学,安全,人工智能

基于同态加密实现 PSI 的经典论文:

  • [1] Chen, H., Huang, Z., Laine, K., & Rindal, P. (2018). Labeled PSI from Fully Homomorphic Encryption with Malicious Security. Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security.

  • [2] Cong, K., Moreno, R.C., Gama, M.B., Dai, W., Iliashenko, I., Laine, K., & Rosenberg, M. (2021). Labeled PSI from Homomorphic Encryption with Reduced Computation and Communication. Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security.

    1. 基于不经意传输的算法(目前速度最快最流行)

    首先是基于布隆过滤器和 OT 的实现方案,有关布隆过滤器及其变种,可参考上面的布隆/混淆布隆过滤器。

    GBF 与 OT 结合解决 PSI 问题:

    我的隐私计算学习——隐私集合求交(1),学习,密码学,安全,人工智能

    我的隐私计算学习——隐私集合求交(1),学习,密码学,安全,人工智能

    ​ 接下来仍以社交软件的发现共有联系人功能为例,假设服务器端有用户集合 S,客户端有联系人集合 C,客户端通过以下步骤可最终获得双方集合的交集 C ∩ \cap S.

    1. 服务器端、客户端约定用于 B F BF BF 以及 G B F GBF GBF 的相关参数:存储的数组的长度 m,使用的哈希函数集合{ ho,…, ht-1 }。

    2. 服务器端针对集合 S 使用 G B F GBF GBF 进行映射,获得字符串数组 G B F s GBF_s GBFs .

    3. 客户端针对集合 C 使用 B F BF BF 进行映射,获得位数组 B F c BF_c BFc .

    4. 客户端使用 OT 协议从服务器端接收 G B F s GBF_s GBFs 信息,服务器端准备 m 个字符串对(xi,0 ,xi,1) ,其中 xi,0 为随机生成的字符串,xi,1 G B F s [ i ] GBF_{s}[i] GBFs[i]。客户端遍历数组 B F c BF_c BFc 。对于 0 ≤ i ≤ m-1,如果 B F c [ i ] BF_c[i] BFc[i] 值为 0,客户端获得随机字符串;如果 B F c [ i ] BF_c[i] BFc[i] 值为 1,客户端获得 G B F s [ i ] GBF_{s}[i] GBFs[i]。最终,客户端获得的结果为 G B F C ∩ S GBF_{C\cap S} GBFCS .

    5. 客户端遍历集合 C 中的所有元素,使用以下方法利用 G B F C ∩ S GBF_{C\cap S} GBFCS 判断自己所拥有的元素是否在集合 S 中。

      我的隐私计算学习——隐私集合求交(1),学习,密码学,安全,人工智能

    基于不经意传输的 PSI 工作原理:

    • OT:利用不经意传输完成隐私集合求交

    • OT Extension: PSI系列(2)组件 | OT Extension (IKNP)

    ​ 2014 年,Pinkas 等人提出了基于 OT 扩展协议的高效隐私集合求交方案,该方案使用 OT 扩展,传输数据使得通信双方获得一个伪随机函数,并使用此伪随机函数对双方持有的数据进行加密比对。方案主要分为三个阶段来执行,哈希阶段,隐匿传输阶段和求交阶段。在哈希阶段,通信 Alice 和 Bob 把各自持有的数据通过哈希运算均匀分布在一个给定大小的地址空间内,并使用随机数填充空余的哈希位置。在隐匿传输阶段,Bob 根据自己持有数据的比特信息作为选择位,使用 OT 扩展安全地获取 Alice 持有同样比特位置上的伪随机生成数据。最后在求交阶段,Bob 解密伪随机数据,并和自己持有的数据进行比较。

    ​ 2016 年,Kolesnikov 使用批量 OT 扩展传输和布谷鸟哈希实现了更高效的隐私集合求交方案,基于 OT 的隐私集合求交成为性能上仅次于朴素哈希求交技术的隐私集合求交方案。2019 年,Pinkas 等人提出了基于稀疏扩展的隐私集合求交方案,方案首先把秘密信息分成三份,这样在未获取到要求交的数据之前,可以提前随机生成两份秘密信息,以便在离线阶段进行 OT 扩展传输,提前获取伪随机生成函数。在在线阶段,为了避免传输大量的秘密信息,方案使用了多项式技术,把要传输的数据融入多项式,仅传递多项式的参数来代替传输大量数据。根据该方案的测试结果,在要对比的数据量庞大,或者带宽受限制场景下,此方案相较于目前最优的基于 OT 的隐私集合求交方案,提供了更好的性能优势。

    ​ 虽然基于不经意传输的隐私集合求交技术仍然是使用非对称加密技术作为其实现原理,但不经意传输使用有限次非对称加密,来完成任意数量的安全数据传输。基于不经意传输的隐私集合求交方案,是目前研究最为活跃的隐私集合求交方案,对该方案的研究是基于安全性和性能平衡后的一种考量,研究的思路主要在减少非对称加密次数和通信双方传输的数据量。

    1. 基于混淆电路等 MPC 技术的算法

    ​ 使用混淆电路通用框架来计算交集有易扩展特性,这是因为使用通用的多方安全计算协议,计算交集的函数是通过电路实现的,而将计算交集的电路的输出连到其他计算电路作为输入就可以计算交集的大小、交集中元素的和等,而且全部过程都能满足保护输人隐私的要求。这种易于扩展的性质是基于公钥加密或基于不经意传输的 PSI 所没有的,因此其是一种有实际应用价值的方案。

​ 总之,以上方法都可以解决两方的 PSI 问题,当遇到多方 PSI 问题时,它们是通过两两求交集的替代方法来实现“等效的多方 PSI”。这一方法可以降低计算的复杂度,却会带来一个非常严重的安全隐患,即会泄露那些属于两方交集但不属于多方交集的数据。

我的隐私计算学习——隐私集合求交(1),学习,密码学,安全,人工智能

  • 隐私计算关键技术:多方隐私集合求交(PSI)从原理到实现

​ 针对此问题,基于 Freedman 协议提出了一种严格的多方安全 PSI 协议,可以保证除了多方样本 ID 交集信息之外,任何其他信息均不会泄露。多方 PSI 协议的核心思想是将样本 ID 集合编码成特殊的数据结构,即不经意多项式,其中每一个样本 ID 均为不经意多项式的根。利用半同态加密算法对多项式参数进行保护,使多个参与方可以在密文空间下进行多项式求值,同时又无法读取多项式参数的明文。

​ 然而,大整数多项式系数展开和求值的计算复杂度均为 O(n3) ,为了解决这一计算瓶颈,提出了一种基于哈希分桶的优化方法。具体而言,利用哈希分桶技术将 ID 集合均匀映射到若干 ID 分桶中,这里要求各参与方使用相同的哈希函数,以便确保相同的样本 ID 被映射到相同的分桶中。这样一来,只需要进行“桶内计算、桶间合并”即可得到完整的多方 ID 集合的交集。将单个桶内样本数量视为一个常数,算法的计算复杂度可以优化到 O(n) 。


10月份新开了一个GitHub账号,里面已放了一些密码学,隐私计算电子书资料了,之后会整理一些我做过的、或是我觉得不错的论文复现、代码项目也放上去,欢迎一起交流!Ataraxia-github文章来源地址https://www.toymoban.com/news/detail-756592.html

到了这里,关于我的隐私计算学习——隐私集合求交(1)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 密码学证明方案寒武纪大爆发——扩容、透明性和隐私的变革潜力

    前序博客有: ZKP大爆炸 本文主要参考: StarkWare 2023年6月博客 Cambrian Explosion of Cryptographic Proofs----The transformative potential for scalability, transparency, and privacy 2023年3月Eli Ben-Sasson在The 13th BIU Winter School on Cryptography - Blockchain Technologies的分享视频 A Cambrian Explosion of Cryptographic Proofs - E

    2024年02月11日
    浏览(43)
  • 计算机网络安全——密码学入门

            网络安全是指在网络领域、专业领域的网络安全包括在基础计算机网络基础设施中所做的规定,网络管理员采取的策略来保护网络及网络可访问资源免受未经授权的访问,以及对其有效性(或缺乏)的持续不断的监控和测量的结合。 1.1.1 保密性         只有授

    2024年01月19日
    浏览(48)
  • 斯坦福Dan Boneh密码学——02 计算密码与语义安全

    语义安全这块内容实在是被书绕晕了,虽然模型就那么一个,但有各种各样的数学符号交织证明,还有官方深奥的语言表述。第一次看是一知半解的,后面势必还要再返回来精读几遍完善笔记。以篇幅来看,语义安全是密码学中非常重要的一个版块。 计算密码与语义安全 我

    2024年02月08日
    浏览(66)
  • 【密码学】【多方安全计算】Secret Sharing秘密共享浅析

    秘密共享(Secret Sharing)是实现多方安全计算的一种常用方式,MPC当然也可以用混淆电路(Garbled Circuit)实现,本文旨在浅析秘密共享的基本原理,有对混淆电路感兴趣的同学可阅读下一篇博客。 Secret Sharing被称为秘密共享或私密共享,有一个秘密数值D,数值D被分解为n个片

    2024年02月15日
    浏览(39)
  • 区块链学习二———密码学原理

    比特币中使用到了密码学的知识,主要是哈希函数与数字签名 哈希碰撞的含义:不同的输入,哈希值是相同的 x≠y,H(x) = H(y) 输入空间较大 输出空间较小,出现哈希碰撞的情况很常见。碰撞是客观存在的。 实际中,靠一个个数试,去找到两个不同的数的哈希值是相同的,几

    2024年02月08日
    浏览(47)
  • 《现代密码学》学习笔记——第三章 分组密码 [二] AES

    版本 密钥长度 分组长度 迭代轮数 AES-128 4 4 10 AES-192 6 4 12 AES-256 8 4 14 (1)字节代换(SubByte) (2)行移位(ShiftRow) (3)列混合(MixColumn) (4)密钥加(AddRoundKey) 1.字节代换   字节代换是非线性变换,独立地对状态的每个字节进行。代换表(S-Box)是可逆的。   将

    2024年02月05日
    浏览(91)
  • 《计算机系统与网络安全》 第四章 密码学基础

    🌷🍁 博主 libin9iOak带您 Go to New World.✨🍁 🦄 个人主页——libin9iOak的博客🎐 🐳 《面试题大全》 文章图文并茂🦕生动形象🦖简单易学!欢迎大家来踩踩~🌺 🌊 《IDEA开发秘籍》学会IDEA常用操作,工作效率翻倍~💐 🪁🍁 希望本文能够给您带来一定的帮助🌸文章粗浅,敬

    2024年02月11日
    浏览(46)
  • 区块链技术与应用 - 学习笔记2【密码学基础】

    大家好,我是比特桃。 本系列笔记只专注于探讨研究区块链技术原理,不做其他违反相关规定的讨论。 区块链技术已被纳入国家十四五规划,在“加快数字发展 建设数字中国”篇章中,区块链被列为“十四五”七大数字经济重点产业之一,迎来创新发展新机遇。 经科技部批

    2024年02月10日
    浏览(39)
  • 【密码学基础】半/全同态加密算法基础学习笔记

    定义:只支持乘法或加法中的一种的同态加密。同态加密指的是允许直接对密文进行计算,密文计算结果解密后与明文直接计算结果相同。 Paillier加解密过程 Paillier的同态性 明文加法 = 密文乘法 明文乘法 = 密文指数幂 Paillier的安全性 基于大整数分解困难问题 相比Paillier,

    2024年02月13日
    浏览(47)
  • 【区块链学习笔记01】BTC-密码学原理-哈希函数

    区块链中最基础的密码学原理就是哈希算法,以下为哈希函数的简单介绍: 哈希函数是一种只只能加密但是不能解密的算法,哈希函数可以将任意长度的信息转化为固定长度的字符串。类似“8b46ec792e943de34605981980751a3c1e008218f77eeb27e474b594f7685019”这样。 当输入相同的值时,得到

    2024年02月03日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包