Encrypted semantic search

Question

I want to implement semantic search but in an encrypted fashion.

For storing passwords, we store Enc(password) in a database, and when a user logs in, we check if Enc(query) == entry in the database.

But for semantic search, is it possible to do the following: A user has a bunch of d-dimensional text embeddings (say from an OpenAI model) e_1 e_2 ... e_n. We then store Enc(e_1) ... Enc(e_n) in a database.

Then, the user searches for some query q. With normal semantic search, we would compare the distance between each e_i and q and choose the closest distance matches. But is there a scheme such that the dist(e_i, q) is approximately equal to dist(Enc(e_i), Enc(q))? This would allow us to do semantic search without an attacker learning about the contents of each e_i and q.

Answer 1

Is it possible? Yes, distance-preserving encryption is theoretically possible.

But without delving too deep into the mathematics of the thing, this also weakens security on the encryption unless you can guarantee somehow that you can't e.g. compose e_i from two smaller e_j and e_k, or that estimate about the distance between (e_j + e_k) and (x) is not related to the distance between e_j and x; because if it is, you can treat the distance estimator as an oracle function and break the encryption piecemeal using repeated known-text attacks.

Several approaches to prevent attacking DPE are presented here, in a scenario that seems to me to closely match yours.