IEEE INTERNET OF THINGS JOURNAL, VOL. 4, NO. 5, OCTOBER 2017 1117
LoDPD: A Location Difference-Based Proximity
Detection Protocol for Fog Computing
Yan Huo, Member, IEEE, Chunqiang Hu, Member, IEEE,XiaoweiQi,andTaoJing
Abstract—Proximity detection is one of the most common
location-based applications in daily life when users intent to
find their friends who get into their proximity. Studies on pro-
tecting user privacy information during the detection process
have been widely concerned. In this paper, we first analyze a
theoretical and experimental analysis of existing solutions for
proximity detection, and then demonstrate that these solutions
either provide a weak privacy preserving or result in a high com-
munication and computational complexity. Accordingly, a loca-
tion difference-based proximity detection protocol is proposed
based on the Paillier cryptosystem for the purpose of deal-
ing with the above shortcomings. The analysis results through
an extensive simulation illustrate that our protocol outper-
forms traditional protocols in terms of communication and
computation cost.
Index Terms—Location privacy, Paillier cryptosystem, privacy
preserving, private proximity detecting.
I. INTRODUCTION
F
OG computing is a paradigm that extends cloud com-
puting and services to the edge of the network, which
has little latency and without intermittent connectivity, espe-
cially in the social network [1] as well as the crowdsourcing
systems [2]. Their high speed Internet connection to the
cloud, and physical proximity to users, enable real time
applications and location-based services (LBSs), and mobil-
ity support [3]. In particular, with the great developments of
mobile smart terminal, LBS have been great popular over
the past years. Specially, proximity detection service is a
typical application of the LBS [4] or the content sharing
services [5].
Considering the scenario that your friends get into your
vicinity, a service provider (SP) will remind you based on
your demand that the friend is close to you. For example,
when Alice wants to know which of her friends are in the
same park with her, she will consider the park as her vicinity
region and send a query command to the SP to find her friends
Manuscript received September 16, 2016; revised December 23, 2016
and February 5, 2017; accepted February 12, 2017. Date of publication
February 16, 2017; date of current version October 9, 2017. This work
was supported in part by the National Natural Science Foundation of China
under Grant 61471028 and Grant 61371069, and in part by the Fundamental
Research Funds for the Central Universities under Grant 2015JBM016.
(Corresponding author: Yan Huo.)
Y. Huo, X. Qi, and T. Jing are with the School of Electronics and
Information Engineering, Beijing Jiaotong University, Beijing 100044, China
(e-mail: yhuo@bjtu.edu.cn; hcq0394@163.com; 13120114@bjtu.edu.cn).
C. Hu is with the School of Software Engineering and the Key Laboratory
of Dependable Service Computing in Cyber Physical Society, Chongqing
University, Chongqing 400030, China (e-mail: tjing@bjtu.edu.cn).
Digital Object Identifier 10.1109/JIOT.2017.2670570
within the same park. The SP will then response Alice if her
friend Bob is in the same park. In the process of data pro-
cessing and transmission, Alice may have a risk of disclosing
her privacy since she broadcasts her personal information via
plain-texts among all services. As series of privacy incidents
resulted from the geographical location disclosure via the edge
nodes in the network, the privacy preserving technologies have
been paid more attention in the world [6], [7]. In fact, any user
does not want others, including the SP or even its friends, to
easily access their privacy and track their location in the case
of unauthorized. On the other hand, the traditional privacy
preserving techniques have been out of date and unsuitable for
the mobile scenarios. Accordingly, it becomes a challenge to
ensure edge nodes exploit LBS applications without disclosing
any individual information [8], [9].
Several private proximity detection (PPD) algorithms using
an alert distance have been proposed in [10]–[13], and also
were applied in smartphones [14]. An SP can only find the
friends whose straight-line distance is below to the alert thresh-
old. However, this kind of method is considered too simple and
inflexible to specify the vicinity region of interest. In order
to achieve PPD, a secure two-party homomorphic encryption
computation protocol was proposed in [15]. Here, Alice was
able to specify any proximity convex polygons and send an
inquiry to all of her friends so as to detect whether they were
in her proximity region. Nevertheless, this protocol also has
several limitations. First, the protocol only dealt with convex
polygons that may be not sufficient in practice, because the
proximity region of Alice was an arbitrary polygon region
in many applications. Second, Alice and her friends had to
interact with each other for several times to achieve privacy,
which led to the high communication costs especially the
complicated proximity area. Moreover, because of process-
ing the large amount of encrypted data for every edge of the
proximity region, the PPD protocol should result in high com-
putation cost as well, which was hard to implement in the
resource-constrained devices such as a smartphone or a tablet.
In this paper, we propose an efficient third-party homo-
morphic secure protocol to solve the above challenges, which
is called as a location difference-based proximity detection
protocol (LoDPD). In our protocol, Alice could find her
friends from any polygon vicinity region that is based on
her requirement. Our major contributions are summarized
as follows.
1) A practical symmetric client-server protocol is presented
in the LBS process, which can protect the privacy of the
users’ location from disclosing to any party.
2327-4662
c
2017 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.
See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.