# Privacy-Preserving Self-Helped Medical Diagnosis Scheme Based on Secure Two-Party Computation in Wireless Sensor Networks

Authors: Yi Sun; Qiaoyan Wen; Yudong Zhang; Wenmin Li
Journal: Computational and Mathematical Methods in Medicine
 (2014)

---

## Abstract

With the continuing growth of wireless sensor networks in pervasive medical care, people pay more and more attention to privacy in medical monitoring, diagnosis, treatment, and patient care. On one hand, we expect the public health institutions to provide us with better service. On the other hand, we would not like to leak our personal health information to them. In order to balance this contradiction, in this paper we design a privacy-preserving self-helped medical diagnosis scheme based on secure two-party computation in wireless sensor networks so that patients can privately diagnose themselves by inputting a health card into a self-helped medical diagnosis ATM to obtain a diagnostic report just like drawing money from a bank ATM without revealing patients’ health information and doctors’ diagnostic skill. It makes secure self-helped disease diagnosis feasible and greatly benefits patients as well as relieving the heavy pressure of public health institutions.


---

## Body

## 1. Introduction

With the rapid development of science, more and more advanced technologies such as the internet of things and cloud computing are utilized in the area of modern medicine and this trend further pushes healthcare into the digital era [1–3]. Currently, numerous healthcare devices such as heart rate monitor, blood pressure monitor, and electrocardiogram are already popular in people’s normal life. It makes it convenient for people to be aware of their health situation by viewing the reports of these devices. Especially, by the growing use of sensor technology in telecare, the new field known as wireless body area networks (WBAN) [1, 4] has designed various sensor devices that can be used to supervise critical body parameters and activities anytime and anywhere. People can easily and conveniently get the health data by these advanced sensor devices [5] such as temperature measurement, respiration monitor, heart rate monitor, pulse oximeter SpO2, blood pressure monitor, pH monitor, glucose sensor, cardiac arrhythmia monitor/recorder, brain liquid pressure sensor, and endoscope capsule. What is more, these devices are becoming more functional and portable. More and more mobile medical monitors have already been used to serve us [2].Therefore, people no longer worry about how to obtain the health data but are concerned about how to securely deal with these sensitive data to have disease diagnosis with a medical institution. Traditionally, the issue of privacy of medical data has been dealt with primarily as a policy problem [6, 7]. Many related laws have been issued to protect the privacy of patients. However, it is still far away from satisfactory and people still fear the leakage of their private data. Hence, the most efficient solution to this problem is to protect patients’ privacy in technology rather than in policy alone. In this aspect, most of previous literatures have introduced homomorphic encryption (HE) [8–10] to protect patients’ privacy in some privacy-preserving medical applications [11]. However, HE will inevitably introduce tremendous cost and is not applicable to practical large-scale applications. Therefore, in this paper, we focus on building a secure and practical privacy-preserving medical diagnosis system that can serve us in our daily life. Starting from the aspiration of the patient, the most secure and plausible diagnostic method is to apply the processed data rather than the original data to interact with the hospital which owns a disease database to diagnose the health status privately. Moreover, it requires that after diagnosis, the hospital gets nothing about the patient’s health data and the patient has no idea of the hospital’s disease database.Inspired by daily used bank automated teller machine (ATM), we introduce the privacy-preserving self-helped medical diagnosis ATM (MD-ATM) so that after obtaining a healthcare card that stores some information about the health data which is collected by various sensor medical devices, patients can privately diagnose himself by inserting the health card into the MD-ATM to obtain diagnostic report just like drawing money from a bank ATM without revealing patient’s health information and the disease database or doctors’ diagnostic skill. When needing local computing, storing, or inputting some information, the patient uses his own portable device, called portable medical diagnostic device (PMDD).In this paper, we will show how to realize this modern diagnosis system without HE. The main idea and technology we used in this scheme are secure two-party computation (STC) and oblivious transfer (OT). Firstly, we assume that patients themselves collect related data by various wireless sensor medical devices and further process and store them in their own health cards using PMDD. When diagnosing, the patient firstly transforms the original data locally and then inserts the card into the MD-ATM of the hospital to check up his health. Operating following the instructions of the MD-ATM, the patient will finally obtain a diagnostic report through OT and the patient then completes the self-helped diagnosis. In brief, our main contributions can be summarized as follows.Our Contributions.
(i)
We build a new “patient-centered” medical diagnosis model in wireless sensor networks where patients themselves collect health data by various sensor medical devices while the hospital provides a disease database to help patients to complete disease diagnosis by themselves. Compared with traditional “doctor-centered” medical diagnosis model where patients have to depend on the doctor, our system is more appropriate especially when people pay more and more attention to privacy in wireless sensor networks.
(ii)
We firstly propose the privacy-preserving self-helped MD-ATM to construct a secure medical diagnosis scheme following the idea of STC. It makes secure self-helped medical diagnosis feasible and convenient just like drawing money from a bank ATM. It will greatly benefit patients as well as relieving the heavy pressure of public health institutions.
(iii)
We construct the self-helped medical diagnosis system based on OT without expensive HE. It provides us with another perspective to consider the problem of secure medical diagnosis for patients.The rest of this paper is organized as follows. In Section2, we briefly give an overview of secure two-party computation and oblivious transfer, and then we present our medical diagnosis system model in Section 3. In Section 4, we propose our privacy-preserving self-helped medical diagnosis scheme in detail and give a strict proof based on real-ideal simulation paradigm in Section 5. Finally, we summarize our work of this paper in the last section.


## 2. Preliminaries

### 2.1. Secure Two-Party Computation

Secure multiparty computation (SMC) is dedicated to deal with the problem of secure computation among distrustful participants. It was first introduced by Yao in 1982 [12] and then was extended by Goldreich et al. [13] and many other researchers [14–19]. Generally speaking, SMC is a method to implement cooperative computation with participants’ private data, ensuring the correctness of the computation as well as not disclosing additional information except the necessary results. It has become a research focus in the international cryptographic community due to its wide applications in various areas and a mass of research results have been published one after another. Secure two-party computation (STC) [20] is a special case in SMC where there are only two participants. The well-known millionaires’ problem [12] put forward by Yao is the representative problem of STC. In our discussing, we will consider the two-party case.Generally speaking, STC is dedicated to computing a certain function between two mutually distrusted participants on their private inputs without revealing their private information. Informally, assuming that there are 2 participants,P
1, P
2, each of them has a private number, x
1, x
2, respectively. They want to cooperate to compute the function y
=
f
(
x
1
,
x
2
). A STC protocol is dubbed secure if no participant can learn more from the description of the public function and the result of the global calculation than what he can learn from his own information.Formally, we usually analyze the security of a STC protocol using the real-ideal paradigm in the semihonest model where both of the two parties act semihonestly, following the protocol but making effort to gain more information about other parties’ inputs, intermediate results, or overall outputs by the transcripts of the protocol [15]. We can overview the real-ideal paradigm as follows.Firstly, in the ideal world, we assume that the computation of the functionalityF on users private inputs is conducted by an additional trusted party, who receives x
i from user P
i
,
i
=
1,2, and returns the result f
(
x
1
,
x
2
) to P
i
,
i
=
1,2. However, there is no trusted party in the real world and so the two parties have to run a protocol Π to get the desired result. During executing protocol Π, both parties act semihonestly. Herein, the view of the ith party during an execution of Π on x
1
,
x
2 is denoted as VIEW
i
Π
(
x
1
,
x
2
), which contains P
i’s input, random tape, and the messages received from the other party. For a deterministic private function f, we say that Π privately computes f if there exist probabilistic polynomial-time algorithms S
1
,
S
2, such that the simulated distribution {
S
i
(
x
i
;
f
(
x
1
,
x
2
)
)
} is indistinguishable to {
VIEW
i
Π
(
x
1
,
x
2
)
}, i
=
1,2. That is,
(1)
{
S
1
(
x
1
;
f
(
x
1
,
x
2
)
)
}
≅
{
VIEW
1
Π
(
x
1
,
x
2
)
}
,
{
S
2
(
x
2
;
f
(
x
1
,
x
2
)
)
}
≅
{
VIEW
1
Π
(
x
1
,
x
2
)
}
.


### 2.2. Oblivious Transfer

In cryptography, OT is a type of protocol in which a sender transfers one of potentially many pieces of information to a receiver but remains oblivious as to which piece has been transferred. It was firstly introduced by Rabin [21] in 1981. Therein, the sender sends a message to the receiver with probability 1/2, while the sender remains oblivious as to whether or not the receiver received the message. Rabin’s oblivious transfer scheme is based on the RSA cryptosystem. In 1985, Even et al. [22] proposed a more useful OT called 1-out-of-2 OT (OT
1
2) to build protocols for secure multiparty computation.Afterwards, it has been generalized to 1-out-of-m OT (OT
1
m) [23] where the receiver gets exactly one message without the sender getting to know which message was queried and the receiver getting to know anything about the other messages that were not retrieved. OT
1
m has become a fundamental tool in cryptography and is usually used as a black-box when constructing protocols.Formally, we can describe anOT
1
m protocol as follows. There are 2 participants called the sender S and the receiver R. Specifically, S has m messages, and R has an index z. R wishes to receive the zth message of the sender’s m messages without leaking z to S, while knowing nothing about the rest m
-
1 messages. A simplified OT
1
m protocol can be presented as in Algorithm 1.Algorithm 1
O
T
1
m
Inputs:
S inputs a set of m messages: (
r
1
,
r
2
,
…
,
r
m
);
R inputs an index: z;
Outputs:
S obtains λ, which means N
u
l
l.
R obtains r
z.


## 2.1. Secure Two-Party Computation

Secure multiparty computation (SMC) is dedicated to deal with the problem of secure computation among distrustful participants. It was first introduced by Yao in 1982 [12] and then was extended by Goldreich et al. [13] and many other researchers [14–19]. Generally speaking, SMC is a method to implement cooperative computation with participants’ private data, ensuring the correctness of the computation as well as not disclosing additional information except the necessary results. It has become a research focus in the international cryptographic community due to its wide applications in various areas and a mass of research results have been published one after another. Secure two-party computation (STC) [20] is a special case in SMC where there are only two participants. The well-known millionaires’ problem [12] put forward by Yao is the representative problem of STC. In our discussing, we will consider the two-party case.Generally speaking, STC is dedicated to computing a certain function between two mutually distrusted participants on their private inputs without revealing their private information. Informally, assuming that there are 2 participants,P
1, P
2, each of them has a private number, x
1, x
2, respectively. They want to cooperate to compute the function y
=
f
(
x
1
,
x
2
). A STC protocol is dubbed secure if no participant can learn more from the description of the public function and the result of the global calculation than what he can learn from his own information.Formally, we usually analyze the security of a STC protocol using the real-ideal paradigm in the semihonest model where both of the two parties act semihonestly, following the protocol but making effort to gain more information about other parties’ inputs, intermediate results, or overall outputs by the transcripts of the protocol [15]. We can overview the real-ideal paradigm as follows.Firstly, in the ideal world, we assume that the computation of the functionalityF on users private inputs is conducted by an additional trusted party, who receives x
i from user P
i
,
i
=
1,2, and returns the result f
(
x
1
,
x
2
) to P
i
,
i
=
1,2. However, there is no trusted party in the real world and so the two parties have to run a protocol Π to get the desired result. During executing protocol Π, both parties act semihonestly. Herein, the view of the ith party during an execution of Π on x
1
,
x
2 is denoted as VIEW
i
Π
(
x
1
,
x
2
), which contains P
i’s input, random tape, and the messages received from the other party. For a deterministic private function f, we say that Π privately computes f if there exist probabilistic polynomial-time algorithms S
1
,
S
2, such that the simulated distribution {
S
i
(
x
i
;
f
(
x
1
,
x
2
)
)
} is indistinguishable to {
VIEW
i
Π
(
x
1
,
x
2
)
}, i
=
1,2. That is,
(1)
{
S
1
(
x
1
;
f
(
x
1
,
x
2
)
)
}
≅
{
VIEW
1
Π
(
x
1
,
x
2
)
}
,
{
S
2
(
x
2
;
f
(
x
1
,
x
2
)
)
}
≅
{
VIEW
1
Π
(
x
1
,
x
2
)
}
.


## 2.2. Oblivious Transfer

In cryptography, OT is a type of protocol in which a sender transfers one of potentially many pieces of information to a receiver but remains oblivious as to which piece has been transferred. It was firstly introduced by Rabin [21] in 1981. Therein, the sender sends a message to the receiver with probability 1/2, while the sender remains oblivious as to whether or not the receiver received the message. Rabin’s oblivious transfer scheme is based on the RSA cryptosystem. In 1985, Even et al. [22] proposed a more useful OT called 1-out-of-2 OT (OT
1
2) to build protocols for secure multiparty computation.Afterwards, it has been generalized to 1-out-of-m OT (OT
1
m) [23] where the receiver gets exactly one message without the sender getting to know which message was queried and the receiver getting to know anything about the other messages that were not retrieved. OT
1
m has become a fundamental tool in cryptography and is usually used as a black-box when constructing protocols.Formally, we can describe anOT
1
m protocol as follows. There are 2 participants called the sender S and the receiver R. Specifically, S has m messages, and R has an index z. R wishes to receive the zth message of the sender’s m messages without leaking z to S, while knowing nothing about the rest m
-
1 messages. A simplified OT
1
m protocol can be presented as in Algorithm 1.Algorithm 1
O
T
1
m
Inputs:
S inputs a set of m messages: (
r
1
,
r
2
,
…
,
r
m
);
R inputs an index: z;
Outputs:
S obtains λ, which means N
u
l
l.
R obtains r
z.


## 3. System Model

In this section, we present the system model including the goals we aim to achieve in detail.In this paper, we consider the privacy-preserving medical diagnosis system with two participants: the patient and the hospital. We assume that each patient can collect his own health data such as heart beat and blood pressure, in the form of a vector, called query vector, easily by various advanced medical devices. Herein, we call the heart beat, blood pressure, and so forth, as parameter items and the health data corresponding to heart beat, blood pressure, and so forth, as parameter values. For example,q
P
=
(
q
P
1
,
…
,
q
P
n
) is the query vector of the patient P, where all {
q
P
w
}
w
=
1
,
…
,
n are the necessary parameters the hospital needs for diagnosis, and q
P
w is the parameter value of the parameter item heart beat. Each patient has a health card to store related data and a portable device PMDD to read the data stored in the card and to do some related computations after inserting the card. The hospital has a disease database DB
=
{
d
i
}
i
=
1
,
…
,
m, which in fact is the standard to determine which disease the patient has got. Each record of the disease database is presented as a triple d
i
=
(
i
,
t
i
,
r
i
)
,
i
=
1
,
…
,
m, where m is the capacity of the disease database; i is the index of a disease; t
i, called the trait vector of the disease d
i, is a vector that covers all necessary parameters the hospital needs for diagnosis; and r
i is the disease diagnostic report including the disease name, doctors’ advices, and prescriptions corresponding to the ith disease d
i. Concerning these parameters, we have some illustrations as follows.(i)
q
P: it includes all necessary parameter items the hospital needs for diagnosis such as heart beat and blood pressure. The query vectors of the same patient P are different if P goes to different hospitals since their medical levels are different. The query vectors of the same patient P may be also different if P goes to the same hospital at different time since the medical level of the hospital has been always keeping improving. The dimension n and every parameter item {
q
P
w
}
w
=
1
,
…
,
n of the query vector are determined by the trait vector t
i of the hospital. After registering to the hospital, patient can know what parameter items are needed in this diagnosis by reading the health card.
(ii)
DB
=
{
d
i
}
i
=
1
,
…
,
m: it concludes all diseases a hospital can diagnose. Different hospitals have different disease databases and the same hospital has different disease databases at different time since its medical level has been keeping improving. The dimension m is determined by the hospital’s medical level.
(iii)
t
i: it includes all necessary parameter items the hospital needs for diagnosis such as heart beat and blood pressure. Different hospitals have different trait vectors and the trait vectors of the same hospital at different time may be different since the medical level of the hospital has been always keeping improving. The dimension n and every parameter item {
t
i
j
}
j
=
1
,
…
,
n of the trait vector are determined by the hospital’s medical level. In order to improve the precision of our diagnosis system, the hospital can consider as many factors as possible such as adding more personal feelings, symptoms, and previous medical features from the patient as parameter items. Although we only can diagnose some simple diseases currently, it is believed that it will be feasible for more complicated diseases in the future by extending the dimension n of the parameter items.
(iv)
r
i: it includes the disease name, doctors’ advices, and prescriptions corresponding to the ith disease d
i. Each report may conclude many doctors' advices and prescriptions. Herein, we assume that every report obtained from the MD-ATM following the self-helped medical diagnosis is authorized by the hospital and all advices and prescriptions of a report are signed by corresponding doctors. After receiving the diagnostic report, patient can choose one doctor’s advice and prescription to treat himself.In this paper, the system makes medical diagnosis according to the Euclidean distances of two vectors. Specifically, taking the query vector of the patient and a trait vector of the database as an example, given a patient’s query vectorq
P
=
(
q
P
1
,
…
,
q
P
n
) and a disease trait vector t
i
=
(
t
i
1
,
…
,
t
i
n
)
,
i
∈
{
1
,
…
,
m
}, their Euclidean distance [3] denoted by dist
⁡
q
P
↔
t
i is
(2)
dist
⁡
q
P
↔
t
i
⁡
=
∑
w
=
1
n
‍
(
q
P
w
-
t
i
w
)
2
.Herein, we compare the squares of the Euclidean distances,(3)
dis
t
q
P
↔
t
i
2
-
dis
t
q
P
↔
t
j
2
=
∑
w
=
1
n
‍
(
q
P
w
-
t
i
w
)
2
-
∑
w
=
1
n
‍
(
q
P
w
-
t
j
w
)
2
.It is obvious that we can figure out which one has smaller distance with patient’s query vector just by checking the sign of (3) without exact result of dist
⁡
q
P
↔
t
i or dist
⁡
q
P
↔
t
j. Assuming that the report r
z corresponding to the trait vector t
z
,
z
∈
{
1
,
…
,
m
}, is the diagnosed disease report, we have the following result, for all j
=
1
,
…
,
m
,
j
≠
z:
(4)
dis
t
q
P
↔
t
z
2
-
dis
t
q
P
↔
t
j
2
<
0
.In our scheme, we will compare the squares of the Euclidean distances of the query vector and the trait vectors to find the diagnostic report that satisfies (4).In real application, the hospital provides a MD-ATM, which is connected with the disease database and can read the data of the card, to direct patients to complete self-helped disease diagnosis. Specifically, we assume that each patient registers to the hospital for the first time and gets a health card. The hospital provides a self-helped MD-ATM in public just like a bank ATM. WheneverP wants to have a diagnosis, inserting his health card into the MD-ATM and following the instructions, P can complete the self-helped diagnosis by himself. The basic model can be illustrated in Figure 1.Figure 1
Self-helped medical diagnosis model of our scheme.Apart from the above, to enable a privacy-preserving medical diagnosis system, our scheme should simultaneously fulfill the following two security goals.(i)
Confidentiality of disease database should be protected during the self-helped diagnosis process.
(ii)
Confidentiality of patient’s private health data should be protected during the self-helped diagnosis process.


## 4. Our Scheme

In this section, we propose our privacy-preserving self-helped medical diagnosis scheme (PP-SH-MDS) in detail to show how a patient can diagnose by himself using his PMDD and the self-helped MD-ATM. The core of our construction can be summarized in Figure2.Figure 2
PP-SH-MDS.Specifically, the patientP executes as follows to make a self-helped diagnosis using his PMDD and the MD-ATM.In the setup phase,P registers to a hospital as traditional medical diagnosis and gets a health card.In the diagnosis phase, there are three subphases.(
1) Local Preprocessing. Whenever P wants to have a diagnosis, he firstly conducts the following two transformations on PMDD locally.(i)
Vector-to-Vector.
(a)
P firstly extends his original health data from an n-vector q
P
=
(
q
P
1
,
…
,
q
P
n
) to an (
n
+
2
)-vector Q
P
=
(
q
P
1
,
…
,
q
P
n
,
q
P
,
n
+
1
,
q
P
,
n
+
2
), where q
P
,
n
+
1
=
-
(
1
/
2
)
∑
w
=
1
n
q
P
w
2 and q
P
,
n
+
2
=
1.
(ii)
Vector-to-Matrix.
(a)
P randomly chooses a password s
P
=
(
s
P
1
,
…
,
s
P
k
) and then generates a k
×
(
n
+
2
) matrix
(5)
B
P
=
[
b
11
⋯
b
1
,
n
+
2
⋮
⋮
b
k
1
⋯
b
k
,
n
+
2
]
,
where∑
u
=
1
k
s
P
u
·
b
u
w
=
1
,
w
=
1
,
…
,
n
+
2.
(b)
By blindingQ
P using the matrix B
P, P further extends Q
P to a matrix
(6)
M
P
=
[
b
11
·
q
P
1
⋯
b
1
,
n
+
2
·
q
P
,
n
+
2
⋮
⋮
b
k
1
·
q
P
1
⋯
b
k
,
n
+
2
·
q
P
,
n
+
2
]
.After completing the above steps,P stores the matrix M
P in the health card.(2) Diagnosis.
(i)
After local preprocessing,P inserts his health card into the MD-ATM and then the MD-ATM reads the card to get the matrix M
P and randomly chooses two trait vectors t
i
=
(
t
i
1
,
…
,
t
i
n
) and t
j
=
(
t
j
1
,
…
,
t
j
n
) and, respectively, extends them to (
n
+
2
)-vectors T
i
=
(
t
i
1
,
…
,
t
i
n
,
t
i
,
n
+
1
,
t
i
,
n
+
2
) and T
j
=
(
t
j
1
,
…
,
t
j
n
,
t
j
,
n
+
1
,
t
j
,
n
+
2
), where t
i
,
n
+
1
=
1
,
t
i
,
n
+
2
=
-
(
1
/
2
)
∑
w
=
1
n
t
i
w
2 and t
j
,
n
+
1
=
1
,
t
j
,
n
+
2
=
-
(
1
/
2
)
∑
w
=
1
n
t
j
w
2. Then the MD-ATM computes Δ
i
j
′
=
M
P
·
(
T
i
-
T
j
)
T
,
i
,
j
=
1
,
…
,
m
,
i
≠
j, and writes (
Δ
i
j
′
,
i
,
j
) in the card and indicates the patient to get back his card.
(ii)
Following the instructions of the MD-ATM, the patient gets the card back and inserts it into PMDD. After inputting his password, PMDD begins to computeΔ
i
j
=
s
P
·
Δ
i
j
′
,
i
,
j
=
1
,
…
,
m
,
i
≠
j, and finds the index z so that for all j
=
1
,
…
,
m
,
j
≠
z
,
Δ
i
j
>
0. z is the input of the following O
T
1
m protocol.(
3) 1-out-of-m OT Protocol.(i)
P inserts his card into the MD-ATM and invokes an O
T
1
m protocol, where P’s input is the index z and the MD-ATM’s input is the diagnostic report set (
r
1
,
r
2
,
…
,
r
m
) of the database.After executing theO
T
1
m protocol, P gets the diagnostic report r
z corresponding to the disease d
z according to the index z, while the MD-ATM gets N
u
l
l, denoted by λ.


## 5. Analysis

In this section, we analyze our scheme in detail. We firstly have a look at the correctness and then give a strict security proof following the real-ideal simulation paradigm of STC in the scenarios of semihonest adversaries.


### 5.1. Correctness

In this aspect, we follow the steps of our scheme and make sure that the patient indeed finds out the most possible disease from the disease database of the hospital using his health data by comparing Euclidean distances.Following the scheme, we can see that the patient transforms the health data in two steps. Firstly, he extends his original health data from ann-vector q
P
=
(
q
P
1
,
…
,
q
P
n
) to an (
n
+
2
)-vector Q
P
=
(
q
P
1
,
…
,
q
P
n
,
q
P
,
n
+
1
,
q
P
,
n
+
2
), where q
P
,
n
+
1
=
-
(
1
/
2
)
∑
w
=
1
n
q
P
w
2 and q
P
,
n
+
2
=
1 and then blinds and extends Q
P using the matrix B
P to a matrix(7)
M
P
=
[
b
11
·
q
P
1
⋯
b
1
,
n
+
2
·
q
P
,
n
+
2
⋮
⋮
b
k
1
·
q
P
1
⋯
b
k
,
n
+
2
·
q
P
,
n
+
2
]
.
On the other hand, the MD-ATM randomly selects two trait vectors t
i
=
(
t
i
1
,
…
,
t
i
n
) and t
j
=
(
t
j
1
,
…
,
t
j
n
) and, respectively, extends them to (
n
+
2
)-vectors T
i
=
(
t
i
1
,
…
,
t
i
n
,
t
i
,
n
+
1
,
t
i
,
n
+
2
) and T
j
=
(
t
j
1
,
…
,
t
j
n
,
t
j
,
n
+
1
,
t
j
,
n
+
2
), where t
i
,
n
+
1
=
1
,
t
i
,
n
+
2
=
-
(
1
/
2
)
∑
w
=
1
n
t
i
w
2 and t
j
,
n
+
1
=
1
,
t
j
,
n
+
2
=
-
(
1
/
2
)
∑
w
=
1
n
t
j
w
2. After receiving M
P, for i
,
j
=
1
,
…
,
m
,
i
≠
j, the MD-ATM computes
(8)
Δ
i
j
′
=
M
P
·
(
T
i
-
T
j
)
T
=
[
b
11
·
q
P
1
⋯
b
1
,
n
+
2
·
q
P
,
n
+
2
⋮
⋮
b
k
1
·
q
P
1
⋯
b
k
,
n
+
2
·
q
P
,
n
+
2
]
·
[
t
i
1
-
t
j
1
⋮
t
i
,
n
+
2
-
t
j
,
n
+
2
]
.After receiving the returned messageΔ
i
j
′, for i
,
j
=
1
,
…
,
m
,
i
≠
j, P uses PMDD to compute
(9)
Δ
i
j
=
s
P
·
Δ
i
j
′
=
s
P
·
M
P
·
(
T
i
-
T
j
)
T
=
(
s
P
1
,
…
,
s
P
k
)
·
[
b
11
·
q
P
1
⋯
b
1
,
n
+
2
·
q
P
,
n
+
2
⋮
⋮
b
k
1
·
q
P
1
⋯
b
k
,
n
+
2
·
q
P
,
n
+
2
]
·
[
t
i
1
-
t
j
1
⋮
t
i
,
n
+
2
-
t
j
,
n
+
2
]
=
∑
u
=
1
k
‍
s
P
u
·
b
u
1
·
q
P
1
·
(
t
i
1
-
t
j
1
)
+
⋯
+
∑
u
=
1
k
‍
s
P
u
·
b
u
,
n
+
2
·
q
P
,
n
+
2
·
(
t
i
,
n
+
2
-
t
j
,
n
+
2
)
=
∑
w
=
1
n
+
2
‍
q
P
w
·
(
t
i
w
-
t
j
w
)
.
Thus, we have
(10)
Δ
i
j
=
∑
w
=
1
n
+
2
‍
q
P
w
·
t
i
w
-
∑
w
=
1
n
+
2
‍
q
P
w
·
t
j
w
=
(
∑
w
=
1
n
‍
q
P
w
·
t
i
w
+
q
P
,
n
+
1
·
t
i
,
n
+
1
+
q
P
,
n
+
2
·
t
i
,
n
+
2
)
-
(
∑
w
=
1
n
‍
q
P
w
·
t
j
w
+
q
P
,
n
+
1
·
t
j
,
n
+
1
+
q
P
,
n
+
2
·
t
j
,
n
+
2
)
=
(
∑
w
=
1
n
‍
q
P
w
·
t
i
w
+
q
P
,
n
+
1
+
t
i
,
n
+
2
)
-
(
∑
w
=
1
n
‍
q
P
w
·
t
j
w
+
q
P
,
n
+
1
+
t
j
,
n
+
2
)
=
(
∑
w
=
1
n
‍
q
P
w
·
t
i
w
-
1
2
∑
w
=
1
n
‍
q
P
w
2
-
1
2
∑
w
=
1
n
‍
t
i
w
2
)
-
(
∑
w
=
1
n
‍
q
P
w
·
t
j
w
-
1
2
∑
w
=
1
n
‍
q
P
w
2
-
1
2
∑
w
=
1
n
‍
t
j
w
2
)
=
1
2
[
∑
w
=
1
n
‍
(
q
P
w
-
t
j
w
)
2
-
∑
w
=
1
n
‍
(
q
P
w
-
t
i
w
)
2
]
=
1
2
(
dis
t
q
P
↔
t
j
2
-
dis
t
q
P
↔
t
i
2
)
.Obviously, if for allj
=
1
,
…
,
m
,
j
≠
z, Δ
z
j
=
(
1
/
2
)
(
dist
⁡
q
P
↔
t
j
2
-
dist
⁡
q
P
↔
t
z
2
)
>
0, then t
z
,
z
∈
{
1
,
…
,
m
}, is the trait vector of the diagnosed disease. The report r
z corresponding to the trait vector t
z is the diagnosed report. Taking the index z as the input of the following OT
1
m protocol, the patient can finally get the disease report r
z from the set (
r
1
,
r
2
,
…
,
r
m
) of the database.Therefore, our scheme is correct.


### 5.2. Security

In this subsection, we strictly prove the security of our scheme. From the whole process, we can specify that the two parties in our system are the patientP and the hospital. They cooperate to compute the function f
(
q
P
,
(
d
1
,
d
2
,
…
,
d
m
)
)
=
r
z, where r
z is the disease diagnostic report corresponding to the disease d
z and the distance dist
⁡
q
p
↔
t
z satisfies the condition dist
⁡
q
p
↔
t
z
2
=
min
⁡
{
dist
⁡
q
p
↔
t
j
2
}
j
=
1
,
…
,
m. As mentioned in Section 3, we should achieve two security goals, that is, keeping both parties’ inputs private. We apply the real-ideal simulation paradigm to prove that our scheme has achieved the two goals in the scenarios of semihonest adversaries assuming the OT
1
m protocol we used is secure.Theory 1.
Our privacy-preserving self-helped medical diagnosis scheme is secure against semihonest adversaries if the
OT
1
m
protocol is secure.Proof.
Notice that the view ofP
i, {
VIEW
i
(
q
p
,
{
d
1
,
…
,
d
m
}
)
}
i
=
1,2, in the real execution consists of three parts, the private input, random tape, and the messages received from the other party including the output. Therefore, we can get the views of P
1 and P
2, respectively, in the real execution as follows:
(11)
{
VIE
W
1
(
q
p
,
{
d
i
}
i
=
1
,
…
,
m
)
}
=
{
q
P
,
s
P
,
B
P
,
{
Δ
i
j
′
}
i
,
j
=
1
,
…
,
m
,
i
≠
j
,
{
VIEW
1
O
T
1
m
(
z
,
{
r
i
}
i
=
1
,
…
,
m
)
}
,
r
z
q
P
,
s
P
,
B
P
,
{
Δ
i
j
′
}
i
,
j
=
1
,
…
,
m
,
i
≠
j
}
;
(12)
{
VIE
W
2
(
q
p
,
{
d
i
}
i
=
1
,
…
,
m
)
}
=
{
{
d
i
}
i
=
1
,
…
,
m
,
M
P
,
{
VIEW
2
O
T
1
m
(
z
,
{
r
i
}
i
=
1
,
…
,
m
)
}
,
λ
}
,
where {
VIE
W
1
OT
1
m
(
z
,
{
r
i
}
i
=
1
,
…
,
m
)
} and {
VIE
W
2
O
T
1
m
(
z
,
{
r
i
}
i
=
1
,
…
,
m
)
} are the views produced in the execution of O
T
1
m protocol.
From the definition of security, we need to construct the probabilistic polynomial-time algorithmS
1
/
S
2 so that given the input and output of the patient P
1/the hospital P
2, (
q
P
;
r
z
)
/
(
{
d
i
}
i
=
1
,
…
,
m
;
λ
), it can output a simulated view {
S
1
(
q
P
;
r
z
)
}
/
{
S
2
(
{
d
i
}
i
=
1
,
…
,
m
;
λ
)
}, which is indistinguishable to the view {
VIEW
1
(
q
p
,
{
d
i
}
i
=
1
,
…
,
m
)
}/{
VIEW
2
(
q
p
,
{
d
i
}
i
=
1
,
…
,
m
)
} in the real execution of the scheme; that is,
(13)
{
S
1
(
q
P
;
r
z
)
}
≅
{
VIEW
1
(
q
p
,
{
d
i
}
i
=
1
,
…
,
m
)
}
,
{
S
2
(
{
d
i
}
i
=
1
,
…
,
m
;
λ
)
}
≅
{
VIEW
2
(
q
p
,
{
d
i
}
i
=
1
,
…
,
m
)
}
.
In the following discussion, we follow the real-ideal simulation paradigm to construct such probabilistic polynomial-time algorithmsS
1
,
S
2. We separately prove the case when P
2 is semihonest and when P
1 is semihonest.
Case
1 (P
2 is semihonest). In this case, we only need to construct a simulator S
2 so that, given P
2’s input {
d
i
}
i
=
1
,
…
,
m and output λ, S
2 can simulate P
2’s view in the real execution presented above as (12).
Firstly, since we assume that theO
T
1
m protocol used in our scheme is secure and can be taken as a black-box, there exists an algorithm S
2
O
T
1
m: given the input {
r
i
}
i
=
1
,
…
,
m and the output λ, it can simulate P
2’s view of the O
T
1
m execution and output {
S
2
O
T
1
m
(
{
r
i
}
i
=
1
,
…
,
m
;
λ
)
} so that
(14)
{
S
2
O
T
1
m
(
{
r
i
}
i
=
1
,
…
,
m
;
λ
)
}
≅
{
VIEW
2
O
T
1
m
(
z
,
{
r
i
}
i
=
1
,
…
,
m
)
}
.
Next, notice thatS
2 is given (
{
d
i
}
i
=
1
,
…
,
m
;
λ
); it can easily simulate the remaining parts of (12) by randomly choosing a k
×
(
n
+
2
) matrix M which is indistinguishable to the blinded matrix M
P. Then, S
2 outputs the simulated view,
(15)
{
S
2
(
{
d
i
}
i
=
1
,
…
,
m
;
λ
)
}
=
{
{
d
i
}
i
=
1
,
…
,
m
,
M
,
{
S
2
O
T
1
m
(
{
r
i
}
i
=
1
,
…
,
m
;
λ
)
}
,
λ
}
.
Obviously, we can conclude that(16)
{
S
2
(
{
d
i
}
i
=
1
,
…
,
m
;
λ
)
}
≅
{
VIEW
2
(
q
p
,
{
d
i
}
i
=
1
,
…
,
m
)
}
.
Case
2 (P
1 is semihonest). Similar to Case 1, we only need to construct a simulator S
1 so that given P
1’s input q
P and output r
z, S
1 can simulate P
1’s view in the real execution presented above as (11).
As discussed above, since theO
T
1
m protocol is secure, there exists an algorithm S
1
O
T
1
m: given the input z and the output r
z, it can simulate P
1’s view of the O
T
1
m execution and output {
S
1
O
T
1
m
(
z
;
r
z
)
} so that
(17)
{
S
1
O
T
1
m
(
z
;
r
z
)
}
≅
{
VIEW
1
O
T
1
m
(
z
,
{
r
i
}
i
=
1
,
…
,
m
)
}
.
Next, given(
q
P
;
r
z
), S
1 then simulates the remaining parts of P
1’s view in the real execution as follows.
Firstly, as in the real execution,S
1 extends the original health data from an n-vector q
P
=
(
q
P
1
,
…
,
q
P
n
) to an (
n
+
2
)-vector Q
P
=
(
q
P
1
,
…
,
q
P
n
,
q
P
,
n
+
1
,
q
P
,
n
+
2
), where q
P
,
n
+
1
=
-
(
1
/
2
)
∑
w
=
1
n
q
P
w
2 and q
P
,
n
+
2
=
1. Then, S
1 randomly chooses a password s
P
′
=
(
s
P
1
′
,
…
,
s
P
k
′
) and then generates a k
×
(
n
+
2
) matrix
(18)
B
P
′
=
[
b
11
′
⋯
b
1
,
n
+
2
′
⋮
⋮
b
k
1
′
⋯
b
k
,
n
+
2
′
]
,
where ∑
u
=
1
k
s
P
u
′
·
b
u
w
′
=
1
,
w
=
1
,
…
,
n
+
2. By blinding Q
P using the matrix B
P
′, S
1 further extends Q
P to a matrix
(19)
M
P
′
=
[
b
11
′
·
q
P
1
⋯
b
1
,
n
+
2
′
·
q
P
,
n
+
2
⋮
⋮
b
k
1
′
·
q
P
1
⋯
b
k
,
n
+
2
′
·
q
P
,
n
+
2
]
.
ThenS
1 randomly selects m vectors, T
j
′
=
(
t
j
1
′
,
…
,
t
j
n
′
,
t
j
,
n
+
1
′
,
t
j
,
n
+
2
′
), t
j
,
n
+
1
′
=
1
,
t
j
,
n
+
2
′
=
-
(
1
/
2
)
∑
w
=
1
n
t
j
w
′
2
,
j
=
1
,
…
,
m, and for all j
=
1
,
…
,
m
,
j
≠
z
,
∑
w
=
1
n
(
q
P
w
-
t
z
w
′
)
2
<
∑
w
=
1
n
(
q
P
w
-
t
j
w
′
)
2; otherwise, S
1 reselects T
j
′
,
j
=
1
,
…
,
m. Afterwards, S
1 computes Λ
i
j
′
=
M
P
′
·
(
T
i
′
-
T
j
′
)
T
,
i
,
j
=
1
,
…
,
m
,
i
≠
j. Thus, for i
,
j
=
1
,
…
,
m
,
i
≠
j
,
Λ
i
j
=
s
P
′
·
Λ
i
j
′
=
∑
w
=
1
n
+
2
q
P
w
·
(
t
i
w
′
-
t
j
w
′
).
Therefore, we have(20)
Λ
i
j
=
∑
w
=
1
n
+
2
‍
q
P
w
·
t
i
w
′
-
∑
w
=
1
n
+
2
‍
q
P
w
·
t
j
w
′
=
(
∑
w
=
1
n
‍
q
P
w
·
t
i
w
′
+
q
P
,
n
+
1
·
t
i
,
n
+
1
′
+
q
P
,
n
+
2
·
t
i
,
n
+
2
′
)
-
(
∑
w
=
1
n
‍
q
P
w
·
t
j
w
′
+
q
P
,
n
+
1
·
t
j
,
n
+
1
′
+
q
P
,
n
+
2
·
t
j
,
n
+
2
′
)
=
(
∑
w
=
1
n
‍
q
P
w
·
t
i
w
′
+
q
P
,
n
+
1
+
t
i
,
n
+
2
′
)
-
(
∑
w
=
1
n
‍
q
P
w
·
t
j
w
′
+
q
P
,
n
+
1
+
t
j
,
n
+
2
′
)
=
(
∑
w
=
1
n
‍
q
P
w
·
t
i
w
′
-
1
2
∑
w
=
1
n
‍
q
P
w
2
-
1
2
∑
w
=
1
n
‍
t
i
w
′
2
)
-
(
∑
w
=
1
n
‍
q
P
w
·
t
j
w
′
-
1
2
∑
w
=
1
n
‍
q
P
w
2
-
1
2
∑
w
=
1
n
‍
t
j
w
′
2
)
=
1
2
[
∑
w
=
1
n
‍
(
q
P
w
-
t
j
w
′
)
2
-
∑
w
=
1
n
‍
(
q
P
w
-
t
i
w
′
)
2
]
=
1
2
(
dis
t
q
P
↔
t
j
′
2
-
dis
t
q
P
↔
t
i
′
2
)
.
Since for allj
=
1
,
…
,
m
,
j
≠
z, we have ∑
w
=
1
n
(
q
P
w
-
t
z
w
′
)
2
<
∑
w
=
1
n
(
q
P
w
-
t
j
w
′
)
2. Obviously, for all j
=
1
,
…
,
m
,
j
≠
z, Λ
z
j
=
(
1
/
2
)
(
dist
⁡
q
P
↔
t
j
′
2
-
dist
⁡
q
P
↔
t
z
′
2
)
>
0 and t
z
,
z
∈
{
1
,
…
,
m
}, is the trait vector of the diagnosed disease. The report r
z corresponding to the trait vector t
z is the diagnosed report, which matches the relationship in the real execution.
Now,S
1 can output the simulated view,
(21)
{
S
1
(
q
P
;
r
z
)
}
=
{
q
P
,
s
P
′
,
B
P
′
,
{
Λ
i
j
′
}
i
,
j
=
1
,
…
,
m
,
i
≠
j
,
{
S
1
OT
1
m
(
z
;
r
z
)
}
,
r
z
}
.
Sinces
P
′ and B
P
′ are randomly chosen and ∑
u
=
1
k
s
P
u
′
·
b
u
w
′
=
1
,
w
=
1
,
…
,
n
+
2, as s
P and B
P in the real view {
VIEW
1
(
q
p
,
{
d
i
}
i
=
1
,
…
,
m
)
}. Due to the randomness and relationship, it is easy to find that (
s
P
′
,
B
P
′
) is indistinguishable to (
s
P
,
B
P
). From the construction process of {
Λ
i
j
′
}
i
,
j
=
1
,
…
,
m
,
i
≠
j, it is obvious to conclude that {
Λ
i
j
′
}
i
,
j
=
1
,
…
,
m
,
i
≠
j is indistinguishable to the set {
Δ
i
j
′
}
i
,
j
=
1
,
…
,
m
,
i
≠
j. Combined with (17), we have
(22)
{
S
1
(
q
P
;
r
z
)
}
≅
{
VIEW
1
(
q
p
,
{
d
i
}
i
=
1
,
…
,
m
)
}
.


## 5.1. Correctness

In this aspect, we follow the steps of our scheme and make sure that the patient indeed finds out the most possible disease from the disease database of the hospital using his health data by comparing Euclidean distances.Following the scheme, we can see that the patient transforms the health data in two steps. Firstly, he extends his original health data from ann-vector q
P
=
(
q
P
1
,
…
,
q
P
n
) to an (
n
+
2
)-vector Q
P
=
(
q
P
1
,
…
,
q
P
n
,
q
P
,
n
+
1
,
q
P
,
n
+
2
), where q
P
,
n
+
1
=
-
(
1
/
2
)
∑
w
=
1
n
q
P
w
2 and q
P
,
n
+
2
=
1 and then blinds and extends Q
P using the matrix B
P to a matrix(7)
M
P
=
[
b
11
·
q
P
1
⋯
b
1
,
n
+
2
·
q
P
,
n
+
2
⋮
⋮
b
k
1
·
q
P
1
⋯
b
k
,
n
+
2
·
q
P
,
n
+
2
]
.
On the other hand, the MD-ATM randomly selects two trait vectors t
i
=
(
t
i
1
,
…
,
t
i
n
) and t
j
=
(
t
j
1
,
…
,
t
j
n
) and, respectively, extends them to (
n
+
2
)-vectors T
i
=
(
t
i
1
,
…
,
t
i
n
,
t
i
,
n
+
1
,
t
i
,
n
+
2
) and T
j
=
(
t
j
1
,
…
,
t
j
n
,
t
j
,
n
+
1
,
t
j
,
n
+
2
), where t
i
,
n
+
1
=
1
,
t
i
,
n
+
2
=
-
(
1
/
2
)
∑
w
=
1
n
t
i
w
2 and t
j
,
n
+
1
=
1
,
t
j
,
n
+
2
=
-
(
1
/
2
)
∑
w
=
1
n
t
j
w
2. After receiving M
P, for i
,
j
=
1
,
…
,
m
,
i
≠
j, the MD-ATM computes
(8)
Δ
i
j
′
=
M
P
·
(
T
i
-
T
j
)
T
=
[
b
11
·
q
P
1
⋯
b
1
,
n
+
2
·
q
P
,
n
+
2
⋮
⋮
b
k
1
·
q
P
1
⋯
b
k
,
n
+
2
·
q
P
,
n
+
2
]
·
[
t
i
1
-
t
j
1
⋮
t
i
,
n
+
2
-
t
j
,
n
+
2
]
.After receiving the returned messageΔ
i
j
′, for i
,
j
=
1
,
…
,
m
,
i
≠
j, P uses PMDD to compute
(9)
Δ
i
j
=
s
P
·
Δ
i
j
′
=
s
P
·
M
P
·
(
T
i
-
T
j
)
T
=
(
s
P
1
,
…
,
s
P
k
)
·
[
b
11
·
q
P
1
⋯
b
1
,
n
+
2
·
q
P
,
n
+
2
⋮
⋮
b
k
1
·
q
P
1
⋯
b
k
,
n
+
2
·
q
P
,
n
+
2
]
·
[
t
i
1
-
t
j
1
⋮
t
i
,
n
+
2
-
t
j
,
n
+
2
]
=
∑
u
=
1
k
‍
s
P
u
·
b
u
1
·
q
P
1
·
(
t
i
1
-
t
j
1
)
+
⋯
+
∑
u
=
1
k
‍
s
P
u
·
b
u
,
n
+
2
·
q
P
,
n
+
2
·
(
t
i
,
n
+
2
-
t
j
,
n
+
2
)
=
∑
w
=
1
n
+
2
‍
q
P
w
·
(
t
i
w
-
t
j
w
)
.
Thus, we have
(10)
Δ
i
j
=
∑
w
=
1
n
+
2
‍
q
P
w
·
t
i
w
-
∑
w
=
1
n
+
2
‍
q
P
w
·
t
j
w
=
(
∑
w
=
1
n
‍
q
P
w
·
t
i
w
+
q
P
,
n
+
1
·
t
i
,
n
+
1
+
q
P
,
n
+
2
·
t
i
,
n
+
2
)
-
(
∑
w
=
1
n
‍
q
P
w
·
t
j
w
+
q
P
,
n
+
1
·
t
j
,
n
+
1
+
q
P
,
n
+
2
·
t
j
,
n
+
2
)
=
(
∑
w
=
1
n
‍
q
P
w
·
t
i
w
+
q
P
,
n
+
1
+
t
i
,
n
+
2
)
-
(
∑
w
=
1
n
‍
q
P
w
·
t
j
w
+
q
P
,
n
+
1
+
t
j
,
n
+
2
)
=
(
∑
w
=
1
n
‍
q
P
w
·
t
i
w
-
1
2
∑
w
=
1
n
‍
q
P
w
2
-
1
2
∑
w
=
1
n
‍
t
i
w
2
)
-
(
∑
w
=
1
n
‍
q
P
w
·
t
j
w
-
1
2
∑
w
=
1
n
‍
q
P
w
2
-
1
2
∑
w
=
1
n
‍
t
j
w
2
)
=
1
2
[
∑
w
=
1
n
‍
(
q
P
w
-
t
j
w
)
2
-
∑
w
=
1
n
‍
(
q
P
w
-
t
i
w
)
2
]
=
1
2
(
dis
t
q
P
↔
t
j
2
-
dis
t
q
P
↔
t
i
2
)
.Obviously, if for allj
=
1
,
…
,
m
,
j
≠
z, Δ
z
j
=
(
1
/
2
)
(
dist
⁡
q
P
↔
t
j
2
-
dist
⁡
q
P
↔
t
z
2
)
>
0, then t
z
,
z
∈
{
1
,
…
,
m
}, is the trait vector of the diagnosed disease. The report r
z corresponding to the trait vector t
z is the diagnosed report. Taking the index z as the input of the following OT
1
m protocol, the patient can finally get the disease report r
z from the set (
r
1
,
r
2
,
…
,
r
m
) of the database.Therefore, our scheme is correct.


## 5.2. Security

In this subsection, we strictly prove the security of our scheme. From the whole process, we can specify that the two parties in our system are the patientP and the hospital. They cooperate to compute the function f
(
q
P
,
(
d
1
,
d
2
,
…
,
d
m
)
)
=
r
z, where r
z is the disease diagnostic report corresponding to the disease d
z and the distance dist
⁡
q
p
↔
t
z satisfies the condition dist
⁡
q
p
↔
t
z
2
=
min
⁡
{
dist
⁡
q
p
↔
t
j
2
}
j
=
1
,
…
,
m. As mentioned in Section 3, we should achieve two security goals, that is, keeping both parties’ inputs private. We apply the real-ideal simulation paradigm to prove that our scheme has achieved the two goals in the scenarios of semihonest adversaries assuming the OT
1
m protocol we used is secure.Theory 1.
Our privacy-preserving self-helped medical diagnosis scheme is secure against semihonest adversaries if the
OT
1
m
protocol is secure.Proof.
Notice that the view ofP
i, {
VIEW
i
(
q
p
,
{
d
1
,
…
,
d
m
}
)
}
i
=
1,2, in the real execution consists of three parts, the private input, random tape, and the messages received from the other party including the output. Therefore, we can get the views of P
1 and P
2, respectively, in the real execution as follows:
(11)
{
VIE
W
1
(
q
p
,
{
d
i
}
i
=
1
,
…
,
m
)
}
=
{
q
P
,
s
P
,
B
P
,
{
Δ
i
j
′
}
i
,
j
=
1
,
…
,
m
,
i
≠
j
,
{
VIEW
1
O
T
1
m
(
z
,
{
r
i
}
i
=
1
,
…
,
m
)
}
,
r
z
q
P
,
s
P
,
B
P
,
{
Δ
i
j
′
}
i
,
j
=
1
,
…
,
m
,
i
≠
j
}
;
(12)
{
VIE
W
2
(
q
p
,
{
d
i
}
i
=
1
,
…
,
m
)
}
=
{
{
d
i
}
i
=
1
,
…
,
m
,
M
P
,
{
VIEW
2
O
T
1
m
(
z
,
{
r
i
}
i
=
1
,
…
,
m
)
}
,
λ
}
,
where {
VIE
W
1
OT
1
m
(
z
,
{
r
i
}
i
=
1
,
…
,
m
)
} and {
VIE
W
2
O
T
1
m
(
z
,
{
r
i
}
i
=
1
,
…
,
m
)
} are the views produced in the execution of O
T
1
m protocol.
From the definition of security, we need to construct the probabilistic polynomial-time algorithmS
1
/
S
2 so that given the input and output of the patient P
1/the hospital P
2, (
q
P
;
r
z
)
/
(
{
d
i
}
i
=
1
,
…
,
m
;
λ
), it can output a simulated view {
S
1
(
q
P
;
r
z
)
}
/
{
S
2
(
{
d
i
}
i
=
1
,
…
,
m
;
λ
)
}, which is indistinguishable to the view {
VIEW
1
(
q
p
,
{
d
i
}
i
=
1
,
…
,
m
)
}/{
VIEW
2
(
q
p
,
{
d
i
}
i
=
1
,
…
,
m
)
} in the real execution of the scheme; that is,
(13)
{
S
1
(
q
P
;
r
z
)
}
≅
{
VIEW
1
(
q
p
,
{
d
i
}
i
=
1
,
…
,
m
)
}
,
{
S
2
(
{
d
i
}
i
=
1
,
…
,
m
;
λ
)
}
≅
{
VIEW
2
(
q
p
,
{
d
i
}
i
=
1
,
…
,
m
)
}
.
In the following discussion, we follow the real-ideal simulation paradigm to construct such probabilistic polynomial-time algorithmsS
1
,
S
2. We separately prove the case when P
2 is semihonest and when P
1 is semihonest.
Case
1 (P
2 is semihonest). In this case, we only need to construct a simulator S
2 so that, given P
2’s input {
d
i
}
i
=
1
,
…
,
m and output λ, S
2 can simulate P
2’s view in the real execution presented above as (12).
Firstly, since we assume that theO
T
1
m protocol used in our scheme is secure and can be taken as a black-box, there exists an algorithm S
2
O
T
1
m: given the input {
r
i
}
i
=
1
,
…
,
m and the output λ, it can simulate P
2’s view of the O
T
1
m execution and output {
S
2
O
T
1
m
(
{
r
i
}
i
=
1
,
…
,
m
;
λ
)
} so that
(14)
{
S
2
O
T
1
m
(
{
r
i
}
i
=
1
,
…
,
m
;
λ
)
}
≅
{
VIEW
2
O
T
1
m
(
z
,
{
r
i
}
i
=
1
,
…
,
m
)
}
.
Next, notice thatS
2 is given (
{
d
i
}
i
=
1
,
…
,
m
;
λ
); it can easily simulate the remaining parts of (12) by randomly choosing a k
×
(
n
+
2
) matrix M which is indistinguishable to the blinded matrix M
P. Then, S
2 outputs the simulated view,
(15)
{
S
2
(
{
d
i
}
i
=
1
,
…
,
m
;
λ
)
}
=
{
{
d
i
}
i
=
1
,
…
,
m
,
M
,
{
S
2
O
T
1
m
(
{
r
i
}
i
=
1
,
…
,
m
;
λ
)
}
,
λ
}
.
Obviously, we can conclude that(16)
{
S
2
(
{
d
i
}
i
=
1
,
…
,
m
;
λ
)
}
≅
{
VIEW
2
(
q
p
,
{
d
i
}
i
=
1
,
…
,
m
)
}
.
Case
2 (P
1 is semihonest). Similar to Case 1, we only need to construct a simulator S
1 so that given P
1’s input q
P and output r
z, S
1 can simulate P
1’s view in the real execution presented above as (11).
As discussed above, since theO
T
1
m protocol is secure, there exists an algorithm S
1
O
T
1
m: given the input z and the output r
z, it can simulate P
1’s view of the O
T
1
m execution and output {
S
1
O
T
1
m
(
z
;
r
z
)
} so that
(17)
{
S
1
O
T
1
m
(
z
;
r
z
)
}
≅
{
VIEW
1
O
T
1
m
(
z
,
{
r
i
}
i
=
1
,
…
,
m
)
}
.
Next, given(
q
P
;
r
z
), S
1 then simulates the remaining parts of P
1’s view in the real execution as follows.
Firstly, as in the real execution,S
1 extends the original health data from an n-vector q
P
=
(
q
P
1
,
…
,
q
P
n
) to an (
n
+
2
)-vector Q
P
=
(
q
P
1
,
…
,
q
P
n
,
q
P
,
n
+
1
,
q
P
,
n
+
2
), where q
P
,
n
+
1
=
-
(
1
/
2
)
∑
w
=
1
n
q
P
w
2 and q
P
,
n
+
2
=
1. Then, S
1 randomly chooses a password s
P
′
=
(
s
P
1
′
,
…
,
s
P
k
′
) and then generates a k
×
(
n
+
2
) matrix
(18)
B
P
′
=
[
b
11
′
⋯
b
1
,
n
+
2
′
⋮
⋮
b
k
1
′
⋯
b
k
,
n
+
2
′
]
,
where ∑
u
=
1
k
s
P
u
′
·
b
u
w
′
=
1
,
w
=
1
,
…
,
n
+
2. By blinding Q
P using the matrix B
P
′, S
1 further extends Q
P to a matrix
(19)
M
P
′
=
[
b
11
′
·
q
P
1
⋯
b
1
,
n
+
2
′
·
q
P
,
n
+
2
⋮
⋮
b
k
1
′
·
q
P
1
⋯
b
k
,
n
+
2
′
·
q
P
,
n
+
2
]
.
ThenS
1 randomly selects m vectors, T
j
′
=
(
t
j
1
′
,
…
,
t
j
n
′
,
t
j
,
n
+
1
′
,
t
j
,
n
+
2
′
), t
j
,
n
+
1
′
=
1
,
t
j
,
n
+
2
′
=
-
(
1
/
2
)
∑
w
=
1
n
t
j
w
′
2
,
j
=
1
,
…
,
m, and for all j
=
1
,
…
,
m
,
j
≠
z
,
∑
w
=
1
n
(
q
P
w
-
t
z
w
′
)
2
<
∑
w
=
1
n
(
q
P
w
-
t
j
w
′
)
2; otherwise, S
1 reselects T
j
′
,
j
=
1
,
…
,
m. Afterwards, S
1 computes Λ
i
j
′
=
M
P
′
·
(
T
i
′
-
T
j
′
)
T
,
i
,
j
=
1
,
…
,
m
,
i
≠
j. Thus, for i
,
j
=
1
,
…
,
m
,
i
≠
j
,
Λ
i
j
=
s
P
′
·
Λ
i
j
′
=
∑
w
=
1
n
+
2
q
P
w
·
(
t
i
w
′
-
t
j
w
′
).
Therefore, we have(20)
Λ
i
j
=
∑
w
=
1
n
+
2
‍
q
P
w
·
t
i
w
′
-
∑
w
=
1
n
+
2
‍
q
P
w
·
t
j
w
′
=
(
∑
w
=
1
n
‍
q
P
w
·
t
i
w
′
+
q
P
,
n
+
1
·
t
i
,
n
+
1
′
+
q
P
,
n
+
2
·
t
i
,
n
+
2
′
)
-
(
∑
w
=
1
n
‍
q
P
w
·
t
j
w
′
+
q
P
,
n
+
1
·
t
j
,
n
+
1
′
+
q
P
,
n
+
2
·
t
j
,
n
+
2
′
)
=
(
∑
w
=
1
n
‍
q
P
w
·
t
i
w
′
+
q
P
,
n
+
1
+
t
i
,
n
+
2
′
)
-
(
∑
w
=
1
n
‍
q
P
w
·
t
j
w
′
+
q
P
,
n
+
1
+
t
j
,
n
+
2
′
)
=
(
∑
w
=
1
n
‍
q
P
w
·
t
i
w
′
-
1
2
∑
w
=
1
n
‍
q
P
w
2
-
1
2
∑
w
=
1
n
‍
t
i
w
′
2
)
-
(
∑
w
=
1
n
‍
q
P
w
·
t
j
w
′
-
1
2
∑
w
=
1
n
‍
q
P
w
2
-
1
2
∑
w
=
1
n
‍
t
j
w
′
2
)
=
1
2
[
∑
w
=
1
n
‍
(
q
P
w
-
t
j
w
′
)
2
-
∑
w
=
1
n
‍
(
q
P
w
-
t
i
w
′
)
2
]
=
1
2
(
dis
t
q
P
↔
t
j
′
2
-
dis
t
q
P
↔
t
i
′
2
)
.
Since for allj
=
1
,
…
,
m
,
j
≠
z, we have ∑
w
=
1
n
(
q
P
w
-
t
z
w
′
)
2
<
∑
w
=
1
n
(
q
P
w
-
t
j
w
′
)
2. Obviously, for all j
=
1
,
…
,
m
,
j
≠
z, Λ
z
j
=
(
1
/
2
)
(
dist
⁡
q
P
↔
t
j
′
2
-
dist
⁡
q
P
↔
t
z
′
2
)
>
0 and t
z
,
z
∈
{
1
,
…
,
m
}, is the trait vector of the diagnosed disease. The report r
z corresponding to the trait vector t
z is the diagnosed report, which matches the relationship in the real execution.
Now,S
1 can output the simulated view,
(21)
{
S
1
(
q
P
;
r
z
)
}
=
{
q
P
,
s
P
′
,
B
P
′
,
{
Λ
i
j
′
}
i
,
j
=
1
,
…
,
m
,
i
≠
j
,
{
S
1
OT
1
m
(
z
;
r
z
)
}
,
r
z
}
.
Sinces
P
′ and B
P
′ are randomly chosen and ∑
u
=
1
k
s
P
u
′
·
b
u
w
′
=
1
,
w
=
1
,
…
,
n
+
2, as s
P and B
P in the real view {
VIEW
1
(
q
p
,
{
d
i
}
i
=
1
,
…
,
m
)
}. Due to the randomness and relationship, it is easy to find that (
s
P
′
,
B
P
′
) is indistinguishable to (
s
P
,
B
P
). From the construction process of {
Λ
i
j
′
}
i
,
j
=
1
,
…
,
m
,
i
≠
j, it is obvious to conclude that {
Λ
i
j
′
}
i
,
j
=
1
,
…
,
m
,
i
≠
j is indistinguishable to the set {
Δ
i
j
′
}
i
,
j
=
1
,
…
,
m
,
i
≠
j. Combined with (17), we have
(22)
{
S
1
(
q
P
;
r
z
)
}
≅
{
VIEW
1
(
q
p
,
{
d
i
}
i
=
1
,
…
,
m
)
}
.


## 6. Conclusions

In this paper, we consider the problem of how to securely make diagnosis without leaking patient’s health data, diagnosed result, and hospital’s disease database in wireless sensor networks. By applying the idea of secure two-party computation and the technology of oblivious transfer, we propose a privacy-preserving self-helped medical diagnosis scheme so that patients can privately diagnose themselves by inserting a health card into a self-helped MD-ATM to obtain the diagnostic report just like drawing money from a bank ATM. We also have a detailed analysis about the correctness and further strictly prove the security following the real-idea simulation paradigm. We expect to provide people another perspective on future medical care.



---

*Source: 214841-2014-07-14.xml*