Efficient private proximity testing with GSM location sketches

Zi Lin, Denis Foo Kune, Nicholas Hopper

Research output: Chapter in Book/Report/Conference proceedingConference contribution

29 Scopus citations


A protocol for private proximity testing allows two mobile users communicating through an untrusted third party to test whether they are in close physical proximity without revealing any additional information about their locations. At NDSS 2011, Narayanan and others introduced the use of unpredictable sets of "location tags" to secure these schemes against attacks based on guessing another user's location. Due to the need to perform privacy-preserving threshold set intersection, their scheme was not very efficient. We provably reduce threshold set intersection on location tags to equality testing using a de-duplication technique known as shingling. Due to the simplicity of private equality testing, our resulting scheme for location tag-based private proximity testing is several orders of magnitude more efficient than previous solutions. We also explore GSM cellular networks as a new source of location tags, and demonstrate empirically that our proposed location tag scheme has strong unpredictability and reproducibility.

Original languageEnglish (US)
Title of host publicationFinancial Cryptography and Data Security - 16th International Conference, FC 2012, Revised Selected Papers
Number of pages16
StatePublished - 2012
Event16th International Conference on Financial Cryptography and Data Security, FC 2012 - Kralendijk, Bonaire, Netherlands
Duration: Feb 27 2012Mar 2 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7397 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other16th International Conference on Financial Cryptography and Data Security, FC 2012
CityKralendijk, Bonaire


Dive into the research topics of 'Efficient private proximity testing with GSM location sketches'. Together they form a unique fingerprint.

Cite this