Welcome to the resource topic for 2024/842
Title:
Computation Efficient Structure Aware PSI From Incremental Function Secret Sharing
Authors: Gayathri Garimella, Benjamin Goff, Peihan Miao
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 S_A has a publicly known structure (for example, interval, ball or union of balls) and Bob’s input S_B is an unstructured set of elements. Prior work achieves sa-psi where the communication cost only scales with the description size of S_A instead of the set cardinality. However, the computation cost remains linear in the cardinality of S_A, which could be prohibitively large.
In this work, we present a new semi-honest sa-psi framework where both computation and communication costs {\it only scale with the description size} of S_A. 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 \ell_\infty norm, which may be of independent interest. Independently, we improve spatial hashing techniques (from prior work) when S_A has structure union of d-dimensional balls in (\bit^u)^d, each of diameter \delta, from \O(u \cdot d \cdot (\log \delta)^d) to \O(\log \delta \cdot 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 S_B to learn the intersection.
- We extend to a richer class of functionalities like structure-aware PSI Cardinality and PSI-Sum of associated values.
ePrint: https://eprint.iacr.org/2024/842
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .