💻 computer science

Private Embedding Lookup with Encrypted Compact Queries under Fully Homomorphic Encryption

This paper proposes Independent Vector Evaluation (IVE), a novel method for private embedding lookup under Fully Homomorphic Encryption that replaces costly one-hot vector generation with a linearly independent representation to achieve up to a 78.4x speedup in amortized lookup time.

Original authors: Daehyun Jang, Jaehee Kang, Hanee Rhee, Jung Hee Cheon

Published 2026-06-03

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Daehyun Jang, Jaehee Kang, Hanee Rhee, Jung Hee Cheon

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive, secret library of books (the embedding table) stored on a giant server. Each book represents a specific word or idea, and inside each book is a unique "fingerprint" (an embedding vector) that helps a computer understand the meaning of that word.

Usually, when you want to ask the server a question, you send it a word. The server looks up that word in its library, grabs the fingerprint, and uses it to give you an answer.

The Privacy Problem:
You don't want the server to know which word you asked for. Maybe you're asking about a medical symptom, a financial secret, or something sensitive. If you just send the word, the server sees it. If you send a secret code, the server can't read it to find the right book.

The Old Way (The "One-Hot" Method):
In the past, to keep your question secret, you had to send a special encrypted list. Imagine this list has a slot for every single word in the library (millions of slots). You encrypt a "1" in the slot for your word and "0" everywhere else.

The Problem: The server has to check every single slot to see which one is the "1." It's like the server has to walk down every aisle of a massive library, checking every single book, just to find the one you want. This takes a huge amount of time and computing power, making the whole process very slow.

The New Way (IVE - Independent Vector Evaluation):
This paper proposes a clever shortcut. Instead of sending a list with a "1" and millions of "0"s, the authors realized the server doesn't actually need that specific list. It just needs some unique code that points to the right book, as long as the server knows how to translate that code back into the right fingerprint.

Think of it like this:

The Old Way: You send a map with a giant red "X" on one specific house and blank spaces everywhere else. The server has to scan the whole map to find the "X."
The New Way (IVE): You send a simple set of coordinates (like "Turn left, then go 3 blocks"). The server knows a secret formula (a change of basis) that instantly turns those coordinates into the exact address of the house you want.

How it Works (The Magic Trick):

The Secret Code: Instead of a "1 and 0s" list, the client sends a compact, encrypted number.
The Math Magic: The server uses a mathematical tool called Discrete Cosine Transform (DCT). Think of this as a special translator. It takes your simple encrypted number and quickly turns it into a unique "fingerprint" code using simple math (powers of a number), rather than slow, heavy checking.
The Translation: The server has a pre-computed "dictionary" (the change of basis matrix) that knows how to turn your new "fingerprint" code back into the exact same book fingerprint the old method would have found.

Why This Matters:

Speed: The old method was like walking down every aisle. The new method is like using a GPS. The paper shows this makes the lookup up to 78 times faster.
Efficiency: It saves a massive amount of computer energy. In tests, the time spent just "finding the book" dropped from taking up 99.6% of the total time to just 66.3%.
Privacy: The server still learns nothing about your specific word, but it gets the answer much faster.

In a Nutshell:
The authors found a way to stop the server from doing a million tiny checks to find your secret word. Instead, they gave it a simple encrypted clue and a magic translation key. This lets the server find the right information almost instantly, keeping your secrets safe without making the computer wait forever.

Technical Summary: Private Embedding Lookup with Encrypted Compact Queries under Fully Homomorphic Encryption

Problem Statement

In privacy-preserving machine learning (PPML) using Fully Homomorphic Encryption (FHE), a critical bottleneck arises during the inference of models that rely on discrete inputs, such as Natural Language Processing (NLP) and recommendation systems. These models typically begin with an embedding layer, which maps a discrete index (e.g., a word token) to a continuous vector.

Under FHE, the server cannot perform standard memory access based on an encrypted index. Instead, the lookup must be realized through homomorphic arithmetic. Existing approaches face a trade-off:

Client-side lookup: The client sends the encrypted embedding vector. This incurs massive communication overhead proportional to the embedding dimension ( $d$ ), which is prohibitive for large tables (e.g., GloVe with 1.9M tokens).
Server-side lookup with One-Hot Generation: The client sends a compact encrypted scalar index. The server must then homomorphically construct a one-hot vector to select the embedding. Prior work (Kim et al., ICML 2024) achieves this using an Encrypted Indicator Function (EIF), but this requires $O(p \log p)$ homomorphic operations (where $p$ is the table size), consuming significant multiplicative depth and becoming the dominant cost in the inference pipeline.

The goal is to achieve Private Embedding Lookup (PEL) that maintains compact client communication (sending only a scalar index) while minimizing the server-side homomorphic computation cost, avoiding the expensive one-hot generation step.

Methodology: Independent Vector Evaluation (IVE)

The authors propose Independent Vector Evaluation (IVE), a method that bypasses the construction of a one-hot vector entirely.

Core Insight

The server does not strictly require a one-hot vector ( $e_j$ ) to retrieve the embedding $M_j$ . It only requires a representation of the index $j$ that is linearly independent across different indices. If a set of vectors $\{v_j\}$ is linearly independent, there exists a change-of-basis matrix $L$ such that $L v_j = e_j$ . Consequently, the embedding retrieval can be rewritten as:
$M_j = M e_j = M (L v_j) = (M L) v_j$
Since $M$ and $L$ are known in plaintext, the server can precompute the matrix $M' = ML$. The online task then shifts from generating a one-hot vector to evaluating the vector $v_j$ homomorphically.

Vector Construction and Stability

To ensure efficiency and numerical stability under the CKKS scheme (which supports approximate arithmetic):

Efficiency: The vectors $v_j$ are constructed using successive powers of a single encrypted value $\alpha_j$ . This allows the server to generate the vector components using standard arithmetic operations (multiplications) rather than complex equality tests.
Stability: To prevent error amplification during the change of basis, the matrix $L$ must be well-conditioned (ideally orthogonal). The authors utilize a Discrete Cosine Transform (DCT) matrix. By using roots of unity and separating real and imaginary parts, they construct an orthogonal basis that aligns with CKKS's complex arithmetic capabilities.

Algorithmic Flow

Client: Encrypts the index $j$ into a value $\alpha_j$ (derived from roots of unity) and transmits it as a compact scalar query.
Server (IVE Phase):
- Receives the encrypted $\alpha_j$ .
- Computes the powers $\alpha_j^0, \alpha_j^1, \dots, \alpha_j^{p/2}$ using a multiplication tree (logarithmic depth).
- Separates real and imaginary parts via conjugation to form the vector $v_j$ .
- This process requires $O(p)$ homomorphic operations, a significant reduction from the $O(p \log p)$ required for one-hot generation.
Server (PCMM Phase):
- Performs a Plaintext-Ciphertext Matrix Multiplication (PCMM) between the precomputed matrix $M' = ML$ and the generated vector $v_j$ .
- This yields the encrypted embedding vector.

Key Contributions

Independent Vector Evaluation (IVE): A novel algorithm that replaces encrypted one-hot generation with the evaluation of a linearly independent vector family. This reduces the vector generation complexity from $O(p \log p)$ to $O(p)$ homomorphic operations.
Orthogonal Basis via DCT: The instantiation of IVE using a DCT-based orthogonal matrix ensures numerical stability, mitigating error amplification inherent in CKKS approximation when performing the change of basis.
Integrated PEL Pipeline: The authors integrate IVE with PCMM to handle batched queries efficiently. This pipeline supports multiple token queries simultaneously, amortizing the cost across the CKKS SIMD slots.
End-to-End Implementation: The method is implemented within a FastText-style text classification pipeline, demonstrating its viability for practical, privacy-sensitive inference tasks.

Experimental Results

The authors evaluated IVE-PEL against the prior state-of-the-art (Kim et al.) using three embedding datasets (GloVe.6B.50d, GloVe.42B.300d, and GPT-2) and an end-to-end FastText inference on the Enron-Spam dataset.

Vector Generation Speedup: IVE-PEL significantly reduces the time spent on vector generation. For a subtable size of $\log p = 10$ , the VecGen time dropped from ~424 ms (Kim et al.) to ~3.15 ms (IVE-PEL) on GloVe.6B.50d, representing a 134.6× speedup in this specific stage.
Total Pipeline Speedup: The amortized lookup time improved by 18.5× to 78.4× depending on the dataset and embedding dimension. The largest gains were observed in scenarios where vector generation was the dominant cost.
Multiplicative Depth: IVE-PEL consumes approximately 1/3 of the multiplicative depth required by the one-hot generation method, allowing for larger subtable sizes and better compression quality without exhausting the CKKS noise budget.
End-to-End Impact: In the Enron-Spam classification task, replacing the one-hot method with IVE reduced the share of vector generation in the total encrypted inference time from 99.6% to 66.3%, substantially lowering the overall latency.

Significance and Claims

The paper claims that IVE-PEL addresses the "missing design point" in private embedding lookup: achieving compact client communication (scalar indices) without incurring the prohibitive server-side cost of homomorphic one-hot generation.

By decoupling the need for a one-hot basis from the retrieval process, the authors demonstrate that private embedding lookup can be made practical for lightweight clients and large-scale models. The results suggest that IVE-PEL makes server-side embedding a viable alternative to client-side embedding, enabling efficient, privacy-preserving inference for NLP and recommendation models without sacrificing the confidentiality of the user's input indices. The method maintains the accuracy of the underlying models (as evidenced by IMDB sentiment classification and spam detection results) while drastically improving computational efficiency.