Paper 2024/842

Computation Efficient Structure Aware PSI From Incremental Function Secret Sharing

Gayathri Garimella, Brown University
Benjamin Goff, Brown University
Peihan Miao, Brown University
Abstract

Structure-Aware Private Set Intersection (sa-PSI), recently introduced by Garimella et al. (Crypto'22), is a PSI variant where Alice's input set SA has a publicly known structure (for example, interval, ball or union of balls) and Bob's input SB is an unstructured set of elements. Prior work achieves sa-PSI where the communication cost only scales with the description size of SA instead of the set cardinality. However, the computation cost remains linear in the cardinality of SA, which could be prohibitively large. In this work, we present a new semi-honest sa-PSI framework where both computation and communication costs only scale with the description size of . Our main building block is a new primitive that we introduce called Incremental Boolean Function Secret Sharing (ibFSS), which is a generalization of FSS that additionally allows for evaluation on input prefixes. We formalize definitions and construct a weak ibFSS for a -dimensional ball with norm, which may be of independent interest. Independently, we improve spatial hashing techniques (from prior work) when has structure union of -dimensional balls in , each of diameter , from to in terms of both computation and communication. Finally, we resolve the following open questions from prior work with communication and computation scaling with the description size of the structured set. - Our PSI framework can handle a union of overlapping structures, while prior work strictly requires a disjoint union. - We have a new construction that enables Bob with unstructured input to learn the intersection. - We extend to a richer class of functionalities like structure-aware PSI Cardinality and PSI-Sum of associated values.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in CRYPTO 2024
Keywords
Private Set IntersectionFuzzy MatchingFunction Secret Sharing
Contact author(s)
gayathri_garimella @ brown edu
benjamin_goff @ brown edu
peihan_miao @ brown edu
History
2024-10-02: last of 2 revisions
2024-05-29: received
See all versions
Short URL
https://ia.cr/2024/842
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/842,
      author = {Gayathri Garimella and Benjamin Goff and Peihan Miao},
      title = {Computation Efficient Structure Aware {PSI} From Incremental Function Secret Sharing},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/842},
      year = {2024},
      url = {https://eprint.iacr.org/2024/842}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.