Paper 2024/842

Computation Efficient Structure Aware PSI From Incremental Function Secret Sharing

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.