Paper 2026/1322

Reliable Homomorphic Matching for Fuzzy Labeled PSI at Scale

Abstract

Fuzzy Labeled Private Set Intersection (FLPSI) lets a receiver learn the labels of enrolled records that are similar to its query, and nothing else. FLPSI can be built in several ways. Constructions based on a set-threshold reduction reach practical performance: a query matches a record when the two agree on a threshold number of components. These constructions delegate the private matching to an inner set-threshold kernel. We study its homomorphic form, which combines leveled-BFV homomorphic encryption (HE), a garbled circuit, and secret sharing to decide the match under encryption and release the record's label. We identify a composition gap in this kernel, an instance of a protocol-level problem: efficiency is bought with a per-trial false-accept probability, but one query runs a trial for every record, so the error compounds with the database size into the kernel's realization soundness error (RSE), the rate at which it accepts a query the plaintext matcher would reject. The RSE is a reliability property of the cryptographic matching layer, not the matcher's accuracy. On a spurious accept the kernel also returns a value the plaintext matcher would never produce. A sound kernel must contribute zero or negligible RSE of its own. We formalize this requirement as a composable security property, give a closed-form bound on the receiver's advantage, and close the gap with CSTPSI, a kernel that runs independent token rounds and raises the per-trial bound to a matching power. We prove CSTPSI secure in the semi-honest model. The closed-form bound sets the round count: two token rounds suffice for million-scale databases and three for billion-scale at the $10^{-6}$ engineering threshold. Our evaluation confirms the prediction. At a million records the baseline kernel's RSE reaches $100\%$ while CSTPSI holds it at $0$ in every measured configuration. CSTPSI decouples threshold-checking and upload costs from label size. For large labels at small to moderate scale it is more than $20\times$ faster than the baseline kernel, with up to $93\%$ less communication. It converges to the baseline only at the million-scale database size. Our implementation, with a one-command reproducibility harness, is publicly available.

Note: Code and reproducibility artifact: https://github.com/euzun/cstpsi Also available on arXiv: https://arxiv.org/abs/2606.27803