Basic principles
Cryptography and math behind the SBF.
The problem
 |
 |
| The user wants to use a location-based service, but he does not want his position to be tracked all the time. Instead, he wants to be sure information on his location is revealed only when they are stricly needed in order for the service to be delivered. | The provider wants to provide a location-based service over several Areas of Interest. However, he may not want to reveal these areas to the user, unless he is moving through one of them. |
The idea
| In order to map location information related to the Areas of Interest, we use the Spatial Bloom Filter (SBF), a probabilistic data structure based on the classic Bloom filter. A SBF can store multiple sets and it is characterized by: - k hash functions - m cells - n elements - s sets |
 |
| The SBF is then encrypted with an asymmetric homomorphic encryption scheme. | + Homomorphic encryption (Paillier Cryptosystem) |
The solution
|
|
| The user conceals his position behind the encrypted version of the SBF, thanks to the homomorphic properties of the encryption scheme. He sends the encrypted information to the provider, enabling him to use the location based service in a privacy preserving way. The user is not aware of the areas the provider is monitoring, as these information are contained in the encrypted SBF, but he can be sure his location is only revealed if it matches one of the areas. |
The provider conceals the Areas of Interest by mapping them to the SBF and encrypting it via the public homomorphic key. When he receives location information from the user he only learns the area the user is in, but not the user's exact position. Moreover, if the user is outside one of the Areas of Interest mapped in the filter, the provider learns nothing about the user's position. |