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 has a publicly known structure (for example, interval, ball or union of balls) and Bob's input is an unstructured set of elements. Prior work achieves sa-PSI where the communication cost only scales with the description size of instead of the set cardinality. However, the computation cost remains linear in the cardinality of , 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.
@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.