This work proposes a practical non-interactive encrypted retrieval framework for RAG based on threshold selection, and introduces a precision-stable mask polarization method that ensures accurate recovery of selected documents.
Abstract
Retrieval-Augmented Generation (RAG) enhances large language models by incorporating external knowledge, but existing pipelines typically operate on plaintext data, raising significant privacy concerns. Prior work on privacy-preserving retrieval leverages cryptographic techniques such as homomorphic encryption (HE) and private information retrieval (PIR), but often relies on interactive protocols or ranking-based selection mechanisms that incur high latency and potential information leakage. In this paper, we propose a practical non-interactive encrypted retrieval framework for RAG based on threshold selection. Instead of performing expensive top-$k$ ranking under encryption, our approach selects documents whose similarity scores exceed a predefined threshold, reducing computational complexity from quadratic to linear in the corpus size. We implement this design using CKKS-based homomorphic computation, enabling fully encrypted similarity evaluation and document selection without revealing query content, intermediate scores, or selected indices. To bridge the gap between approximate encrypted computation and discrete token reconstruction, we introduce a precision-stable mask polarization method that ensures accurate recovery of selected documents. Experiments on standard retrieval benchmarks demonstrate that our approach achieves competitive retrieval effectiveness while significantly reducing latency compared to ranking-based encrypted methods. These results highlight threshold-based selection as a practical foundation for scalable and secure RAG systems.
Homomorphic encryption (HE) schemes based on the Ring Learning with Errors (RLWE) problem have been rapidly developed and widely applied to secure computation tasks, such as privacy-preserving deep learning inference and database queries. However, existing HE schemes mainly focus on the feasibility and efficiency of homomorphic computation, while practical requirements including ciphertext copyright protection, provenance tracking, and computation supervision remain largely unexplored. In this work, we propose a watermarking technique for RLWE-based HE ciphertexts. By exploiting the algebraic structure of RLWE polynomials, we embed watermark information into ciphertext noise without affecting plaintext correctness. To address watermark degradation caused by homomorphic operations, we introduce two practical schemes. The first scheme, ARWMark, leverages noise stratification to achieve robustness against homomorphic additive operations. The second scheme, MRWMark, is based on the roots of a linear equation and supports zero-bit watermarking while remaining robust against both homomorphic addition and multiplication. We provide rigorous theoretical analysis demonstrating that the proposed schemes preserve the original security of HE while maintaining correctness and watermark robustness. Extensive experiments further validate the effectiveness and practicality of the proposed watermarking schemes.
We propose a novel multi-server threshold oblivious retrieval system (ThORY). Our construction extends DORY (a two-server non-threshold oblivious retrieval system proposed in USENIX OSDI 2020) to support arbitrary threshold access structures. The technical centrepiece of ThORY is threshold function secret sharing (TFSS) – an extension of traditional FSS that allows the key to be secret-shared across multiple servers following any arbitrary threshold access structure. We present novel constructions of TFSS based on either purely symmetric-key cryptoprimitives, or any seed-homomorphic pseudorandom generator (for the latter, we present two concrete instantiations from standard group-theoretic assumptions and plausibly quantum-safe lattice-based assumptions). Leveraging TFSS, ThORY achieves leakage-free keyword search and document identifier retrieval under a (t,p)-threshold model, hiding access, search, and volume patterns against any adversary corrupting fewer than t servers. We analyse and evaluate the security and performance of end-to-end implementations of ThORY based on each of these TFSS constructions. Our experiments demonstrate that ThORY scales efficiently with threshold size, outperforming state-of-the-art literature in query latency over large databases.
C. Kumar, Sikhar Patranabis, Debdeep Mukhopadhyay· IACR Communications in Crypt...· 0 citations
Privacy-preserving machine learning and encrypted statistics increasingly require evaluating long chains of matrix products directly on ciphertexts. In the CKKS homomorphic encryption scheme, however, every multiplication amplifies noise and enlarges ciphertexts, so the available precision budget is exhausted after only a few products. This work establishes
c
F
H
E
(compressed FHE), a unified analytical and empirical framework that integrates low-rank matrix factorization techniques into the CKKS homomorphic encryption scheme. Its central idea is a co-design: instead of tuning the low-rank approximation and the cryptographic parameters in isolation,
c
F
H
E
balances the two error sources against each other so that neither wastes precision. Theoretical bounds are derived for the accumulation of relative error across sequences of factorized matrices, leading to an explicit expression for the attainable computation depth as a function of target accuracy, norm amplification behavior, and per-layer approximation quality. Extensions to tree-based evaluation structures are also formulated, allowing depth to scale logarithmically with the number of factors.
Concretely, this co-design is realized as a precision-balancing model that, for a target accuracy, automatically selects the CKKS parameters: the polynomial modulus degree, the modulus chain, and the scaling factor.
Experimental evaluations demonstrate that encrypted low-rank matrix multiplications achieve both significant runtime improvements and reduction of ciphertext sizes over direct or tree-based encrypted multiplications while maintaining the prescribed accuracy.
c
F
H
E
is agnostic to other CKKS optimizations and can be combined with them for further gains.
Dimitrios Schoinianakis, M. Sabzevari· IACR Communications in Crypt...· 0 citations
Encrypted inference under homomorphic encryption (HE) imposes stringent constraints on computation, making the direct deployment of deep neural networks infeasible on resource-constrained edge devices. Existing approaches, such as FHEEDGE and UniHENN, primarily focus on improving the efficiency of encrypted computation through algorithmic and systems-level optimizations. In contrast, we adopt a complementary perspective by redesigning neural architectures to align with the inherent cost model of HE operations. In this work, we present a framework that reformulates HE-aware model design as a constrained neural architecture search problem, where the objective is to identify architectures that are both cryptographically feasible and computationally efficient while preserving task performance. Starting from a pretrained network, we perform a structured, iterative transformation process that includes HE-compatible operator substitutions, depth–width trade-offs, and rotation-efficient design strategies such as successive average pooling. These transformations are guided by constraints on ciphertext slots, multiplicative depth, and rotation complexity, and are evaluated using short-horizon training to efficiently explore the architecture space. We provide a theoretical analysis showing that the transformed network approximates the original model with bounded error under layer-wise Lipschitz propagation, ensuring controlled performance degradation. As a case study, we apply the proposed framework to encrypted crack detection for structural health monitoring. The optimized model achieves an execution time of 86.5 seconds for single-threaded CPU inference in the encrypted domain, compared to an estimated 3.5 hours required by the original encrypted convolutional pipeline. Furthermore, deployment on a Raspberry Pi demonstrates end-to-end encrypted inference within approximately 7.5 minutes. These results highlight that architecture-level optimization, when framed as a constrained search problem, complements existing algorithmic acceleration approaches and provides a practical pathway for enabling efficient and privacy-preserving inference on edge devices across a broad class of sensitive AI workloads.
Reeshav Chowdhury, Anoop Mishra, Deepak Khazanchi et al.· ACM Transactions on Internet...· 0 citations
Large-scale biometric identification in outsourced settings requires two properties simultaneously: biometric templates and queries must remain protected during computation, and the encrypted similarity outputs produced by an untrusted compute node must be verifiably correct before any application result is released. Existing FHE-based biometric systems primarily address confidentiality, while practical verifiability introduces two bottlenecks in the underlying encrypted 1:N matching layer: rotation- and bandwidth-heavy similarity evaluation and the high cost of proving repeated homomorphic similarity traces. We present BioZKFHE, a framework for scalable encrypted biometric identification via verifiable homomorphic similarity evaluation that combines BGV homomorphic computation with committee-mediated proof opening/decryption and smart-contract verification of opened proof batches. To reduce encrypted storage and avoid rotation-heavy encrypted 1:N matching, we propose Single-Coefficient Multi-Value (SCMV) packing, which binds multiple quantized embedding values into each plaintext entry through base-T expansion. To make proof generation practical, we propose Parallelizable and Verifiable Similarity Computation (PVSC), which exploits the Double-CRT execution structure of BGV to decompose each blockwise similarity trace into parallel proof instances that are opened and checked before result release. Under standard lattice assumptions and explicit committee/verifier assumptions, we analyze recoverability, noise growth, confidentiality, encrypted-output integrity, and finalized-result integrity. Experiments on FaceNet and MobileFaceNet show near-lossless biometric utility, up to 67 percent encrypted-storage reduction, and about 22 to 44 seconds end-to-end proof-verified runtime for 10k to 40k templates.
Rundong Xin, Taotao Wang, Xiaoxiao Wu et al.· IEEE Transactions on Dependa...· 0 citations
Many privacy-preserving data analysis tasks based on multi-party computation require oblivious retrieval of data elements for downstream use. As database sizes grow, this retrieval step becomes a dominant bottleneck, highlighting the need for more efficient oblivious access (OA) primitives that retrieve a database entry without revealing the accessed position. A common approach uses distributed point functions (DPFs), which reduce communication but still incur local computation that scales linearly with the database size. Early termination (ET) optimization reduces local computation, but applying it yields only Boolean shares that require costly conversion for arithmetic use. This incompatibility between ET and arithmetic outputs makes it difficult for OA to scale efficiently on large databases. We introduce RingOA, the first three-party OA protocol that supports ET while directly producing arithmetic shares. Our method eliminates the need for share conversion and preserves the computational benefits of ET. RingOA achieves a 13.1x to 15.7x improvement in runtime on databases exceeding one billion entries compared to a state-of-the-art OA protocol. Building on RingOA, we construct an oblivious rank query, a core primitive underlying many structured-data analyses. We develop two practical applications: a fully oblivious full-text search protocol for pattern matching over secret-shared string datasets, and a fully oblivious range-search protocol supporting statistical queries over secret-shared numerical sequences. Experiments on real large-scale genomic datasets show that these applications achieve practical performance, demonstrating the utility of our OA protocol and its applications.
Tomoki Uchiyama, Kana Shimizu· Proceedings on Privacy Enhan...· 0 citations