# SCRHM: A Secure Continuous Remote Health Monitoring System

Authors: Qiuxiang Dong; Zhi Guan; Kunlun Gao; Zhong Chen
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

With the growing need for the remote caring at home and the everincreasing popularity of mobile devices, more and more applications are being developed to enable remote health monitoring. Combining cloud computing with mobile technologies has enabled the healthcare service provider to offer continuous health data collection and physicians to conveniently monitor and assess users’ health while they are at home. However, users’ health data contain highly confidential information, and servers in the cloud are out of users’ trusted domain. Therefore, users may be reluctant to take advantage of remote health monitoring systems before they make sure their data are properly protected. In this paper, we propose a secure continuous remote health monitoring system named SCRHM with the main component, a searchable encryption scheme supporting range searches for remote health monitoring system. With this scheme, remote health monitoring service provider is able to detect outliers over encrypted health parameters. Using analysis, we prove the correctness and security of the proposed scheme on privacy protection of users’ health data. Via simulation experiments, we validate the performance of the proposed scheme in terms of computation and communication overhead.


---

## Body

## 1. Introduction

Background. With the rising of life expectancy and declining birth rates, the proportion of the population above a certain age increases. This phenomenon, known as population aging, is occurring all over the world. The population report [1] indicates that the overall median age in the world rose from 23.5 in 1950 to 28.5 in 2010 and is projected to increase from 29 to 36 years between 2013 and 2050 and to 41 years in 2100. The global share of older people (aged 60 years or over) increased from 9.2% in 1990 to 11.7% in 2013 and will continue to grow as a proportion of the world population, reaching 21.1% by 2050. Globally, 40% of older persons aged 60 years or over live independently, that is, alone or with their spouse only, and this number is projected to increase in the future. These “empty-nest” seniors are vulnerable to helplessness at home when they suffer sudden health problems.The health issues related to the aging population are complex and many health risks may lead serious sequelae and even death. One of the most serious health risks is injuries, particularly those caused by falls, which may lead to postfall syndrome, such as increased dependence, loss of autonomy, confusion, immobilization, and depression. According to [2], within the year following a hip fracture from a fall, 20% of the seniors will die. Nevertheless, if an inventive detection apparatus and compatible reporting system was used, almost 80% of the falls could be quickly determined and medical services would be provided quickly to the injured seniors. The sooner they get medical services, the better they would recover and thus the less likely they would suffer disabilities or death.Chronic medical conditions, such as cardiovascular disease and Parkinson’s disease, are another health killer to seniors. They are responsible for 60% of all deaths worldwide with almost half of chronic disease deaths occurring in people under the age of 70. According to [2], 133 million people live with chronic medical conditions. That number is projected to increase by more than 1% per year by 2030 and reaches 171 million then. It is impossible to completely cure or eliminate chronic diseases and lengthy, expensive treatments involving complex, ongoing care are often required. The global epidemic of chronic disease is an underappreciated cause of poverty and hinders the economic development of many countries (source: World Health Organization (as defined in Wikipedia, the World Health Organization (WHO) is a specialized agency of the United Nations (UN) that is concerned with international public health)). If some vital signs of chronic disease sufferers can be continuously monitored and abnormal medical conditions can be alerted once they occur so that the patients can obtain timely treatment, then some serious sequelae can be avoided. For example, according to American Heart Association [3], $16 billion can be saved per year and 42% rehospitalization could be prevented if adequate patient monitoring, instruction, and education outside hospital could be provided.A 2012 eHealth patient survey by the public relations agency Ruder Finn found that 40% of elder patients want access to technology that can alert physicians and other caregivers if they are having a health emergency [4]. This trend demands an increased focus on preparing a continuous Remote Health Monitoring (RHM for short) system capable of caring for seniors and improving their health and independence for their late life. The recent advances in wireless sensor networks and cloud computing have made it possible to provide remote health monitoring to patients. Patients’ vital signs are collected by the sensors and then forwarded to the RHM service provider. These parameters are checked by the RHM service provider to find odd conditions, deliver medication reminders, and trigger alerts. They may also be stored by the service provider for future long-term analysis or for the physicians to examine them. A fully operable prototype of PERFORM [5], which constantly measures the patient’s symptoms and alerts physicians in case of any outlier based on a system of “wearable” sensors, has been tested in three European hospitals [6]. This tool is really helpful to improve the monitoring of patients with Parkinson disease and allows the physician to be constantly informed about the patient’s clinical state and readjust appropriately the treatment plan. An evidence of the long-term impacts of RHM systems is that IT giant Apple and IT giant Google have participated in the battle. Not only do we have Android Wear up against the Apple Watch in the hardware and sensor stakes, but also there is now the small matter of the underlying platforms powering them: Google Fit versus Apple HealthKit [7].Although RHM services minimize the need for physicians and caregivers and help the chronically ill and the elderly to survive an independent life, users may worry about how the providers make use of the collected data and protection that user data enjoy. In [8], four popular health monitoring services, Fitbit, JawBone, Nike+, and BASIS, were investigated. These service providers offer their service free for buyers of their hardware monitors and require users to register an online account in order to use the wearable devices. All data collected by the devices are uploaded to the provider’s online service. When logging into the account, the users can obtain analysis of the data via a website or smartphone application. All of the four health monitoring services leave user data privacy to serious privacy threats. Health data of users using Fitbit and BASIS may be sold to advertisers or other companies. In which way and by whom the health data are used are out of users’ control. This threatens users privacy very much, since the health data are highly sensitive, especially when they are combined with information from other sources. Even if the service providers claim not to sell users’ data or collect information from other sources, the malicious inside staff or outside attackers may have the root right to the system and thus to the health data.A trivial approach to protecting users data privacy is encryption-before-outsourcing; that is, the users encrypt their health data before uploading them onto the untrusted servers. Encryption reduces security and privacy risks by hiding all information about the plaintext data, but it brings a new problem at the same time; it removes search capabilities from the service providers, resulting in loss of functionality of finding odd conditions. Nevertheless, if the RHM services do not support real-time monitoring and emergency alert, their functional value will be greatly reduced. The elder patients who suffer sudden medical conditions cannot get help at the first moment and RHM seems to turn into simply a data recorder. To address this problem, in this paper, we propose a secure continuous RHM system (SCRHM), which is capable of finding odd health parameters over encrypted user health data uploaded continuously from users’ gateway. After investigating a sample table from [9], we find that almost all the parameters are numerical values and the remaining such as “normal” or “bad” could be encoded into numerical values as well. Therefore, without loss of generality, we assume that all the health parameters are numerical, and the normal values are within given range(s). We design a searchable encryption scheme supporting numerical range searches for remote health monitoring system, in particular, encrypted health data vectors consisting of several numerical fields.Related Works. In what follows, we introduce some related works. Firstly, we introduce secure healthcare services where encryption is utilized to protect health data privacy. Then we introduce searchable encryption used as the tool to enable secure continuous remote health monitoring.Secure Healthcare Services. Combining healthcare with cloud computing draws more and more attentions because of the following three factors: firstly, the growing interest in transforming from paper-based health records to electronic health records (EHRs) [10]; secondly, large storage capacities and heavy burden on storing and managing EHRs [11] (the currently emerging pervasive computing technologies in healthcare [12, 13] will greatly intensify this trend); thirdly, the increasing importance of interorganizational sharing and collaborative use of health data [14]. Narayan et al. [15] propose the use of ciphertext-policy attribute-based encryption (CP-ABE) [16] to ensure that the cloud provider cannot see or copy EHR data. Löhr et al. [17] present a security architecture for establishing privacy domains in e-health infrastructures. Li et al. [18] propose utilizing multiauthority attribute-based encryption to encrypt EHRs so that only authorized users are able to decrypt the ciphertexts. One of the most similar researches as ours is by Li et al. [19]. They establish a scalable framework for authorized private keyword search over encrypted personal health records and propose two novel solutions. Different from ours, their solutions only support keywords searches but not range searches. Thus it is not applicable in continuous remote health monitoring with numerical health parameters. The other similar work is [20]. The authors propose encrypting patients’ health parameters homomorphically and outsourcing to healthcare service provider to compute statistical functions over these data and determine patients’ health risks. Their scheme is capable of finding odd conditions by calculating risk values. It is a two-round protocol since the service provider cannot obtain the result but have to send it back to the patients for decryption. However, homomorphic encryption scheme is not suitable for mobile devices with power and storage constrains in most applications [21]. In continuous remote health monitoring, many encryption and decryption operations are needed, thus leading to heavy computation and communication overhead. Another deficiency of this work is that patients are not allowed to pinpoint which health parameters need monitoring but have to wear all the devices and get all necessary values, or else the collected parameters would be invalid inputs to the evaluation function.Searchable Encryption. Searchable encryption is developed to enable searches over encrypted cloud data [22–24]. There exist several researches on searchable encryption supporting range searches over encrypted data. Boneh and Waters [25] design a predicate encryption, called Hidden Vector Encryption, which can be utilized to construct searchable encryption scheme supporting multidimensional range queries over encrypted data. Shi et al. [26] also propose an encryption scheme to handle multidimensional range queries. Both schemes are in the public-key setting, that is, multiple senders and a single search entity, and are computationally costly for real-world applications. Considering deficiencies of these two schemes, following works mainly focus on efficiency improvement. Lu [27] designs a single dimensional range search scheme (named LSED) on encrypted data in the symmetric-key setting. The author also mentions a direct extension, named LSED+, in the multidimensional setting. However the proposed scheme supporting multidimensional range searches has privacy leakage in single dimension. The recent work [28] proposed by Wang et al. also has the same privacy leakage in single dimension as LSED+. Although the scheme proposed by Wang et al. [29] is secure and more efficient, it is still too computationally costly and only supports small number of dimensions; for example, the maximal dimension size set in the simulation experiments is 6, whereas the health parameters which need monitoring may be few hundreds or more. The time costs of this scheme will be too high to use in practice. In this paper, we construct a searchable encryption scheme for remote health monitoring system.Our Contributions. Our contributions are threefold:(i)
To enable secure monitoring of users’ health conditions, we propose a secure continuous remote health monitoring system, SCRHM. With SCRHM, users encrypt their monitored health parameters and upload the encrypted data to the remote health monitoring service provider without worrying about private information leakage.(ii)
We design a searchable encryption scheme for the RHM system, so that the RHM service provider can perform numerical range searches over the encrypted data without knowing users’ private health data.(iii)
Using analysis, we prove the correctness and security of the proposed searchable encryption scheme and validate the performance of this scheme via simulation experiments.Paper Organization. The rest of the paper is organized as follows. Section 2 describes the problem and the main component of SCRHM system, that is, a searchable encryption scheme supporting range searches for remote health monitoring system. Section 3 provides correctness and security analysis and evaluates the performance of the proposed scheme. Finally, Section 4 concludes the paper.


## 2. Problem Statement and Solution

### 2.1. Problem Statement

In this section, we introduce the system model, system workflow, and adversarial model as well as our design goals. In the part ofSystem Model andSystem Workflow, we describe how sensitive health data are collected and processed in SCRHM. The remote health monitoring service provider and malicious users may collude to pry into the uploaded sensitive data. Their malicious activities and interested sensitive information are presented in the part ofAdversarial Model. To prevent data leakage, as discussed in Section 1, sensitive health data should be encrypted before outsourcing. Traditional encryption schemes such as 3DES (Triple Data Encryption Standard) (http://csrc.nist.gov/publications/fips/fips46-3/fips46-3.pdf) or AES (Advanced Encryption Standard) (http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf) and existing searchable encryption schemes ([22–24], to name a few) are not suitable for secure continuous remote health monitoring. To address this problem, we propose a new searchable encryption scheme supporting range searches in the remote health monitoring system. By incorporating this searchable encryption scheme into the system, SCRHM should achieve the design goals described inDesign Goals. In particular, to protect sensitive health data, SCRHM should prevent service provider and malicious users from getting known of the solutions to the questions shown inAdversarial Model.System Model. The system architecture of SCRHM is depicted as in Figure 1. Note that the authors of [9] propose a novel remote health monitoring system with a similar three-tier architecture as ours; however they do not take secure data processing into consideration. In what follows, we show the functionality of each component in our system.(i)
Health Data Collection. The body area network subsystem consists of body sensors, which are placed in, on, or around a user’s body for continuous monitoring of the user’s physiological conditions such as heart rate, SpO2, and body temperature. The personal area network subsystem is optional and is composed of ambient sensors. These sensors are deployed in the surrounding of a user, so that the environmental conditions of the user’s body such as air temperature, humidity, and brightness can be monitored. Multihop wireless links interconnect the body sensors and the ambient sensors. The gateway, which can be a mobile phone or personal digital assistant, collects the sensory data transmitted from the sensors. In our system, the gateway not only is responsible for collecting sensory data but also generates trapdoors and encrypts the collected health data. All these sensors and the gateway, connected by the multihop wireless links, constitute the health data collection module of the SCRHM system.(ii)
Communication and Networking. The advanced wireless communication technologies, for example, 3G/4G/GSM/GPRS/WiFi, link the gateway to the Internet. In this way, various types of sensory data collected by the health data collection module can be sent to the remote health monitoring service provider.(iii)
Remote Health Monitoring Service Provider (RHMSP). The RHM service provider is responsible for recording and analyzing user health data, which are in the encrypted form in our system. Once health deterioration of a user is detected by the RHM server, it may alert the caregiver or the physician. If a user is identified to be in an emergency, the RHM service provider may trigger an immediate procedure (e.g., informing the emergency contact and/or hospital, or dispatching ambulance directly) to save the user’s life.(iv)
Medical Service Provider. The medical service provider is responsible for providing timely medical assistance when a user is in a health emergency and also performs routine checks of users’ physical conditions to recommend long-time medical treatment.Figure 1
Architecture of the secure continuous RHM system.System Workflow. In what follows, we describe the workflow of the SCRHM system as depicted in Figure 2.(1)
In the system setup phase, each user generates user specific secret key and sends the key to authorized medical service providers. Besides uploading searchable health data ciphertexts, in step(2) the users also upload ciphertexts encrypted under a symmetric encryption scheme. To enable medical service providers to look inside the health data records, users also send the symmetric key to the authorized medical service providers.(2)
Each user creates trapdoor, encrypts the health parameters, and then uploads the trapdoor, encrypted indexes, and encrypted records to RHM service provider. Trapdoor generation is implemented only once when the user registers the RHM service. The indexes are encrypted with our searchable encryption scheme and the records are encrypted with symmetric key encryption scheme, for example, AES or 3DES.(3)
RHMSP stores the uploaded health data records and analyzes whether they are abnormal by implementing theSearch algorithm of our searchable encryption scheme over the encrypted data. According to the search results, RHMSP notifies the medical service providers, including calling ambulance, notifying caregivers, and physicians.(4)
The medical service providers may also want to search interested health records. They generate the corresponding trapdoors and send them to the RHM service provider.(5)
RHMSP runs theSearch2 algorithm of our searchable encryption scheme. The encrypted records satisfying search requirements corresponding to the trapdoors are sent to the medical service providers, who decrypt the ciphertexts with the secret key obtained from the users.Figure 2
Workflow of the secure continuous RHM system.Note that, in this paper, we focus on how to enable the remote health monitoring system to search outliers or data records designated by the medical service provider over encrypted user health data. Access control of the health data records, which is a perpendicular problem of ours in this paper, could be implemented by applying other mechanisms, such as attribute based encryption. We refer interested readers to [15, 16, 18, 30–32] for further information.Adversarial Model. In our system, authorized medical service providers are fully trusted. The RHM service provider is considered as semihonest; that is, it will honestly follow the designated protocol but curiously infer additional private information based on the data available to it. Specifically, the RHM service provider may be interested in the following questions.What is the value of the monitored parameter? Which health parameter of a user is abnormal? And is it below the lower bound or above the upper bound? Do user1 and user2 suffer from the same abnormal health parameters? The above-mentioned information about a user can be sold by the RHM service provider to advertisement companies for profits or other commercial purposes. Some of the RHM service users may be malicious and they may collude with RHMSP to get private information about other users. Therefore our system aims to protect honest users from being attacked by the RHM service provider and malicious users.Design Goals. Our system should satisfy the following requirements:(i)
Functionality. Firstly, RHMSP should be capable of searching over the encrypted health data so that any outliers can be detected at the first moment. Secondly, authorized medical service providers could generate trapdoors to search health data satisfying designated requirements.(ii)
Security. To protect private information about honest users’ health conditions, our system should prevent RHMSP from getting the solutions to the questions mentioned in the adversarial model. In particular, the following security requirements should be met. (1) Confidentiality: the RHM service provider can access the encrypted indexes and the trapdoors. Therefore, we should guarantee that RHMSP will not learn private information from them. Firstly, the encrypted indexes should not leak any information about the users’ health parameters. This aims to protect confidentiality of users’ monitored parameters. Secondly, the trapdoor generation algorithm should guarantee that any information about the health parameter encrypted in the trapdoor will not be leaked. If this information is known by the RHM service provider, it can get private information about the encrypted parameters through running the search algorithm. (2) Single parameter privacy: the service provider should be prevented from getting known of the mapping between the trapdoors (uploaded by the users) and the parameters and whether the abnormal parameters are higher or lower than the normal values. (3) Trapdoor uniqueness: trapdoors generated with one user’s secret key should not be used to search the other users’ encrypted indexes. This security requirement prevents the RHMSP from getting known whether two users suffer from the same abnormal health parameters or guessing the exact parameter values through a divide-and-conquer or brute-force approach with the help of malicious users.(iii)
Efficiency. SCRHM is required to achieve both computation and communication efficiency. Specifically, trapdoor generation, data encryption, and search over the encrypted data should be efficient and the size of the trapdoors and the encrypted indexes should be suitable for applications in practice.


### 2.2. Preliminaries

The encryption scheme we adopt to construct searchable index and trapdoor is extended from theAsymmetric Scalar-Product Preserving Encryption (ASPE) scheme, which is proposed in [33] for efficient secure nearest neighbor search on the cloud. It is also utilized by the authors of [34] to enable searches over encrypted data.Suppose thatP1 and P2 are two data points and Q is a query point in an Euclidean space. If P1, P2, and Q are encrypted by ASPE, then a third party will not learn the values of the points and the query. But it can still determine whether P1 is closer to Q than P2. The secret key consists of a (d+1)-bit binary vector as S and two (d+1)×(d+1) invertible matrices as {M1,M2}, where d is the number of dimensions for each data point P. First, every data vector P and query vector Q are extended to a (d+1)-dimension vector as P¯ and Q^, where the (d+1)-dimension is set to -0.5P2 and 1, respectively. Besides, the query vector Q^ is scaled by a random number r>0 as (rQ,r). Then P¯ is split into two random vectors as {Pa,Pb}, and Q^ is also split into two random vectors as {Qa,Qb} with S as a splitting indicator. That is, if the jth bit of S is 0, then Pa[j] and Pb[j] are the same as P¯[j], while Qa and Qb are set to two random numbers so that their sum is equal to Q^[j]; if the jth bit of S is 1, the splitting process is similar except that P¯ and Q^ are switched. The split data vector pair {Pa,Pb} is encrypted as [(M1TPa)T,(M2TPb)T]T, and the split query vector pair {Qa,Qb} is encrypted as [(M1-1Qa)T,(M2-1Qb)T]T.In the query step, the product of[PaT,PbT]T and [QaT,QbT]T, that is, -0.5r(P2-2P·Q), is serving as the indicator of Euclidean distance between P and Q. Wong et al. [33] show that the security of ASPE is roughly equal to a symmetric encryption scheme with d-bit key. In the following we briefly discuss the correctness of the protocol. The full proof of correctness and security of the ASPE scheme can be found in [33]:Fact 1
(1)
P
¯
⊙
Q
^
=
P
a
⊙
Q
a
+
P
b
⊙
Q
b
.Fact 2
(2)
P
¯
1
-
P
¯
2
⊙
Q
^
=
0.5
r
d
2
P
2
,
Q
-
d
2
P
1
,
Q
,where ⊙ denotes inner product of two vectors and function d measures the Euclidean distance between two points. Based on the two facts above, we have(3)
M
1
T
P
1
a
T
,
M
2
T
P
1
b
T
T
-
M
1
T
P
2
a
T
,
M
2
T
P
2
b
T
T
⊙
M
1
-
1
Q
a
T
,
M
2
-
1
Q
b
T
T
=
M
1
T
P
1
a
T
,
M
2
T
P
1
b
T
T
-
M
1
T
P
2
a
T
,
M
2
T
P
2
b
T
T
T
·
M
1
-
1
Q
a
T
,
M
2
-
1
Q
b
T
T
=
P
1
a
T
,
P
1
b
T
T
-
P
2
a
T
,
P
2
b
T
T
⊙
Q
a
T
,
Q
b
T
T
=
P
¯
1
-
P
¯
2
⊙
Q
^
=
0.5
r
d
2
P
2
,
Q
-
d
2
P
1
,
Q
.Therefore,0.5r(d2(P2,Q)-d2(P1,Q))>0⇔d2(P2,Q)>d2(P1,Q). Without learning the values of the points and the query, we can determine whether P1 is closer to Q than P2.The notations we use in the remaining of this paper are listed as follows:(i)
κ—it is an integer and denotes the security parameter.(ii)
v[i]—it denotes the ith element of a vector v.(iii)
v1+v2—v1 and v2 are vectors; the jth element of v1+v2 is v1[j]+v2[j].(iv)
U—it denotes the service user collection; a set of N users U={U1,U2,…,UN}.(v)
L, H—the lower bound set is denoted as L={L1,L2,…,Lm} and the upper bound set is denoted as H={H1,H2,…,Hm}.(vi)
I—the encrypted index set is stored on the RHM server. Element Iȷ∈I is the encrypted index corresponding to user Uȷ’s health data.(vii)
MT and M-1—MT is the transpose matrix of matrix M and M-1 is the inverse matrix of matrix M.


### 2.3. The Proposed Searchable Encryption Scheme

By extending thekNN computation scheme, we propose a searchable encryption scheme for continuous health monitoring system consisting of the following algorithms.(i) Setup
(
κ
,
m
). If the health data dimension m is smaller than κ, extra dummy fields can be added; therefore, in what follows, without loss of generality, we assume m≥κ.The gateway of userUȷ generates a secret key (4)SK=Sȷ,Mȷ,Mȷ′,where Sȷ is an m+1-dimensional binary vector and Mȷ, Mȷ′ are both (m+1)×(m+1) invertible matrices. SK is sent to the authorized medical service providers trusted by user Uȷ.(ii) GenIndex
(
S
ȷ
,
M
ȷ
,
M
ȷ
′
,
P
ȷ
). After collecting sensory data, the gateway creates an m-dimensional health data vector Pȷ. Then the health data vector Pȷ is encrypted by the gateway with the ASPE scheme in the following way.ExtendPȷ to Pȷ¯=r(PȷT,1)T, where r is a positive random number. Generate (Pȷa,Pȷb) such that(i)
ifSȷ[i]=1, set Pȷa[i]=Pȷb[i]=Pȷ¯[i];(ii)
ifSȷ[i]=0, set Pȷa[i]=σi and Pȷb[i]=Pȷ¯[i]-σi, where σi is a random number.The encrypted index for Pȷ is Iȷ=[(Mȷ-1Pȷa)T,(Mȷ′-1Pȷb)T]T.(iii) GenTrapdoor
(
S
ȷ
,
M
ȷ
,
M
ȷ
′
,
L
,
H
). When registering the RMH service, the user generates trapdoors for the RHM server so that the server can search over the encrypted health data in the future. The gateway creates two m-dimensional vectors for each value in L and H. In particular, for α=Lλ∈L, the vectors are constructed according to (5), and for α=Hλ∈H, the vectors are created according to (6). One has(5)Qȷλ1=γ1,γ2,…,γλ-1,α-s,γλ+1,…,γm,Qȷλ2=γ1,γ2,…,γλ-1,α+s,γλ+1,…,γm,(6)Qȷλ1=γ1,γ2,…,γλ-1,α+s,γλ+1,…,γm,Qȷλ2=γ1,γ2,…,γλ-1,α-s,γλ+1,…,γm,where s and γi (i=1,2,…,λ-1,λ+1,…,m) are randomly chosen private positive numbers. Then Qȷλ1 and Qȷλ2 are encrypted by an encryption function E, which proceeds as follows.LetQ be an m-dimensional vector. Extend Q to Q^=(QT,-0.5Q2)T. Create (Qa,Qb) such that(i)
ifSȷ[i]=0, set Qa[i]=Qb[i]=Q^[i];(ii)
ifSȷ[i]=1, set Qa[i]=ρi, and Qb[i]=Q^[i]-ρi, where ρi is a random number. The encryption of Q is E(Q)=[(MȷTQa)T,(Mȷ′TQb)T]T. The trapdoor for the λth parameter is (7)TQȷλL=TQȷλ1=EQȷλ1,TQȷλ2=EQȷλ2,where Qȷλ1 and  Qȷλ2 are  set  as  in (5);(8)TQȷλH=TQȷλ1=EQȷλ1,TQȷλ2=EQȷλ2,where Qȷλ1 and Qȷλ2 are  set  as  in (6).The gateway randomly permutes the2m trapdoors and sends the trapdoors to the RHM service provider(9)TQȷ=TQȷ1,TQȷ2,…,TQȷm,TQȷm+1,…,TQȷ2m=TQȷλL,TQȷλH∣λ=1,2,…,m.(iv) GenTrapdoor2
(
S
,
M
,
M
′
,
α
,
o
p
). The medical service provider may want to search interested health data, for example, health data records with the λth parameter greater or smaller than α. First generate the following two vectors:(i)
whenop is “≤”, that is, search records with the λth parameter greater than α,(10)Q1=γ1,γ2,…,γλ-1,α-s,γλ+1,…,γm,Q2=γ1,γ2,…,γλ-1,α+s,γλ+1,…,γm,(ii)
whenop is “≥”, that is, search records with the λth parameter smaller than α,(11)Q1=γ1,γ2,…,γλ-1,α+s,γλ+1,…,γm,Q2=γ1,γ2,…,γλ-1,α-s,γλ+1,…,γm,where s and γi (i=1,2,…,λ-1,λ+1,…,m) are randomly chosen private positive numbers. Set token TQ as TQ=(TQ[1],TQ[2]), with TQ[1]=E(Q1) and TQ[2]=E(Q2), where E(·) is the encryption function, the same as in the algorithmGenTrapdoor but with the secret key of a specific user Uȷ, denoted by (S,M,M′), as the encryption key.(v) Search
(
T
Q
ȷ
,
I
ȷ
). For user Uȷ, the remote health monitoring service provider calculates (TQȷi[1]-TQȷi[2])·Iȷ. The server gets the comparison results according to the following equations: (12)TQȷi1-TQȷi2⊙Iȷ≤01≤i≤2m.For α=Lλ∈L, (TQȷi[1]-TQȷi[2])⊙Iȷ≤0 means that the λth parameter is greater than or equal to α, while for α=Hλ∈H, this equation indicates that the λth parameter is smaller than or equal to α. If for any i∈{1,2,…,2m}, this equation does not hold, that is, some health parameter is out of the range of [Lλ,Hλ], then the RHM service provider would notify the medical service provider. When uploading the trapdoors the users may attach emergency tags on some vital health parameters, so that when RHMSP detects these parameters abnormal, direct help from the health center can be provided to the patients.(vi) Search2
(
T
Q
,
I
,
ȷ
). This search algorithm is run when RHMSP receives search requests from the medical service provider. Note that the medical service provider can only search over the encrypted health data, whose owner permits it to search over the encrypted data; that is, it sends the user specific secret key to it. The RHM service provider sends the records satisfying the search request to the medical service provider according to the following equation: (13)TQ1-TQ2⊙Iȷ≤0,Iȷ∈I.


## 2.1. Problem Statement

In this section, we introduce the system model, system workflow, and adversarial model as well as our design goals. In the part ofSystem Model andSystem Workflow, we describe how sensitive health data are collected and processed in SCRHM. The remote health monitoring service provider and malicious users may collude to pry into the uploaded sensitive data. Their malicious activities and interested sensitive information are presented in the part ofAdversarial Model. To prevent data leakage, as discussed in Section 1, sensitive health data should be encrypted before outsourcing. Traditional encryption schemes such as 3DES (Triple Data Encryption Standard) (http://csrc.nist.gov/publications/fips/fips46-3/fips46-3.pdf) or AES (Advanced Encryption Standard) (http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf) and existing searchable encryption schemes ([22–24], to name a few) are not suitable for secure continuous remote health monitoring. To address this problem, we propose a new searchable encryption scheme supporting range searches in the remote health monitoring system. By incorporating this searchable encryption scheme into the system, SCRHM should achieve the design goals described inDesign Goals. In particular, to protect sensitive health data, SCRHM should prevent service provider and malicious users from getting known of the solutions to the questions shown inAdversarial Model.System Model. The system architecture of SCRHM is depicted as in Figure 1. Note that the authors of [9] propose a novel remote health monitoring system with a similar three-tier architecture as ours; however they do not take secure data processing into consideration. In what follows, we show the functionality of each component in our system.(i)
Health Data Collection. The body area network subsystem consists of body sensors, which are placed in, on, or around a user’s body for continuous monitoring of the user’s physiological conditions such as heart rate, SpO2, and body temperature. The personal area network subsystem is optional and is composed of ambient sensors. These sensors are deployed in the surrounding of a user, so that the environmental conditions of the user’s body such as air temperature, humidity, and brightness can be monitored. Multihop wireless links interconnect the body sensors and the ambient sensors. The gateway, which can be a mobile phone or personal digital assistant, collects the sensory data transmitted from the sensors. In our system, the gateway not only is responsible for collecting sensory data but also generates trapdoors and encrypts the collected health data. All these sensors and the gateway, connected by the multihop wireless links, constitute the health data collection module of the SCRHM system.(ii)
Communication and Networking. The advanced wireless communication technologies, for example, 3G/4G/GSM/GPRS/WiFi, link the gateway to the Internet. In this way, various types of sensory data collected by the health data collection module can be sent to the remote health monitoring service provider.(iii)
Remote Health Monitoring Service Provider (RHMSP). The RHM service provider is responsible for recording and analyzing user health data, which are in the encrypted form in our system. Once health deterioration of a user is detected by the RHM server, it may alert the caregiver or the physician. If a user is identified to be in an emergency, the RHM service provider may trigger an immediate procedure (e.g., informing the emergency contact and/or hospital, or dispatching ambulance directly) to save the user’s life.(iv)
Medical Service Provider. The medical service provider is responsible for providing timely medical assistance when a user is in a health emergency and also performs routine checks of users’ physical conditions to recommend long-time medical treatment.Figure 1
Architecture of the secure continuous RHM system.System Workflow. In what follows, we describe the workflow of the SCRHM system as depicted in Figure 2.(1)
In the system setup phase, each user generates user specific secret key and sends the key to authorized medical service providers. Besides uploading searchable health data ciphertexts, in step(2) the users also upload ciphertexts encrypted under a symmetric encryption scheme. To enable medical service providers to look inside the health data records, users also send the symmetric key to the authorized medical service providers.(2)
Each user creates trapdoor, encrypts the health parameters, and then uploads the trapdoor, encrypted indexes, and encrypted records to RHM service provider. Trapdoor generation is implemented only once when the user registers the RHM service. The indexes are encrypted with our searchable encryption scheme and the records are encrypted with symmetric key encryption scheme, for example, AES or 3DES.(3)
RHMSP stores the uploaded health data records and analyzes whether they are abnormal by implementing theSearch algorithm of our searchable encryption scheme over the encrypted data. According to the search results, RHMSP notifies the medical service providers, including calling ambulance, notifying caregivers, and physicians.(4)
The medical service providers may also want to search interested health records. They generate the corresponding trapdoors and send them to the RHM service provider.(5)
RHMSP runs theSearch2 algorithm of our searchable encryption scheme. The encrypted records satisfying search requirements corresponding to the trapdoors are sent to the medical service providers, who decrypt the ciphertexts with the secret key obtained from the users.Figure 2
Workflow of the secure continuous RHM system.Note that, in this paper, we focus on how to enable the remote health monitoring system to search outliers or data records designated by the medical service provider over encrypted user health data. Access control of the health data records, which is a perpendicular problem of ours in this paper, could be implemented by applying other mechanisms, such as attribute based encryption. We refer interested readers to [15, 16, 18, 30–32] for further information.Adversarial Model. In our system, authorized medical service providers are fully trusted. The RHM service provider is considered as semihonest; that is, it will honestly follow the designated protocol but curiously infer additional private information based on the data available to it. Specifically, the RHM service provider may be interested in the following questions.What is the value of the monitored parameter? Which health parameter of a user is abnormal? And is it below the lower bound or above the upper bound? Do user1 and user2 suffer from the same abnormal health parameters? The above-mentioned information about a user can be sold by the RHM service provider to advertisement companies for profits or other commercial purposes. Some of the RHM service users may be malicious and they may collude with RHMSP to get private information about other users. Therefore our system aims to protect honest users from being attacked by the RHM service provider and malicious users.Design Goals. Our system should satisfy the following requirements:(i)
Functionality. Firstly, RHMSP should be capable of searching over the encrypted health data so that any outliers can be detected at the first moment. Secondly, authorized medical service providers could generate trapdoors to search health data satisfying designated requirements.(ii)
Security. To protect private information about honest users’ health conditions, our system should prevent RHMSP from getting the solutions to the questions mentioned in the adversarial model. In particular, the following security requirements should be met. (1) Confidentiality: the RHM service provider can access the encrypted indexes and the trapdoors. Therefore, we should guarantee that RHMSP will not learn private information from them. Firstly, the encrypted indexes should not leak any information about the users’ health parameters. This aims to protect confidentiality of users’ monitored parameters. Secondly, the trapdoor generation algorithm should guarantee that any information about the health parameter encrypted in the trapdoor will not be leaked. If this information is known by the RHM service provider, it can get private information about the encrypted parameters through running the search algorithm. (2) Single parameter privacy: the service provider should be prevented from getting known of the mapping between the trapdoors (uploaded by the users) and the parameters and whether the abnormal parameters are higher or lower than the normal values. (3) Trapdoor uniqueness: trapdoors generated with one user’s secret key should not be used to search the other users’ encrypted indexes. This security requirement prevents the RHMSP from getting known whether two users suffer from the same abnormal health parameters or guessing the exact parameter values through a divide-and-conquer or brute-force approach with the help of malicious users.(iii)
Efficiency. SCRHM is required to achieve both computation and communication efficiency. Specifically, trapdoor generation, data encryption, and search over the encrypted data should be efficient and the size of the trapdoors and the encrypted indexes should be suitable for applications in practice.


## 2.2. Preliminaries

The encryption scheme we adopt to construct searchable index and trapdoor is extended from theAsymmetric Scalar-Product Preserving Encryption (ASPE) scheme, which is proposed in [33] for efficient secure nearest neighbor search on the cloud. It is also utilized by the authors of [34] to enable searches over encrypted data.Suppose thatP1 and P2 are two data points and Q is a query point in an Euclidean space. If P1, P2, and Q are encrypted by ASPE, then a third party will not learn the values of the points and the query. But it can still determine whether P1 is closer to Q than P2. The secret key consists of a (d+1)-bit binary vector as S and two (d+1)×(d+1) invertible matrices as {M1,M2}, where d is the number of dimensions for each data point P. First, every data vector P and query vector Q are extended to a (d+1)-dimension vector as P¯ and Q^, where the (d+1)-dimension is set to -0.5P2 and 1, respectively. Besides, the query vector Q^ is scaled by a random number r>0 as (rQ,r). Then P¯ is split into two random vectors as {Pa,Pb}, and Q^ is also split into two random vectors as {Qa,Qb} with S as a splitting indicator. That is, if the jth bit of S is 0, then Pa[j] and Pb[j] are the same as P¯[j], while Qa and Qb are set to two random numbers so that their sum is equal to Q^[j]; if the jth bit of S is 1, the splitting process is similar except that P¯ and Q^ are switched. The split data vector pair {Pa,Pb} is encrypted as [(M1TPa)T,(M2TPb)T]T, and the split query vector pair {Qa,Qb} is encrypted as [(M1-1Qa)T,(M2-1Qb)T]T.In the query step, the product of[PaT,PbT]T and [QaT,QbT]T, that is, -0.5r(P2-2P·Q), is serving as the indicator of Euclidean distance between P and Q. Wong et al. [33] show that the security of ASPE is roughly equal to a symmetric encryption scheme with d-bit key. In the following we briefly discuss the correctness of the protocol. The full proof of correctness and security of the ASPE scheme can be found in [33]:Fact 1
(1)
P
¯
⊙
Q
^
=
P
a
⊙
Q
a
+
P
b
⊙
Q
b
.Fact 2
(2)
P
¯
1
-
P
¯
2
⊙
Q
^
=
0.5
r
d
2
P
2
,
Q
-
d
2
P
1
,
Q
,where ⊙ denotes inner product of two vectors and function d measures the Euclidean distance between two points. Based on the two facts above, we have(3)
M
1
T
P
1
a
T
,
M
2
T
P
1
b
T
T
-
M
1
T
P
2
a
T
,
M
2
T
P
2
b
T
T
⊙
M
1
-
1
Q
a
T
,
M
2
-
1
Q
b
T
T
=
M
1
T
P
1
a
T
,
M
2
T
P
1
b
T
T
-
M
1
T
P
2
a
T
,
M
2
T
P
2
b
T
T
T
·
M
1
-
1
Q
a
T
,
M
2
-
1
Q
b
T
T
=
P
1
a
T
,
P
1
b
T
T
-
P
2
a
T
,
P
2
b
T
T
⊙
Q
a
T
,
Q
b
T
T
=
P
¯
1
-
P
¯
2
⊙
Q
^
=
0.5
r
d
2
P
2
,
Q
-
d
2
P
1
,
Q
.Therefore,0.5r(d2(P2,Q)-d2(P1,Q))>0⇔d2(P2,Q)>d2(P1,Q). Without learning the values of the points and the query, we can determine whether P1 is closer to Q than P2.The notations we use in the remaining of this paper are listed as follows:(i)
κ—it is an integer and denotes the security parameter.(ii)
v[i]—it denotes the ith element of a vector v.(iii)
v1+v2—v1 and v2 are vectors; the jth element of v1+v2 is v1[j]+v2[j].(iv)
U—it denotes the service user collection; a set of N users U={U1,U2,…,UN}.(v)
L, H—the lower bound set is denoted as L={L1,L2,…,Lm} and the upper bound set is denoted as H={H1,H2,…,Hm}.(vi)
I—the encrypted index set is stored on the RHM server. Element Iȷ∈I is the encrypted index corresponding to user Uȷ’s health data.(vii)
MT and M-1—MT is the transpose matrix of matrix M and M-1 is the inverse matrix of matrix M.


## 2.3. The Proposed Searchable Encryption Scheme

By extending thekNN computation scheme, we propose a searchable encryption scheme for continuous health monitoring system consisting of the following algorithms.(i) Setup
(
κ
,
m
). If the health data dimension m is smaller than κ, extra dummy fields can be added; therefore, in what follows, without loss of generality, we assume m≥κ.The gateway of userUȷ generates a secret key (4)SK=Sȷ,Mȷ,Mȷ′,where Sȷ is an m+1-dimensional binary vector and Mȷ, Mȷ′ are both (m+1)×(m+1) invertible matrices. SK is sent to the authorized medical service providers trusted by user Uȷ.(ii) GenIndex
(
S
ȷ
,
M
ȷ
,
M
ȷ
′
,
P
ȷ
). After collecting sensory data, the gateway creates an m-dimensional health data vector Pȷ. Then the health data vector Pȷ is encrypted by the gateway with the ASPE scheme in the following way.ExtendPȷ to Pȷ¯=r(PȷT,1)T, where r is a positive random number. Generate (Pȷa,Pȷb) such that(i)
ifSȷ[i]=1, set Pȷa[i]=Pȷb[i]=Pȷ¯[i];(ii)
ifSȷ[i]=0, set Pȷa[i]=σi and Pȷb[i]=Pȷ¯[i]-σi, where σi is a random number.The encrypted index for Pȷ is Iȷ=[(Mȷ-1Pȷa)T,(Mȷ′-1Pȷb)T]T.(iii) GenTrapdoor
(
S
ȷ
,
M
ȷ
,
M
ȷ
′
,
L
,
H
). When registering the RMH service, the user generates trapdoors for the RHM server so that the server can search over the encrypted health data in the future. The gateway creates two m-dimensional vectors for each value in L and H. In particular, for α=Lλ∈L, the vectors are constructed according to (5), and for α=Hλ∈H, the vectors are created according to (6). One has(5)Qȷλ1=γ1,γ2,…,γλ-1,α-s,γλ+1,…,γm,Qȷλ2=γ1,γ2,…,γλ-1,α+s,γλ+1,…,γm,(6)Qȷλ1=γ1,γ2,…,γλ-1,α+s,γλ+1,…,γm,Qȷλ2=γ1,γ2,…,γλ-1,α-s,γλ+1,…,γm,where s and γi (i=1,2,…,λ-1,λ+1,…,m) are randomly chosen private positive numbers. Then Qȷλ1 and Qȷλ2 are encrypted by an encryption function E, which proceeds as follows.LetQ be an m-dimensional vector. Extend Q to Q^=(QT,-0.5Q2)T. Create (Qa,Qb) such that(i)
ifSȷ[i]=0, set Qa[i]=Qb[i]=Q^[i];(ii)
ifSȷ[i]=1, set Qa[i]=ρi, and Qb[i]=Q^[i]-ρi, where ρi is a random number. The encryption of Q is E(Q)=[(MȷTQa)T,(Mȷ′TQb)T]T. The trapdoor for the λth parameter is (7)TQȷλL=TQȷλ1=EQȷλ1,TQȷλ2=EQȷλ2,where Qȷλ1 and  Qȷλ2 are  set  as  in (5);(8)TQȷλH=TQȷλ1=EQȷλ1,TQȷλ2=EQȷλ2,where Qȷλ1 and Qȷλ2 are  set  as  in (6).The gateway randomly permutes the2m trapdoors and sends the trapdoors to the RHM service provider(9)TQȷ=TQȷ1,TQȷ2,…,TQȷm,TQȷm+1,…,TQȷ2m=TQȷλL,TQȷλH∣λ=1,2,…,m.(iv) GenTrapdoor2
(
S
,
M
,
M
′
,
α
,
o
p
). The medical service provider may want to search interested health data, for example, health data records with the λth parameter greater or smaller than α. First generate the following two vectors:(i)
whenop is “≤”, that is, search records with the λth parameter greater than α,(10)Q1=γ1,γ2,…,γλ-1,α-s,γλ+1,…,γm,Q2=γ1,γ2,…,γλ-1,α+s,γλ+1,…,γm,(ii)
whenop is “≥”, that is, search records with the λth parameter smaller than α,(11)Q1=γ1,γ2,…,γλ-1,α+s,γλ+1,…,γm,Q2=γ1,γ2,…,γλ-1,α-s,γλ+1,…,γm,where s and γi (i=1,2,…,λ-1,λ+1,…,m) are randomly chosen private positive numbers. Set token TQ as TQ=(TQ[1],TQ[2]), with TQ[1]=E(Q1) and TQ[2]=E(Q2), where E(·) is the encryption function, the same as in the algorithmGenTrapdoor but with the secret key of a specific user Uȷ, denoted by (S,M,M′), as the encryption key.(v) Search
(
T
Q
ȷ
,
I
ȷ
). For user Uȷ, the remote health monitoring service provider calculates (TQȷi[1]-TQȷi[2])·Iȷ. The server gets the comparison results according to the following equations: (12)TQȷi1-TQȷi2⊙Iȷ≤01≤i≤2m.For α=Lλ∈L, (TQȷi[1]-TQȷi[2])⊙Iȷ≤0 means that the λth parameter is greater than or equal to α, while for α=Hλ∈H, this equation indicates that the λth parameter is smaller than or equal to α. If for any i∈{1,2,…,2m}, this equation does not hold, that is, some health parameter is out of the range of [Lλ,Hλ], then the RHM service provider would notify the medical service provider. When uploading the trapdoors the users may attach emergency tags on some vital health parameters, so that when RHMSP detects these parameters abnormal, direct help from the health center can be provided to the patients.(vi) Search2
(
T
Q
,
I
,
ȷ
). This search algorithm is run when RHMSP receives search requests from the medical service provider. Note that the medical service provider can only search over the encrypted health data, whose owner permits it to search over the encrypted data; that is, it sends the user specific secret key to it. The RHM service provider sends the records satisfying the search request to the medical service provider according to the following equation: (13)TQ1-TQ2⊙Iȷ≤0,Iȷ∈I.


## 3. System Evaluation

In Section2.3, we construct a searchable encryption scheme for continuous health monitoring system. In the following, we first prove that it achieves the functionality goal and the security goal. On the one hand, the service provider is able to find odd conditions over the encrypted data. In particular, on the other hand, the searchable encryption scheme ensures that curious service provider or malicious users would not get known of private information about honest users’ sensitive health data, thus protecting user privacy. Then, through simulation experiments, we evaluate system performance in terms of computation and communication overhead.


### 3.1. Correctness Analysis

In the following, we briefly discuss the correctness of the proposed searchable encryption scheme on the basis of the correctness proof of the ASPE scheme shown in Section2.2. We prove the correctness of GenTrapdoor2(·) and Search2(·), and it is easy to prove the correctness of the other trapdoor generation and search algorithm designed for supporting detection of outliers over the encrypted health data in the same way.In vectorQ1 and Q2, except for the values on the λth position, all the others are the same. Therefore, when the operation is “≤” we have(14)TQ1-TQ2⊙Iȷ=Q1aT,Q1bTT-Q2aT,Q2bTT⊙PȷaT,PȷbTT=Q1^-Q2^⊙Pȷ¯=0.5rd2Q2,Pȷ-d2Q1,Pȷ=2rsα-Pȷλ.When the operation is “≥” we have(15)TQ1-TQ2⊙Iȷ=Q1aT,Q1bTT-Q2aT,Q2bTT⊙PȷaT,PȷbTT=Q1^-Q2^⊙Pȷ¯=0.5rd2Q2,Pȷ-d2Q1,Pȷ=2rsPȷλ-α.Furthermore, r and s are positive numbers; therefore it is easy to verify that(16)2rsα-Pȷλ≤0,iffα≤Pȷλ,2rsPȷλ-α≤0,iffα≥Pȷλ.Therefore, SCRHM, which aims to perform range searches over the encrypted health data, can accomplish the claimed functionality correctly.


### 3.2. Security Analysis

In what follows, we prove that our system satisfies the three proposed security requirements, that is, confidentiality, single parameter privacy, and trapdoor uniqueness.Confidentiality. The privacy protection of searchable indexes and trapdoors is based on the security of the ASPE scheme. On the security of this scheme, Wong et al. claim that it can guard against any attacks based on the knowledge of a number of (plaintext, ciphertext) pairs, and their argument is as follows [33]. If the boolean vector S is known to the adversary, then he/she would be able to use the known (plaintext, ciphertext) pairs to construct linear equations about M1 and M2 and then solve the equations to obtain M1 and M2. However, since S is secret, it would be hard for the adversary to derive the correct linear equations to use, since the formulation of the equations depends on S. A brute-force approach would require the adversary to examine all possible bit vector S, which leads to 2S linear equation systems that cannot be solved in reasonable time when S is large. That is, the RHM service providers are unable to obtain the matrices Mȷ and Mȷ′ of a honest user Uȷ. Therefore, the encrypted index [(Mȷ-1Pȷa)T,(Mȷ′-1Pȷb)T]T will not leak private information of data vector Pȷ. The trapdoors will keep the confidentiality of the corresponding λth searched health parameter as well.However Yao et al. [35] propose a chosen plaintext attack that can recover the data point not by solving the aforementioned linear equations. Their attack is as follows [35]. Assume that the server obtains d query points and their corresponding ciphertexts (by asking the oracle in the chosen plaintext attack model). For each Q of those query points, the server would have two encrypted points Qa and Qb generated by the query point encryption function. The ASPE scheme ensures that dot product between Q and any data point P can be calculated based on the following equation: P·Q=Pa·Qa+Pb·Qb. Notice that the above equation contains only d variables unknown to the adversary, that is, the d fields of the data point P. Since the adversary has the (plaintext, ciphertext) pair of d query points, he can construct d linear equations to derive all the fields of P. Therefore, the ASPE scheme is prone to chosen plaintext attack and this attack still works if data point is encrypted by the query point encryption function, and the query point is encrypted with the data point encryption function, which is the case in our scheme.Fortunately, this attack will not affect the security of our proposed scheme. The most important part in the above mentioned attack is that the adversary knows the plaintext, whereas, in our scheme, even if the adversary is allowed to access the trapdoor generation oracle, he is unable to obtain the plaintext. For example, the adversary’s query is denoted byQ, according to the trapdoor generation algorithm in our scheme; the adversary will get the ciphertexts E(Q1) and E(Q2) (or E(Qȷλ1) and E(Qȷλ2)), where Q1 and Q2 (or Qȷλ1 and Qȷλ2) are two random vectors which are only known by the honest user Uȷ and fully trusted authorized medical service providers but unknown to neither the RHM service provider nor malicious users. Therefore, the adversary cannot implement the chosen plaintext attack in our scheme. The adversary is only able to obtain the private information within the encrypted indexes and trapdoors by implementing brute force search, whereas brute force search is computationally infeasible when the number of dimensions is greater than 80 [33].Single Parameter Privacy. Trapdoor generation is a randomized algorithm. For each value α∈L∪H, two random vectors Q1 (or Qȷλ1) and Q2 (or Qȷλ2) are generated and both of them are randomly split into two vectors which are then multiplied by two secret matrices Mȷ and Mȷ′. That is, the trapdoors are indistinguishable from random vectors. After the user randomly permutes the 2m trapdoors before uploading them to RHSMP, it is impossible to establish a mapping between the parameters and the trapdoors since all the 2m trapdoors are random and indistinguishable from each other. For lower bound and upper bound, the trapdoor generation phase is different, so that in the search phase, the criteria of whether the values are abnormal or not are the same, that is, whether (TQ[1]-TQ[2])⊙Iȷ≤0 holds or not. As a result, even if RHMSP finds that a certain health data record is an outlier, it will not get known of which parameter is abnormal and whether it is greater than the upper bound or smaller than the lower bound, thus protecting single parameter privacy proposed in our security requirements.Trapdoor Uniqueness. From the above confidentiality analysis, we know that even if the RHM service provider colludes with malicious users, the private information in the indexes and trapdoors cannot be recovered; however we omit some other possible approaches. That is, if the trapdoors generated by the honest users or medical service provider can be used to search the encrypted indexes by the malicious users or vise verse, then the malicious users can recover the values in a divide-and-conquer or brute-force way. For example, if the trapdoors generated by a malicious user A can be used to search a honest user B’s encrypted indexes, then A generates trapdoors for all possible values of a specific health parameter with the algorithmGenTrapdoor2 and runs the search algorithmSearch2 over the encrypted indexes; if the equation (TQ[1]-TQ[2])⊙Iȷ=0 holds for a certain trapdoor, then A can get known that the encrypted health parameter equals to the value α encrypted by this trapdoor. The malicious users can recover the value encrypted in the honest users’ or medical service providers’ trapdoors in a similar way by generating encrypted indexes for all possible values and running theSearch2 algorithm with these encrypted indexes and the trapdoors as inputs. Therefore it is of great importance that the trapdoor is unique; that is, the trapdoor generated by user A can only be used to search the encrypted indexes generated by him/herself but not other users. Fortunately, our scheme satisfies this property since when using different user specific secret key to generate the encrypted indexes and trapdoors, Fact 1 and Fact 2 in Section 2.2 do not hold. When trapdoor generated by malicious user A is used for searching over honest user B’s encrypted indexes, ([(MATQ1a)T,(MA′TQ1b)T]T-[(MATQ2a)T,(MA′TQ2b)T]T)⊙[(MB-1Pa)T,(MB-1Pb)T]T (MA, MA′ are user A’s secret key and MB, MB′ are user B’s secret key) will be a random value, which does not leak any information about the honest user B’s encrypted indexes. In a similar way, we can prove that A cannot get private information of B’s trapdoors. Therefore, trapdoor uniqueness required in our design goals is satisfied in our scheme.From analysis above, we can conclude that our scheme is secure in terms of the three security requirements proposed in Section2.1.


### 3.3. Performance Evaluation

In this section, we run simulation experiments to evaluate the performance of the proposed scheme in terms of computation and communication overhead. All the data vectors used in our experiments below are generated randomly.Computation Overhead. The computations are performed on a 1.4 GHz MAC OS X Yosemite system. All the data reported below are averaged over 100 randomized runs. Time costs of the algorithms are evaluated with varied size of parameters and users. We set the number of parameters to be four different values: 80, 120, 160, and 200. On the one hand, the size is set to be greater than 80 for guaranteeing the security property of the ASPE scheme; on the other hand, 200 parameters are enough for remote health monitoring systems in practice. As for user numbers, we choose 10000, 50000, 100000, 150000, and 200000 to evaluate system performance. Algorithms running on the remote health monitoring server can be parallelized; therefore computation efficiency can be further improved.Time for Generating Index and Trapdoors. In what follows, we consider the time cost for each RHM service user to generate indexes and trapdoors. To generate an index, firstly an m-dimensional data vector is created by the gateway. Each dimension of the vector represents a monitored parameter. This vector is encrypted by the ASPE encryption scheme; that is, it is split into two random vectors with a secret binary vector S as the splitting indicator and encrypted by two (m+1)×(m+1) invertible matrices. To create trapdoors for 2m bounds, firstly two m-dimensional random vectors are generated and then each vector is encrypted by the ASPE encryption scheme. We study whether the size of health data parameters will affect the time costs for generating an index or trapdoors. As shown in Figure 3, index for one health data record can be generated within 0.5 ms. Figure 4 indicates that the trapdoors for all parameters can be created in less than 0.35 s (note that trapdoors are created once for all), which is efficient for practical applications. The computation cost of algorithmGenTrapdoor2 is almost the same asGenIndex; we omit the experimental results here.Figure 3
Encrypted index generation.Figure 4
Trapdoor generation.Time for Searches. In each time interval, an encrypted health data is uploaded to the remote health monitoring service provider, who runs the search algorithmSearch. We show the time cost in Figure 5. For each health data record, outliers detection can be accomplished very efficiently; for example, only about 5 μs is consumed when the parameter size is 200. When a medical service provider wants to search interested health data records, the search time is related with the size of the specific user’s health data records. From Figure 6, when we set the health data record size to 200000, the time consumed is only about 450 ms, which is efficient for practical applications.Figure 5
Outlier detection computation overhead.Figure 6
Search2 computation overhead.Communication Overhead. We mainly focus on the communication overhead of the index and trapdoor generation phase, since these phases may be executed on a mobile devices, which requires low communication costs. From Figures 7 and 8, when the size of the health parameters is set as m=200, the size of the index is 1.6 KB and the size of the trapdoors is about 700 KB, which is a feasible storage requirement on most mobile devices. In addition, the trapdoor generation is run only once; therefore, our scheme achieves communication efficiency and is applicable on mobile devices.Figure 7
Size of index.Figure 8
Size of trapdoor.


## 3.1. Correctness Analysis

In the following, we briefly discuss the correctness of the proposed searchable encryption scheme on the basis of the correctness proof of the ASPE scheme shown in Section2.2. We prove the correctness of GenTrapdoor2(·) and Search2(·), and it is easy to prove the correctness of the other trapdoor generation and search algorithm designed for supporting detection of outliers over the encrypted health data in the same way.In vectorQ1 and Q2, except for the values on the λth position, all the others are the same. Therefore, when the operation is “≤” we have(14)TQ1-TQ2⊙Iȷ=Q1aT,Q1bTT-Q2aT,Q2bTT⊙PȷaT,PȷbTT=Q1^-Q2^⊙Pȷ¯=0.5rd2Q2,Pȷ-d2Q1,Pȷ=2rsα-Pȷλ.When the operation is “≥” we have(15)TQ1-TQ2⊙Iȷ=Q1aT,Q1bTT-Q2aT,Q2bTT⊙PȷaT,PȷbTT=Q1^-Q2^⊙Pȷ¯=0.5rd2Q2,Pȷ-d2Q1,Pȷ=2rsPȷλ-α.Furthermore, r and s are positive numbers; therefore it is easy to verify that(16)2rsα-Pȷλ≤0,iffα≤Pȷλ,2rsPȷλ-α≤0,iffα≥Pȷλ.Therefore, SCRHM, which aims to perform range searches over the encrypted health data, can accomplish the claimed functionality correctly.


## 3.2. Security Analysis

In what follows, we prove that our system satisfies the three proposed security requirements, that is, confidentiality, single parameter privacy, and trapdoor uniqueness.Confidentiality. The privacy protection of searchable indexes and trapdoors is based on the security of the ASPE scheme. On the security of this scheme, Wong et al. claim that it can guard against any attacks based on the knowledge of a number of (plaintext, ciphertext) pairs, and their argument is as follows [33]. If the boolean vector S is known to the adversary, then he/she would be able to use the known (plaintext, ciphertext) pairs to construct linear equations about M1 and M2 and then solve the equations to obtain M1 and M2. However, since S is secret, it would be hard for the adversary to derive the correct linear equations to use, since the formulation of the equations depends on S. A brute-force approach would require the adversary to examine all possible bit vector S, which leads to 2S linear equation systems that cannot be solved in reasonable time when S is large. That is, the RHM service providers are unable to obtain the matrices Mȷ and Mȷ′ of a honest user Uȷ. Therefore, the encrypted index [(Mȷ-1Pȷa)T,(Mȷ′-1Pȷb)T]T will not leak private information of data vector Pȷ. The trapdoors will keep the confidentiality of the corresponding λth searched health parameter as well.However Yao et al. [35] propose a chosen plaintext attack that can recover the data point not by solving the aforementioned linear equations. Their attack is as follows [35]. Assume that the server obtains d query points and their corresponding ciphertexts (by asking the oracle in the chosen plaintext attack model). For each Q of those query points, the server would have two encrypted points Qa and Qb generated by the query point encryption function. The ASPE scheme ensures that dot product between Q and any data point P can be calculated based on the following equation: P·Q=Pa·Qa+Pb·Qb. Notice that the above equation contains only d variables unknown to the adversary, that is, the d fields of the data point P. Since the adversary has the (plaintext, ciphertext) pair of d query points, he can construct d linear equations to derive all the fields of P. Therefore, the ASPE scheme is prone to chosen plaintext attack and this attack still works if data point is encrypted by the query point encryption function, and the query point is encrypted with the data point encryption function, which is the case in our scheme.Fortunately, this attack will not affect the security of our proposed scheme. The most important part in the above mentioned attack is that the adversary knows the plaintext, whereas, in our scheme, even if the adversary is allowed to access the trapdoor generation oracle, he is unable to obtain the plaintext. For example, the adversary’s query is denoted byQ, according to the trapdoor generation algorithm in our scheme; the adversary will get the ciphertexts E(Q1) and E(Q2) (or E(Qȷλ1) and E(Qȷλ2)), where Q1 and Q2 (or Qȷλ1 and Qȷλ2) are two random vectors which are only known by the honest user Uȷ and fully trusted authorized medical service providers but unknown to neither the RHM service provider nor malicious users. Therefore, the adversary cannot implement the chosen plaintext attack in our scheme. The adversary is only able to obtain the private information within the encrypted indexes and trapdoors by implementing brute force search, whereas brute force search is computationally infeasible when the number of dimensions is greater than 80 [33].Single Parameter Privacy. Trapdoor generation is a randomized algorithm. For each value α∈L∪H, two random vectors Q1 (or Qȷλ1) and Q2 (or Qȷλ2) are generated and both of them are randomly split into two vectors which are then multiplied by two secret matrices Mȷ and Mȷ′. That is, the trapdoors are indistinguishable from random vectors. After the user randomly permutes the 2m trapdoors before uploading them to RHSMP, it is impossible to establish a mapping between the parameters and the trapdoors since all the 2m trapdoors are random and indistinguishable from each other. For lower bound and upper bound, the trapdoor generation phase is different, so that in the search phase, the criteria of whether the values are abnormal or not are the same, that is, whether (TQ[1]-TQ[2])⊙Iȷ≤0 holds or not. As a result, even if RHMSP finds that a certain health data record is an outlier, it will not get known of which parameter is abnormal and whether it is greater than the upper bound or smaller than the lower bound, thus protecting single parameter privacy proposed in our security requirements.Trapdoor Uniqueness. From the above confidentiality analysis, we know that even if the RHM service provider colludes with malicious users, the private information in the indexes and trapdoors cannot be recovered; however we omit some other possible approaches. That is, if the trapdoors generated by the honest users or medical service provider can be used to search the encrypted indexes by the malicious users or vise verse, then the malicious users can recover the values in a divide-and-conquer or brute-force way. For example, if the trapdoors generated by a malicious user A can be used to search a honest user B’s encrypted indexes, then A generates trapdoors for all possible values of a specific health parameter with the algorithmGenTrapdoor2 and runs the search algorithmSearch2 over the encrypted indexes; if the equation (TQ[1]-TQ[2])⊙Iȷ=0 holds for a certain trapdoor, then A can get known that the encrypted health parameter equals to the value α encrypted by this trapdoor. The malicious users can recover the value encrypted in the honest users’ or medical service providers’ trapdoors in a similar way by generating encrypted indexes for all possible values and running theSearch2 algorithm with these encrypted indexes and the trapdoors as inputs. Therefore it is of great importance that the trapdoor is unique; that is, the trapdoor generated by user A can only be used to search the encrypted indexes generated by him/herself but not other users. Fortunately, our scheme satisfies this property since when using different user specific secret key to generate the encrypted indexes and trapdoors, Fact 1 and Fact 2 in Section 2.2 do not hold. When trapdoor generated by malicious user A is used for searching over honest user B’s encrypted indexes, ([(MATQ1a)T,(MA′TQ1b)T]T-[(MATQ2a)T,(MA′TQ2b)T]T)⊙[(MB-1Pa)T,(MB-1Pb)T]T (MA, MA′ are user A’s secret key and MB, MB′ are user B’s secret key) will be a random value, which does not leak any information about the honest user B’s encrypted indexes. In a similar way, we can prove that A cannot get private information of B’s trapdoors. Therefore, trapdoor uniqueness required in our design goals is satisfied in our scheme.From analysis above, we can conclude that our scheme is secure in terms of the three security requirements proposed in Section2.1.


## 3.3. Performance Evaluation

In this section, we run simulation experiments to evaluate the performance of the proposed scheme in terms of computation and communication overhead. All the data vectors used in our experiments below are generated randomly.Computation Overhead. The computations are performed on a 1.4 GHz MAC OS X Yosemite system. All the data reported below are averaged over 100 randomized runs. Time costs of the algorithms are evaluated with varied size of parameters and users. We set the number of parameters to be four different values: 80, 120, 160, and 200. On the one hand, the size is set to be greater than 80 for guaranteeing the security property of the ASPE scheme; on the other hand, 200 parameters are enough for remote health monitoring systems in practice. As for user numbers, we choose 10000, 50000, 100000, 150000, and 200000 to evaluate system performance. Algorithms running on the remote health monitoring server can be parallelized; therefore computation efficiency can be further improved.Time for Generating Index and Trapdoors. In what follows, we consider the time cost for each RHM service user to generate indexes and trapdoors. To generate an index, firstly an m-dimensional data vector is created by the gateway. Each dimension of the vector represents a monitored parameter. This vector is encrypted by the ASPE encryption scheme; that is, it is split into two random vectors with a secret binary vector S as the splitting indicator and encrypted by two (m+1)×(m+1) invertible matrices. To create trapdoors for 2m bounds, firstly two m-dimensional random vectors are generated and then each vector is encrypted by the ASPE encryption scheme. We study whether the size of health data parameters will affect the time costs for generating an index or trapdoors. As shown in Figure 3, index for one health data record can be generated within 0.5 ms. Figure 4 indicates that the trapdoors for all parameters can be created in less than 0.35 s (note that trapdoors are created once for all), which is efficient for practical applications. The computation cost of algorithmGenTrapdoor2 is almost the same asGenIndex; we omit the experimental results here.Figure 3
Encrypted index generation.Figure 4
Trapdoor generation.Time for Searches. In each time interval, an encrypted health data is uploaded to the remote health monitoring service provider, who runs the search algorithmSearch. We show the time cost in Figure 5. For each health data record, outliers detection can be accomplished very efficiently; for example, only about 5 μs is consumed when the parameter size is 200. When a medical service provider wants to search interested health data records, the search time is related with the size of the specific user’s health data records. From Figure 6, when we set the health data record size to 200000, the time consumed is only about 450 ms, which is efficient for practical applications.Figure 5
Outlier detection computation overhead.Figure 6
Search2 computation overhead.Communication Overhead. We mainly focus on the communication overhead of the index and trapdoor generation phase, since these phases may be executed on a mobile devices, which requires low communication costs. From Figures 7 and 8, when the size of the health parameters is set as m=200, the size of the index is 1.6 KB and the size of the trapdoors is about 700 KB, which is a feasible storage requirement on most mobile devices. In addition, the trapdoor generation is run only once; therefore, our scheme achieves communication efficiency and is applicable on mobile devices.Figure 7
Size of index.Figure 8
Size of trapdoor.


## 4. Conclusion

In this paper, considering the increasing need for remote health monitoring and confidential property of the health data, we introduce a secure continuous remote health monitoring system, named SCRHM. To enable remote health monitoring service provider to find odd conditions while preserving users’ data privacy, a searchable encryption scheme, which supports range searches for the remote health monitoring system, is proposed. We perform the correctness and security analysis of the proposed scheme and prove that our proposed scheme supports range searches over encrypted data correctly and achieves the security goals to protect user privacy. Through extensive simulation experiments, we validate the performance of our system. In particular, high performance in terms of computation and communication overhead can be achieved. In the future, we would like to extend our system to support more complex computation over encrypted health data, so that remote health monitoring service provider would be able to perform more versatile analyses and provide more plentiful services for users.



---

*Source: 392439-2015-12-17.xml*