How to compute distance between binary vectors?

FHE Questions
1

Hi!

I am a beginner in the field of homomomorphic encryption. I want to compute a distance metric (e.g. Hamming, Euclidean distance) between encrypted binary vectors. The size of the vectors is usually 256 or 512. What scheme or library should I use to implement this in an efficient way? Thank you

2

Hello! It depends. Hamming distance might be computed using FHEW/TFHE and using a XOR between the two vectors.

On the other hand, Euclidean distance requires square root and squaring. I think you can always use FHEW/TFHE with Look up Tables (LUT), but I never used them.
You could use CKKS as follows (pseudocode):

  • X \gets \texttt{Encrypt}([1,2,3,4, \dots])
  • Y \gets \texttt{Encrypt}([4,6,4, 0, \dots])

Euclidean distance is computed as:

\sqrt{\sum_i^n(x_i - y_i)^2}

where x_i is the i-th element of X, and y_i is the i-th element of Y.

We can compute all the differences in one single SIMD operation:

  • \Delta \gets \texttt{EvalSub}(X, Y)

When we square it:

  • \Delta \gets \texttt{EvalSquare}(\Delta)

As a last step, we have to add all the elements together. Naively, in case of 256:

  • \Delta \gets \texttt{EvalAdd}(\Delta, \texttt{EvalRot}(\Delta, 1))
  • \Delta \gets \texttt{EvalAdd}(\Delta, \texttt{EvalRot}(\Delta, 2))
  • \Delta \gets \texttt{EvalAdd}(\Delta, \texttt{EvalRot}(\Delta, 4))
  • \Delta \gets \texttt{EvalAdd}(\Delta, \texttt{EvalRot}(\Delta, 8))
  • \Delta \gets \texttt{EvalAdd}(\Delta, \texttt{EvalRot}(\Delta, 16))
  • \Delta \gets \texttt{EvalAdd}(\Delta, \texttt{EvalRot}(\Delta, 32))
  • \Delta \gets \texttt{EvalAdd}(\Delta, \texttt{EvalRot}(\Delta, 64))
  • \Delta \gets \texttt{EvalAdd}(\Delta, \texttt{EvalRot}(\Delta, 128))

But maybe it is better to get the sum using \texttt{EvalSum}.

1 Like