网站开发员工结构,项城网站建设,国外家居创意空间设计,中国建盏logo笔记内容来自多本书籍、学术资料、白皮书及ChatGPT等工具#xff0c;经由自己阅读后整理而成。
#xff08;一#xff09;PSI的介绍
隐私计算关键技术#xff1a;隐私集合求交#xff08;PSI#xff09;原理介绍
隐私计算关键技术#xff1a;隐私集合求交#xff08…笔记内容来自多本书籍、学术资料、白皮书及ChatGPT等工具经由自己阅读后整理而成。
一PSI的介绍
隐私计算关键技术隐私集合求交PSI原理介绍
隐私计算关键技术隐私集合求交PSI的性能扩展
笔记分享 | 组队学习密码学 —— 隐私求交的关键路径及其应用
笔记分享 | 组队学习密码学 —— 隐私求交之不经意的伪随机函数构造
隐私集合求交( Private Set IntersectionPSI是多方安全计算领域中的经典问题它要求参与方在互相不公开本地集合的前提下共同计算得出多个参与方的集合的交集且不能向任何参与方泄露交集以外的信息。
在纵向联邦学习场景中PSI 也被称为样本对齐 ( Sample Alignment ) 或者数据库撞库即各参与方需要首先求出各自的训练样本 ID 集合之间的交集基于计算得到的训练样本 ID 交集进行后续的纵向联邦模型训练。 样本对齐概念 样本对齐是纵向联邦学习中不可或缺的一环。纵向联邦学习的样本分属于不同的组织各个组织的样本的覆盖范围各有差异所以需要找出参与方 A 与参与方 B 共有的训练样本 ID且除了A和B双方共有的样本 ID例如一家银行和另一家电商共同的客户的 ID可以用手机设备号的哈希值作为客户的 ID 标识找出交集以外不能泄露其他样本 ID 给彼此。这个过程需要用到加密样本 ID 对齐机制。交集的方式一般是通过 Join 键比如 ID 证件号这些敏感信息不适合直接进行交集的计算需要进行签名处理并且要保障不被破解。样本对齐的方式有多种例如基于映射的散列算法、比特承诺基于RSA加密体系的茫然传输等。 隐私集合求交技术通常是基于 ID 来实现交集的计算即在计算的过程仅通过样本集的 ID 列参与计算在求得 ID 集合的交集后再同步相对应的特征标签列给其他参与方或是仅在节点内同步特征列为后续的其他计算做准备。 二PSI的方法 基于 Diffie-Hellman 密钥交换的 DH 算法公钥 基于盲签名的 Blind-RSA 算法公钥 以基于 RSA 盲签名和哈希算法的 PSI 技术为例简单介绍其工作原理
RSA 计算复杂度较高协议中 RSA 的计算次数会随着数据量的增大呈线性增长使得基于 RSA 的求交方法在数据量较大时会产生性能问题。由于 RSA 盲签名算法在运行时只对一端的数据进行 RSA 加密使得在求交数据量级差距较大时可以把数据量较小的一端作为 Client 端这样可以获得非常大的性能优势。另外RSA 算法的流程适合并行处理方便利用并行计算来提升性能。
RSA 盲签名协议能够在恶意对手模型下为隐私集合求交提供安全保障但由于非对称加密的次数随比对的数量量的增加呈线性增长所以无法处理海量数据的隐私集合求交场景。 基于同态加密的算法 比较适合拥有较小集合的一方将数据加密后发送给另一方进行计算然后将结果返回给加密方进行解密的场景。但实际上这种原型协议实现起来效率特别差因为同态加密密文长度都不算太小。另外同态加密电路的深度随着集合元素数量增加而快速增加导致方案性能较差。 此协议应用相同元素的差为0的原理进行交集判断使用 HE 算法来完成密文求差操作。为了防止差不为 0 的元素值泄露每一次求差操作后会乘一个随机数 r。为了提高协议的实际性能Chen 等人使用了一些优化方法。包括 PSI 领域的 hash、切分技术还使用了 HE 领域的批处理、分窗、模数转换技术。上面的过程简化下来就是 基于同态加密实现 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. 基于不经意传输的算法目前速度最快最流行 首先是基于布隆过滤器和 OT 的实现方案有关布隆过滤器及其变种可参考上面的布隆/混淆布隆过滤器。 GBF 与 OT 结合解决 PSI 问题 接下来仍以社交软件的发现共有联系人功能为例假设服务器端有用户集合 S客户端有联系人集合 C客户端通过以下步骤可最终获得双方集合的交集 C ∩ \cap ∩ S. 服务器端、客户端约定用于 B F BF BF 以及 G B F GBF GBF 的相关参数存储的数组的长度 m使用的哈希函数集合{ ho,…, ht-1 }。 服务器端针对集合 S 使用 G B F GBF GBF 进行映射获得字符串数组 G B F s GBF_s GBFs . 客户端针对集合 C 使用 B F BF BF 进行映射获得位数组 B F c BF_c BFc . 客户端使用 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} GBFC∩S . 客户端遍历集合 C 中的所有元素使用以下方法利用 G B F C ∩ S GBF_{C\cap S} GBFC∩S 判断自己所拥有的元素是否在集合 S 中。 基于不经意传输的 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 的隐私集合求交方案提供了更好的性能优势。 虽然基于不经意传输的隐私集合求交技术仍然是使用非对称加密技术作为其实现原理但不经意传输使用有限次非对称加密来完成任意数量的安全数据传输。基于不经意传输的隐私集合求交方案是目前研究最为活跃的隐私集合求交方案对该方案的研究是基于安全性和性能平衡后的一种考量研究的思路主要在减少非对称加密次数和通信双方传输的数据量。 基于混淆电路等 MPC 技术的算法 使用混淆电路通用框架来计算交集有易扩展特性这是因为使用通用的多方安全计算协议计算交集的函数是通过电路实现的而将计算交集的电路的输出连到其他计算电路作为输入就可以计算交集的大小、交集中元素的和等而且全部过程都能满足保护输人隐私的要求。这种易于扩展的性质是基于公钥加密或基于不经意传输的 PSI 所没有的因此其是一种有实际应用价值的方案。
总之以上方法都可以解决两方的 PSI 问题当遇到多方 PSI 问题时它们是通过两两求交集的替代方法来实现“等效的多方 PSI”。这一方法可以降低计算的复杂度却会带来一个非常严重的安全隐患即会泄露那些属于两方交集但不属于多方交集的数据。 隐私计算关键技术多方隐私集合求交PSI从原理到实现
针对此问题基于 Freedman 协议提出了一种严格的多方安全 PSI 协议可以保证除了多方样本 ID 交集信息之外任何其他信息均不会泄露。多方 PSI 协议的核心思想是将样本 ID 集合编码成特殊的数据结构即不经意多项式其中每一个样本 ID 均为不经意多项式的根。利用半同态加密算法对多项式参数进行保护使多个参与方可以在密文空间下进行多项式求值同时又无法读取多项式参数的明文。
然而大整数多项式系数展开和求值的计算复杂度均为 O(n3) 为了解决这一计算瓶颈提出了一种基于哈希分桶的优化方法。具体而言利用哈希分桶技术将 ID 集合均匀映射到若干 ID 分桶中这里要求各参与方使用相同的哈希函数以便确保相同的样本 ID 被映射到相同的分桶中。这样一来只需要进行“桶内计算、桶间合并”即可得到完整的多方 ID 集合的交集。将单个桶内样本数量视为一个常数算法的计算复杂度可以优化到 O(n) 。 10月份新开了一个GitHub账号里面已放了一些密码学隐私计算电子书资料了之后会整理一些我做过的、或是我觉得不错的论文复现、代码项目也放上去欢迎一起交流Ataraxia-github
