Reliable Homomorphic Matching for Fuzzy Labeled PSI at Scale

• URL: http://arxiv.org/abs/2606.27803v1
• Date: Fri, 26 Jun 2026 07:40:03 GMT
• Title: Reliable Homomorphic Matching for Fuzzy Labeled PSI at Scale
• Abstract summary: Fuzzy Labeled Private Set Intersection (FLPSI) lets a receiver learn the labels of enrolled records similar to its query, and nothing else.<n>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.
• Score: 0.6430130814523795
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Fuzzy Labeled Private Set Intersection (FLPSI) lets a receiver learn the labels of enrolled records similar to its query, and nothing else. 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, and the private matching is delegated 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: 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, and a sound kernel must contribute zero or negligible RSE of its own. We formalize this 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 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 this: at a million records the baseline kernel's RSE reaches 100% while CSTPSI holds it at 0 in every measured configuration. For large labels at small to moderate scale CSTPSI is more than 20x faster than the baseline, with up to 93% less communication, converging to the baseline only at million-scale. Our implementation, with a one-command reproducibility harness, is publicly available.

Related papers

• Significance-First Splitting: Aligning Treatment Heterogeneity Detection with Honest Estimation [0.0]
  Estimating heterogeneous treatment effects (CATE) requires simultaneously detecting effect modification and quantifying estimation uncertainty.<n>Existing tree-based methods make an uneasy trade-off: significance-based approaches identify subgroup interactions directly but lack valid inference.<n>We introduce a hybrid algorithm that fuses significance-based splitting with honest sample-splitting and cross-validation.
  arXiv  Detail & Related papers  (2026-07-04T19:50:35Z)
• ScoreGate: Adaptive Chunk Selection for Retrieval-Augmented Generation via Dual-Score Statistical Fusion [0.0]
  We describe ScoreGate, a lightweight score-space decision mechanism that controls retrieval cardinality at inference time.<n>On MS MARCO (200 dev queries), ScoreGate achieves MRR@10 = 0.401 with 35% fewer retained chunks than Standard Top-K.<n>Results on both MS MARCO and real-world production traffic suggest that adaptive retrieval cardinality can improve retrieval efficiency without degrading retrieval quality.
  arXiv  Detail & Related papers  (2026-06-12T08:51:24Z)
• Practical Anonymous Two-Party Gradient Boosting Decision Tree [7.18882495711708]
  High speed and interpretability make gradient-boosted decision trees (GBDTs) popular in finance and healthcare.<n> Enabling secure computation for GBDTs poses unique challenges, requiring secure record alignment for comparison.<n>We propose circuit-PSI in our design lets the parties alternate as receiver to run pick-then-sum over local features.
  arXiv  Detail & Related papers  (2026-05-26T12:02:14Z)
• Auditing Privacy in Multi-Tenant RAG under Account Collusion [1.253312107729806]
  Multi-tenant retrieval-augmented generation services advertise per-account differential privacy as the operative leakage boundary.<n>We identify same-index multi-account collusion as a privacy-boundary failure.<n>We design the first audit protocol that operates against unmodified RAG deployments.
  arXiv  Detail & Related papers  (2026-05-19T13:41:59Z)
• Deterministic Fuzzy Triage for Legal Compliance Classification and Evidence Retrieval [0.0]
  Legal teams increasingly use machine learning to triage large volumes of contractual evidence.<n>Many models are opaque, non-deterministic, and difficult to align with frameworks such as HIPAA or NERC-CIP.<n>We study a simple, reproducible alternative based on deterministic dual encoders and transparent fuzzy triage bands.
  arXiv  Detail & Related papers  (2026-03-08T00:31:34Z)
• DiffGRM: Diffusion-based Generative Recommendation Model [63.35379395455103]
  Generative recommendation (GR) is an emerging paradigm that represents each item via a tokenizer as an n-digit semantic ID (SID)<n>We propose DiffGRM, a diffusion-based GR model that replaces the autoregressive decoder with a masked discrete diffusion model (MDM)<n> Experiments show consistent gains over strong generative and discriminative recommendation baselines on multiple datasets.
  arXiv  Detail & Related papers  (2025-10-21T03:23:32Z)
• One Sample is Enough to Make Conformal Prediction Robust [53.78604391939934]
  We show that conformal prediction attains some robustness even with a forward pass on a single randomly perturbed input.<n>Our approach returns robust sets with smaller average set size compared to SOTA methods which use many (e.g. around 100) passes per input.
  arXiv  Detail & Related papers  (2025-06-19T19:14:25Z)
• Robust Conformal Prediction with a Single Binary Certificate [58.450154976190795]
  Conformal prediction (CP) converts any model's output to prediction sets with a guarantee to cover the true label with (adjustable) high probability.<n>We propose a robust conformal prediction that produces smaller sets even with significantly lower MC samples.
  arXiv  Detail & Related papers  (2025-03-07T08:41:53Z)
• PAC Prediction Sets Under Label Shift [52.30074177997787]
  Prediction sets capture uncertainty by predicting sets of labels rather than individual labels. We propose a novel algorithm for constructing prediction sets with PAC guarantees in the label shift setting. We evaluate our approach on five datasets.
  arXiv  Detail & Related papers  (2023-10-19T17:57:57Z)
• Detection Transformer with Stable Matching [48.963171068785435]
  We show that the most important design is to use and only use positional metrics to supervise classification scores of positive examples. Under the principle, we propose two simple yet effective modifications by integrating positional metrics to DETR's classification loss and matching cost. We achieve 50.4 and 51.5 AP on the COCO detection benchmark using ResNet-50 backbones under 12 epochs and 24 epochs training settings.
  arXiv  Detail & Related papers  (2023-04-10T17:55:37Z)
• Confident Sinkhorn Allocation for Pseudo-Labeling [40.883130133661304]
  Semi-supervised learning is a critical tool in reducing machine learning's dependence on labeled data. This paper studies theoretically the role of uncertainty to pseudo-labeling and proposes Confident Sinkhorn Allocation (CSA) CSA identifies the best pseudo-label allocation via optimal transport to only samples with high confidence scores.
  arXiv  Detail & Related papers  (2022-06-13T02:16:26Z)
• S3: Supervised Self-supervised Learning under Label Noise [53.02249460567745]
  In this paper we address the problem of classification in the presence of label noise. In the heart of our method is a sample selection mechanism that relies on the consistency between the annotated label of a sample and the distribution of the labels in its neighborhood in the feature space. Our method significantly surpasses previous methods on both CIFARCIFAR100 with artificial noise and real-world noisy datasets such as WebVision and ANIMAL-10N.
  arXiv  Detail & Related papers  (2021-11-22T15:49:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.