Calculating euclidian distance between two points

Library Questions
1

Hello guys,

I’m trying to figure out the most efficient way to calculate the euclidian distance between two points.

Screenshot 2024-11-12 at 11.35.01
Screenshot 2024-11-12 at 11.35.01395×128 3.89 KB

I have implemented an approach with CKKS and a scheme switch to FHEW that returns correct values BUT the computation is quite time consuming. Do you guys have a better approach to reach my goal in less time, maybe everything with FHEW? Here is my code for the computations:

// Encrypt latitudes and longitudes of recieved POIs
    auto points = getPoints(latitudes, longitudes);
    vector<Ciphertext<DCRTPoly>> encPoints(points.size());
    for (int i = 0; i < points.size(); i++) {
        encPoints[i] = serverCC->Encrypt(serverPublicKey, serverCC->MakeCKKSPackedPlaintext(points[i]));
    }
    std::cout << "Done with encryption of recieved POIs" << '\n' << std::endl;

    // Scale the inputs to ensure their difference is correctly represented after switching to FHEW
    double scaleSign = 512.0;
    auto beta        = serverBinCC->GetBeta().ConvertToInt();
    auto pLWE        = modulus_LWE / (2 * beta);
    serverCC->EvalCompareSwitchPrecompute(pLWE, scaleSign, false);
    std::cout << "Done with precomputations" << '\n' << std::endl;

    std::cout << "Running computations for euclidian distance ... " << '\n' << std::endl;
    vector<Ciphertext<DCRTPoly>> euclidDistanceComparisons(encPoints.size());

    for (int i = 0; i < encPoints.size(); i++) {
        cout << i;

        // All calculations before the square root
        auto ctSubs = serverCC->EvalSub(encPoints[i], serverC);
        auto ctSquares = serverCC->EvalSquare(ctSubs);
        auto ctSum1 = serverCC->EvalSum(ctSquares, 2);

        // approximate the sqrt
        double lowerBound = 0;
        double upperBound = 0.09;
        auto ctDistance = serverCC->EvalChebyshevFunction([](double x) -> double { return std::sqrt(x); }, ctSum1, lowerBound, upperBound, 10);

        // comparing the calculated distance with a given distance
        auto ct = serverCC->EvalRotate(serverC, 2);
        auto ctCompareDist = serverCC->EvalCompareSchemeSwitching(ct, ctDistance);

        // storing all comparison results
        euclidDistanceComparisons[i] = ctCompareDist;
    }
2

I do not fully understand your problem, but I suspect you are not using CKKS packing.
Can the for-loop shown here be vectorized? This can make a huge difference since you would do the homomorphic evaluations inside the loop much less frequently especially if the size of encPoints is large.

3

@Caesar I’m still pretty new to the FHE universe. Can you tell me how to use CKKS packing and what the difference between full/sparse packing is?

Vectorizing a for-loop is also new to me. Do you have a first approach for me?

4

Here is an example with pseudo-code. Suppose you have a vector x and want to find y=f(x).

Say, x=\{0.1,0.2,0.3,0.4\}.

Non-vectorized code:

enc_x = {};
for (const auto& element : x)
        enc_x.push_back(Encrypt(element)); // size(x) of encryptions

enc_y ={};
for (const auto& element : enc_x) {
  curr_enc_y = EvalChebyshevf(element); // size(x) of evaluations of f
  enc_y.push_back(curr_enc_y);
}

Vectorized code (more efficient):

enc_x=Encrypt(x); // 1 encryption for the entire vector
enc_y = EvalChebyshevf(enc_x); // 1 evaluation of f

Both codes compute the same result. The non-vectorized code uses for-loop and calculates the result one element at a time. The vectorized version works on vectors and applies the operations simultaneously on each component in the input vector.

If the number of points is large, you better vectorize your code over them. Note that CKKS can pack up to N/2 real/complex numbers in one ciphertext, where N is the ring dimension.

5

Hi Caesar. This is very useful information. But what if I have the number of points to be >N/2. Is there a way to efficiently pack the vector into one ciphertext?

6

There is a variant of CKKS that can pack N real numbers in one ciphertext, but it has not yet been released in OpenFHE - only a prototype implementation exists.

If the slot-capacity of a ciphertext is not sufficient to pack your data, you can pack it in multiple ciphertexts.

7

Thank you. Can you please share any pointer to the variant of CKKS?

8

Here is the paper that introduced the “Real-CKKS” or conjugate-invariant CKKS variant.

9

Thank you, that solved my problem!