Nearest neighbor search is everywhere. Face recognition compares a captured face against a gallery of known people. Recommendation systems find the items closest to a user’s taste. Semantic search finds the documents closest to a question. All of them turn their inputs into vectors, called embeddings, and ask the same question: which stored vectors are closest to this one? The trouble is that those vectors are deeply personal. A face embedding is biometric data, a preference vector is a profile of your habits, and a question embedding can be translated back into something close to the original text. In this post, we’ll find the nearest neighbors without revealing the query, using partially homomorphic encryption with LightPHE in Python, Go, Java and TypeScript.
Our running example is face recognition, where embeddings typically come from a model such as DeepFace. Real face embeddings have 128 to 512 dimensions. We’ll use 4-dimensional ones to keep the examples readable, but the code works the same way for any dimension.
🙋♂️ You may consider to enroll my top-rated cryptography course on Udemy
Two Settings, Two Different Problems
Encrypted nearest neighbor search comes in two flavours, depending on who owns the gallery of stored vectors, and they need very different cryptography:
- A server owns the gallery in plain, and a client has a private query. A building’s server holds the face embeddings of its employees, and a visitor’s phone wants to know whether the visitor is one of them, without showing its face to the server. The server must not learn the query or the result, and the client must not learn anyone else in the gallery—only who the nearest people are.
- An owner stores its encrypted gallery in an untrusted cloud. A company keeps the face embeddings of its employees in a public cloud, and searches them with encrypted queries. The cloud stores and computes, but must learn nothing: neither the gallery, nor the queries, nor the results.
Both measure closeness with the squared euclidean distance:
d(q, x) = (q_1 - x_1)^2 + (q_2 - x_2)^2 + ... + (q_n - x_n)^2
The square root is skipped on purpose: it is monotonic, so it doesn’t change which vector is the nearest, and it would be a nightmare under encryption.
Setting 1: Plain Gallery, Encrypted Query
Required Homomorphic Features
This setting follows the protocol of Erkin et al. in Privacy-Preserving Face Recognition (PETS 2009), and it needs five things.
1. Additive homomorphism and scalar multiplication to compute distances. The query is encrypted, but each gallery vector is the server’s own plain data. Expanding the square makes the distance linear in the encrypted query:
d(q, x) = ||q||^2 - 2 (q . x) + ||x||^2 E(d) = E(||q||^2) * E(q_1)^(-2 x_1) * ... * E(q_n)^(-2 x_n) * E(||x||^2)
The only term the server cannot compute is ||q||^2, since squaring an encrypted value needs a multiplication of two ciphertexts. So the client simply computes it in plain and sends it encrypted along with the query. Everything else is additions and multiplications with the server’s plain numbers.
2. Integers. Embeddings are floats, so they are quantized: scaled, e.g. by 100, and rounded. Both the query and the gallery must be quantized the same way. Squared distances must be less than 2^bit_length, which you pass to the search.
3. Encrypted argmin. The server now holds an encrypted distance for every gallery vector, and it cannot decrypt them. Sending them to the client would leak far too much: the distances to every person in the gallery. Instead, the server turns each distance into 2^bit_length - 1 - d, so the nearest vector gets the greatest value, and runs the encrypted argmax of Damgard-Geisler-Kroigaard, which compares encrypted values with a few masked round trips to the client. The result is the encrypted index of the nearest vector, and neither side learns anything else. We covered encrypted argmax in detail in the post on encrypted logistic regression and linear SVM.
4. An encrypted equality test, to find the next nearest vector. For k > 1, the server must exclude the vector it just found, but it only has its index in encrypted form. So it turns the encrypted index into an encrypted one-hot vector with the client’s help: for every position i, it computes E(r_i (index - i)) with a fresh random r_i, shuffles them, and sends them to the client. Exactly one of them decrypts to zero, at a random position, and every other one is a random number. The client returns an encrypted 1 for the zero and an encrypted 0 for the others, without learning which vector it was. The server then lifts every other value by 2^bit_length homomorphically, so the next argmax finds the next nearest vector. The same one-hot vector also selects the label of the found vector, e.g. an employee ID, in encrypted form.
5. A small plaintext space with a cheap zero test. Both the argmax comparisons and the equality test rely on checking many blinded values for zero, which Damgard-Geisler-Kroigaard does with a single exponentiation, thanks to its plaintext space of about 32 bits.
Example: Unlocking a Door with Your Face
A visitor walks up to an office building. Their phone computes a face embedding from a selfie and encrypts it. The building’s server holds the embeddings of its employees, labeled with employee IDs, and finds the 2 nearest employees. The phone learns only the IDs of the 2 nearest employees, and the server learns nothing.
from lightphe import LightPHE # visitor's phone builds the cryptosystem, keeps the private key and shares the public key phone_cs = LightPHE(algorithm_name = "Damgard-Geisler-Kroigaard") phone_cs.export_keys(target_file = "public.txt", public = True) # face embedding of the visitor, quantized to integers by scaling with 100 and rounding embedding = [0.12, -0.07, 0.33, 0.05] encrypted_query = phone_cs.encrypt_knn_query([round(x * 100) for x in embedding]) # building's server keeps the face embeddings of its employees in plain server_cs = LightPHE(algorithm_name = "Damgard-Geisler-Kroigaard", key_file = "public.txt") gallery = [[0.10, -0.05, 0.30, 0.04], [-0.40, 0.22, 0.01, 0.09], [0.13, -0.08, 0.35, 0.06]] employees = [101, 102, 103] quantized_gallery = [[round(x * 100) for x in vector] for vector in gallery] # server finds the 2 nearest employees with the phone's help. # squared distances must be less than 2^bit_length result = server_cs.evaluate_knn( encrypted_query, quantized_gallery, k = 2, bit_length = 16, client = phone_cs.answer_knn, labels = employees ) # phone learns only who the nearest employees are, from the nearest one assert [phone_cs.decrypt(label) for label in result["labels"]] == [103, 101]
package main
import (
"fmt"
"log"
"math"
"github.com/serengil/lightphe-go/lightphe"
)
func check(err error) {
if err != nil {
log.Fatal(err)
}
}
// quantize scales a float embedding by 100 and rounds it to integers
func quantize(vector []float64) []int64 {
out := make([]int64, len(vector))
for i, x := range vector {
out[i] = int64(math.Round(x * 100))
}
return out
}
func main() {
// visitor's phone builds the cryptosystem, keeps the private key and shares the public key
phoneCs, err := lightphe.New(lightphe.DamgardGeislerKroigaard)
check(err)
check(phoneCs.ExportKeys("public.txt", true))
// face embedding of the visitor, quantized to integers
embedding := []float64{0.12, -0.07, 0.33, 0.05}
encryptedQuery, err := phoneCs.EncryptKNNQuery(quantize(embedding))
check(err)
// building's server keeps the face embeddings of its employees in plain
serverCs, err := lightphe.New(lightphe.DamgardGeislerKroigaard, lightphe.WithKeyFile("public.txt"))
check(err)
gallery := [][]float64{{0.10, -0.05, 0.30, 0.04}, {-0.40, 0.22, 0.01, 0.09}, {0.13, -0.08, 0.35, 0.06}}
employees := []int64{101, 102, 103}
var quantizedGallery [][]int64
for _, vector := range gallery {
quantizedGallery = append(quantizedGallery, quantize(vector))
}
// server finds the 2 nearest employees with the phone's help.
// squared distances must be less than 2^bitLength
result, err := serverCs.EvaluateKNN(encryptedQuery, quantizedGallery, 2, 16, phoneCs.AnswerKNN, employees)
check(err)
// phone learns only who the nearest employees are, from the nearest one
for _, label := range result.Labels {
employee, err := phoneCs.Decrypt(label)
check(err)
fmt.Println(employee) // 103, then 101
}
}
import io.github.serengil.lightphe.LightPHE;
import io.github.serengil.lightphe.model.EncryptedKnnQuery;
import io.github.serengil.lightphe.model.KnnResult;
import java.math.BigInteger;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.List;
// visitor's phone builds the cryptosystem, keeps the private key and shares the public key
LightPHE phoneCs = LightPHE.builder().algorithmName("Damgard-Geisler-Kroigaard").build();
phoneCs.exportKeys(Path.of("public.txt"), true);
// face embedding of the visitor, quantized to integers by scaling with 100 and rounding
double[] embedding = {0.12, -0.07, 0.33, 0.05};
List<Long> query = new ArrayList<>();
for (double x : embedding) {
query.add(Math.round(x * 100));
}
EncryptedKnnQuery encryptedQuery = phoneCs.encryptKnnQuery(query);
// building's server keeps the face embeddings of its employees in plain
LightPHE serverCs = LightPHE.builder()
.algorithmName("Damgard-Geisler-Kroigaard")
.keyFile(Path.of("public.txt"))
.build();
double[][] gallery = {{0.10, -0.05, 0.30, 0.04}, {-0.40, 0.22, 0.01, 0.09}, {0.13, -0.08, 0.35, 0.06}};
List<Long> employees = List.of(101L, 102L, 103L);
List<List<Long>> quantizedGallery = new ArrayList<>();
for (double[] vector : gallery) {
List<Long> quantized = new ArrayList<>();
for (double x : vector) {
quantized.add(Math.round(x * 100));
}
quantizedGallery.add(quantized);
}
// server finds the 2 nearest employees with the phone's help.
// squared distances must be less than 2^bitLength
KnnResult result = serverCs.evaluateKnn(
encryptedQuery, quantizedGallery, 2, 16, phoneCs::answerKnn, employees);
// phone learns only who the nearest employees are, from the nearest one
List<BigInteger> nearest = result.labels().stream().map(phoneCs::decrypt).toList();
assert nearest.equals(List.of(BigInteger.valueOf(103), BigInteger.valueOf(101)));
import { LightPHE } from 'lightphe-ts';
// quantize scales a float embedding by 100 and rounds it to integers
const quantize = (vector: number[]) => vector.map((x) => Math.round(x * 100));
// visitor's phone builds the cryptosystem, keeps the private key and shares the public key
const phoneCs = new LightPHE({ algorithmName: 'Damgard-Geisler-Kroigaard' });
phoneCs.exportKeys('public.txt', true);
// face embedding of the visitor, quantized to integers
const embedding = [0.12, -0.07, 0.33, 0.05];
const encryptedQuery = phoneCs.encryptKnnQuery(quantize(embedding));
// building's server keeps the face embeddings of its employees in plain
const serverCs = new LightPHE({ algorithmName: 'Damgard-Geisler-Kroigaard', keyFile: 'public.txt' });
const gallery = [
[0.1, -0.05, 0.3, 0.04],
[-0.4, 0.22, 0.01, 0.09],
[0.13, -0.08, 0.35, 0.06],
];
const employees = [101, 102, 103];
// server finds the 2 nearest employees with the phone's help.
// squared distances must be less than 2^bitLength
const result = await serverCs.evaluateKnn(
encryptedQuery,
gallery.map(quantize),
2,
16,
phoneCs.answerKnn,
{ labels: employees }
);
// phone learns only who the nearest employees are, from the nearest one
const nearest = result.labels!.map((label) => phoneCs.decrypt(label));
console.assert(nearest.join() === '103,101');
After quantization, the squared distances from the visitor to employees 101, 102 and 103 are 18, 4585 and 7, so the phone gets 103 first and 101 second. It never sees these distances, and it never learns that employee 102 exists. In this run, the server sent the phone 14 messages: 12 for the two argmax rounds, 3 round trips per comparison of 3 candidates, and 2 equality rounds, one for each found label. In each equality round, the phone saw exactly one zero among 3 values, in a shuffled position.
The cost grows with both the gallery size and k, since every round compares all vectors. In Python with 1024-bit keys, it takes about 0.6 seconds per gallery vector and per nearest vector to find; Go is about four times faster. That’s fine for a building with a few hundred employees, and it’s the price of hiding everything from both sides. Java snippets use assert for brevity, so run them with -ea to enable assertions.
Setting 2: Encrypted Gallery in an Untrusted Cloud
Required Homomorphic Features
Now the gallery is encrypted as well, so the trick of the first setting stops working: q . x is a product of two ciphertexts. Squared distance is a degree-2 function, so we need exactly one multiplication of ciphertexts, followed by additions:
E(d) = E(q_1 - x_1) * E(q_1 - x_1) + ... + E(q_n - x_n) * E(q_n - x_n)
Additively homomorphic cryptosystems cannot multiply two ciphertexts on their own. The Catalano-Fiore transform boosts them with exactly one multiplication, without changing the underlying cryptosystem. A multiplied ciphertext can still be added to others and multiplied by constants, but not multiplied again—which is all a squared distance needs.
There is no argmin under encryption here, and no interaction: the cloud computes every encrypted distance with the public key alone, and the owner decrypts them and sorts them locally. That’s fine, because the owner owns both the gallery and the query, so the distances reveal nothing it doesn’t already know. The cloud sees ciphertexts only.
Example: Searching an Encrypted Employee Gallery in the Cloud
A company encrypts the face embeddings of its employees once and uploads them to a public cloud. Whenever a camera captures a face, the company encrypts its embedding, the cloud computes the encrypted distances to the whole gallery, and the company decrypts them to find the nearest employees.
from lightphe import LightPHE # company builds a cryptosystem boosted with one multiplication, and keeps the private key company_cs = LightPHE(algorithm_name = "Paillier", boost = "Catalano-Fiore") company_cs.export_keys(target_file = "public.txt", public = True) # company encrypts the face embeddings of its employees once, and uploads them to the cloud gallery = [[0.10, -0.05, 0.30, 0.04], [-0.40, 0.22, 0.01, 0.09], [0.13, -0.08, 0.35, 0.06]] encrypted_gallery = [[company_cs.encrypt(round(x * 100)) for x in vector] for vector in gallery] # later, company encrypts the embedding of a captured face as a query embedding = [0.12, -0.07, 0.33, 0.05] encrypted_query = [company_cs.encrypt(round(x * 100)) for x in embedding] # cloud computes encrypted squared distances with the public key only cloud_cs = LightPHE(algorithm_name = "Paillier", key_file = "public.txt", boost = "Catalano-Fiore") encrypted_distances = cloud_cs.evaluate_knn_distances(encrypted_query, encrypted_gallery) # company decrypts the distances and finds the 2 nearest employees locally result = company_cs.decrypt_knn(encrypted_distances, k = 2) assert result["indices"] == [2, 0] assert result["distances"] == [7, 18]
package main
import (
"fmt"
"log"
"math"
"github.com/serengil/lightphe-go/lightphe"
)
func check(err error) {
if err != nil {
log.Fatal(err)
}
}
func main() {
// company builds a cryptosystem boosted with one multiplication, and keeps the private key
companyCs, err := lightphe.New(lightphe.Paillier, lightphe.WithBoost(lightphe.CatalanoFiore))
check(err)
check(companyCs.ExportKeys("public.txt", true))
// encrypt scales a float embedding by 100, rounds it and encrypts it
encrypt := func(vector []float64) []*lightphe.Ciphertext {
var out []*lightphe.Ciphertext
for _, x := range vector {
c, err := companyCs.EncryptInt(int64(math.Round(x * 100)))
check(err)
out = append(out, c)
}
return out
}
// company encrypts the face embeddings of its employees once, and uploads them to the cloud
gallery := [][]float64{{0.10, -0.05, 0.30, 0.04}, {-0.40, 0.22, 0.01, 0.09}, {0.13, -0.08, 0.35, 0.06}}
var encryptedGallery [][]*lightphe.Ciphertext
for _, vector := range gallery {
encryptedGallery = append(encryptedGallery, encrypt(vector))
}
// later, company encrypts the embedding of a captured face as a query
encryptedQuery := encrypt([]float64{0.12, -0.07, 0.33, 0.05})
// cloud computes encrypted squared distances with the public key only
cloudCs, err := lightphe.New(lightphe.Paillier, lightphe.WithKeyFile("public.txt"), lightphe.WithBoost(lightphe.CatalanoFiore))
check(err)
encryptedDistances, err := cloudCs.EvaluateKNNDistances(encryptedQuery, encryptedGallery)
check(err)
// company decrypts the distances and finds the 2 nearest employees locally
nearest, err := companyCs.DecryptKNN(encryptedDistances, 2)
check(err)
fmt.Println(nearest.Indices, nearest.Distances) // [2 0] [7 18]
}
import io.github.serengil.lightphe.LightPHE;
import io.github.serengil.lightphe.model.CatalanoFioreCiphertext;
import io.github.serengil.lightphe.model.KnnDistances;
import java.math.BigInteger;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.List;
// company builds a cryptosystem boosted with one multiplication, and keeps the private key
LightPHE companyCs = LightPHE.builder().algorithmName("Paillier").boost("Catalano-Fiore").build();
companyCs.exportKeys(Path.of("public.txt"), true);
// company encrypts the face embeddings of its employees once, and uploads them to the cloud
double[][] gallery = {{0.10, -0.05, 0.30, 0.04}, {-0.40, 0.22, 0.01, 0.09}, {0.13, -0.08, 0.35, 0.06}};
List<List<CatalanoFioreCiphertext>> encryptedGallery = new ArrayList<>();
for (double[] vector : gallery) {
List<CatalanoFioreCiphertext> encryptedVector = new ArrayList<>();
for (double x : vector) {
encryptedVector.add(companyCs.encryptBoosted(Math.round(x * 100)));
}
encryptedGallery.add(encryptedVector);
}
// later, company encrypts the embedding of a captured face as a query
List<CatalanoFioreCiphertext> encryptedQuery = new ArrayList<>();
for (double x : new double[] {0.12, -0.07, 0.33, 0.05}) {
encryptedQuery.add(companyCs.encryptBoosted(Math.round(x * 100)));
}
// cloud computes encrypted squared distances with the public key only
LightPHE cloudCs = LightPHE.builder()
.algorithmName("Paillier")
.keyFile(Path.of("public.txt"))
.boost("Catalano-Fiore")
.build();
List<CatalanoFioreCiphertext> encryptedDistances =
cloudCs.evaluateKnnDistances(encryptedQuery, encryptedGallery);
// company decrypts the distances and finds the 2 nearest employees locally
KnnDistances result = companyCs.decryptKnn(encryptedDistances, 2);
assert result.indices().equals(List.of(2, 0));
assert result.distances().equals(List.of(BigInteger.valueOf(7), BigInteger.valueOf(18)));
import { LightPHE } from 'lightphe-ts';
// company builds a cryptosystem boosted with one multiplication, and keeps the private key
const companyCs = new LightPHE({ algorithmName: 'Paillier', boost: 'Catalano-Fiore' });
companyCs.exportKeys('public.txt', true);
// encrypt scales a float embedding by 100, rounds it and encrypts it
const encrypt = (vector: number[]) => vector.map((x) => companyCs.encrypt(Math.round(x * 100)));
// company encrypts the face embeddings of its employees once, and uploads them to the cloud
const gallery = [
[0.1, -0.05, 0.3, 0.04],
[-0.4, 0.22, 0.01, 0.09],
[0.13, -0.08, 0.35, 0.06],
];
const encryptedGallery = gallery.map(encrypt);
// later, company encrypts the embedding of a captured face as a query
const encryptedQuery = encrypt([0.12, -0.07, 0.33, 0.05]);
// cloud computes encrypted squared distances with the public key only
const cloudCs = new LightPHE({
algorithmName: 'Paillier',
keyFile: 'public.txt',
boost: 'Catalano-Fiore',
});
const encryptedDistances = cloudCs.evaluateKnnDistances(encryptedQuery, encryptedGallery);
// company decrypts the distances and finds the 2 nearest employees locally
const result = companyCs.decryptKnn(encryptedDistances, 2);
console.assert(result.indices.join() === '2,0');
console.assert(result.distances.join() === '7,18');
The company gets indices 2 and 0, with squared distances 7 and 18, the same answer as in the first setting. This setting is much cheaper, since there are no round trips and no comparisons under encryption. The price is size: each multiplied ciphertext keeps a pair of ciphertexts for every product, so an encrypted distance over 512 dimensions is far larger than a plain Paillier ciphertext.
Which Algorithms Can Be Used, and Why
The two settings need different features, so they accept different cryptosystems. I ran both examples against every candidate in LightPHE, and here is what works:
| Algorithms | Plain gallery, encrypted query | Encrypted gallery in the cloud | Why |
| Damgard-Geisler-Kroigaard | ✅ | ✅ | Small plaintext space, cheap zero test and encrypted argmax for the first setting, and additive, so Catalano-Fiore can boost it for the second |
| Paillier, Damgard-Jurik, Benaloh, Naccache-Stern, Joye-Libert, Bresson-Catalano-Pointcheval, Camenisch-Shoup, Castagnos-Laguillaumie, Elliptic Curve Paillier | ❌ | ✅ | Additive with a public plaintext space and direct decryption, which is what Catalano-Fiore needs. Their plaintext spaces are too large for the comparisons of the first setting, so LightPHE refuses them there and points to Damgard-Geisler-Kroigaard |
For the cloud setting, Paillier is the practical default. In my tests, Paillier, Joye-Libert and Damgard-Geisler-Kroigaard ran the cloud example in about a second, key generation included, while Elliptic Curve Paillier, Benaloh, Castagnos-Laguillaumie and Naccache-Stern took between 12 and 46 seconds, mostly in key generation.
Comparing the Two Settings
| Plain gallery, encrypted query | Encrypted gallery in the cloud | |
| Gallery owner | Server | Same party as the query owner |
| Cryptosystem | Damgard-Geisler-Kroigaard | Additive scheme boosted with Catalano-Fiore, e.g. Paillier |
| Homomorphic features | Addition, scalar multiplication, encrypted argmax, encrypted equality | Addition, one multiplication of ciphertexts |
| Interaction | Several round trips per nearest vector | None |
| Who learns the distances | Nobody | The owner only |
| Client learns | Indices or labels of the k nearest vectors only | Everything, as it owns the data |
| Cost | Grows with gallery size times k | One pass over the gallery, larger ciphertexts |
More Scenarios
- Sanctions screening: A bank checks whether a new customer’s face matches anyone on a sanctions list held by a screening provider. With a plain gallery and an encrypted query, the provider doesn’t learn who the bank’s customer is, and the bank doesn’t get the list.
- Private semantic search: A user asks a question over a company’s document collection, as in retrieval-augmented generation. The question embedding is encrypted, so the search service returns the IDs of the most relevant documents without learning what the user asked.
- Product recommendations: A retailer finds the nearest items to a user’s encrypted preference vector, so the server recommends products without learning the user’s taste.
- Encrypted photo library: A photo app stores the face embeddings of a user’s photos in the cloud, encrypted, and searches them for a person. A breach of the cloud reveals neither the faces nor the searches.
- Duplicate detection: An insurer checks whether a new claim’s photo embedding is close to photos of earlier claims stored by another insurer, to catch reused photos, without either insurer sharing its claims.
Caveats
- Nearest is not the same as a match: A face recognition system also checks that the nearest face is close enough, i.e. that its distance is below a threshold. Otherwise, a stranger is simply matched to the most similar employee. The protocol in the first setting returns the nearest vectors, not whether they are within a threshold, so a verification threshold needs an extra secure comparison on top.
- Semi-honest parties: Both settings assume every party follows the protocol and is only curious. A malicious server could, for example, search a different gallery than it claims.
- Repeated queries: In the first setting, the client learns the k nearest labels for every query. With many queries, an attacker can learn who is in the gallery, so rate-limit queries per client.
- Quantization: Rounding embeddings can swap two neighbors that are almost equally close. Pick a scale that keeps the ranking stable on your data, while keeping squared distances within
2^bit_length.
Conclusion
Encrypted nearest neighbor search is really two problems, depending on who owns the gallery. When a server owns it in plain, the distances are linear in the encrypted query, so additive encryption computes them, and the hard part is finding the nearest vectors without revealing any distance. That takes an encrypted argmin and an encrypted equality test, which is why it runs on Damgard-Geisler-Kroigaard. When the gallery itself is encrypted in an untrusted cloud, the hard part moves to the distances, which need one multiplication of ciphertexts, and an additive cryptosystem boosted with Catalano-Fiore provides exactly that.
Either way, faces, preferences and questions stay encrypted while they are being searched, and with LightPHE, both settings are only a few lines of Python, Go, Java or TypeScript.
Support this blog financially if you do like!
