Towards Secure and Practical Location Privacy through Private Equality Testing

Abstract.

We propose a practical, privacy-preserving equality testing protocol which allows two users to learn if they share the same encrypted input data. Our protocol assumes no trust on third parties and/or other peers, and it is suited for low-min entropy data (\textit{i.e.}, which can be exhaustively searched by an attacker), such as encrypted users locations. Our primitive is secure and efficient: Two public-key exponentiations are required, per each user, for each equality testing. Finally, we describe how we could use our primitive as a building block for a proximity testing buddy-finder service for social networks.

Keywords: Equality testing; Location privacy; Buddy-finder service;

Download: (pdf)