编程总结

基于 OT 扩展的可扩展隐私集合求交集

隐私集合求交集（PSI）允许双方计算他们的集的交集，而不透露不在交集中的项目的任何信息。这是研究得最好的安全计算应用之一，许多 PSI 协议已经被提出。然而，现有的 PSI 协议的多样性使得我们很难确定在各自场景中表现最好的解决方案，特别是由于它们没有在相同的环境中进行比较。此外，现有的 PSI 协议比不安全的朴素散列解决方案慢几个数量级，而这是在实践中使用的。

在这篇文章中，我们回顾了在 PSI 协议方面取得的进展，并对各种安全模型中的现有协议进行了概述。然后，我们关注对半诚实对手安全的 PSI 协议，并利用不经意传输（OT）扩展的最新效率改进，对以前的 PSI 协议提出重大优化，并提出一种运行时间优于现有协议的新 PSI 协议。我们通过在同一平台上实现所有协议，从理论上和实验上比较了协议的性能，对在特定环境下使用哪种协议提出了建议，并通过与目前采用的不安全的朴素散列协议进行比较，评估了 PSI 协议的进展。我们通过处理两个各有 10 亿元素的集合来证明我们新的 PSI 协议的可行性。

基于同态加密的快速隐私保护集合求交

隐私保护集合求交（PSI）是一种加密技术，它允许双方在不透露任何东西的情况下计算他们的集的交集，除了交集。我们使用完全同态加密来构建一个快速的 PSI 协议，其通信开销很小，当两个集合中的一个比另一个小得多时，该协议特别好用，并且对半诚实的对手是安全的。

计算效率最高的 PSI 协议是使用哈希函数和不经意传输等工具构建的，但这些方法的一个潜在限制是通信复杂度，它与较大集合的大小呈线性扩展。当在一个持有小集合的受限设备（手机）和一个大型服务提供商（如 WhatsApp）之间执行 PSI 时，这是一个特别值得关注的问题，例如在私人联系人发现应用中。

我们的协议的通信复杂度与小集合的大小成线性关系，而与大集合成对数关系。更确切地说，如果集合的大小是 ，我们实现的通信开销是 。我们的运行时间优化基准显示，将 5000 个 32 位字符串与 1600 万个 32 位字符串相交，需要 36 秒的在线计算，71 秒的非交互式（独立于接收器）预处理，以及仅 12.5MB 的往返通信。与之前的工作相比，这大约减少了 38-115 倍的通信量，而计算开销的差别很小。

恶意安全的全同态加密中的标签化 PSI

隐私保护集合求交（Private Set Intersection - PSI）允许双方，即发送方和接收方，在不向对方透露额外信息的情况下计算其私有集的交集。我们对不平衡的 PSI 设置感兴趣，其中（1）接收方的集合明显小于发送方的集合，以及（2）接收方（拥有较小的集合）有一个低功率设备。另外，在标签式 PSI 设置中，发送方为其集合中的每个项目持有一个标签，而接收方则从相交的项目中获得标签。我们在 Chen、Laine 和 Rindal（CCS 2017）的非平衡 PSI 协议的基础上进行了一些改进：我们增加了对任意长度项目的有效支持，我们构建并实现了一个具有小通信复杂性的非平衡标签化的 PSI 协议，并且在预处理阶段使用不经意伪随机函数（OPRF）加强了安全模型。我们的协议优于以前的协议：对于一个任意长度的 220 和 512 大小的集合的交集，我们的协议的总在线运行时间仅为 1 秒（单线程），总通信成本为 4MB。对于一个更大的例子，一个 228 和 1024 大小的任意长度项目集的交集，在线运行时间为 12 秒（多线程），总通信量小于 18MB。

基于 Merkle Semantic Trie 的混合存储区块链高效查询方案

作为一个去中心化的可信数据库，区块链在越来越多的领域找到了应用，如金融、供应链和医药追溯，大量有价值的数据被存储在区块链上。目前，主流区块链采用了链上和链下存储相结合的混合数据存储架构。对存储在这种混合系统中的海量数据进行实时分布式搜索是目前的主要需求。然而，以往的区块链系统快速检索方案只针对链上数据，没有考虑其与链下数据的相关性，因此无法满足要求。在本文中，我们通过引入一种新颖的基于 Merkle Semantic Trie 的索引技术，提出了一种高效的区块链数据查询方案，而无需修改底层数据库。利用提取的链下数据的语义信息构建共识的链上索引结构，在链上和链下数据之间建立映射，从而实现链上和链下的实时数据查询。我们的方案还提供了多种复杂的分析查询原语，以支持语义查询、范围查询，甚至是模糊查询。在三个开放数据集上的实验表明，所提出的方案具有良好的查询性能，对四种不同的搜索类型具有较短的查询延迟，并提供比现有方案更好的检索性能和验证效率。

用密码泄露警报来保护账户不被盗用

由于知识的不对称性，保护账户免受密码填充攻击的工作仍然十分繁重：攻击者可以大范围地接触到数十亿被盗的用户名和密码，而用户和身份提供者对哪些账户需要补救仍然一无所知。在本文中，我们提出了一个保护隐私的协议，根据该协议，客户可以查询一个集中的泄露库，以确定特定的用户名和密码组合是否公开泄露，但不透露查询的信息。在这里，客户端可以是一个最终用户，一个密码管理器，或一个身份提供者。为了证明我们协议的可行性，我们实现了一个云服务，该服务调解访问在泄露中发现的 40 多亿个密码，以及一个作为初始客户端的 Chrome 扩展。基于来自近 67 万名用户和 2100 万次登录的匿名遥测数据，我们发现网络上 1.5% 的登录涉及泄露的密码。通过提醒用户注意这种泄露状态，我们 26% 的警告导致用户迁移到一个新的密码，至少与原来的密码一样强大。我们的研究说明了安全的、民主化的密码泄露警告可以帮助缓解账户劫持的一个方面。

论安全计算的部署：具有 Cardinality 的隐私集合交集求和问题

在这项工作中，我们讨论了我们在行业内部署加密安全计算协议的成功努力。我们考虑的问题是隐私计算广告活动的总转换率。这个基础功能可以被抽象为具有 Cardinality 的隐私交集和（PI-Sum）。在这种情况下，两方持有包含用户标识符的数据集，其中一方还拥有与其每个用户标识符相关的整数值。双方希望了解他们共同拥有的标识符的数量以及与这些用户相关的整数值的总和，而不透露任何有关他们私人输入的信息。

我们确定了主要的特性和有利因素，这些特性和因素使得部署一个加密协议成为可能、实用，并被独特地定位为手头任务的一个解决方案。我们描述了我们的部署环境和最相关的效率衡量标准，在我们的环境中，它是通信开销而不是计算。我们还提出了一个货币成本模型，可以作为一个统一的成本衡量标准，以及反映我们使用情况的计算模型：一个低优先级的批量计算。

我们提出了三个带 cardinality 的 PI-Sum 协议：我们目前部署的协议，它依赖于 Diffie-Hellman 风格的双重掩码，以及两个新的协议，它们利用了最近的私有集相交（PSI）技术，使用不经意传输和加密的布隆过滤器。当用不同的加法同态加密方案进行实例化时，我们将后面两个协议与我们的原始解决方案进行比较。我们实现了我们的构造并比较了它们的成本。我们还与最近用于计算两个数据集的交集的通用方法进行了比较，结果表明，我们最好的协议的货币成本比已知的最佳通用方法低 20 倍。