Private Embedding Lookup with Encrypted Compact Queries under Fully Homomorphic Encryption Volume: 2027 X DOI: XXXXXXX.XXXXXXX CCS: Security and privacy Privacy-preserving protocols

Jung Hee Cheon, Daehyun Jang, Jaehee Kang, Hanee Rhee · 2026

Read Private Embedding Lookup with Encrypted Compact Queries under Fully Homomorphic Encryption Volume: 2027 X DOI: XXXXXXX.XXXXXXX CCS: Security and privacy Privacy-preserving protocols by Jung Hee Cheon, Daehyun Jang, Jaehee Kang, Hanee Rhee (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-03191.txt.

Introduction

Cheon, Jang, Kang, and Rhee speed up private embedding lookup under fully homomorphic encryption. Many language and recommendation models start by mapping a client's input to an embedding vector. The table stays on the server, and the client sends just a small encrypted index.

Past work first built a one-hot vector from that index, then multiplied by the table. That build step cost the most, with cost near p log p steps. The team's key point is that any linearly independent form of the index will do. Their method, IVE, builds such a vector from powers of one encrypted value, at cost near p. A preset change of basis, using a cosine transform, then gives the same embedding back. Lookup ran up to about 78 times faster. In encrypted FastText tests, the vector build share of total time fell from near all of it to two thirds.

Catalog record

CREATORJung Hee Cheon, Daehyun Jang, Jaehee Kang, Hanee Rhee
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE108 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.03191

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Private Embedding Lookup with Encrypted Compact Queries under Fully Homomorphic Encryption Volume: 2027 X DOI: XXXXXXX.XXXXXXX CCS: Security and privacy Privacy-preserving protocols Jung Hee Cheon, Daehyun Jang, Jaehee Kang, Hanee Rhee Abstract . Many Natural Language Processing (NLP) and recommendation models begin by mapping discrete client inputs to embedding vectors. Because these inputs can reveal sensitive information, this embedding step need to be protected in privacy-preserving inference. Fully Homomorphic Encryption (FHE) enables inference over encrypted client data, but under FHE the embedding lookup is no longer a simple table access and has to be realized through homomorphic computation. To keep the embedding table on the server and avoid transmitting encrypted embedding vectors from the client, we focus on the server-side lookup: the client sends only a small encrypted index. Prior work from ICML 2024 ( 36 ) first builds a one-hot vector from the encrypted index before multiplying it with the embedding table, and this one-hot generation is the dominant cost. However, one-hot-based methods are expensive in FHE because they construct a p p -dimensional selection vector by performing an equality test for each coordinate, requiring O ⁡ ( p ​ log ⁡ p ) O(p\log p) homomorphic operations in total. Our key observation is that private embedding lookup only requires a linearly independent representation of the encrypted index, not the one-hot basis itself. Building on this observation, we propose Independent Vector Evaluation (IVE). Instead of constructing a one-hot vector, IVE evaluates a linearly independent vector built from successive powers of a single encrypted value, reducing the vector-generation cost to O ⁡ ( p ) O(p) homomorphic operations. It then recovers the same embedding vector through a precomputed change of basis, which we instantiate with an orthogonal Discrete Cosine Transform (DCT) to mitigate error amplification. Our implementation demonstrates that this design improves amortized lookup time by up to 78.4 × 78.4\times over the prior method. We further evaluate its impact through end-to-end encrypted FastText inference, where embedding lookup is a major cost in the shallow model. Concretely, on the Enron-Spam email-spam dataset, replacing one-hot generation with IVE reduces the share of vector generation in encrypted inference time from 99.6 % 99.6\% to 66.3 % 66.3\% . 1. Introduction Modern machine learning (ML) services increasingly run through an outsourcing model: a client sends an input to a server, and the server evaluates a model on that input. This model is natural in ML-as-a-Service (MLaaS), where clients such as smartphones, wearable devices, or small applications may not have the memory or compute resources to run the full model locally. This delegated computation creates an immediate privacy problem. The input sent to the server can reveal medical symptoms, financial behavior, search intent, or the exact words typed by the user. Thus, the client may want to use the model while keeping the input hidden from the server that evaluates it. Privacy-preserving machine learning (PPML) addresses this problem by allowing the server to compute on the client’s data without directly observing it. Fully Homomorphic Encryption (FHE) is a natural tool for PPML because it supports arithmetic computation directly on ciphertexts ( 26 ; 24 ; 8 ; 15 ; 23 ; 14 ; 9 ) . Compared with MPC or OT-based protocols, FHE keeps the online interaction simple: the client encrypts its input, the server evaluates the circuit, and the client or a later component decrypts only the intended result. This is attractive in the MLaaS setting because the client does not need to participate in every layer of the computation after sending the encrypted input. Compared with differential privacy, FHE targets cryptographic confidentiality of the input rather than hiding an individual’s contribution through noise. Among various homomorphic encryption schemes, the CKKS scheme ( 14 ) is widely used for PPML because it efficiently supports approximate computation over complex numbers. Recent progress in such FHE schemes, together with FHE algorithms for neural-network inference ( 28 ; 21 ; 20 ; 11 ; 44 ; 51 ) , has made encrypted inference a realistic target for a growing range of ML workloads. For arithmetic layers, this progress is especially visible: homomorphic linear layers can use algorithmic reductions to plaintext matrix multiplication ( 5 ; 47 ; 13 ) , while nonlinear functions such as activation functions are increasingly optimized through polynomial approximations ( 17 ) . This paper focuses on a different bottleneck in such pipelines: privately performing the embedding lookup for discrete user inputs. For models whose inputs include discrete tokens or indices, inference begins with an embedding layer. Given an index j\in[P] , the embedding layer retrieves the vector M_{j}\in\mathbb{R}^{d} , the column indexed by j of an embedding table M\in\mathbb{R}^{d\times P} , and passes this vector to the remaining layers. Equivalently, if {\bf e}_{j} is the one-hot vector for index j , then the lookup can be written as M_{j}=M{\bf e}_{j} . The embedding layer therefore converts a discrete index into the continuous vector representation expected by the rest of the model. This step is standard in word embeddings ( 43 ; 49 ) , transformers ( 54 ; 22 ) , and recommendation models ( 45 ) . The privacy of the index itself is important. A token index is not an arbitrary number: it identifies a word, subword, item, or query chosen by the user. Revealing whether a user typed a medical term, a financial term, or a politically sensitive term may already reveal the sensitive part of the interaction. Thus, for FHE-based inference over discrete inputs, the lookup from the index to the embedding vector must also be handled without revealing the index. There are two direct ways to handle this step. The first way is client-side embedding: the client obtains the embedding table, performs the lookup locally, encrypts M_{j} , and sends the encrypted vector to the server. This avoids encrypted lookup on the server, but it requires the server to distribute the embedding table to the client and the client to send an encrypted d -dimensional vector per token. For GloVe.42B.300d, the table has 1.9\mathrm{M} vectors of dimension 300 , which is about 2.3 GB in single precision before any encryption is considered. Thus, the client must receive and store a large table. If the table is proprietary, distributing it also exposes model parameters to the client. Even when the table is public, storage, redistribution, and update costs remain substantial. The encrypted vector sent per token also adds substantial client-to-server communication, since the transmitted ciphertexts scale with the embedding dimension d . This cost becomes more pronounced for multi-token inputs or large embedding dimensions. These requirements are unattractive for lightweight clients. The other way is server-side embedding: the client sends an encrypted query derived from the index j , and the server performs the lookup on ciphertexts. This keeps the table on the server and avoids sending the embedding vector from the client, but it shifts the table-size dependent lookup cost to the server. We call this server-side task Private Embedding Lookup (PEL) : the client sends an encrypted query derived from a private index, and the server produces ciphertexts encoding the corresponding embedding vector in a form suitable for the following homomorphic layers. The main difficulty

Read the complete text