Hello guys,
I’m trying to figure out the most efficient way to calculate the euclidian distance between two points.
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;
}