International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Computation Efficient Structure-Aware PSI From Incremental Function Secret Sharing

Authors:
Gayathri Garimella , Brown University
Benjamin Goff , Brown University
Peihan Miao , Brown University
Download:
DOI: 10.1007/978-3-031-68397-8_10 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2024
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 SA. 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 d-dimensional ball with ℓ∞ norm, which may be of independent interest. Independently, we improve spatial hashing techniques (from prior work) when SA has structure union of d-dimensional balls in ({0,1}u)d, each of diameter δ, from O(u⋅d⋅(log⁡δ)d) to O(log⁡δ⋅d) 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 SB to learn the intersection. - We extend to a richer class of functionalities like structure-aware PSI Cardinality and PSI-Sum of associated values.
BibTeX
@inproceedings{crypto-2024-34239,
  title={Computation Efficient Structure-Aware PSI From Incremental Function Secret Sharing},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-68397-8_10},
  author={Gayathri Garimella and Benjamin Goff and Peihan Miao},
  year=2024
}