Paper 2022/1011
StructureAware Private Set Intersection, With Applications to Fuzzy Matching
Abstract
In twoparty private set intersection (PSI), Alice holds a set $X$, Bob holds a set $Y$, and they learn (only) the contents of $X \cap Y$. We introduce structureaware PSI protocols, which take advantage of situations where Alice's set $X$ is publicly known to have a certain structure. The goal of structureaware PSI is to have communication that scales with the description size of Alice's set, rather its cardinality. We introduce a new generic paradigm for structureaware PSI based on function secretsharing (FSS). In short, if there exists compact FSS for a class of structured sets, then there exists a semihonest 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 structureaware PSI. If Alice's set $X$ is the union of many radius$\delta$ balls in some metric space, then an intersection between $X$ and $Y$ corresponds to fuzzy PSI, in which the parties learn which of their points are within distance $\delta$. In structureaware 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 for $\ell_\infty$ and $\ell_1$ metrics (and approximations of $\ell_2$ metric) in high dimensions. We implemented this fuzzy PSI protocol for 2dimensional $\ell_\infty$ metrics. For reasonable input sizes, our protocol requires 4560% less time and 85% less communication than competing approaches that simply reduce the problem to plain PSI.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 A minor revision of an IACR publication in CRYPTO 2022
 Keywords
 secure computation private set intersection function secret sharing
 Contact author(s)

garimelg @ oregonstate edu
rosulekm @ eecs oregonstate edu
singjasp @ oregonstate edu  History
 20220807: approved
 20220805: received
 See all versions
 Short URL
 https://ia.cr/2022/1011
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/1011, author = {Gayathri Garimella and Mike Rosulek and Jaspal Singh}, title = {StructureAware Private Set Intersection, With Applications to Fuzzy Matching}, howpublished = {Cryptology ePrint Archive, Paper 2022/1011}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/1011}}, url = {https://eprint.iacr.org/2022/1011} }