Select-Then-Compute: Encrypted Label Selection and Analytics over Distributed Datasets using FHE

Select-Then-Compute: Encrypted Label Selection and Analytics over Distributed Datasets using FHE

Speakers: Nirajan Koirala

Conference: NDSS Symposium 2026

YouTube: https://www.youtube.com/watch?v=rPvvOE8nlac

Overview

This talk presents a novel cryptographic protocol called Select-Then-Compute that enables privacy-preserving label selection and analytics across distributed, encrypted datasets using Fully Homomorphic Encryption (FHE). The protocol addresses a critical gap in the current landscape of privacy-preserving computation: the ability to query encrypted ID-label pairs across multiple data owners, select matching labels, and perform downstream analytics -- all without decrypting any data at any point in the pipeline.

The work targets real-world scenarios where data is fragmented across institutions -- banks, mortgage lenders, healthcare providers -- and regulatory constraints like HIPAA prevent direct data sharing. The protocol introduces new cryptographic primitives including a Value Annihilating Function (VAF) computed via weak domain-preserving polynomials and bell-shaped functions, alongside a slot-wise windowing technique that enables scalable equality testing over wide identifier ranges. Evaluated against three real-world fraud detection datasets, the protocol achieves end-to-end latency under two minutes at high network bandwidths while maintaining zero false positives up to 24-bit precision.

Background

▶ Watch: Problem motivation: data fragmentation in finance and healthcare (0:00)

Data fragmentation across institutions is one of the most persistent obstacles to effective fraud detection and clinical care coordination. In financial services, fraud signals visible across multiple banks remain invisible to any single institution, leading to high false positive rates and inconsistent risk models. In healthcare, patient data spread across providers impedes diagnosis and care coordination under regulations like HIPAA.

Existing cryptographic primitives each address only a piece of this problem. Private Set Intersection (PSI) computes the intersection of datasets but does not support label retrieval. Private Information Retrieval (PIR) enables private queries but lacks analytics capabilities. Private Segmented Membership Test handles membership queries but does not provide label extraction. More advanced protocols like Private Join and Compute and Private Match and Compute offer some combined functionality but are limited to symmetric functions like cardinality and aggregation, and critically, they do not scale to large numbers of data holders.

The protocol is built on top of the CKKS (Cheon-Kim-Kim-Song) homomorphic encryption scheme, which supports approximate arithmetic on encrypted data and is particularly well-suited for real-valued analytics like logistic regression. The work was a collaboration between researchers at the University of Notre Dame, Hanyang University, and Old Dominion University.

Key Findings

▶ Watch: Two-stage protocol overview and basic equality testing idea (4:00)

The research makes several key contributions to the field of privacy-preserving computation:

Unified protocol for encrypted label selection and analytics: Unlike prior work that addresses only intersection, retrieval, or computation in isolation, Select-Then-Compute provides all three capabilities in a single protocol. Data owners encrypt their ID-label pairs and offload them to a cloud server, a querier submits encrypted queries, and the protocol returns analytics results computed over the matching labels.

Novel VAF primitives with provable precision: The Value Annihilating Function (VAF) maps zero inputs to a constant k and all non-zero inputs to zero, enabling clean binary selection. Previous approaches using domain extraction polynomials could only achieve coarse-grained approximation. The new approach using weak domain-preserving (DP) polynomials and bell-shaped functions achieves clean separation between match and non-match values with provable bounds.

Sub-linear scaling with sender count: The protocol scales sub-linearly with the number of data owners, handling up to 4,000 senders with overall latency staying below 400 seconds on 20 Gbps networks. This represents up to 27x latency improvement over previous state-of-the-art methods.

Zero false positives on real fraud data: Across three real-world fraud detection datasets (vehicle loan fraud, credit card fraud, and IT-ECIS credit card fraud), the protocol achieved no false positives at up to 24-bit precision in the CKKS scheme.

Technical Deep Dive

▶ Watch: Slot-wise windowing technique for large identifier spaces (8:00)

The protocol operates in two stages. Stage one handles encrypted equality testing and label extraction. The querier's identifier is encrypted and packed into all slots of a CKKS ciphertext. The cloud computes the homomorphic subtraction between each encrypted database ID and the query ciphertext, producing a difference ciphertext. The VAF then transforms this difference: zero values (indicating a match) are mapped to one, while all non-zero values are mapped to zero. A homomorphic multiplication with the label ciphertext then extracts only the matching labels.

The VAF computation is the core technical innovation. It consists of two components:

1. Weak Domain-Preserving (DP) Polynomial: This compresses the wide input domain to a smaller range while preserving the critical property that only zero inputs map to zero. This relaxation of the standard DP definition enables more efficient computation while retaining the necessary discriminative power.

1. Bell-Shaped Function: Applied after the weak DP, this concentrates mass at zero -- any input below an epsilon threshold maps to a value close to one, while everything above epsilon maps to a value less than a small bound B. The composition guarantees that g(0) = 1 exactly, while g(x) < B for all non-zero x.

The slot-wise windowing technique addresses the challenge of performing equality testing over large identifier spaces. Each delta-bit identifier is decomposed into smaller windows of delta/kappa bits. The VAF is computed in parallel on each chunk, then the results are multiplied together in log2(k) depth to produce the final indicator value. This parallelization is what enables the 27x latency improvement.

Stage two performs downstream analytics on the extracted labels. One designated data holder aggregates labels across senders into a single ciphertext to conserve memory, then computes the target function -- in this evaluation, logistic regression -- over the aggregated encrypted labels. A match flag is also computed and returned alongside the result to indicate whether a genuine match occurred.

The protocol operates under a semi-honest threat model with threshold CKKS providing additional protection: no single sender can decrypt the shared dataset alone, requiring coalition formation for decryption. The authors note that malicious security could be achieved through OPRFs or ZK-SNARKs, though at significant performance cost.

Demo / Proof of Concept

▶ Watch: Benchmarks: sub-linear scaling up to 4,000 senders (10:00)

No live demo was performed, but the speaker presented comprehensive benchmarking results across multiple dimensions. The selection stage benchmarks showed sub-linear scaling up to 4,000 senders, with latency staying mostly flat until set sizes exceeded 2^27, at which point per-sender ciphertext volume began dominating. Compared to the Kong et al. and KTSJ baselines, the protocol operates on fully encrypted datasets while achieving higher precision at lower FHE depth.

The fraud detection evaluation used three real-world datasets: a vehicle loan fraud detection dataset, a credit card fraud detection dataset, and an IT-ECIS credit card fraud detection dataset. All three completed with online latency under 65 seconds. End-to-end latency including communication overhead stayed under 2 minutes on 10-20 Gbps networks. The runtime breakdown showed that VAF plus windowing consumed approximately 57% of total computation time, followed by logistic regression plus flag computation, then label extraction. Increasing identifier size to 128 bits added only 11-41% additional latency.

Defensive Implications

▶ Watch: Q&A: accuracy, threat model, and future richer predicates (14:00)

This work has significant implications for organizations that need to perform cross-institutional analytics without exposing sensitive data. Fraud detection is the primary use case: banks and financial institutions could collaboratively detect fraud patterns that span multiple institutions without sharing customer data, potentially reducing the false positive rates that plague single-institution models.

For healthcare organizations, the protocol enables collaborative diagnostics and care coordination across providers while maintaining HIPAA compliance. The ability to perform logistic regression on encrypted labels means predictive models can be trained on distributed patient data without centralized data collection.

From a security operations perspective, the protocol could enable threat intelligence sharing across organizations -- matching indicators of compromise against distributed datasets without revealing each organization's internal threat data. The semi-honest threat model with threshold encryption provides meaningful protection even when some participants may be compromised.

The practical latency numbers (under 2 minutes end-to-end) bring this from theoretical possibility to operational viability for batch analytics, though real-time applications would still require further optimization.

Key Takeaways

• Select-Then-Compute is the first unified protocol that combines encrypted label selection and analytics over distributed datasets using FHE, addressing gaps left by PSI, PIR, and private join-and-compute approaches
• The novel VAF primitives using weak domain-preserving polynomials and bell-shaped functions achieve zero false positives up to 24-bit precision in CKKS
• Slot-wise windowing enables up to 27x latency improvement over prior state-of-the-art by parallelizing equality testing across identifier chunks
• The protocol scales sub-linearly to 4,000+ data owners and achieves end-to-end latency under 2 minutes on high-bandwidth networks
• Real-world fraud detection evaluation demonstrates practical viability across three datasets with online latency under 65 seconds
• Future work targets multi-query workloads, richer predicates (interval checks, range queries), and system-level optimization of the VAF and windowing computation

About the Speaker(s)

Nirajan Koirala is a researcher affiliated with the University of Notre Dame, working in the area of privacy-preserving computation and fully homomorphic encryption. This work was conducted in collaboration with co-authors from Hanyang University and Old Dominion University. Koirala's research focuses on bridging the gap between theoretical cryptographic primitives and practical privacy-preserving analytics, with particular emphasis on scalability across distributed data environments.