Secreach: Secure reachability computation on encrypted location check-in data

Hanyu Quan, Boyang Wang, Iraklis Leontiadis, Ming Li, Yuqing Zhang

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

1 Scopus citations


Reachability, which answers whether one person is reachable from another through a sequence of contacts within a period of time, is of great importance in many domains such as social behavior analysis. Recently, with the prevalence of various location-based services (LBSs), a great amount of spatiotemporal location check-in data is generated by individual GPS-equipped mobile devices and collected by LBS companies, which stimulates research on reachability queries in these location check-in datasets. Meanwhile, a growing trend is for LBS companies to use scalable and cost-effective clouds to collect, store, and analyze data, which makes it necessary to encrypt location check-in data before outsourcing due to privacy concerns. In this paper, for the first time, we propose a scheme, SecReach, to securely evaluate reachability queries on encrypted location check-in data by using somewhat homomorphic encryption (SWHE). We prove that our scheme is secure against a semihonest cloud server. We also present a proof-of-concept implementation using the state-of-the-art SWHE library (i.e., HElib), which shows the efficiency and feasibility of our scheme.

Original languageEnglish (US)
Title of host publicationCryptology and Network Security - 15th International Conference, CANS 2016, Proceedings
EditorsGiuseppe Persiano, Sara Foresti
Number of pages16
ISBN (Print)9783319489643
StatePublished - 2016
Event15th International Conference on Cryptology and Network Security, CANS 2016 - Milan, Italy
Duration: Nov 14 2016Nov 16 2016

Publication series

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


Conference15th International Conference on Cryptology and Network Security, CANS 2016


  • Homomorphic encryption
  • Location privacy
  • Reachability

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Secreach: Secure reachability computation on encrypted location check-in data'. Together they form a unique fingerprint.

Cite this