Computation Efficient Structure-Aware PSI from Incremental Function Secret Sharing

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 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 \((\{0,1\} ^u)^d\) , each of diameter \(\delta \) , from \(\mathcal {O} (u \cdot d \cdot (\log \delta )^d)\) to \(\mathcal {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.