CS Paper Radar

Signed Dyadic Path Encoding for Efficient Non-Interactive Private Decision Tree Evaluation over TFHE

Xintong Song, Yiqiang Zhao, Qizhi Zhang, Yao Li, Jiaji He, Fei Zhao

cs.CR ·submitted 2026-11-12 13:54 UTC · v1

Abstract

Private decision-tree evaluation lets a server classify a client's encrypted query without learning the input. In the non-interactive, path-based setting over TFHE, the server returns a single encrypted prediction by aggregating per-path comparison outcomes, and the standard per-leaf formulation pays one programmable bootstrap (PBS) per leaf, which dominates the cost. We propose a signed dyadic path-sum encoding that nearly halves this cost: each internal node receives a signed dyadic label so that every root-to-leaf path accumulates a distinct integer sum, which lets the two children of a leaf-parent be packed into a single test polynomial and resolved by one PBS, reducing the PBS count from the number of leaves to the number of leaf-parents. We formalize the distinct-sum property and prove that the dyadic labeling is the range-minimal encoding satisfying it, and its half-symmetric signed form is magnitude-optimal, tightening the comparison-stage noise bound at fixed parameters. We derive the two conditions under which the encrypted evaluation returns the exact prediction and instantiate parameters with per-inference failure below $2^{-64}$ at 128-bit security. We show that the ring degree grows linearly with the consumed plaintext range, which confines the profitable regime to depths $\leq 4$, where our method stays faster even when each scheme runs at its own cost-optimal parameters. We further extend the encoding to gradient-boosted ensembles. On standard UCI benchmarks at depths 1-4, our method reduces single-tree latency by $1.51\times$-$1.92\times$ and ensemble latency by $2\times$, without accuracy loss, while preserving the compact, non-interactive response.

Comment
17 pages (15 + 2 pages of supplementary material), 6 figures, 9 tables. Submitted to IEEE Transactions on Emerging Topics in Computing

Closest papers

Nearest neighbours by meaning across the whole index.

Efficient Privacy-Preserving Range Filtered Approximate Nearest Neighbor Search

cs.DB cs.IR ·2026-08-17 ·Haoyu Wang, Yandi Zhang, Jiadong Xie, Yingfan Liu, Hui Li +2 more
similarity 0.60
Abstract · According to the best of our knowledge, this work is the first attempt to study privacy-preserving range-filterd ANN search problem. This is…

Range-filtered approximate nearest neighbor search (RFANNS) is an important primitive for vector databases; it retrieves vectors that are similar to a query and satisfy a numerical range predicate, but existing RFANNS indexes expose vectors, attributes, and queries in plaintext. This assumption is unsuitable for outsourced vector databases, where sensitive data and queries must be protected from an honest-but-curious cloud server. To the best of our knowledge, this is the first study that systematically formulates and evaluates privacy-preserving RFANNS over outsourced encrypted vector databases. Our approach separates range localization from encrypted vector search: an authorized user maps the query range to a compact set of nodes in a local N-ary attribute tree, and the server searches only the corresponding proximity graph sub-indices over encrypted vectors. To reduce expensive encrypted comparisons, we use a filter-and-refine pipeline that first retrieves coarse candidates with approximate distance-comparison-preserving encryption and then reranks a small candidate set with exact distance-comparison encryption. We then analyze the computation, storage, communication, and leakage of the protocol. Experiments on four widely used vector datasets show that our method improves the QPS-Recall trade-off over representative secure adaptations of existing RFANNS approaches, scaling effectively to large datasets.

0.15

VerfGraph: Efficient Zero-Knowledge Verifiable Graph Query Evaluation System

cs.CR ·2026-11-03 ·Tianyi Ma, Yuncong Zhang, Yuanzhuo Yu, Boshi Yuan, Shi-Feng Sun
benchmark similarity 0.60
Abstract · 13 pages, 3 figures, 7 tables

Graph databases are often used to manage relationship-rich data, whose graph structure and attributes may be sensitive. In many applications, a database owner or a service provider evaluates queries over a private graph for a client. Because the graph cannot be fully disclosed and independently re-executing the query may be impractical, the client cannot directly verify the returned result. This creates a need for verifiable graph query evaluation that preserves data confidentiality. We present VerfGraph, a zero-knowledge system for verifiable graph query evaluation, which enables a client to verify that the query result was correctly computed over a committed graph data, without revealing private graph records or intermediate query values beyond the public inputs and what is implied by the query result. Building on the expansion-centric model introduced by the state-of-the-art zero-knowledge verifiable graph query evaluation system ZKGraph (ICDE'26), VerfGraph achieves more efficient and expressive zero-knowledge verifiable graph query evaluation by advancing design in two key ways. First, we propose novel operator-proof methods for core expansion and shortest-path operations that reduce costly sorting and comparison checks and eliminate edge canonicalization for bidirectional expansion. Furthermore, we introduce correctness proofs for count and weighted shortest-path operators, broadening the class of graph queries that can be verified. We evaluate VerfGraph using the LDBC Social Network Benchmark. Compared with ZKGraph on complex IC queries, VerfGraph achieves $33.9\times$-$59.7\times$ speedups in proof generation and reduces peak prover memory by factors of $4.5\times$-$6.6\times$, while maintaining millisecond-level verification and producing sub-MB proofs.

0.27

Static Bootstrap Placement for Encrypted Language Model Decoding

cs.CR cs.DCcs.LG ·2026-10-04 ·Halil Ibrahim Kanpak, Didem Unat
similarity 0.59
Abstract · 20 pages, 10 figures, 8 tables

Language models increasingly serve prompts that carry private data, and secure inference under homomorphic encryption lets a client outsource the computation without revealing the prompt. Existing secure inference systems run a forward pass without consuming a token under encryption, and generating text with them requires a client round trip at every generated token. Keeping the loop on the server instead requires selecting and consuming a token under encryption, and placing bootstraps for a loop body that grows with the context. We build AR-HE, which runs the whole loop on the server, selects each token under encryption, retrieves its embedding, and writes it back into the encrypted state. The client sends one prompt and remains offline until the output. One rule places every bootstrap in the run, without search, so the bootstrap cost of a token is a formula in the context length that is known before the run starts. The schedule skips work whose result cannot reach the output, packs bootstraps that share an operand, and keeps the keys and values of past positions in an encrypted cache. With every optimization applied, generating a GPT-2 small token costs 544 seconds on one NVIDIA H100, down from 4715 seconds without optimization. The prompt step before it costs 4630 seconds. The cache alone takes a generated step from 11751 bootstraps to 1072. The formula predicts every step we measured, including steps of a model it was not derived from.

0.43

CAROUSEL: GPU-Accelerated Private Vector Search via Homomorphic Sketching

cs.CR ·2026-11-07 ·Sohaib, Divyakant Agrawal, Amr El Abbadi, Soamar Homsi
similarity 0.58
Abstract

Vector search on untrusted infrastructure exposes the \emph{query embedding}, a faithful summary of the user's intent. Fully homomorphic encryption can hide the query, but existing approaches still require a full scan followed by ranking of encrypted scores. Scalable private systems avoid encrypted ranking by either sending scores from a single cluster to the client or moving the search to the client, which must first stream the entire vector index for preprocessing. We present \textsc{Carousel}, which instead scores the full corpus under encryption and compresses the results for client-side ranking. The server scores every vector under encryption, raises the scores to a power that preserves their order by magnitude while suppressing all but a handful, and compresses the resulting sparse vector into a logarithmic number of ciphertexts using homomorphic additions alone. Because every vector is scored, \textsc{Carousel} incurs no recall loss from discarding candidates. Since clients hold no database-dependent state, insertions and deletions take effect immediately at the cost of a single vector write. \textsc{Carousel} searches $1$ billion vectors of BIGANN SIFT1B across multiple GPUs and achieves recall@100 of $0.9715$. At $100$ million SIFT vectors, it achieves recall@100 of $0.9845$ with a query latency of $3.735$ seconds on a single GPU.

0.20

Retained Encrypted Search with Certified Split Joins

cs.CR ·2026-11-18 ·Yavor Litchev, Liwen Ouyang
similarity 0.58
Abstract

Retaining encrypted search across data edits and worker replacement requires separating computational validity from current release authority. We give exact Hamming search with at most one authorized decryption and decoding attempt per query preparation. Under authenticated prescribed execution, exclusive nonrollback owner state, an ideal public seed-expansion interface and a stated observation model, we reduce bounded adaptive privacy to ordinary ring learning with errors (Ring-LWE). Expanded second components depend only on public masks and fixed maps, independently of queries and the fresh database key. This compiler invariant permits a retained split join against a smaller-modulus encrypted database. A simultaneous bound on the completed circuit covers a finite honest reservation family, including adaptive queries and slot selection, with explicit statistical correctness and privacy losses. In three post-calibration local CPU comparisons on 32,768 vectors of 512 bits, the 60-bit-join construction takes a median 9.825 s for an end-to-end two-query workload, versus 12.159 s for the optimized full-source-modulus baseline. These times include setup, transfers, preparation and private completion. They are local implementation results, not deployment or concrete-security claims.

0.39

BetweenCut: Private Heavy-Node Classification with Doubly Logarithmic Error in Tree Height

cs.CR cs.DS ·2026-10-07 ·Ergute Bao, Graham Cormode, Xiaokui Xiao, Ting Yu
similarity 0.58
Abstract

Finding heavy nodes in a tree---those whose counts exceed a given threshold---is a building block for analysis and learning over structured data. Achieving record-level differential privacy (DP) without sacrificing accuracy is challenging because each record contributes to counts along an entire root-to-leaf path, allowing privacy costs to accumulate across levels. Existing methods account for the multiple threshold comparisons for each record incur additive error margins of $Ω_{\varepsilon,δ}(\log h)$ or $Ω_{\varepsilon,δ}(\sqrt{\log h})$ for tree height $h$. We introduce \textsc{BetweenCut}, an $(\varepsilon,δ)$-DP algorithm with an additive error margin of $O_{\varepsilon,δ}(\log\log h)$, improving the existing bounds for deep trees. This error holds simultaneously for all nodes and is independent of the input database size.

0.23

Differential Privacy Meets Fixed Parameter Tractability: Algorithms and Lower Bounds

cs.DS cs.CR ·2026-09-11 ·Pritish Kamath, Ravi Kumar, Pasin Manurangsi
theory similarity 0.57
Abstract

We study combinatorial optimization problems under the constraint of $ε$-differential privacy ($ε$-DP). Given the strong lower bounds for explicitly outputting solutions, we work within the implicit representation framework of Gupta et al. (SODA 2010), where a private polynomial-time randomized "encoder" generates a representation of a solution, and a "decoder" uses this representation along with the input to extract a valid final solution. In this work, we generalize this framework by allowing the encoder to run in fixed-parameter tractable time. This circumvents approximation barriers inherent to polynomial-time algorithms and obtains improved guarantees for many fundamental combinatorial optimization problems. Finally, we establish the first representation-independent lower bounds for our framework. Assuming a non-uniform variant of the Gap Exponential Time Hypothesis, for sufficiently small $ε> 0$, we prove that no $ε$-DP encoder-decoder pair can achieve certain approximation guarantees, if the decoder runs in subexponential time. We further provide representation-dependent lower bounds that hold even for larger $ε$.

0.39

Private Vulnerability Testing for User Oversharing

cs.CR ·2026-11-04 ·Alexander Boyd, Daniel Gardham, Nishanth Sastry, Suparna De
similarity 0.56
Abstract · 19 pages, 4 figures, submitted to WWW 2027

Users can inadvertently increase their vulnerability to privacy attacks by oversharing personal information. In particular, the combination of individually innocuous attributes can place a user in a sufficiently small population to enable linkage or re-identification attacks. We present a privacy-preserving mechanism that allows users to determine whether the information they disclose places them below a predefined population threshold, without revealing their query or the data of other users. Our setting presents several practical challenges: users contributing data may be offline when queries are made, queries may select arbitrary subsets of attributes, and neither server should learn the queried population or its size. We address these challenges using secret-shared data and queries, private equality testing, and secure threshold computation. Our protocol provides computational privacy against a malicious client and semi-honest, non-colluding servers, while supporting arbitrary queries and dynamic database updates. We define reactive $f$-privacy for a dynamically evolving database and prove that our construction satisfies it, with the sequence of permitted threshold outputs defining the information available to the adversary across an execution. We optimise the protocol using oblivious-transfer extensions and pre-computation, achieving sub-second online query times for 96-bit queries on datasets of up to one million records.

0.35