Private Embedding Lookup with Encrypted Compact Queries under Fully Homomorphic Encryption

Many NLP and recommendation models begin by mapping discrete client inputs to embedding vectors. Since these inputs can reveal sensitive information, the embedding step must be protected in privacy-preserving inference. Fully Homomorphic Encryption (FHE) enables inference over encrypted client data, but turns embedding lookup from simple table access into homomorphic computation. To keep the embedding table server-side and avoid transmitting encrypted embedding vectors from the client, this work focuses on server-side lookup: the client sends only a small encrypted index.

Prior work first builds a one-hot vector from the encrypted index before multiplying it with the embedding table, making one-hot generation the dominant cost. This paper observes that private embedding lookup only requires a linearly independent representation of the encrypted index, not the one-hot basis itself. It proposes Independent Vector Evaluation (IVE), which evaluates a linearly independent vector from successive powers of one encrypted value, reducing vector-generation cost from O(p log p) to O(p). The method recovers the embedding vector through a precomputed change of basis instantiated with an orthogonal Discrete Cosine Transform (DCT). The implementation improves amortized lookup time by up to 78.4x over the prior method and reduces the vector-generation share of encrypted FastText inference time on Enron-Spam from 99.6% to 66.3%.