Structure-Aware Private Set Intersection, With Applications to Fuzzy Matching
Structure-Aware Private Set Intersection, With Applications to Fuzzy Matching
复制标题
DOI：
10.1007/978-3-031-15802-5_12
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Gayathri Garimella;Mike Rosulek;Jaspal Singh
中科院分区：
文献类型：
--
作者：
Gayathri Garimella;Mike Rosulek;Jaspal Singh
在两方私有集合交集（PSI）中，Alice 持有 setX，Bob 持有 setY，他们（仅）学习其中的内容。我们引入了结构感知 PSI 协议，它利用了 Alice 的 setX 众所周知具有某种结构的情况。结构感知 PSI 的目标是实现根据 Alice 集合的描述大小而不是其基数进行扩展的通信。我们为基于函数秘密共享 (FSS) 的结构感知 PSI 引入了一种新的通用范例。简而言之，如果存在针对一类结构化集的紧凑 FSS，则存在支持此类输入集的半诚实 PSI 协议，其通信成本仅与 FSS 共享大小成正比。之前的几个高效（普通）PSI 协议可以被视为我们新范式的特例，具有用于非结构化集的隐式 FSS。我们的 PSI 协议可以从 FSS 的明显较弱的风格实例化，这在之前尚未被研究过。我们开发了几种改进的 FSS 技术，利用这些宽松的要求，在某些情况下比现有的 FSS 好得多。最后，我们深入探索结构感知 PSI 的自然应用。如果 Alice 的 setX 是某个度量空间中许多半径球的并集，那么 X 和 Y 之间的交集对应于模糊 PSI，其中各方了解他们的哪些点在距离内。在结构感知 PSI 中，通信成本随着 Alice 集合中球的数量而不是总体积而变化。我们的技术可以为高维的度量（以及度量的近似值）提供高效的模糊 PSI。我们为二维度量实现了模糊 PSI 协议。对于合理的输入大小，与简单地将问题简化为普通 PSI 的竞争方法相比，我们的协议需要的时间减少 45-60%，通信量减少 85%。
In two-party private set intersection (PSI), Alice holds a setX, Bob holds a setY, and they learn (only) the contents of. We introducestructure-aware PSIprotocols, which take advantage of situations where Alice’s setXis publicly known to have a certain structure. The goal of structure-aware PSI is to have communication that scales with thedescription sizeof Alice’s set, rather itscardinality.We introduce a new generic paradigm for structure-aware PSI based on function secret-sharing (FSS). In short, if there exists compact FSS for a class of structured sets, then there exists a semi-honest PSI protocol that supports this class of input sets, with communication cost proportional only to the FSS share size. Several prior protocols for efficient (plain) PSI can be viewed as special cases of our new paradigm, with an implicit FSS for unstructured sets.Our PSI protocol can be instantiated from a significantly weaker flavor of FSS, which has not been previously studied. We develop several improved FSS techniques that take advantage of these relaxed requirements, and which are in some cases exponentially better than existing FSS.Finally, we explore in depth a natural application of structure-aware PSI. If Alice’s setXis the union of many radius-balls in some metric space, then an intersection betweenXandYcorresponds tofuzzy PSI, in which the parties learn which of their points are within distance. In structure-aware PSI, the communication cost scales with the number of balls in Alice’s set, rather than their total volume. Our techniques lead to efficient fuzzy PSI forandmetrics (and approximations ofmetric) in high dimensions. We implemented this fuzzy PSI protocol for 2-dimensionalmetrics. For reasonable input sizes, our protocol requires 45–60% less time and 85% less communication than competing approaches that simply reduce the problem to plain PSI.