Open AccessArticle

Privacy-Enhancing k-Nearest Neighbors Search over Mobile Social Networks^†

School of Computer Science and Engineering, Northeastern University, Shenyang 110819, China

Software College, Northeastern University, Shenyang 110819, China

School of Cybergram, Hainan University, Haikou 570228, China

Author to whom correspondence should be addressed.

^†

This paper is an extended version of our paper published in “Li, Y.; Zhou, F.; Xu, Z.; Ge, Y. PPFQ: Privacy-Preserving Friends Query over Online Social Networks. In Proceedings of the 2020 IEEE 19th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom), Guangzhou, China, 29 December 2020–1 January 2021; pp. 1348–1353, doi:10.1109/TrustCom50675.2020.00181.”.

^‡

Current address: No.195, Chuangxin Road, Hunnan District, Shenyang 116024, China.

Sensors 2021, 21(12), 3994; https://doi.org/10.3390/s21123994

Submission received: 16 April 2021 / Revised: 26 May 2021 / Accepted: 4 June 2021 / Published: 9 June 2021

(This article belongs to the Section Sensor Networks)

Download

Browse Figures

Versions Notes

Abstract

Focusing on the diversified demands of location privacy in mobile social networks (MSNs), we propose a privacy-enhancing k-nearest neighbors search scheme over MSNs. First, we construct a dual-server architecture that incorporates location privacy and fine-grained access control. Under the above architecture, we design a lightweight location encryption algorithm to achieve a minimal cost to the user. We also propose a location re-encryption protocol and an encrypted location search protocol based on secure multi-party computation and homomorphic encryption mechanism, which achieve accurate and secure k-nearest friends retrieval. Moreover, to satisfy fine-grained access control requirements, we propose a dynamic friends management mechanism based on public-key broadcast encryption. It enables users to grant/revoke others’ search right without updating their friends’ keys, realizing constant-time authentication. Security analysis shows that the proposed scheme satisfies adaptive

L

-semantic security and revocation security under a random oracle model. In terms of performance, compared with the related works with single server architecture, the proposed scheme reduces the leakage of the location information, search pattern and the user–server communication cost. Our results show that a decentralized and end-to-end encrypted k-nearest neighbors search over MSNs is not only possible in theory, but also feasible in real-world MSNs collaboration deployment with resource-constrained mobile devices and highly iterative location update demands.

Keywords:

mobile social networks; privacy-enhancing; collaboration architecture; location search; secure multi-party computation; homomorphic encryption

1. Motivation

With the rapid development of 5G Wireless Communication, mobile social networks (MSNs), represented by instant messaging and location sharing, have become essential parts of people’s everyday lives. According to [1], the number of enrolled users in MSNs worldwide reaches 862 million in 2020, and it is estimated to exceed 900 million by the end of 2021. In particular, the utilization rate of location-based MSN services reaches 96.9% based on the positioning system (e.g., GPS, WiFi, Bluetooth, etc.) embedded in mobile devices, such as Facebook’s “Nearby friends”, Foursquare’s “Swarm”, and Joyrun’s “real-time running competition”, and so forth. In these services, users can broadcast their locations among friends and send location-based queries for nearby friends. Therefore, the location-based services provide a profoundly mobile interface for users’ real-life social networks.

Nevertheless, people are using the enormously popular MSNs services without realizing their privacy concerns: the MSNs services providers can observe and accumulate the geo-location that users transmit through the network. According to the Mobile APP Security Research [2], among the 50 MSN services surveyed, there are 35 services that leak users’ location data to advertisers or data analysis services on purpose without any permission. In recent years, a lot of research also uses data analysis and machine learning technology to extract a large number of their sensitive information from users’ location information over MSNs: by analyzing their search patterns, the matched friends and search similarities and so forth, it is easy to predict the location conversion patterns between users and their friends [3,4]. It is also turned out that Facebook’s historical spatiotemporal trajectory leaks the geographical distance between each user and the spot that he frequently queries, and then the service provider can learn the access probability—whether and when the user will check-in the next time [5].

To avoid illegal access to users’ locations and search patterns by unauthorized service providers and hackers, previous research aimed to encrypt the location information before uploading. However, traditional encryption methods limit the MSNs service provider’s ability to provide location-based services for users. To achieve privacy-preserving location-based query, the straightforward mathematical methods deploy private information retrieval [6], searchable encryption [7] and other crypto primitives to make the encrypted location data searchable. However, these methods come at the huge cost of computation and communication overhead. Moreover, in a privacy-preserving setting, users have their keys embedded in their mobile devices. If a user is allowed to share his/her location encryption key with friends, he/she needs to launch a search request to the platform multiple times when he wants to retrieve his/her friends’ locations. Moreover, when granting or revoking friends’ search rights, a user and his/her friends should update their keys with synchronous locally, which are not suitable for MSNs platforms with highly extensible requirements. To the best of our knowledge, it is fair to say that achieving fine-grained location access control while providing an efficient, secure location-based neighbors search service has become one of the challenging research topics in the field of privacy-enhancing MSNs and still remains open.

In this work, we translate the high-level vision of the above issues and location privacy demand in MSNs into technical requirements and design a privacy-enhancing k-nearest neighbors search scheme containing cryptographic protocols that meet them. The purpose of this work is to protect users’ location data and search patterns privacy, and make it available for users to query for their k-nearest neighbors based on current distances. In terms of technical contribution, our work presents an efficient construction so that the server can effectively compute and sort the encrypted distance between a user and his/her friends without any decryption operation, which is the first to tackle this problem through the lens of secure multi-party computation. It also achieves lightweight friend authentication and authority management by enabling users to grant/revoke their friends’ search rights without updating others’ keys. In terms of security, our scheme satisfies adaptive

L

-semantic secure and revocation secure under random oracle model. We also undertook an extensive experiment that validates our work, showing that the proposed scheme is possible in theory and feasible in practice.

2. Related Works

2.1. MSNs Privacy

In recent decades, researchers have proposed many privacy-preserving approaches for MSNs. Encryption is the most common method for achieving privacy. For example, Flybynight [8] is a Facebook application for encrypting and decrypting sensitive data using client-side JavaScript. However, it is easy to be attacked by an adversary because the server holds users’ keys and takes charge of key management. NOYB (short for none of your business) [9] offers privacy and preserves MSN services’ functionality based on a secret dictionary’s encryption. Besides, there have been many privacy-preserving matching solutions over MSNs proposed with different techniques. Some schemes are based on private set intersection protocols [10,11] to allow two users to compute the intersection of the two private profile sets privately, but leak no useful information of both parties. For example, Niu et al. designed a spatiotemporal matching scheme for privacy-aware users in MSNs based on the profile’s weight or level and the participant’s social strength [10]. Zhang et al. proposed the concept of a fine-grained privacy information matching protocol by giving preference to each profile and using a similarity function to measure the matching degree [11]. To reduce computation cost, some works [12,13] designed non-encryption-based privacy-preserving matching protocols. Fu et al. proposed a privacy-preserving common-friend matching scheme based on a bloom filter [12]. It transmitted the common profiles of two users into an intersection of bloom filters, which ensures the privacy of friend lists against unknown users. However, it will not be able to resist brute-force attacks, resulting in privacy information leakage. Sun et al. [13] proposed a privacy-preserving spatiotemporal profiles matching scheme to let each user periodically record his locations by a geographic cell index among a large set of predefined ones, which can ensure spatiotemporal privacy at the cost of possibly huge communication and computation overhead.

2.2. Location Privacy

With the rapid development and enormous popularity of location-based services, scholars have paid more and more attention to location data’s privacy and security. Many approaches focus on how to perform privacy-preserving location queries: Bamba et al. proposed a k-anonymity-based scheme that relies on a server to construct an anonymous set based on users’ original queries to make query indistinguishable on the server-side [14]. Bordenabe et al. [15] and Shi et al. [16] both integrated differential privacy to realize nearby friends’ queries. Differential privacy provides a rigorous privacy guarantee by adding noise (randomly to choose a set of fake locations ) to make their data and query deferentially private. Jorgensen et al. incorporated a clustering procedure that groups users according to the social network’s natural community structure and significantly reduced noise [17]. The above works [14,15,16,17] can achieve relatively high efficiency. However, the limitations of these works are that it is challenging to achieve provable security guarantees with formal security definitions, since they did not employ well-designed and provable encryption methods. Zhou et al. took advantage of private information retrieval (PIR) to realize nearby friends’ queries [18]. It provides strong cryptographic guarantees but needs complex operations, and it only protects query privacy but not location privacy. Li et al. designed a private location information matching protocol over MSNs based on inner product similarity (IPS) [19], putting users’ map locations into vectors and encrypting the vectors. The similarity function is used to measure the similarity degree of the encrypted vectors of different users. Schlegel et al. designed an encryption method of dynamic location grid index structure [20], achieving neighbor point search on the premise of not revealing location privacy to the third party. In the above encryption-based schemes, the computation efficiencies are not ideal, requiring multi-round interactions at the logarithmic level between user and server.

Many other works are based on higher security assumptions to achieve a trade-off between security and efficiency. For example, some works [21,22] assumed that the service provider is honest and that it has the authority to access the location plaintext without leaking any information to others. Some works [21,23,24] introduced a trusted third party (TTP) to achieve the trade-off between security and efficiency. Unfortunately, there may not exist such a TTP in real MSNs scenarios. Some non-TTP solutions [15,20] are based on approximate measurements (e.g., linear programming and dynamic grid) with no accurate result. Some works [18,25] need complex operations (e.g., sending fake queries or receiving redundant results) to achieve secure guarantees, which incur high communication and computation overhead at the user-side, making them unsuitable for resource-constrained mobile devices.

3. The Proposed Scheme

3.1. Overview

The privacy-enhancing k-nearest neighbors search scheme over MSNs can be viewed as a decentralized system of end-to-end encrypted social network databases, focusing on the diversified demands of location privacy in MSNs. Our design relies on various cryptographic building blocks, including pseudo-random function, homomorphic crypto mechanism, secure multi-party computation and broadcast encryption.

-: Aiming at the limited computation power of resource-constrained mobile devices, we design a lightweight end-to-end location encryption algorithm and a server-aid location re-encryption protocol based on Paillier homomorphic encryption to achieve further location sharing. The protocol allows the service provider to transfer friends’ location ciphertexts into the query user’s homomorphic ciphertexts without requiring them to be online to participate in the calculation.
-: We build a secure dual-server architecture and design a secure k-nearest neighbors search protocol by secure multi-party computation and a homomorphic encryption mechanism under this architecture. The server can effectively compute and sort the distance between users and their friends without any decryption operation. Compared with the cloud-center model, where a single server holds complete knowledge, the dual-server architecture minimizes the leakage to the servers and reduces the cost of communication between the mobile user and the server.
-: To achieve fine-grained access control, we design a dynamic friends management mechanism based on public-key broadcast encryption. It enables users to grant/revoke their friends’ search rights without updating others’ keys, achieving lightweight friend authentication and authority management. Moreover, this mechanism satisfies revocation secure that the adversary cannot obtain the user’s location information through collusion with the server and the revoked friends, thus further improving the scheme’s overall security.

3.2. Architecture and Syntax

Our scheme is designed to be executed among: U,

S_{1}

, and

S_{2}

. U is a set that contains n mobile users

{U_{1}, \dots, U_{n}}

. Each user

U_{i} \in U

can connect with others as his friends dynamically.

S_{1}

is the primary server that provides a mobile social network service to all users in U. Each user

U_{i} \in U

can send a search request to

S_{1}

for k-nearest neighbors among friends based on current location.

S_{2}

is a collaborated server to conduct secure computation with

S_{1}

for k-nearest neighbors search.

The scheme’s architecture is shown in Figure 1. At a high level, users’ information and their relationships are modeled by a direct graph structure

G

. To initialize the system, the primary server

S_{1}

executes Initial algorithm to output public parameter

p a r a m s

and an empty

G

. Any user

U_{i}

should use public parameter

p a r a m s

to generate his symmetric key

K_{i}

and public/secret keys

(P K_{i}, S K_{i})

locally by executing

KeyGen

algorithm and interacts with the primary server

S_{1}

for registration by Join protocol. Any enrolled user

U_{i} \in U

can grant/revoke

U_{j} \in U

’s location search right by interacting with

S_{1}

in Grant/Revoke protocols.

U_{i}

holds a friends index

F_{i}

that records his granted friends. According to the real-life MSNs’ location service architecture, we deploy trusted location infrastructure to provide tracing service by sending the current location

l_{i}

of each user

U_{i} \in U

to his local mobile device periodically.

U_{i}

executes

LocUpdate

to encrypt his location data

l_{i}

by his symmetric key

K_{i}

at local and uploads the location ciphertext

C_{i}

S_{1}

U_{i}

then can execute Search protocol with

S_{1}

by sending k-nearest neighbors search request.

S_{1}

performs encrypted search in

G

with the assistance of

S_{2}

and returns the search result to

U_{i}

, without relying on the presence of any other user. The proposed scheme’s syntax consists of seven polynomial-time algorithms and protocols, which is shown in Syntax below:

Definition 1

(Correctness). Correctness implies that, for all

1^{k}

, all

(G, p a r a m s)

generated by Initial

(1^{k})

, all

(K_{i}, P K_{i}, S K_{i})

generated by KeyGen

(p a r a m s)

, all

(F_{i}; G^{'})

generated by

Join (U_{i} (i d_{i}, P K_{i}); S_{1} (G))

, all

(K_{i}, P K_{i}, S K_{i})

generated byKeyGen

(p a r a m s)

, and all sequences of LocUpdate, Grant and Revoke protocols,

Search (U_{i} (K_{i}, F_{i}); S_{1} (G); S_{2} (S K_{i}))

will always output result

R_{k}

that:

R_{k}

satisfies

D_{1} < \dots < D_{K}

; and there does not exist

U_{i} \in R_{k}

such that

U_{i} \notin F_{s}

and

U_{i} \in {F_{s} ∖ R_{k}}

that

D_{i} < m a x_{U_{j} \in R_{k}} {D_{j}}

3.3. Security Definition

3.3.1. Adaptive $L$ -Semantic Secure

The security definition of adaptive

L

-semantic secure is formalized by an ideal/real-world paradigm [7]. Roughly speaking, we require that the execution of the scheme in the real-world is indistinguishable from an ideal-world. In real-world Real

(1^{k})

, the protocols between the adversarial servers and the user execute just like in the real scheme. In ideal-world Ideal

(1^{k})

, there exist two simulators

S i m_{1}

and

S i m_{2}

that can obtain the leakage information from leakage functions and try to simulate the execution of

A_{1}

and

A_{2}

in Real

(1^{k})

Definition 2

(Adaptive

L

-Semantic Secure). Given the syntax in Section 3.2 and considering the following probabilistic paradigms, where U=

{U_{1}, \dots, U_{n}}

is the users’ set,

A_{1}

and

A_{2}

are two non-colluding adversaries with pseudo-random polynomial time (PPT) computation ability,

S i m_{1}

and

S i m_{2}

are two PPT simulators and

L_{1}

L_{4}

are leakage functions.

The proposed scheme achieves adaptive

L

-semantic security if, for all polynomial time

A_{1}

and

A_{2}

, there exists polynomial time simulators

S i m_{1}

and

S i m_{2}

such that the following two distribution ensembles are computationally indistinguishable:

{Output}_{A_{1 / 2}}^{Real (1^{k})} \approx {Output}_{S i m_{1 / 2}}^{Ideal (1^{k})} .

3.3.2. Revocation Security

Revocation security guarantees that the scheme satisfies that any user’s revoked friend cannot provide a valid search for his location, even if an adversary illegally steals the revoked friend’s key. We construct the experiment

{Exp}_{A_{r e v}}^{Revoke} (1^{k})

to formalize the revocation security definition.

{Exp}_{A_{r e v}}^{Revoke} (1^{k})

is interactively executed by a challenger

C

and an adversary

A_{r e v}

who has the ability to add friends, perform a search and revoke friends in the real scheme.

C

deletes the user who has been added to the friends index by

A_{r e v}

A_{r e v}

continues to generate a search token using the revoked friend’s identity and makes a search request. After a polynomial number of queries,

C

revokes all users that are queried to the Grant oracle but are not subsequently queried to the Revoke oracle (i.e., all users for which

A_{r e v}

holds their valid user keys).

The adversary

A_{r e v}

must then produce a search token which, when used as an input to Search protocol, does not produce null, that is,

A_{r e v}

must produce a valid search request even though it does not hold a non-revoked key. After several rounds of queries, if

A_{r e v}

’s probability of winning the revocation security experiment with PPT computation ability is negligible, then we can say that the proposed scheme satisfies revocation security.

Definition 3

(Revocation Secure). Given the syntax in Section 3.2 and considering

{Exp}_{A_{r e v}}^{Revoke} (1^{k})

, which is executed by a challenger

C

and an adversary

A_{r e v}

Specifically,

C

runs

Initial

to initialize

G

, generates key

(K_{i}, P K_{i}, S K_{i})

and state ciphertext

c s t_{i}

KeyGen

and Join.

C

sends

G

and

c s t_{i}

A_{r e v}

A_{r e v}

can access to the following oracles, where

\cdot

denotes the parameters that are provided by

A_{r e v}

himself:

-: $O_{Grant} (\cdot, G, i d_{j}, P K_{i}, F_{i})$ : $A_{r e v}$ can send grant friend request to this oracle. If $i d_{j} \notin F_{i}$ , then the oracle $O_{Grant}$ runs Grant by the input provides by $A_{r e v}$ . If $i d_{j} \in F_{i}$ , then the oracle $O_{Revoke}$ outputs ⊥.
-: $O_{Revoke} (\cdot, G, i d_{j}, P K_{i}, F_{i})$ : $A_{r e v}$ can send revoke friend request to this oracle. If $i d_{j} \in F_{i}$ , then the oracle $O_{Revoke}$ runs $Revoke$ by the input provides by $A_{r e v}$ . If $i d_{j} \notin F_{i}$ , then the oracle $O_{Revoke}$ outputs ⊥.
-: $O_{Search} (\cdot, G, P K_{s}, F_{s})$ : $A_{r e v}$ can send a search request in $G$ to this oracle. $A_{r e v}$ generates a search token and sends it to $O_{Search}$ . Then, the oracle $O_{Search}$ runs $Search$ by the input provides by $A_{r e v}$ , and outputs the search result to $A_{r e v}$ .

After polynomial times rounds of queries,

C

revokes all the users that have access to

O_{Grant} (\cdot, G, i d_{j}, P K_{i}, F_{i})

but not

O_{Revoke} (\cdot, G, i d_{j}, P K_{i}, F_{i})

A_{r e v}

generates a search token τ in

Search

protocol. If the output of

Search

is not ⊥, then returns 1, otherwise returns 0.

The proposed scheme achieves revocation security if, for all

A_{r e v}

, all

1^{k}

, the advantage of

A_{r e v}

to win

{Exp}_{A}^{Revoke} (1^{k})

is negligible:

| \Pr [{Exp}_{A_{r e v}}^{Revoke} (1^{k}) = 1] | \leq negl (1^{k}) .

3.4. The Detailed Construction

Let

BE = {BE . K e y G e n, BE . J o i n, BE . E n c, BE . D e c}

be a broadcast encryption scheme that retains CPA secure against a coalition of revoked users [26],

P = {P . K e y G e n, P .

E n c, P . D e c}

be the Pallier encryption scheme [27],

GM = {GM . K e y G e n, GM . E n c, GM . D e c}

be the Goldwasser-Micali encryption scheme [28], and

F : {0, 1}^{k} \times {0, 1}^{*} \to {0, 1}^{k}

be a pseudo-random function. The detailed construction is given as follows:

3.4.1. Initialization

On input of the security parameter

1^{k}

S_{1}

initializes the global social network graph structure

G = (V, E)

and public parameters

p a r a m s

. In graph

G

, the maximal number of vertexes in

V

is n, that is

| V | = n

, which represents the maximum amount of enrolled users. Each vertex

v_{i} \in V

should be attached with the information for an enrolled user

U_{i} \in U

that

S_{1}

gathered. The existence of a non-zero edge

e_{i j} \in E

between

v_{i} \in V

and

v_{j} \in V

represents the friends relationship of

U_{i}

and

U_{j}

. In other words, if

U_{i}

and

U_{j}

are strangers to each other, then

e_{i j} = 0

G

is empty at initialization.

3.4.2. Key Generation

If a user

U_{i}

is willing to join in the system, he should generate his own keys at local.

U_{i}

’s keys consists of the following parts: the key for the pseudo-random function

F

to encrypt location data, the key pair for the broadcast encryption scheme

BE

, the key pairs for the Pallier encryption scheme

P

and the Goldwasser-Micali encryption scheme

GM

U_{i}

first takes as input the binary representation of the public parameters

p a r a m s

, and randomly selects a k-bit string

k_{i} \in {0, 1}^{k}

for his key of

F

. Then he generates

(b p k_{i}, m s k_{i})

BE . K e y G e n

(p k_{i}, s k_{i})

P . K e y G e n

and

(p k_{i}^{'}, s k_{i}^{'})

GM . K e y G e n

. Afterwards, he forms his symmetric key

K_{i}

(m s k_{i}, k_{i})

, public key

P K_{i}

(b p k_{i}, p k_{i}, p k_{i}^{'})

and secret key

S K_{i}

(s k_{i}, s k_{i}^{'})

. The lengths of the above keys are determined by the security parameter

1^{k}

. Finally,

U_{i}

publishes his public key

P K_{i}

throughout the system.

3.4.3. Join

Before joining in,

U_{i}

should generate his friends index

F_{i}

with d entries, where d represents the maximum amount of

U_{i}

’s friends.

F_{i}

is a key-value data structure, which is empty at first. The key part of

F_{i}

will be attached with the granted friends’ identities, the corresponding value part will be attached with the granted friends’ session keys. More precisely, if

U_{j}

is a friend of

U_{i}

, then

F_{i} [i d_{j}]

stores the session key

k_{j}^{i}

that

U_{j}

has shared with

U_{i}

, where

i d_{i}

represents

U_{i}

’s identity:

F_{i} [i d_{j}] = k_{j}^{i}

, where

i d_{j}

represents

U_{j}

’s identity. To register,

U_{i}

should also add the server

S_{1}

F_{i}

by generating

S_{1}

’s session key

k_{S_{1}}^{i}

BE . J o i n_{m s k_{i}} (S_{1})

and setting

F_{i} [S_{1}] = k_{S_{1}}^{i}

. Afterwards,

U_{i}

randomly selects a k-bit string

s t_{i}

as his current state value and encrypts

s t_{i}

c s t_{i}

BE . E n c_{b p k_{i}} (S_{1}, s t_{i})

. Then

U_{i}

sends

S_{1}

a registration request

R e_{i} = (i d_{i} | | c s t_{i} | | k_{S_{1}}^{i})

S_{1}

selects an empty vertex

v_{i} \in V

G

and attaches

v_{i}

with

R e_{i}

3.4.4. Location Update

An enrolled user

U_{i} \in U

can interact with

S_{1}

to update his location by LocUpdate protocol. First,

U_{i}

obtains his current geo-location

l_{i}

from the trusted location infrastructure that sends

U_{i}

’s geo-location to his local mobile device periodically.

U_{i}

maps

l_{i}

into an integer

x_{i}

from

Z_{k}

and computes its square

{x_{i}}^{2}

. To hide

l_{i}

from

S_{1}

U_{i}

needs to encrypt

x_{i}

and

{x_{i}}^{2}

at local: he chooses two random values

r_{1}

and

r_{2}

from

Z_{k}

, uses his key

k_{i}

to generate

p_{1} = F_{k_{i}} (r_{1})

and

p_{2} = F_{i} (r_{2})

by pseudo-random function

F

, and hides

x_{i}

and

{x_{i}}^{2}

into

c_{x_{i}} = (x_{i} + p_{1}, r_{1})

and

c_{{x_{i}}^{2}} = ({x_{i}}^{2} + p_{2}, r_{2})

(p_{1}, p_{2})

and

(r_{1}, r_{2})

. Finally he forms his current location ciphertext

L_{i}

L_{i} = (c_{x_{i}}, c_{x_{i}^{2}})

and sends

L_{i}

S_{1}

S_{1}

updates the information embedded in vertex

v_{i}

G

v_{i} \leftarrow v_{i} | | {L_{i}}

3.4.5. Grant

When

U_{i}

connects

U_{j}

as his friend, he should grant

U_{j}

’s right to search his location by conducting Grant protocol with

S_{1}

. First,

U_{i}

adds

U_{j}

’s identity

i d_{j}

as an entry in

U_{i}

’s friends index

F_{i}

, generates

U_{j}

’s session key

k_{j}^{i}

BE . J o i n_{m s k_{i}} (i d_{j})

, sends

k_{j}^{i}

U_{j}

in secure channel.

U_{i}

then selects a k-bit string

s t_{i}^{'}

as his updated state value, encrypts

s t_{i}^{'}

c s t_{i}^{'}

for the updated friends group in

F_{i}

that contains

U_{j}

BE . E n c_{(b p k_{i})} (s t_{i}^{'}, F_{i})

, and boardcasts

c s t_{i}^{'}

to the system. After receiving his session key

k_{i}^{j}

from

U_{j}

, he attaches

F_{i} [i d_{j}]

with

k_{i}^{j}

F_{i} [i d_{j}] = k_{i}^{j}

. Afterwards, he sends grant request

(c s t_{i}^{'} | | i d_{j})

S_{1}

S_{1}

first checks whether there is a non-zero direct edge

e_{i j}

G

. If not, it sets

e_{i j} = 1

and update

v_{i}

G

with new

c s t_{i}^{'}

v_{i} \leftarrow v_{i} ∖ {c s t_{i}} \cup {c s t_{i}^{'}}

3.4.6. K-Nearest Neighbors Search

Each enrolled user

U_{s} \in U

can send a search request to

S_{1}

for retrieving his k-nearest neighbors sorted by distances, shown in Protocol 1. First of all,

U_{s}

retrieves his friends’ identities

{i d_{1}, \dots, i d_{d}}

from his friends index

F_{i}

, downloads the state ciphertexts

{c s t_{1}, \dots, c s t_{d}}

for all his friends

{U_{1}, \dots, U_{d}}

from the system. For each

c s t_{i} \in {c s t_{1}, \dots, c s t_{d}}

U_{s}

decrypts it to

s t_{i}^{'}

BE . D e c_{k_{s}^{i}} (s t_{i}^{'})

. Afterwards,

U_{s}

consolidates the decryption results into search token

τ = (s t_{1}^{'}, \dots, s t_{d}^{'})

and sends

τ

S_{1}

. After receiving

τ

S_{1}

extracts

{c s t_{1}, \dots, c s t_{d}}

from

v_{j}

’s all adjacents

{v_{1}, \dots, v_{d}}

G

. For each

c s t_{i} \in {c s t_{1}, \dots, c s t_{d}}

S_{1}

decrypts it to

s t_{i}

BE . D e c_{k_{S_{1}}^{i}} (c s t_{i})

. It compares each

s t_{i}

{s t_{1}, \dots, s t_{d}}

with

s t_{i}^{'}

τ

: if

s t_{j}^{'}

is equal to

s t_{i}

, then

U_{s}

has been granted the right to search for

U_{i}

’s location. Afterwards, for each granted

U_{i}

S_{1}

retrieves the encrypted location

L_{i}

attached in

v_{i}

. Then,

S_{1}

and

S_{2}

conduct the following protocols:

After conducting

P_{1}

and

P_{2}

for all

U_{s}

’s friends,

S_{1}

forms a key-value set

I = {(i d_{1}, [D_{1}]), \dots, (i d_{d}, [D_{d}])}

that contains all pairs of the encrypted distances between

U_{s}

and his friends along with their identities.

S_{1}

encrypts each

i d_{i} \in I

[i d_{i}]

P . E n c_{p k_{s}} (i d_{i})

, and generates

\tilde{R} = {([i d_{1}], [D_{1}]), \dots, ([i d_{d}], [D_{d}])}

S_{1}

and

S_{2}

perform a secure comparison protocol

P_{3}

[29] for

S_{1}

and

S_{2}

to compare each pair

([i d_{x}], [D_{x}])

and

([i d_{y}], [D_{y}])

\tilde{R}

based on the distance

D_{x}

and

D_{y}

. We use

P_{3}

as a black-box building block for Search protocol, and pick Batcher’s sorting [30] for performing efficient parallel multi-time comparisons.

Finally,

S_{1}

obtains the sorted final result

R = {([i d_{1}], [D_{1}]), \dots, ([i d_{d}], [D_{d}])}

, and sends it back to

U_{s}

U_{s}

can decrypt each

[i d_{i}]

i d_{i}

P . D e c_{s k_{s}} [i d_{i}]

, then obtain his k-nearest neighbors identities

R_{k} = (i d_{1}, \dots, i d_{k})

that were sorted by distance.

3.4.7. Revoke

When

U_{i}

wants to revoke

U_{j}

’s search right, he should conduct Revoke protocol with

S_{1}

U_{i}

first deletes

F_{i} [i d_{j}]

locally, selects a k-bit string

s t_{i}^{'}

as his updated state value, encrypts

s t_{i}^{'}

c s t_{i}^{'}

BE . E n c_{b p k_{i}} (s t_{i}^{'}, F_{i})

for the updated group in

F_{i}

that excludes

U_{j}

. Afterwards, he sends revoke request

(c s t_{i}^{'} | | i d_{j})

S_{1}

S_{1}

first checks whether there is a non-zero direct edge

e_{i j}

G

. If true, it set

e_{i j} = 0

and update

v_{i}

G

with new

c s t_{i}^{'}

v_{i} \leftarrow v_{i} ∖ {c s t_{i}} \cup {c s t_{i}^{'}}

4. Security Analysis

4.1. Adaptive $L$ -Semantic Secure

Theorem 1.

F

is a pseudo-random function,

P

GM

and

BE

are CPA secure, and the DGK protocol [31] is proved to be semantically secure in the random oracle model, then the proposed scheme satisfies adaptive

L

-semantic security, which is defined in Definition 2.

Proof.

We construct two simulators

S i m_{1}, S i m_{2}

that can generate the simulated values in

Ideal (1^{k})

using the information given in the leakage functions

L_{1}

L_{4}

, and prove that

Ideal (1^{k})

is indistinguishable with Real

(1^{k})

by any PPT adversary.

Given the information leaked from

L_{1}

S i m_{1}

can learn

| c s t_{i}^{j} |

and

{| c s t_{i}^{1} |, \dots, | c s t_{i}^{q} |}

. Afterwords, it can choose random value

{\tilde{c s t}}_{i}^{j}

with lengths

| c s t_{i}^{j} |

to simulate

c s t_{i}^{j}

. Due to the CPA secure of

BE

{c s t}_{i}^{j}

is indistinguishable from

{\tilde{c s t}}_{i}^{j}

by any PPT adversary. Therefore,

S i m_{1}

cannot learn extra information from

{| c s t_{i}^{1} |, \dots, | c s t_{i}^{q} |}

, which satisfies:

{Output}_{A_{1}}^{Real} ({c s t_{i}^{1}, \dots, c s t_{i}^{q}}) \approx {Output}_{S i m_{1}}^{Ideal} ({{\tilde{c s t}}_{i}^{1}, \dots, {\tilde{c s t}}_{i}^{q}}) .

Given the information leaked from

L_{2}

S i m_{1}

can learn

| c_{x_{i}}^{j} |

and

| c_{{x_{i}}^{2}}^{j} |

L_{i}^{j} = (c_{x_{i}}^{j}, c_{{x_{i}}^{2}}^{j})

. Afterwards, it can choose two random values in lengths

| c_{x_{i}}^{j} |

and

| c_{{x_{i}}^{2}}^{j} |

to output the simulated

{\tilde{L}}_{i}^{j} = ({\tilde{c}}_{x_{i}}^{j}, {\tilde{c}}_{{x_{i}}^{2}}^{j})

. Since

L_{i}^{j}

is generated by

F

{\tilde{L}}_{i}^{j}

and

L_{i}^{j}

are indistinguishable by any PPT adversary due to the randomness of

F

. Therefore,

S i m_{1}

cannot learn extra information from the update history

{L_{i}^{1}, \dots, L_{i}^{q}}

, which satisfies:

{Output}_{A_{1}}^{Real} ({L_{i}^{1}, \dots, L_{i}^{q}}) \approx {Output}_{S i m_{1}}^{Ideal} ({{\tilde{L}}_{i}^{1}, \dots, {\tilde{L}}_{i}^{q}}) .

Given the information leaked from

L_{3}

S i m_{1}

can obtain search tokens

{τ_{1}, \dots, τ_{q}}

. Afterwards, it can choose random value

{\tilde{τ}}_{i}

in size

| τ_{i} |

to simulate each

τ_{i}

. Moreover, since

{s t_{1}^{'}, \dots, s t_{d}^{'})

is generated by

BE . D e c

by decrypting

{c s t_{1}, \dots, c s t_{d}}

using keys

{k_{s}^{1}, \dots, k_{s}^{d})

, and each

k_{s}^{i}

{k_{s}^{1}, \dots, k_{s}^{d}}

is a k-bit random string, each

s t_{j}^{'}

τ_{i}

is indistinguishable from

{\tilde{τ}}_{i}

by any PPT adversary. Therefore,

S i m_{1}

cannot learn extra information from

τ_{1}, \dots, τ_{q}

, which satisfies:

{Output}_{A_{1}}^{Real} ({τ_{1}, \dots, τ_{q}}) \approx {Output}_{S i m_{1}}^{Ideal} ({{\tilde{τ}}_{1}, \dots, {\tilde{τ}}_{q}}) .

The sorting network between

A_{1}

and

A_{2}

contains

{(log d)}^{2}

levels, and each level contains

{(log d)}^{2}

times of

P_{3}

protocols. Therefore, the simulation of the sorting network can be reduced to prove

S i m_{1}

and

S i m_{2}

can simulate the secure comparison protocol

P_{1}

with leakage functions. Given the information leaked from

L_{4}

S i m_{2}

can learn the leaked information

([[z_{i}]], [λ_{i}])

from each round of

P_{3}

and the rounds number

{(log d)}^{2}

. In each round,

S i m_{2}

can learn

([D_{x}], [D_{y}], l)

S i m_{1}

and

S i m_{2}

should simulate

A_{1}

and

A_{2}

with

L_{4}

by all pairs with

{(log d)}^{2}

times in sorting protocol to get the final simulation value. At every pairs i,

A_{1}

’s view can be denoted as

v i e w_{A_{1}} = (s k_{s}, [[z]], ∥λ∥)

. Given

(s k_{s}, [[z]], [λ])

, we can build

S i m_{1}

in the following phases:

-: Randomly choose $\tilde{λ}$ , compute $| | \tilde{λ} | |$ as $x_{x} \leq x_{y}$ ;
-: Randomly choose $\tilde{z} \leftarrow (0, 2^{λ + l}) ⋃ Z$ ;
-: Encrypt $\tilde{z}$ : $[\tilde{z}] \leftarrow P . E n c_{p k_{s}} (z)$ ;
-: Output $v i e w_{S i m_{1}} = (s k_{s}, l, [\tilde{z}], | | \tilde{λ} | |)$ .

Since

z = x + r

, where x is a l-bits integer and r is a

l + λ

-bits integer, the distribution of

\tilde{z}

is indistinguishable from z. We can get

(s k_{s}, [\tilde{z}]) \approx (s k_{s}, [z])

. Besides, since the distribution of

\tilde{z}

and z are independent of t, we can get

(s k_{s}, l, [\tilde{z}] | | \tilde{λ} | |) \approx (s k_{s}, l, [z], | | \tilde{λ} | |)

. In a similar way, at every pairs i,

A_{2}

’s view can be denoted as

v i e w_{A_{2}} = (({[D_{x}]}_{i}, {[D_{y}]}_{i}, l, p k_{s}, r, ∥λ∥, [z_{l}])

. We can build

S i m_{2}

to simulate

A_{2}

in the following phases:

-: Choose $\tilde{r} \leftarrow (0, 2^{λ + l}) ⋃ Z$ ;
-: Choose two random values $\tilde{λ}, {\tilde{z}}_{l}$ , computes $| | \tilde{λ} | |, ∥\tilde{z}∥$ ;
-: Output $v i e w_{S i m_{2}} = ([D_{x}], [D_{y}], l, p k_{s}, \tilde{r}, [{\tilde{z}}_{l}])$ .

In both

v i e w_{A_{2}}

and

v i e w_{S i m_{2}}

, r is extracted from uniform distribution

(0, 2^{λ + l}) ⋃ Z

[{\tilde{z}}_{l}]

is the ciphertext of

P

which is randomness, so

([D_{x}], [D_{y}], l, p k_{s}) \approx ([D_{x}], [D_{y}], l, p k_{s}, r,

[{\tilde{z}}_{l}])

. We can obtain:

v i e w_{A_{2}}

and

v i e w_{S i m_{2}}

are computational indistinguishable. What is more, since

| | \tilde{λ} | | \approx ∥[D_{x}] \leq [D_{y}]∥

(s k_{s}, l, [z], | | \tilde{λ} | |) \approx (s k_{s}, l, [z],

∥[x_{x}] \leq [y_{y}]∥)

. Due to the semantic security of DGK,

S i m_{1}

and

S i m_{2}

can obtain d ciphertexts that are unsorted from the leakage function

L_{4}

. Then,

S i m_{1}

and

S i m_{2}

can simulate Bathcer’s sorting protocols in

{(log d)}^{2}

times.

Therefore, for all polynomial time

A_{1}

and

A_{2}

, there exists polynomial time simulators

S i m_{1}

and

S i m_{2}

such that:

We can demonstrate that the proposed scheme satisfies adaptive

L

-semantic security in the random oracle model, which is defined in Definition 2. Theorem 1 proved. □

4.2. Revocation Secure

Theorem 2.

BE

is CPA secure, then the proposed scheme satisfies revocation secure, which is defined in Definition 3.

Proof.

Assuming the advantage of

A_{r e v}

to win

{Exp}_{A_{r e v}}^{Revoke} (1^{k})

is negligible, we can construct an adversary

A_{b e}

, who can break the CPA secure of

BE

with assist of

A_{r e v}

. We will show that if

A_{r e v}

has a non-negligible advantage in

{Exp}_{A_{r e v}}^{Revoke} (1^{k})

, then we can construct an adversary

A_{b e}

that uses

A_{r e v}

as a subroutine to break the CPA secure of

BE

To make the output of

{Exp}_{A_{r e v}}^{Revoke} (1^{k})

as 1,

A_{r e v}

needs to provide a valid search token. To achieve that,

A_{r e v}

must know

s t_{i}

. A new value of

s t_{i}

is randomly selected and encrypted by

BE . E n c_{b p k_{i}} (s t_{i}, F_{i} ∖ u_{j})

at each time a user is revoked from the system, where

F_{i} ∖ u_{j}

is the new friends index.

A_{r e v}

then broadcast this encrypted value to all users.

BE

’s security ensures that only a non-revoked friend of

U_{i}

can decrypt this ciphertext to obtain

s t_{i}

with overwhelming probability. Hence, the adversary can only create a valid search token if he is a valid friend of

U_{i}

, or he will break the security of

BE

. That is, the probability that a random bit string is valid is

2^{- k}

. It means that the adversary will not be able to produce a valid token with non-negligible probability.

Let

C

be the challenger for the adversary

A_{b e}

against

BE

A_{b e}

will act as the challenger for

A_{r e v}

$C$ runs $BE . K e y G e n (1^{k})$ to generate keys $(m s k_{b e}, b p k_{i})$ . $A_{b e}$ initializes $F_{i}$ , randomly chooses a k-bit string $s t_{i}$ , and sends $(s t_{i}, F_{i})$ to $C$ . $C$ runs $BE . E {nc}_{b p k_{i}} (s t_{i}, F_{i})$ to generate $s t_{S_{1}}$ , and sends it to $A_{b e}$ . $A_{b e}$ runs $KeyGen$ to generate $K_{i}$ , runs $Join$ to generate $k_{S_{1}}^{i}$ , where $K_{i}$ does not include $k_{b e}$ .
$A_{b e}$ issues a query to $C$ for the secret key of $A_{r e v}$ . $C$ runs $BE . J {oin}_{m s k_{i}} (A_{r e v})$ to generate $k_{A_{r e v}}$ , sends $k_{A_{r e v}}$ to $A_{b e}$ . To fully enroll $A_{r e v}$ as a valid friend, the state ciphertext also needs to be updated by $A_{b e}$ . $A_{b e}$ send $F_{i}$ and a newly generated $s t_{i}$ to $C$ , $C$ runs $BE . E n c_{b p k_{i}} (s t_{i}, F_{i})$ to generate new $c s t_{i}$ . $A_{b e}$ runs $Grant$ to generate the key $k_{A_{r e v}}^{i}$ of $A_{r e v}$ .
$A_{b e}$ runs Initial to generate graph $G$ , and sends $k_{A_{r e v}}^{i}$ and $G$ to $A_{r e v}$ . $A_{r e v}$ can access to oracles $O_{Grant}$ and $O_{Revoke}$ .
$A_{b e}$ revokes $A_{r e v}$ by running $Revoke$ , $A_{b e}$ runs Revoke a second time in order to produce two values $s t_{i 0} \leftarrow {0, 1}^{k}$ and $s t_{i 1} \leftarrow {0, 1}^{k}$ for $s t_{i}$ , and sends $s t_{i 0}$ and $s t_{i 1}$ to $C$ as the challenge value for $A_{b e}$ , along with a set of no revoked friends $F_{i}$ of $A_{r e v}$ .
$C$ selects a bit $b \in {0, 1}$ , uses $BE . E n c_{b p k_{i}} (s t_{i b}, F_{i})$ to encrypt $s t_{i b}$ and generates ${c s t_{i}}_{b}$ , sends ${c s t_{i}}_{b}$ to $A_{b e}$ as the challenge ciphertext for the CPA secure of $BE$ . $A_{b e}$ sends ${c s t_{i}}_{b}$ to $A_{r e v}$ as the challenge ciphertext of ${Exp}_{A_{r e v}}^{Revoke} (1^{k})$ .
$A_{r e v}$ generates token $τ$ , and sends $τ$ to $A_{b e}$ . Since the advantage for $A_{r e v}$ to win ${Exp}_{A_{r e v}}^{Revoke} (1^{k})$ is non-negligible, the probability of validity of $τ$ is non-negligible.
If $t_{0} \neq ⊥$ , then Search stops. According to the following situations, $A_{b e}$ outputs its guess for b:
-
If $t_{0} \neq ⊥$ , this tells $A_{b e}$ that $s t_{i 0}$ was used to generate the token, $A_{b e}$ outputs its guess for b as $b^{'} = 0$ ;
-
Of $t_{1} \neq ⊥$ , this tells $A_{b e}$ that $s t_{i 1}$ was used to generate the token, $A_{b e}$ outputs its guess for b as $b^{'} = 1$ .

From the above analysis, the advantage of

A_{b e}

to break the CPA secure of

BE

can be computed as

{Adv}_{A_{b e}}^{BE} (1^{k})

\begin{matrix} {Adv}_{A_{b e}}^{BE} (1^{k}) & = | [(Pr [(t_{0} \lor t_{1}) \neq ⊥] \cdot 1 - \frac{1}{2}) + (Pr [((t_{0} \land t_{1}) \neq ⊥] \cdot \frac{1}{2} - \frac{1}{2}) | \\ = | δ \cdot 1 + (1 - δ) \cdot \frac{1}{2} - \frac{1}{2} | \\ = | \frac{(δ + 1)}{2} - \frac{1}{2} | \\ = \frac{δ}{2} . \end{matrix}

Since the advantage

δ

A_{r e v}

to win

{Exp}_{A_{r e v}}^{Revoke} (1^{k})

is non-negligible, the advantage

\frac{δ}{2}

A_{b e}

to break the CPA security of

BE

is non-negligible, which contradicts the CPA security of

BE

. Therefore, there exists no

A_{r e v}

, who can win

{Exp}_{A_{r e v}}^{Revoke} (1^{k})

with non-negligible probability, and the proposed scheme satisfies revocation security as defined in Definition 3. Theorem 2 proved. □

5. Theoretical Analysis

The complexity analysis is shown in Table 1, where n is the maximum amount of enrolled users and d is the maximum amount of each user’s friends. We compare our scheme with the related privacy-preserving location-based query schemes [15,18,20] in Table 2. Due to the significant differences among the existing schemes in application scenarios, secure models, evaluation indicators and other factors, we focus on comparing characteristics and security.

For result accuracy, [15] achieves differential privacy for location information using linear programming techniques. It is specifically designed for simple computation that cannot provide accurate encrypted distance sorting. Ref. [20] uses a dynamic location grid structure to cluster users close to each other. However, the search results in [15,20] have a specific rate of false positives, which are suitable for similarity search. Our scheme and [18] use Euclidean distance to calculate the encrypted distance to achieve precise secure sorting. Ref. [18] focuses on searching the number of points of interest in a specific location area; our scheme sorts the distances based on the proven-secure comparison protocol. In terms of security, Ref. [18] protects location search privacy by way of private information retrieval (PIR). Although it adopts the anchor technology to improve search efficiency, it still has a certain communication overhead. Ref. [20] achieves sort privacy by assuming the server only performs the search, and the user performs the result sorting. As a result, the above methods each sort privacy but lead to high computation or communication costs.

Besides, compared with other schemes, our scheme also has a flexible access control mechanism. Moreover, our scheme achieves a constant-time computation cost and communication cost when updating friends and encrypting locations, and a user only needs to store key-related information locally. Therefore, we can demonstrate that our proposed scheme has both a very light user workload and a moderate server workload while being secure against the honest-but-curious adversary. In nowadays’s mobile social networking environment, the user-side lightweight device’s storage and computation cost should be minimized as much as possible. As a consequence, the proposed scheme is more suitable for the real-life thin clients MSNs deployment scenario.

6. Implementation

We implement and analyze the performance of our scheme. The experiments were run on several computers with Linux Ubuntu 18.04.2 64-Bit Version with Inter(R) Core(TM) I7-2600 quad-core processor (3.4 ghz) and 8 GB memory, which were installed on VMware Workstation in the LAN in C++ language. One of the computers acted as the server-end and the others acted as user-ends, respectively. We implemented a job allocation mechanism in the server-end that the computer acted as the master server and used threads to simulate the collaborated server that performed the assistant job. Each user-end stored the user’s keys locally and interacted with the server-end. To submit a search request, a user-end only communicated with the master server.

In the simulation experiments, the security parameter k was set to 256 bits. We chose SHA256 in the OpenSSL library [32] for the pseudo-randomness function, and used the Relic library [33] to implement Paillier and GM homomorphic encryption. To implement the scheme more securely, we improved the modulus n of the Paillier and GM to 1024 bits. Besides, we used BGW2 [26] to implement public-key broadcast encryption. The key length in the above public encryption methods was set to be 1024 bits.

We conducted data simulations based on real-world data sets, which came from the newest version of the Enron email dataset [34], where we randomly selected 1000 accounts as the total users set. We represented users’ friendships in the form of linked contacts. We selected a random integer in

(10, 50)

to simulate the user’s location’ value, which was updated periodically. Moreover, we initialized the social network graph structure

G

with 1000 vertexes and 3831 edges that contained the above data and used a unique value to identify each vertex (user) in

Z_{k}

. We did not record the network communication time during all the experiments since it depends on the user-end and the server-end’s network connection. Each data point in the experiments was obtained after being repeated 50 times to generate the average value.

6.1. Storage Analysis

We first analyzed the storage overhead of our scheme. Table 3 shows the comparison between the encrypted

G

and unencrypted

G

of the generation time and the server’s storage cost in the trend of the number of users increases. It can be seen that the server’s storage cost increased almost linearly with the increase of the number of users. Since we used symmetric encryption to encrypt location, compared with the Paillier homomorphism ciphertext, the inflation rate of the symmetric ciphertext of the location decreased significantly, which is consistent with the theoretical analysis. Therefore, the proposed scheme achieves the trade-off of users’ location confidentiality and search privacy with the acceptable additional storage cost.

6.2. Communication

In terms of communication, we mainly analyzed the amount of data transformed between (1)

U_{i}

and

S_{1}

and (2)

S_{1}

and

S_{2}

in Search protocol. Theoretically, when

U_{i}

requests to search k-nearest neighbors among his d friends,

U_{i}

’s communication overhead increases almost linearly with k. When

S_{1}

and

S_{2}

interact with each other to compute the distance from the total of d friends’ location ciphertexts, the data size of the communication between them is

O ({(\log d)}^{2})

Figure 2a,b shows the relationship between the two types of communication overhead in the experiment with the increasing trends of the friends’ number d and the search parameter k, respectively. In general, the amount of data transmission required by the user in Search protocol is positively related to k. When k increases to a particular value (greater than d), the data transmission volume tends to be stable. The communication overhead between

S_{1}

and

S_{2}

is mainly positively related to d, but independent of the increase of k. Moreover, the distance computation sub-procedure requires several rounds of interactions, so the amount of communication overhead between servers is relatively large, which is consistent with the theoretical analysis.

6.3. Search Time

We also analyzed the primary source of the search time overhead for Search protocol. First, we divided the Search protocol at the server-end into two sub-procedures of location search and distance sort. Figure 3 shows the relationship between search time and the number of friends d. In Figure 3, the total time overhead of Search protocol is shown in the blue curve, the time overhead to extract and re-encrypt location ciphertext is shown in the yellow curve, and the time overhead to compute and sort the encrypted distance is shown in the red curve.

From Figure 3, we can see that the time overhead of the two sub-procedures in the Search protocol generally increases with the increasing trend of d. Specifically, the location search time is far lower than the distance sort time, and with d increases to 4, the curve growth is slowing down. The distance sort time has a stable approximate linear relation with d. Therefore, it can be concluded that the computation and comparison of encrypted distances are two primary time-overhead sources of the Search protocol, which is consistent with the theoretical analysis.

6.4. Scalability

In terms of scalability, we first analyzed the impact of the search users’ number who submit search requests in parallel on the time overhead of the Search protocol. To be specific, we deploy one host to simulate one user to execute the Search protocol and record the total time overhead. Then we deploy six hosts to simulate six users to repeat the same experiment and compare the results. It is worth mentioning that, when recording the time of multi-user search, multiple user-ends simultaneously send the search requests to the server-end. We record the start and end time when the server-end receives the search request until it completes each user’s search. Figure 4 shows the relationship between the parallel search users’ number and Search protocol’s total time. It can be seen that one user’s search time is slightly lower than six parallel users’ search times. The former is approximately in a stable linear relation with d, and the latter slows down to a constant level with the increase of d. From the trend it can be concluded that, with the number of search users d increasing, its impact on search time overhead is weakened, and it further weakens the influence of the increasing number of friends on the search time. Therefore, the multi-user parallelism has a weak impact on search time overhead, which helps the scheme to achieve a certain level of scalability.

Besides, we analyzed the influence of the expandable number of remote servers on the search time overhead. First, we deployed three servers to execute the Search protocol for six users simultaneously and recorded the total time overhead. Then we deployed six servers to repeat the same experiment and compare the results. Figure 4 shows the relationship between the number of servers and the search time. It can be seen that the search time of 6-server deployment is significantly lower than the running time with 3-server deployment, and the former’s growth was slowed down to a constant level after d reaches 4, but the latter’s growth takes an approximately linear relationship with the number of friends steadily. Therefore, it can be concluded that deploying multiple servers to perform parallel searches can reduce the search time overhead and further weaken the influence of the increasing number of friends on the search time.

Remark 1.

It is worth pointing out that the search process’s main computation cost is the homomorphic encryption/decryption operation and broadcast decryption operation. The computation efficiency is closely related to the selected parameters of the underlying algorithms. The server-end implementation can also be optimized to reduce the search time by using multiple threads for distance sorting and using approximate sorting algorithms, and so forth. In our experiment, we did not adopt any optimization method. The server was allowed to complete all the computation steps in a single thread in each phase to reflect the scheme’s original execution efficiency faithfully.

7. Conclusions

Aiming at the problem of location privacy disclosure in MSNs, we propose a privacy-enhancing k-nearest neighbors search scheme over MSNs. We deploy a dual-server collaborative architecture and design an encrypted location-oriented k-neighbor search protocol based on secure multi-party computation and homomorphic encryption. Our scheme achieves accurate nearby friends retrieval while protecting the geo-location and the distance order from revealing them to the servers. We propose a lightweight dynamic friends management mechanism based on public-key broadcast encryption to satisfy the fine-grained access control requirement. It enables users to grant/revoke a friend’s location search right without updating others’ keys and achieves constant-time identity authentication. The scheme satisfies adaptive

L

-semantic security and revocation security under the random oracle model. Compared with the works on single server architecture, the proposed scheme reduces the communication cost between users and the server and prevents location information leakage, which achieves a trade-off of the location availability and privacy.

Author Contributions

Conceptualization, Y.L. and F.Z.; Data curation, Y.L.; Formal analysis, Y.L.; Funding acquisition, F.Z.; Methodology, Y.L.; Project administration, F.Z.; Validation, Y.G. and Z.X.; Writing–original draft, Y.L.; Writing–review & editing, Y.L., Y.G. and Z.X. All authors have read and agreed to the published version of the manuscript.

Funding

This research was funded by Northeastern University Annual Basic Scientific Research Funding under Grant 02190022121006 and the Natural Science Foundation of China under Grant 61772127, Grant 61532007 and Grant 61472184.

Conflicts of Interest

The authors declare no conflict of interest.

References

Global Social Media Stats. Available online: https://datareportal.com/social-media-users (accessed on 10 April 2021).
Weichbroth, P.; Łysik, Ł. Mobile Security: Threats and Best Practices. Mob. Inf. Syst. 2020. [Google Scholar] [CrossRef]
Anastasios, N.; Salvatore, S.; Mascolo, C.; Pontil, M. An empirical study of geographic user activity patterns in foursquare. In Proceedings of the Fifth International AAAI Conference on Weblogs and Social Media, Barcelona, Spain, 17–21 July 2011. [Google Scholar]
Cheng, Z.; Caverlee, J.; Lee, K.; Sui, D. Exploring millions of footprints in location sharing services. In Proceedings of the International Conference on Weblogs and Social Media, Barcelona, Spain, 17–21 July 2011; pp. 81–88. [Google Scholar]
Preotiuc, P.D.; Cohn, T. Mining user behaviors: A study of check-in patterns in location based social network. In Proceedings of the Conference on ACM Web Science, Paris, France, 2–4 May 2013; pp. 306–315. [Google Scholar]
Chor, B.; Goldreich, O.; Kushilevitz, E.; Sudan, M. Private information retrieval. In Proceedings of the IEEE 36th Annual Foundations of Computer Science, Milwaukee, Wisconsin, 23–25 October 1995; pp. 41–50. [Google Scholar]
Curtmola, R.; Garay, J.; Kamara, S.; Ostrovsky, R. Searchable symmetric encryption: Improved definitions and efficient constructions. J. Comput. Secur. 2016, 19, 895–934. [Google Scholar] [CrossRef] [Green Version]
Lucas, M.M.; Nikita, B. Flybynight: Mitigating the privacy risks of social networking. In Proceedings of the 7th ACM Workshop on Privacy in the Electronic Society, Alexandria, VA, USA, 27 October 2008; pp. 1–8. [Google Scholar]
Guha, S.; Kevin, T.; Paul, F. NOYB: Privacy in online social networks. In Proceedings of the First Workshop on Online Social Networks, Seattle, WA, USA, 18 August 2008; pp. 49–54. [Google Scholar]
Niu, B.; Li, X.; Zhu, X.; Li, X.; Li, H. Are you really my friend? Exactly spatiotemporal matching scheme in Privacy-Preserving mobile social networks. In Proceedings of the International Conference on Security and Privacy in Communication Systems, Beijing, China, 24–26 September 2014; pp. 33–40. [Google Scholar]
Zhang, R.; Zhang, Y.; Sun, J.; Yan, G. Fine-grained private matching for proximity-based mobile social networking. In Proceedings of the IEEE INFOCOM, Orlando, FL, USA, 25–30 March 2012; pp. 1969–1977. [Google Scholar]
Fu, Y.; Wang, Y. BCE: A privacy-preserving common-friend estimation method for distributed online social networks without cryptography. In Proceedings of the 7th International Conference on Communications and Networking, Kunming, China, 8–10 August 2012; pp. 212–217. [Google Scholar]
Sun, J.; Zhang, R.; Zhang, Y. Privacy-preserving spatiotemporal matching. In Proceedings of the IEEE INFOCOM, Turin, Italy, 14–19 April 2013; pp. 800–808. [Google Scholar]
Bamba, B.; Liu, L.; Pesti, P.; Wang, T. Supporting anonymous location queries in mobile environments with PrivacyGrid. In Proceedings of the 17th international conference on World Wide Web, New York, NY, USA, 21–25 April 2008; pp. 237–246. [Google Scholar]
Bordenabe, N.E.; Chatzikokolakis, K.; Palamidessi, C. Optimal Geo-Indistinguishable Mechanisms for Location Privacy. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security (CCS ’14), Scottsdale, AZ, USA, 3–7 November 2014; pp. 251–262. [Google Scholar]
Elaine, S.; Richard, C.; Hubert, C. Privacy-preserving aggregation of time-series data. In Proceedings of the Network and Distributed System Security Symposium (NDSS 2011), San Diego, CA, USA, 6–9 February 2011; pp. 1–17. [Google Scholar]
Jorgensen, Z.; Yu, T.; Cormode, G. Publishing attributed social graphs with formal privacy guarantees. In Proceedings of the 2016 International Conference on Management of Data, San Francisco, CA, USA, 26 June–1 July 2016; pp. 107–122. [Google Scholar]
Zhou, C.L.; Chen, Y.H.; Tian, H.; Cai, S.B. Location Privacy and Query Privacy Preserving Method for K-nearest Neighbor Query in Road Networks. J. Softw. 2020, 31, 471–492. [Google Scholar] [CrossRef]
Li, Z.; Wang, C.; Yang, S.; Jiang, C.; Li, X. Lass: Local-activity and social-similarity based data forwarding in mobile social networks. IEEE Trans. Parallel Distrib. Syst. 2014, 26, 174–184. [Google Scholar] [CrossRef] [Green Version]
Schlegel, R.; Chow, C.; Huang, Q.; Wong, D. User-defined privacy grid system for continuous location-based services. IEEE Trans. Mob. Comput. 2015, 14, 2158–2172. [Google Scholar] [CrossRef]
Han, M.; Li, L.; Xie, Y.; Wang, J.; Duan, Z.; Li, J.; Yan, M. Cognitive approach for location privacy protection. IEEE Access 2018, 6, 13466–13477. [Google Scholar] [CrossRef]
Siddula, M.; Li, Y.; Cheng, X.; Tian, Z.; Cai, Z. Privacy-enhancing preferential lbs query for mobile social network users. Wirel. Commun. Mob. Comput. 2020. [Google Scholar] [CrossRef]
Yang, X.; Yang, M.; Yang, P.; Leng, Q. A multi-authority attribute-based encryption access control for social network. In Proceedings of the 2017 3rd IEEE International Conference on Control Science and Systems Engineering (ICCSSE), Beijing, China, 17–19 August 2017; pp. 671–674. [Google Scholar]
Luo, E.; Liu, Q.; Wang, G. Hierarchical multi-authority and attribute-based encryption friend discovery scheme in mobile social networks. IEEE Commun. Lett. 2016, 20, 1772–1775. [Google Scholar] [CrossRef]
Alanwar, A.; Shoukry, Y.; Chakraborty, S.; Martin, P.; Tabuada, P.; Srivastava, M. PrOLoc: Resilient localization with private observers using partial homomorphic encryption. In Proceedings of the 2017 16th ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN), Pittsburgh, PA, USA, 18–21 April 2017; pp. 41–52. [Google Scholar]
Boneh, D.; Craig, G.; Brent, W. Collusion resistant broadcast encryption with short ciphertexts and private keys. In Proceedings of the Advances in Cryptology—CRYPTO 2005, Santa Barbara, CA, USA, 14–18 August 2005; pp. 258–275. [Google Scholar]
Paillier, P. Public-key cryptosystems based on composite degree residuosity classes. In Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques, Prague, Czech Republic, 2–6 May 1999; pp. 223–238. [Google Scholar]
Goldwasser, S.; Micali, S. Probabilistic Encryption. J. Comput. Syst. Sci. 1984, 28, 270–299. [Google Scholar] [CrossRef] [Green Version]
Li, Y.; Zhou, F.; Xu, Z. PPFQ: Privacy-Preserving Friends Query over Online Social Networks. In Proceedings of the 2020 IEEE 19th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom), Guangzhou, China, 29 December–1 January 2021; pp. 1348–1353. [Google Scholar]
Batcher, K.E. Sorting networks and their applications. In Proceedings of the spring joint computer conference, New York, NY, USA, 30 April–2 May 1968; pp. 307–314. [Google Scholar]
Veugen, T. Improving the DGK comparison protocol. In Proceedings of the International Workshop on Information Forensics and Security, Tenerife, Spain, 2 December 2012; pp. 49–54. [Google Scholar]
The OpenSSL Project. OpenSSL: The Open Source Toolkit for SSL/TLS. 2015. Available online: http://www.openssl.org/ (accessed on 26 May 2021).
Relic-Toolkit. Available online: https://github.com/relic-toolkit (accessed on 26 May 2021).
Cohen, W.W. Enron Email Dataset. 2015. Available online: https://www.cs.cmu.edu/~enron/ (accessed on 26 May 2021).

Figure 1. The architecture.

Figure 2. Communication overhead.

Figure 3. Search time overhead.

Figure 4. Scalability.

Table 1. Complexity analysis.

	${Stor}_{u}$	${Stor}_{S_{1}}$	${Stor}_{S_{2}}$	${Comp}_{u}$	${Comp}_{S_{1}}$	${Comp}_{S_{2}}$	${Comm}_{u}$	${Comm}_{S_{1}}$	${Comm}_{S_{2}}$
Register	$O$ (1)	$O$ (n)	$O$ (n)	$O$ (1)	–	–	$O$ (1)	$O$ (1)	$O$ (1)
Grant	$O$ (d)	$O$ ( $n d$ )	–	$O$ (d)	–	–	$O$ (d)	$O$ ( $n d$ )	–
Revoke	–	–	–	$O$ (1)	$O$ (1)	–	$O$ (1)	$O$ (1)	–
LocUpdate	–	$O$ (n)	–	$O$ (1)	–	–	$O$ (1)	$O$ (n)	–
Search	–	–	–	$O$ (d)	$O$ ( $d +$ (logd) $^{2}$ )	$O$ ( $d +$ (logd) $^{2}$ )	$O$ (k)	$O ({(\log d)}^{2})$	$O ({(\log d)}^{2})$

S t o r

: storage complexity;

C o m p

: computation complexity;

C o m m

: communication complexity.

Table 2. Properties comparison.

	Accuracy	Evaluation Method	Dynamic	Cryptography tool	SP	LP	AC	Rank Model
[16]	✓	Euclidean distance/Anchor points	×	PIR/ $P$	✓	✓	×	–
[17]	×	Linear Programming	✓	HMAC	✓	✓	×	–
[21]	×	Dynamic Grid	×	HMAC	✓	×	×	User
Ours	✓	Squared Euclidean distance	✓	$P$ / $GM$ / $BE$	✓	✓	✓	2 servers

SP: Search Privacy; LP: Location Privacy; AC: Access Control.

Table 3. Storage cost.

	Unencrypted $G$		Encrypted $G$
Vertex	Storage (kb)	GenTime (s)	Storage (kb)	GenTime (s)	Inflation Rate
200	18.752	0.423	57.506	2.359	306.665%
400	38.101	0.477	115.302	2.941	302.622%
600	57.460	0.514	174.379	3.316	303.478%
800	74.677	0.538	225.039	3.770	301.349%
1000	95.988	0.575	289.864	4.113	301.979%

Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

© 2021 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Li, Y.; Zhou, F.; Ge, Y.; Xu, Z. Privacy-Enhancing k-Nearest Neighbors Search over Mobile Social Networks. Sensors 2021, 21, 3994. https://doi.org/10.3390/s21123994

AMA Style

Li Y, Zhou F, Ge Y, Xu Z. Privacy-Enhancing k-Nearest Neighbors Search over Mobile Social Networks. Sensors. 2021; 21(12):3994. https://doi.org/10.3390/s21123994

Chicago/Turabian Style

Li, Yuxi, Fucai Zhou, Yue Ge, and Zifeng Xu. 2021. "Privacy-Enhancing k-Nearest Neighbors Search over Mobile Social Networks" Sensors 21, no. 12: 3994. https://doi.org/10.3390/s21123994

APA Style

Li, Y., Zhou, F., Ge, Y., & Xu, Z. (2021). Privacy-Enhancing k-Nearest Neighbors Search over Mobile Social Networks. Sensors, 21(12), 3994. https://doi.org/10.3390/s21123994

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

Privacy-Enhancing k-Nearest Neighbors Search over Mobile Social Networks †

Abstract

1. Motivation

2. Related Works

2.1. MSNs Privacy

2.2. Location Privacy

3. The Proposed Scheme

3.1. Overview

3.2. Architecture and Syntax

3.3. Security Definition

3.3.1. Adaptive L -Semantic Secure

3.3.2. Revocation Security

3.4. The Detailed Construction

3.4.1. Initialization

3.4.2. Key Generation

3.4.3. Join

3.4.4. Location Update

3.4.5. Grant

3.4.6. K-Nearest Neighbors Search

3.4.7. Revoke

4. Security Analysis

4.1. Adaptive L -Semantic Secure

4.2. Revocation Secure

5. Theoretical Analysis

6. Implementation

6.1. Storage Analysis

6.2. Communication

6.3. Search Time

6.4. Scalability

7. Conclusions

Author Contributions

Funding

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI

Privacy-Enhancing k-Nearest Neighbors Search over Mobile Social Networks^†

3.3.1. Adaptive $L$ -Semantic Secure

4.1. Adaptive $L$ -Semantic Secure