Overview: We propose to showcase how Zama's homomorphic encryption could be used to create a travel routing service that preserves localisation's privacy through a combination of tutorials/posts/demo-app.
Description:
Introduction
Geolocalisation is sensitive personal data that can easily be used to identify and deduce further information about oneself such as home address, work, favourite foods, hobbies, and more.
Nonetheless, almost all of us use some form of maps on smartphones to compute best itinerairies when traveling.
We thus accept to send our localisation to an external party who could potentially use it for other purposes.
We propose in this tutorial to showcase how Zama's homomorphic encryption could be used to preserve our localisation's privacy while still offering an itinerary computation service.
In this scenario, the server does not learn anything about a client's position at anytime as it sees only encrypted data.
Deliverables
The solution would be a demo client/server app which would demonstrate the feasability of the usecase, together with explanations of the methods and choices made along the way.
Concretely, the deliverables could include:
Extended gist or series of posts on the project
Code and data for both client and server
Demo App (optional)
Roadmap
Part 1: Algorithm
The first phase of the project consists in exploring the feasability of using tfhe for some shortest path algorithm.
Benchmarks will permit to understand what size of a task is computationnally reasonable today.
This will influence how to setup pre-indexing vs caching in order to accelerate computations over time.
Possible algorithms include Djikstra, Bellman-Ford, A*, and many others.
Part 2 : Client-Server
In a second time, we will now code the usecase. The solution we envision is in the lines of:
Client registers a sessions by sending the encrypted map of a region to the server.
(Optional) Server pre-indexes the database.
Client sends an encrypted origin and destination in the region.
Server computes the shortest path using an algorithm from phase 1.
(Optional) Server caches intermediate results
Client decyphers the result.
Part 3 : Tutorials and Demo
Write a gist about the app, what problems were encountered and how they were solved/avoided.
Optionnally, build a demo app that allows a user to select an origin and destination on a map and obtain the shortest path.
A panel will show the messages that are transmitted encrypted to the server, with their decrypted variants client-side.
Potential Difficulties
Homomorphic encryption is computationally intensive and noisy. This project tries to go to the limit of what is possible today, but there are risks involved:
Size of a realistic map is too large:
on the one hand, we explore graph algorithms in tfhe regardless of the nature of the graph, and we thus can deliver results for at least small graphs.
Furthermore, there are solutions to either pre-compute indexes or use caching mechanisms to decrease considerably the computation done on the fly.
Finally, we can accept a higher level of noise in the distance computations.
Shortest path algorithm is not tfhe friendly:
This is part of the challenge of the usecase, nonetheless we have many different algorithms to choose from.
Algorithms can often be written as array operations and thus make use of concrete.
This might incur some overheads, but at least we could have a first solution fairly quickly.
Optimisations can then follow if needed.
bcm-at-zama
commented
7 months ago
Zama Bounty Program Proposal : Travel Routing
Bounty name: Travel Routing
Bounty type:
major_bountyCategory:
ApplicationLibrary targeted:
ConcreteReward: 5K-10K depending on included components.
Overview: We propose to showcase how Zama's homomorphic encryption could be used to create a travel routing service that preserves localisation's privacy through a combination of tutorials/posts/demo-app.
Description:
Introduction
Geolocalisation is sensitive personal data that can easily be used to identify and deduce further information about oneself such as home address, work, favourite foods, hobbies, and more. Nonetheless, almost all of us use some form of maps on smartphones to compute best itinerairies when traveling. We thus accept to send our localisation to an external party who could potentially use it for other purposes.
We propose in this tutorial to showcase how Zama's homomorphic encryption could be used to preserve our localisation's privacy while still offering an itinerary computation service. In this scenario, the server does not learn anything about a client's position at anytime as it sees only encrypted data.
Deliverables
The solution would be a demo client/server app which would demonstrate the feasability of the usecase, together with explanations of the methods and choices made along the way. Concretely, the deliverables could include:
Roadmap
Part 1: Algorithm
The first phase of the project consists in exploring the feasability of using tfhe for some shortest path algorithm. Benchmarks will permit to understand what size of a task is computationnally reasonable today. This will influence how to setup pre-indexing vs caching in order to accelerate computations over time. Possible algorithms include Djikstra, Bellman-Ford, A*, and many others.
Part 2 : Client-Server
In a second time, we will now code the usecase. The solution we envision is in the lines of:
Part 3 : Tutorials and Demo
Write a gist about the app, what problems were encountered and how they were solved/avoided. Optionnally, build a demo app that allows a user to select an origin and destination on a map and obtain the shortest path. A panel will show the messages that are transmitted encrypted to the server, with their decrypted variants client-side.
Potential Difficulties
Homomorphic encryption is computationally intensive and noisy. This project tries to go to the limit of what is possible today, but there are risks involved:
Size of a realistic map is too large:
Shortest path algorithm is not tfhe friendly:
Macro Sizing (Estimated)