I’m new in the FHE universe and started the challenge of conducting an implementation evaluation of a specific use case. The use case is as follows:
A solution for kNN queries
(k-nearest neighbor) using FHE is to be presented.
A vehicle that is located in a predetermined region
initiates a query by sending a location-based
request to the LBS server. Since the
location in this request is sent encrypted to the LBS
server, the location of the vehicle remains
unknown.
The LBS server performs computations with the
encrypted location and the POIs in this region
and in this way provides location-based services to the vehicle.
The encrypted result of the computations is
sent back to the vehicle.
After decrypting the received result,
the vehicle is informed whether there is a hotel or
gas station in the vicinity. If so, how many hotels or
gas stations are located near the vehicle’s location
?
My question to you guys is:
Do you think this would be conceivable and realizable as a possible use case and which FHE scheme would be best suited for it?
Well, I don’t know the answer to your query. But I must say that your idea is a very important one in the area of anonymity, security and privacy. It is ideas like this that help us all. I wish you all the best.
It is possible but may not be practical depending on the problem parameters.
I can identify the following issues just from a preliminary analysis, I think many other issues will arise as you research the problem further:
How do you encode your location data? If they are real numbers, CKKS seems to be the most amenable FHE scheme choice for approximate numbers.
How do you compute the distance and for how many nodes do you need to do that? This will have a great impact on the performance.
KNN requires sorting. This is difficult in the encrypted domain.
Communication should be considered. FHE encrypted data can be very large and communicating such large data might be an unacceptable cost for real-time systems.
You mentioned the nodes (hotels, … etc) locations are also encrypted. This can be even more challenging. Consider the option where only the vehicle’s location is encrypted.
Overall, it is an interesting research but I have my doubts about its practicality.
To me, I think your idea of using KNN is quite interesting. Still, I am confused about the context of privacy-preserving of location data because we have many other solutions to handle location data that are more suitable and do not require massive computation like FHE.
Do I understand correctly that the issue is not the security and privacy of the communication between the vehicle and the server, since any encrypted comms can solve that problem, but rather, the issue is that of securing the information on the server while processing?
@Caesar Thank you for your very valuable thoughts on my use case. I’m responding to your thoughts as follows:
I think that if I only use one location coordinate and compare it with other locations, the TFHE scheme would be better suited and probably also faster, since in CKKS comparisons are only possible via scheme switching, right?
I thought of using the Euclidean Distance. Does that make sense to you?
The use of KNN is not in scope anymore because it’s actually not necessary. The point here, as you said, is that if I calculate the distance to my coordinate for each POI, I get problems with performance.
Good point that I haven’t thought about yet.
Thanks, that’s also a good thought that I will think about.
@DenisRed, I think the vehicular society will prefer lightweight approaches like authentication protocol or SMPC. That is what I obtained by reading their scientific papers but I agree that KNN with FHE is an interesting context.