One Encrypted Dot Product for Many Distances

Private similarity search usually looks like this: a client sends an encrypted query vector to a server, the server compares it against a database, and the client gets back the closest matches. The encryption is fully homomorphic encryption (FHE), a scheme that lets the server compute on ciphertexts without ever decrypting them. FHE handles additions and multiplications cheaply, but it is extremely expensive for anything nonlinear, such as absolute values, maxima, or comparisons. Encrypted retrieval systems therefore support essentially one metric, the dot product. A client who wants Manhattan ($L_1$) distance for time series, or worst-coordinate ($L_\infty$) distance for tolerance matching, is forced into deep polynomial approximations. Those approximations use up the noise budget of the ciphertexts and require bootstrapping, the costly procedure that refreshes a ciphertext so that computation can continue.

This note proposes a fix based on one observation. Each of these distances can be rewritten exactly, or up to a controlled quantization error, as a dot product between a fixed "lifted" encoding of each database vector and a query-side encoding whose coefficients select the metric. Under this encoding, $L_2$, cosine, inner product, even-power $L_p$ (and through it an approximation to $L_\infty$), $L_1$, and weighted mixtures of them all cost one encrypted matrix–vector product. That is a single multiplication level with no bootstrapping. The database is encoded once and never re-encoded. Because the metric lives only in the encrypted query coefficients, the server also cannot tell which metric the client asked for.

Core Claim

Two identities carry the idea. For an even integer $p$, database vector $x$ and query $q$ in $\mathbb{R}^d$,

$$ \|x-q\|_p^p=\sum_{i=1}^{d}\sum_{k=0}^{p}\binom{p}{k}\,x_i^{k}\,(-q_i)^{p-k}. $$

This is an inner product between the database's coordinate-power features $\{x_i^k\}$, which the server precomputes, and the query's weighted power features $\{\binom{p}{k}(-q_i)^{p-k}\}$, which the client computes in the clear before encrypting. For $L_1$, quantize each coordinate to $B$ levels with thresholds $t_1<\dots<t_B$. Then

$$ |x_i-q_i|\approx\sum_{b=1}^{B}\Delta_b\left(u_b(x_i)-u_b(q_i)\right)^2 ,\qquad u_b(z)=\mathbf{1}[z>t_b], $$

where $\Delta_b$ is the gap between consecutive thresholds. Expanding the square gives another inner product, this time between "thermometer" bit encodings. The error per coordinate is at most one grid step, which follows from the fact that $|x_i-q_i|$ equals the total length of the intervals lying between $x_i$ and $q_i$. $L_2$, inner product and cosine are the $p=2$ and $k=1$ blocks, plus a norm slot.

The database stores one concatenated lift: power blocks up to degree $p_{\max}$ and one thermometer block. A query for any metric in this family, or any non-negative mixture of them, is a single plaintext–ciphertext linear map. The client can always send nonzero-shaped coefficients for every block, zeroing the unused ones inside the encryption, so the server learns nothing about the metric. The price is a larger lifted dimension, roughly $d(p_{\max}+1+B)$. SIMD packing, which places thousands of values in the slots of one ciphertext as introduced in CryptoNets, absorbs this width far more cheaply than it absorbs extra multiplicative depth. $L_\infty$ is handled only approximately through $L_{p_{\max}}$, with a looseness factor of at most $d^{1/p_{\max}}$. We treat that as a limitation to be measured, not hidden.

Relation to Prior Work

The unified-distance literature motivates the goal of one representation serving many metrics. Sharing Hash Codes for Multiple Purposes stores a shared angular hash plus norm metadata so that one index serves $L_2$, cosine and inner product search, and it reports 224 versus 4,344 bytes per sample on SIFT1B against concatenating per-metric codes. Fast Time Sequence Indexing for Arbitrary Lp Norms shows that segment means lower-bound every $L_p$ distance, so one R-tree serves all norms. One sketch for all estimates several distances from one sampled sketch.

All three accept approximation because they compress for plaintext speed. Under FHE the tradeoff flips: the inner product is exact and cheap, and nonlinearity is the expensive part. mp-LSH's angular decomposition is therefore unnecessary inside ciphertexts, because $L_2$, cosine and inner product already follow exactly from one encrypted dot product plus norms. What remains unsolved is $L_1$, $L_\infty$ and mixtures, and that is what the lift targets. Segment means supply a method we reuse. They are linear, so lifting segment means instead of raw coordinates gives a cheaper encrypted score that still lower-bounds each $L_p$.

The encrypted-retrieval literature constrains the design. SecureNets documents the tradeoff between polynomial degree and depth that makes per-coordinate absolute-value approximation costly, and Circuit Bootstrapping makes clear why avoiding bootstrapping matters. Secure Data Retrieval on the Cloud compresses outputs with coresets and group-testing decoders, but those work only for sparse binary match indicators, not continuous scores. We therefore do not use that decoder and leave top-$k$ selection to the client after decryption. SF-Relate pairs plaintext LSH pruning with CKKS scoring for a single, domain-specific kinship estimator; its pruning stage composes with our scorer.

The closest retrieval systems avoid FHE depth by changing the threat model. $p^2$RAG uses two non-colluding servers and interactive bisection over dot products. CAPRISE/ppRAG reveals query-to-database comparisons to the server. Both are single-metric. None of this work makes the metric a hidden, query-time choice over a fixed encrypted pipeline.

Research Program

We will build the lifted encoder and a CKKS scorer in the standard setting: the database is in the server's plaintext, and the query is encrypted. The server computes packed, rotation-summed plaintext–ciphertext products and returns the encrypted score vector. The client decrypts it and selects the top $k$. We will also run a variant in which both the database and the query are encrypted, which costs one ciphertext–ciphertext multiplication level, to measure storage growth.

The analysis has three parts. First, we bound the ranking error from quantization ($B$) and from the finite-$p$ stand-in for $L_\infty$. Second, we measure CKKS precision loss from the large dynamic range of high powers, and test per-coordinate rescaling as a remedy. Third, we measure what metric hiding costs in slots compared with sending metric-specific queries.

Two limitations are stated up front. Returning all $N$ scores discloses database-to-query distances to the client; this is acceptable when the database owner is the client, and otherwise it is a known gap. Server work is also linear in $N$, as in every exact encrypted scorer.

Baselines

The reference point is the plaintext exact metric computed on the same vectors. It gives the recall ceiling for each metric, and we report every encrypted method as recall@$k$ against it.

The strongest direct competitor inside FHE combines two pieces. For $L_2$, cosine and inner product it uses an encrypted inner product plus norms. For $L_1$ and $L_\infty$ it computes encrypted coordinate differences and then applies a composite polynomial approximation of $|z|$, and for $L_\infty$ a pairwise max tree, in the style whose depth–accuracy tradeoff SecureNets describes. It runs on the same CKKS library, the same ring dimension, and the same hardware. Its polynomial degree is tuned on a validation split under the same budget we give $B$ and $p_{\max}$. We beat it if we match its recall at a lower depth, with no bootstrapping, and with lower latency. No reported result found on Lacuna for encrypted $L_1$ or $L_\infty$ nearest-neighbor search, so we produce this number ourselves.

A per-metric baseline keeps separately encoded databases and separate circuits for each metric, the FHE analogue of mp-LSH-CC. We compare total server memory and per-query cost for a workload that mixes metrics.

For context only, since the threat model differs, we report $p^2$RAG. On BEIR trec-covid it reports roughly 0.2 seconds of server latency at $N=2^{17}$ and $k=16$, with recall 1 and about 2 MB of communication, for dot product only. We also report CAPRISE's approximately 2,339 vectors per second on MS MARCO from Ye & Guo. Our dot-product configuration should come within a small constant of the $p^2$RAG latency while using a single server.

We run three ablations. The first removes the thermometer block and ranks $L_1$ queries by $L_2$. The second sweeps $B$ and $p_{\max}$. The third compares metric-hiding queries with metric-specific ones.

Why not just…?

Why not just rank by $L_2$ when the client asks for $L_1$? Rankings under the two metrics are often correlated, and this is the most serious threat to the idea's value. The first ablation measures recall@$k$ of $L_2$-ranked results against exact $L_1$ neighbors on STOCK, SYNTH and SIFT. Yi & Faloutsos found that $L_1$ and $L_\infty$ behave differently from $L_2$ on STOCK, which suggests the metrics do diverge. If the recall gap is small on embeddings, we will narrow the claim to time-series and tolerance workloads.

Why not just approximate $|z|$ with a polynomial per coordinate? This works, but it adds multiplicative depth for every coordinate, which on standard parameters pushes the circuit toward bootstrapping. The lift pays in slots instead. The head-to-head comparison on depth, latency and recall settles which cost is lower, and if a shallow polynomial matches our recall at similar latency, the lift offers only its metric-hiding benefit.

Why not keep one circuit per metric? For $L_2$, cosine and inner product, no separate circuit is needed in the first place. For mixed workloads, separate encodings multiply storage, which is already large under FHE according to Haralampieva. Separate circuits also reveal the chosen metric to the server. The per-metric baseline quantifies both costs.

Why not use PCA or random projections first? These are orthogonal to the lift and can be composed with it, but they preserve $L_2$ distance only, so applying them before a thermometer encoding distorts $L_1$. We will test PCA followed by the lift and report whether the $L_1$ recall that survives justifies the smaller dimension.

Proposed Experiments

The data follow the file. We use a 1M-vector SIFT subset drawn from SIFT1B, BEIR trec-covid embeddings at $N=2^{17}$ to allow comparison with $p^2$RAG, MS MARCO gtr-t5-base embeddings, and for $L_1$ and $L_\infty$ the 675-sequence STOCK set and the 30,000 random-walk sequences of length 128 from Yi & Faloutsos. For every metric and for mixtures we report recall@$k$ at $k\in\{10,100\}$, server latency, multiplicative depth, ciphertext and key sizes, and communication.

The first decisive check asks whether the lift reaches at least 0.95 recall@10 for $L_1$ at a moderate $B$ within depth 1, where the polynomial baseline needs bootstrapping or more than three levels. The second asks whether a metric-hidden query costs less than twice a metric-specific one. The third, run on SYNTH, asks whether lifted segment means preserve the zero-false-dismissal property under encryption noise, which would allow an encrypted coarse pass over time series at a fraction of the slots. A negative result on the first check, meaning quantization or CKKS precision prevents reaching the recall target at feasible $B$, would show that the lift is not viable for $L_1$ and would restrict the contribution to hidden-metric $L_2$, cosine, inner product and $L_p$ scoring.