# An Efficient Online Multiparty Interactive Medical Prediagnosis Scheme with Privacy Protection

Authors: Qiuyue Zhang; Xiao Zheng; Xiujun Wang
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Medical prediagnosis systems are now available online to give users quick and preliminary diagnosis information. The need for such a system has become particularly evident in areas with insufficient health professionals. Due to the privacy of patient medical information and the sensitivity of cloud diagnosis models, it is necessary to protect the security of data, models, and communications. These existing diagnosis systems can hardly provide a satisfied diagnosis accuracy while ensuring comprehensive security and high efficiency. In order to solve these problems, we proposed Relief-k minimum Wasserstein distance (Relief-kMW) classification method, which combined data encryption and BLS signature to form a privacy-preserving efficient online multiparty interactive medical prediagnostic scheme (OMPD). Theoretical analysis shows our OMPD effectively provides high-precision prediagnosis services. Extensive experimental results demonstrate that OMPD not only greatly improves the diagnostic accuracy but also reduces the computational and communication overhead.


---

## Body

## 1. Introduction

With the rapid development of mobile Internet, wearable devices, and intelligent Internet of Things, online medical prediagnosis systems that can provide prediagnosis services and medical advice anytime and anywhere have received extensive research attention due to their importance. Typically, an online medical prediagnosis system needs to provide a high degree of diagnostic accuracy along with a strong level of privacy protection. In order to achieve these two goals at the same time or at least maintain an acceptable balance between the two goals, multiple factors need to be considered. Firstly, a good classifier must be carefully selected from the existing classification algorithm library to achieve high diagnostic accuracy. And the classifier must be refined to capture the peculiar nature of the online diagnostic problem. The existing literature already provides us some candidate algorithms such as random forest [1], neural network [2], and other methods [3–5], and they have been widely used in medical diagnosis. However, in general, these algorithms often yield either an interminable training and response time or an unbearably low diagnostic accuracy and privacy protection. Therefore, we need to reinvestigate the potential of existing classifiers and then select the one that can be modified to offer the experimentally best performances in terms of computational overhead and privacy protection.Secondly, in order to keep the medical data used by an online medical prediagnosis system well protected from malicious users who may attach and profit from these data, we need to choose appropriate privacy protection schemes [6–15] for security needs. There are three kinds of privacy protection schemes: anonymity protection, differential privacy protection, and homomorphic encryption. The anonymity protection (such as k-anonymity [9] and l-diversity [10]) simply erases users’ private information which may lead to a decreased diagnostic accuracy as the deleted data cannot be used. The differential privacy protection [11–13] protects users’ privacy by adding noise to completely obfuscate the query response. However, these random noise can cover the critical information that are needed to boost the diagnostic accuracy. Different from the prior two schemes, homomorphic encryption [14, 15] can strictly protect privacy without destroying the original data. However, the encryption and decryption process of the homomorphic encrption usually requires huge computational overhead. Therefore, to have homomorphic encryption work for the scenarios of online medical prediagnosis, it still requires us considerable effort to bring the computational burden of the homomorphic encryption down considerably without sacrificing the protection strength very much.In addition, a multiparty interactive system usually needs to be aware of the problem of communication security. This becomes particularly essential for online medical prediagnosis scenarios with vulnerable and unsecure communication channels. It is possible that the transmitted messages between the two parties can be eavesdropped malicious attackers. Hence, we need an efficient information security scheme for online medical prediagnosis system to protect the communication. For this target, there are some existing methods [16–19], such as secure multiparty protocol, digital signature, and some other data encryption methods. In this paper, we choose digital signature information authentication scheme. Because it can ensure that only the correct recipient can obtain the communication information through its private key, it can effectively ensure that the communication content is not maliciously stolen or tampered with. The BLS short signature [16] is considered to be one of the most effective methods. This technology authenticates and confirms users’ identity information. It can prevent others from fraudulently using users’ identity information.Based on the above three points, it is difficult to combine the classification method with the privacy protection method, while saving computation and communication overhead to achieve high system efficiency. In this paper, we proposed an online multiparty interactive medical prediagnosis service scheme with high efficiency, high precision, and privacy protection, called OMPD. It can protect the private information of medical users, a large of medical instances of the hospital and the diagnosis model in the cloud. And the users can obtain online medical prediagnosis services when the original data is not available in the cloud. The main contributions of this paper are as follows:(1)
OMPD can provide high-precision prediagnosis services. We introduced a data preprocessing method (simple data encryption and some conversion) based on the newly proposed Relief-kMW classifier, and these data processing operations would not change the original classification accuracy of the classifier. In order to verify the classification accuracy of OMPD, we conducted accuracy analysis and experiments on two real data sets on the UCI machine learning library (http://archive.ics.uci.edu/ml). Experimental results showed that OMPD can provide high-precision services(2)
OMPD is a three-party interactive system that can provide medical prediagnosis services with full-process protection. By preprocessing medical data and applying BLS signatures to communication information, the security of private information of medical users, the instance of the hospital’s database, the diagnostic model in the cloud, and the interaction can be guaranteedThe structure of our work is as follows: Section2 introduces some related works, and Section 3 introduces the Relief-kMW classification method and BLS signatures. Section 4 introduces the entire detailed process of the OMPD. Section 5 carries out accuracy and safety analysis. The experimental evaluation is carried out in Section 6. Finally, we conclude in Section 7.


## 2. Related Works

In recent years, more and more people have paid attention to the efficiency and privacy safety of medical diagnosis services, and many solutions [20–25] have been proposed. In view of the privacy and security issues in online medical prediagnosis services, homomorphic encryption technology can well protect the private information in medical data and is widely used in various medical diagnosis schemes. For example, literature [22] constructed three classification protocols based on the Paillier cryptosystem to protect the security of data collected from medical users and service providers. Literature [23] developed an automatic diagnosis system for privacy protection. The remote server classified the biomedical signal provided by the client without obtaining any information about the signal itself and the final result of the classification. Liu et al. [24] proposed a privacy-preserving patient-centered clinical decision support system based on additive homomorphism to help clinicians assist in diagnosing patients’ disease risks. Hua et al. [25] proposed an efficient and privacy-preserving medical diagnosis framework, which outsourced the accurate diagnosis model to a cloud server in an encrypted manner based on partial decryption and security comparison technology to achieve the advantages of two-way ciphertext quantification. Since all encryption operations are based on homomorphic encryption, the huge computational overhead makes the system extremely inefficient, which is not suitable for online medical service scenarios.In addition, many online medical prediagnosis schemes based on various machine learning classification algorithms [26–33] adopt different privacy protection strategies. Wu et al. [27] designed a new efficient and privacy-preserving conditional unintentional transmission protocol. The literature [28] proposed a novel privacy protection biometric identification scheme, which improved efficiency by using the power of cloud computing. Zhang et al. [29] proposed a cloud-based privacy protection deep computing model to improve the efficiency of big data feature learning. Their schemes mainly protect the privacy information of users’ query vector, but do not protect the security of communication information and diagnostic models.Zhang et al. [32] proposed a disease prediction system (called PPDP) that used random matrices to construct new medical data encryption, disease learning, and disease prediction. Although the use of a single-layer perceptron makes the disease prediction stage simple and efficient, the accuracy of the prediagnosis is not high enough. And in the disease learning stage, constantly updating the weights until convergence would consume huge computation and communication overhead. At the same time, in this three-party interaction scenario, the users’ private information is directly transmitted without communication security. Zhu et al. [33] proposed an efficient and privacy-preserving medical primary diagnosis based on kNN (called EPDK). With lightweight multiparty random shielding and polynomial aggregation technology, users can ensure the security of their sensitive information in the online medical diagnosis. This is an interactive service in which only the user and the server participate. The diagnostic model of the server is based on the original medical data set. Medical data that is not encrypted or processed is vulnerable to attack or theft. In addition, the classification accuracy of EPDK is still not high enough. There are few schemes that provide comprehensive privacy protection, high-precision, and high-efficiency prediagnosis services.


## 3. Preliminaries

This section introduces the Relief-kMW classifier used by OMPD and the BLS signature technology to protect communication security.


### 3.1. Relief-kMW Classifier

The Relief-kMW classifier first needs to use the Relief algorithm [34] to obtain weight=w1,w2,⋯,wn, and then calculates the Relief-Wasserstein distance between the query vector X=x1,x2,⋯,xn and each medical instance Yj=y1j,y2j,⋯,ynj, j∈1,N in the database D, where n is the number of features in each vector, and N is the total number of data in the database. The specific steps are as follows:


#### 3.1.1. Relief Feature Weight Distribution Algorithm

Before the Relief-kMW classifier works, the weight of the feature is calculated according to the Relief feature weight distribution algorithm (as shown in Algorithm 1).Algorithm 1: Relief feature weight distribution algorithm.
Input: training data set D, sample sampling times m, feature setF=f1,f2,⋯,fn, which has n features in total.Output: feature weight weight=w1,w2,⋯,wn.1:The feature rights are reset to 0;2:forr=1 to m do3: Randomly select a sampleR;4: Find the nearest neighbor sampleH in the same class of R,and the nearest neighbor sampleM in different classes of R;5: fori=1 to n do6:wi=wi−diffi,R,H/m+diffi,R,M/m;7: end for8:end for9:returnweight.The functiondiffi,R,H in Algorithm 1 represents the difference between the sample R and the sample H on the i-th feature, and its formula is as follows:
(1)diffi,R,H=0,iffidiscreteandRi=HiRi−Himaxi−mini,ifficontinuous1,iffidiscreteandRi≠Hi.


#### 3.1.2. Relief-kMW Classification Method

After getting theweight, we perform the Relief-kMW classification method, which is similar to kNN, except that kNN uses Euclidean distance, and our method uses Relief-Wasserstein distance. First, we calculate the Relief-Wasserstein distance between the query vector X=x1,x2,⋯,xn and each instance Yj=y1j,y2j,⋯,ynj, j∈1,N in the database D, its definition as the following:
(2)θ0=0,θ1=θ0+w1×x1−y1,θ2=θ1+w2×x2−y2,⋯θn=θn−1+wn×xn−yn.Definition 1 (Relief-Wasserstein distance).
SupposeX=x1,x2,⋯,xn and Y=y1,y2,⋯,yn are two input samples, where n is the total number of features, θi is the iterative value of the difference between X and Y on each component, and weight=w1,w2,⋯,wn is the weight value of the corresponding features obtained by the Algorithm 1. Then, we calculate the followings:The Relief-Wasserstein distance betweenX and Y is
(3)RW=∑i=1nθi.Then, we select the closestk instances. At last, we use most of the classification results of these k instances as the final classification result. In fact, the choice of k value is not optimal in theory. It depends on data characteristics and classification requirements. Some articles [35] on the optimal theoretical value of k pointed out that the best choice of k for a given data set may also depend on many attributes of the data. They have carried out the selection experiment of k value under different applications for different specific data sets and selected the best k value for the application as much as possible.


### 3.2. BLS Signature

Suppose there is a large prime numberq and two cyclic groups G1 and G2, their orders are both q, and g is a generator of G1. Then, there is a mapping e:G1×G1⟶G2, for ∀a,b∈Zq⋆ and ∀u,v∈G1, and it has the following properties:
(4)ega,gb=egb,ga=eg,gab.(1)
Generate public keyDefinition 2 (BLS signature).
The bilinear parameter generator takes a safety parameterμ as input and outputs a 5-tuple q,g,G1,G2,e, where q is the prime number of μ, G1 and G2 are two cyclic groups of order q, and g is the generator of G1, e:G1×G1⟶G2 is a nondegenerate and effectively calculated bisexual mapping. The steps of BLS signature are as follows:The message sender randomly selects an integer as the private keySK and 0<SK<q−1, and then calculates the public key:
(5)PK=gSK.(2)
Create a signature. The sender creates a signature by performing the following operations on the messagem∈G1:(6)Sig=mSK.(3)
Verify the signature. After receiving the signature, the receiver performs the verification of the following formula, and the message content can be obtained after the verification is successful:(7)eg,Sig=?ePK,m.


## 3.1. Relief-kMW Classifier

The Relief-kMW classifier first needs to use the Relief algorithm [34] to obtain weight=w1,w2,⋯,wn, and then calculates the Relief-Wasserstein distance between the query vector X=x1,x2,⋯,xn and each medical instance Yj=y1j,y2j,⋯,ynj, j∈1,N in the database D, where n is the number of features in each vector, and N is the total number of data in the database. The specific steps are as follows:


### 3.1.1. Relief Feature Weight Distribution Algorithm

Before the Relief-kMW classifier works, the weight of the feature is calculated according to the Relief feature weight distribution algorithm (as shown in Algorithm 1).Algorithm 1: Relief feature weight distribution algorithm.
Input: training data set D, sample sampling times m, feature setF=f1,f2,⋯,fn, which has n features in total.Output: feature weight weight=w1,w2,⋯,wn.1:The feature rights are reset to 0;2:forr=1 to m do3: Randomly select a sampleR;4: Find the nearest neighbor sampleH in the same class of R,and the nearest neighbor sampleM in different classes of R;5: fori=1 to n do6:wi=wi−diffi,R,H/m+diffi,R,M/m;7: end for8:end for9:returnweight.The functiondiffi,R,H in Algorithm 1 represents the difference between the sample R and the sample H on the i-th feature, and its formula is as follows:
(1)diffi,R,H=0,iffidiscreteandRi=HiRi−Himaxi−mini,ifficontinuous1,iffidiscreteandRi≠Hi.


### 3.1.2. Relief-kMW Classification Method

After getting theweight, we perform the Relief-kMW classification method, which is similar to kNN, except that kNN uses Euclidean distance, and our method uses Relief-Wasserstein distance. First, we calculate the Relief-Wasserstein distance between the query vector X=x1,x2,⋯,xn and each instance Yj=y1j,y2j,⋯,ynj, j∈1,N in the database D, its definition as the following:
(2)θ0=0,θ1=θ0+w1×x1−y1,θ2=θ1+w2×x2−y2,⋯θn=θn−1+wn×xn−yn.Definition 1 (Relief-Wasserstein distance).
SupposeX=x1,x2,⋯,xn and Y=y1,y2,⋯,yn are two input samples, where n is the total number of features, θi is the iterative value of the difference between X and Y on each component, and weight=w1,w2,⋯,wn is the weight value of the corresponding features obtained by the Algorithm 1. Then, we calculate the followings:The Relief-Wasserstein distance betweenX and Y is
(3)RW=∑i=1nθi.Then, we select the closestk instances. At last, we use most of the classification results of these k instances as the final classification result. In fact, the choice of k value is not optimal in theory. It depends on data characteristics and classification requirements. Some articles [35] on the optimal theoretical value of k pointed out that the best choice of k for a given data set may also depend on many attributes of the data. They have carried out the selection experiment of k value under different applications for different specific data sets and selected the best k value for the application as much as possible.


## 3.1.1. Relief Feature Weight Distribution Algorithm

Before the Relief-kMW classifier works, the weight of the feature is calculated according to the Relief feature weight distribution algorithm (as shown in Algorithm 1).Algorithm 1: Relief feature weight distribution algorithm.
Input: training data set D, sample sampling times m, feature setF=f1,f2,⋯,fn, which has n features in total.Output: feature weight weight=w1,w2,⋯,wn.1:The feature rights are reset to 0;2:forr=1 to m do3: Randomly select a sampleR;4: Find the nearest neighbor sampleH in the same class of R,and the nearest neighbor sampleM in different classes of R;5: fori=1 to n do6:wi=wi−diffi,R,H/m+diffi,R,M/m;7: end for8:end for9:returnweight.The functiondiffi,R,H in Algorithm 1 represents the difference between the sample R and the sample H on the i-th feature, and its formula is as follows:
(1)diffi,R,H=0,iffidiscreteandRi=HiRi−Himaxi−mini,ifficontinuous1,iffidiscreteandRi≠Hi.


## 3.1.2. Relief-kMW Classification Method

After getting theweight, we perform the Relief-kMW classification method, which is similar to kNN, except that kNN uses Euclidean distance, and our method uses Relief-Wasserstein distance. First, we calculate the Relief-Wasserstein distance between the query vector X=x1,x2,⋯,xn and each instance Yj=y1j,y2j,⋯,ynj, j∈1,N in the database D, its definition as the following:
(2)θ0=0,θ1=θ0+w1×x1−y1,θ2=θ1+w2×x2−y2,⋯θn=θn−1+wn×xn−yn.Definition 1 (Relief-Wasserstein distance).
SupposeX=x1,x2,⋯,xn and Y=y1,y2,⋯,yn are two input samples, where n is the total number of features, θi is the iterative value of the difference between X and Y on each component, and weight=w1,w2,⋯,wn is the weight value of the corresponding features obtained by the Algorithm 1. Then, we calculate the followings:The Relief-Wasserstein distance betweenX and Y is
(3)RW=∑i=1nθi.Then, we select the closestk instances. At last, we use most of the classification results of these k instances as the final classification result. In fact, the choice of k value is not optimal in theory. It depends on data characteristics and classification requirements. Some articles [35] on the optimal theoretical value of k pointed out that the best choice of k for a given data set may also depend on many attributes of the data. They have carried out the selection experiment of k value under different applications for different specific data sets and selected the best k value for the application as much as possible.


## 3.2. BLS Signature

Suppose there is a large prime numberq and two cyclic groups G1 and G2, their orders are both q, and g is a generator of G1. Then, there is a mapping e:G1×G1⟶G2, for ∀a,b∈Zq⋆ and ∀u,v∈G1, and it has the following properties:
(4)ega,gb=egb,ga=eg,gab.(1)
Generate public keyDefinition 2 (BLS signature).
The bilinear parameter generator takes a safety parameterμ as input and outputs a 5-tuple q,g,G1,G2,e, where q is the prime number of μ, G1 and G2 are two cyclic groups of order q, and g is the generator of G1, e:G1×G1⟶G2 is a nondegenerate and effectively calculated bisexual mapping. The steps of BLS signature are as follows:The message sender randomly selects an integer as the private keySK and 0<SK<q−1, and then calculates the public key:
(5)PK=gSK.(2)
Create a signature. The sender creates a signature by performing the following operations on the messagem∈G1:(6)Sig=mSK.(3)
Verify the signature. After receiving the signature, the receiver performs the verification of the following formula, and the message content can be obtained after the verification is successful:(7)eg,Sig=?ePK,m.


## 4. OMPD Scheme

Our OMPD includes three entities: the hospital, the cloud, and the users. And it consists of six stages: initialization, query generation, query processing, prediagnosis service, query result analysis, and result acquisition. Figure1 shows the flow of the OMPD. For ease of expression, Table 1 gives the description of the notations used in the following sections.Figure 1
Architecture diagram of OMPD.Table 1
Descriptions of notations.
NotationDescriptiont1,t2,t3Safety parameters selected by the hospitalq,g,G1,G2,eParameters of the bilinear groupE,HashSecure asymmetric encryption algorithm and cryptographic hash functionPKH,PKU,PKCPublic keys for the hospital, the user, and the cloudSKH,SKU,SKCSecret keys for the hospital, the user, and the cloudSigH,SigU,SigCSignatures created by the hospital, the user, and the cloudL,lTotal number of disease labels and thelth disease labelDl,NlThe data subset to diseasel, the total number of data in DlnlThe number of features contained in each data inDlweightl,wliThe feature weight vector and theith component of weightlX,YljQuery vector and thejth data in DlIX,IYljThe vector obtained by feature weight distribution ofX,YljIIX,IIYljThe vector obtained by iterative transformation ofIX,IYljIIIX,IIIYljThe vector obtained by forward expansion ofIIX,IIYljEX,EYljThe vector obtained by encryption ofIIIX,IIIYljxi,Ixi,IIxi,IIxi,exiThe components ofX,IX,IIX,IIIX,EXylij,Iylij,IIylij,IIIylij,eylijThe components ofYlj,IYlj,IIYlj,IIIYlj,EYljp,aTwo large prime numbers chosen by the hospitalβ,γ,bi,bijRandom numbers chosen by the hospitalklThe number of nearest neighbors selected by relief-kMW classifier for disease lRWRelief-Wasserstein distance between two pieces of dataθIntermediate parameters when calculatingRWTSi,IDUTimestamp of thei-th moment and the user’s IDXQQuery request encrypted withPKH by the userQQuery vector encrypted withPKC by the hospitalR,RlPrediagnosis result and pre-diagnosis result encrypted withPKH by the cloudAlMedical advice given by the hospitalRAlPrediagnosis result and medical advice encrypted withPKU by the hospital


### 4.1. Initialization

The hospital first generates a bilinear parameterq,g,G1,G2,e. Then, the hospital uses a random number as private key SKH (SKH∈Zq⋆), calculates public key PKH=gSHH, and sets the parameters t1, t2, and t3, where t1>t2>t3. It needs to choose a secure asymmetric encryption algorithm E and encrypted hash function Hash, where Hash:0,1⋆⟶G1. The hospital securely saves its private key SKH as the master key and publishes system parameters q,g,G1,G2,e,t1,t2,t3,E,Hash.Suppose there is a medical data setDl=Ylj=yl1j,yl2j,⋯,ylnlj,j∈1,Nl,l∈1,L in the hospital database, these medical instances include L kinds of diseases, and each disease corresponds to a data subset Dl containing Nl data. For each Dl, the instance contains nl features. The hospital uses the Algorithm 1 to obtain the feature weight weightl=wl1,wl2,⋯,wlnl in each data subset Dl. The preprocessing of medical data is shown in Algorithm 2. The hospital selects two large prime numbers p and a and sets lenp=lent1, lena=lent2. Next, it chooses a large random number β and β∈Zp. Each medical instance Ylj=yl1j,yl2j,⋯,ylnlj,j∈1,Nl should successively perform vector feature weight distribution (to get the vector IYlj=Iyl1j,Iyl2j,⋯,Iylnlj,j∈1,Nl), vector value iterative transformation (to get the vector IIYlj=IIyl1j,IIyl2j,⋯,IIylnlj,j∈1,Nl), forward expansion (to get the vector IIIYlj=IIIyl1j,IIIyl2j,⋯,IIIylnl+2j, j∈1,Nl), and finally to get the processed medical vector EYlj=eyl1j,eyl2j,⋯,eylnl+2j, j∈1,Nl. The time complexity of Algorithm 2 is Onl.The hospital keeps the parametersp,a,bij secret and sends all preprocessed medical instances to the cloud. After obtaining the preprocessed medical instances, the cloud randomly selects part of the data as the test set to obtain the optimal kl value of the classifier for the diseases l. Then, the cloud can have the Relief-kMW classifier with the best value kl and many preprocessed medical instances received from the hospital.Algorithm 2: Preprocessing for medical instances.
Input: disease l, medical vector Ylj=yl1j,yl2j,⋯,ylnlj,j∈1,Nl (or X=x1,x2,⋯,xnl), feature weightvectorweightl=wl1,wl2,⋯,wlnl.Output: the preprocessed vector EYlj=eyl1j,eyl2j,⋯,eylnl+2j, j∈1,Nl (or EX=ex1,ex2,⋯,exnl+2).1: Generate two large prime numbersp,a and a random number β (or γ) and satisfy lenp=lent1,lena=lent2 and β∈Zp (or γ∈Zp);2: The feature weight is assigned to getIYlj=Iyl1j,Iyl2j,⋯,Iylnlj=wl1yl1j,wl2yl2j,⋯,wlnlylnlj,j∈1,Nl (or IX=Ix1,Ix2,⋯,Ixnl=wl1xl1,wl2xl2,⋯,wlnlxlnl);3: The vector value is iteratively transformed to getIIYlj=IIyl1j,IIyl2j,⋯,IIylnlj=wl1yl1j,wl1yl1j+wl2yl2j,⋯,wl1yl1j+wl2yl2j+⋯+wlnlylnlj, j∈1,Nl(orIIX=IIx1,IIx2,⋯,IIxnl=wl1xl1,wl1xl1+wl2xl2,⋯,wl1xl1+wl2xl2+⋯+wlnlxlnl);4: The vector is expanded forward to getIIIYlj=IIIyl1j,IIIyl2j,⋯,IIIylnl+2j=0,0,wl1yl1j,wl1yl1j+wl2yl2j,⋯,wl1yl1j+wl2yl2j+⋯+wlnlylnlj, j∈1,Nl(orIIIX=IIIx1,IIIx2,⋯,IIIxnl+2=0,0,wl1xl1,wl1xl1+wl2xl2,⋯,wl1xl1+wl2xl2+⋯+wlnlxlnl);5:fori=1 to nl+2 do6: Generate a random numberbij (or bi) and satisfy lenbijorbi=lent3;7: ifIIIylijorIIIxi≠0 do8:eylij=βa·IIIylij+bijmodp (or exi=γa·IIIxi+bimodp);9: else do10:eylij=β·bijmodp (or exi=γ·bimodp);11: end if12:end for13: returnEYlj,j∈1,Nl (or EX).


### 4.2. Query Generation

The user generates query vectorX=x1,x2,⋯,xnl. Then, the user uses the hospital’s public key PKH to encrypt the query vector to get XQ=EPKHlx1x2⋯xnl, where l is the disease that the user wants to query. Then, he (she) uses private key SKU to create a signature SigU=HashXQTS1SKU and then sends IDUXQSigUTS1 to the hospital.


### 4.3. Query Processing

After receiving theIDUXQSigUTS1 from the user, the hospital first needs to confirm the IDU, and then uses the following formula to verify the validity of the message:
(8)eg,SigU=?ePKU,HashXQTS1.If the equation is true, then the hospital performs Algorithm2. The processing method is the same as that of medical instances. The hospital selects a large random number γ, and γ∈Zp then performs vector features weight distribution (to get the vector IX=Ix1,Ix2,⋯,Ixnl), vector value iterative transformation (to get the vector IIX=IIx1,IIx2,⋯,IIxnl), and two-dimensional forward expansion (to get the vector IIIX=IIIx1,IIIx2,⋯,IIIxnl+2), and obtains the preprocessed query vector EX=ex1,ex2,⋯,exnl+2 after encryption.The hospital calculatesQ=EPKClβγex1ex2⋯exnl+2 and keeps the parameters p,a,bi secret. Then, it uses private key SKH to create a signature SigH=HashQTS2SKH and sends QSigHTS2 to the cloud.


### 4.4. Prediagnostic Service

After receivingQSigHTS2 from the hospital, the cloud verifies the validity of the message by using the following formula:
(9)eg,SigH=?ePKH,HashQTS2.If the above equation is true, the cloud performs the prediagnosis service algorithm. As shown in Algorithm3, the cloud finds the data subset Dl corresponding to the disease l and calculates the Relief-Wasserstein distance between EX and each preprocessed encrypted medical instance in Dl. Then, the cloud selects the kl instances with the smallest distance and takes most of the categories of these kl instances as the final prediagnosis result R. The time complexity of Algorithm 3 is ONlnl. The cloud keeps each RW, and computation rules secret. Then, it uses the hospital’s public key to calculate Rl=EPKHR and uses SKC to create a signature SigC=HashRlTS3SKC. Findly, the cloud sends RlSigCTS3 to the hospital.Algorithm 3: Prediagnosis service algorithm of the Relief-kMW classifier.
Input: the preprocessed query vector EX, β, γ, l and kl.Output: pre-diagnosis result R.1:EX=γ−1·EX;2:forj=1 to Nl do3: setRW=0;4: fori=1 to nl+2 do5:RW=RW+exi−β−1·eylij;6: end for7:end for8:Select thekl data with the smallest RW between the Nl data and the query vector, and use most of the classification results in the kldata as the pre-diagnostic resultR;9:returnR.


### 4.5. Query Result Analysis

After receivingRlSigCTS3 from the cloud, the hospital verifies the validity of the message by using the following formula:
(10)eg,SigC=?ePKC,HashRlTS3The prediagnosis resultR can be obtained if the equation holds. The hospital gives some advice Al for this result and calculates RAl=EPKURAl. Then, the hospital uses private key to create a signature SigH=HashRAlTS4SKH and sends RAlSigHTS4 to the user.


### 4.6. Result Acquisition

After receivingRAlSigHTS4 from the hospital, the user verifies the validity of the message by using the following formula:
(11)eg,SigH=?ePKH,HashRAlTS4If the equation holds, the user can obtain the pre-diagnosis resultR and the advice Al.


## 4.1. Initialization

The hospital first generates a bilinear parameterq,g,G1,G2,e. Then, the hospital uses a random number as private key SKH (SKH∈Zq⋆), calculates public key PKH=gSHH, and sets the parameters t1, t2, and t3, where t1>t2>t3. It needs to choose a secure asymmetric encryption algorithm E and encrypted hash function Hash, where Hash:0,1⋆⟶G1. The hospital securely saves its private key SKH as the master key and publishes system parameters q,g,G1,G2,e,t1,t2,t3,E,Hash.Suppose there is a medical data setDl=Ylj=yl1j,yl2j,⋯,ylnlj,j∈1,Nl,l∈1,L in the hospital database, these medical instances include L kinds of diseases, and each disease corresponds to a data subset Dl containing Nl data. For each Dl, the instance contains nl features. The hospital uses the Algorithm 1 to obtain the feature weight weightl=wl1,wl2,⋯,wlnl in each data subset Dl. The preprocessing of medical data is shown in Algorithm 2. The hospital selects two large prime numbers p and a and sets lenp=lent1, lena=lent2. Next, it chooses a large random number β and β∈Zp. Each medical instance Ylj=yl1j,yl2j,⋯,ylnlj,j∈1,Nl should successively perform vector feature weight distribution (to get the vector IYlj=Iyl1j,Iyl2j,⋯,Iylnlj,j∈1,Nl), vector value iterative transformation (to get the vector IIYlj=IIyl1j,IIyl2j,⋯,IIylnlj,j∈1,Nl), forward expansion (to get the vector IIIYlj=IIIyl1j,IIIyl2j,⋯,IIIylnl+2j, j∈1,Nl), and finally to get the processed medical vector EYlj=eyl1j,eyl2j,⋯,eylnl+2j, j∈1,Nl. The time complexity of Algorithm 2 is Onl.The hospital keeps the parametersp,a,bij secret and sends all preprocessed medical instances to the cloud. After obtaining the preprocessed medical instances, the cloud randomly selects part of the data as the test set to obtain the optimal kl value of the classifier for the diseases l. Then, the cloud can have the Relief-kMW classifier with the best value kl and many preprocessed medical instances received from the hospital.Algorithm 2: Preprocessing for medical instances.
Input: disease l, medical vector Ylj=yl1j,yl2j,⋯,ylnlj,j∈1,Nl (or X=x1,x2,⋯,xnl), feature weightvectorweightl=wl1,wl2,⋯,wlnl.Output: the preprocessed vector EYlj=eyl1j,eyl2j,⋯,eylnl+2j, j∈1,Nl (or EX=ex1,ex2,⋯,exnl+2).1: Generate two large prime numbersp,a and a random number β (or γ) and satisfy lenp=lent1,lena=lent2 and β∈Zp (or γ∈Zp);2: The feature weight is assigned to getIYlj=Iyl1j,Iyl2j,⋯,Iylnlj=wl1yl1j,wl2yl2j,⋯,wlnlylnlj,j∈1,Nl (or IX=Ix1,Ix2,⋯,Ixnl=wl1xl1,wl2xl2,⋯,wlnlxlnl);3: The vector value is iteratively transformed to getIIYlj=IIyl1j,IIyl2j,⋯,IIylnlj=wl1yl1j,wl1yl1j+wl2yl2j,⋯,wl1yl1j+wl2yl2j+⋯+wlnlylnlj, j∈1,Nl(orIIX=IIx1,IIx2,⋯,IIxnl=wl1xl1,wl1xl1+wl2xl2,⋯,wl1xl1+wl2xl2+⋯+wlnlxlnl);4: The vector is expanded forward to getIIIYlj=IIIyl1j,IIIyl2j,⋯,IIIylnl+2j=0,0,wl1yl1j,wl1yl1j+wl2yl2j,⋯,wl1yl1j+wl2yl2j+⋯+wlnlylnlj, j∈1,Nl(orIIIX=IIIx1,IIIx2,⋯,IIIxnl+2=0,0,wl1xl1,wl1xl1+wl2xl2,⋯,wl1xl1+wl2xl2+⋯+wlnlxlnl);5:fori=1 to nl+2 do6: Generate a random numberbij (or bi) and satisfy lenbijorbi=lent3;7: ifIIIylijorIIIxi≠0 do8:eylij=βa·IIIylij+bijmodp (or exi=γa·IIIxi+bimodp);9: else do10:eylij=β·bijmodp (or exi=γ·bimodp);11: end if12:end for13: returnEYlj,j∈1,Nl (or EX).


## 4.2. Query Generation

The user generates query vectorX=x1,x2,⋯,xnl. Then, the user uses the hospital’s public key PKH to encrypt the query vector to get XQ=EPKHlx1x2⋯xnl, where l is the disease that the user wants to query. Then, he (she) uses private key SKU to create a signature SigU=HashXQTS1SKU and then sends IDUXQSigUTS1 to the hospital.


## 4.3. Query Processing

After receiving theIDUXQSigUTS1 from the user, the hospital first needs to confirm the IDU, and then uses the following formula to verify the validity of the message:
(8)eg,SigU=?ePKU,HashXQTS1.If the equation is true, then the hospital performs Algorithm2. The processing method is the same as that of medical instances. The hospital selects a large random number γ, and γ∈Zp then performs vector features weight distribution (to get the vector IX=Ix1,Ix2,⋯,Ixnl), vector value iterative transformation (to get the vector IIX=IIx1,IIx2,⋯,IIxnl), and two-dimensional forward expansion (to get the vector IIIX=IIIx1,IIIx2,⋯,IIIxnl+2), and obtains the preprocessed query vector EX=ex1,ex2,⋯,exnl+2 after encryption.The hospital calculatesQ=EPKClβγex1ex2⋯exnl+2 and keeps the parameters p,a,bi secret. Then, it uses private key SKH to create a signature SigH=HashQTS2SKH and sends QSigHTS2 to the cloud.


## 4.4. Prediagnostic Service

After receivingQSigHTS2 from the hospital, the cloud verifies the validity of the message by using the following formula:
(9)eg,SigH=?ePKH,HashQTS2.If the above equation is true, the cloud performs the prediagnosis service algorithm. As shown in Algorithm3, the cloud finds the data subset Dl corresponding to the disease l and calculates the Relief-Wasserstein distance between EX and each preprocessed encrypted medical instance in Dl. Then, the cloud selects the kl instances with the smallest distance and takes most of the categories of these kl instances as the final prediagnosis result R. The time complexity of Algorithm 3 is ONlnl. The cloud keeps each RW, and computation rules secret. Then, it uses the hospital’s public key to calculate Rl=EPKHR and uses SKC to create a signature SigC=HashRlTS3SKC. Findly, the cloud sends RlSigCTS3 to the hospital.Algorithm 3: Prediagnosis service algorithm of the Relief-kMW classifier.
Input: the preprocessed query vector EX, β, γ, l and kl.Output: pre-diagnosis result R.1:EX=γ−1·EX;2:forj=1 to Nl do3: setRW=0;4: fori=1 to nl+2 do5:RW=RW+exi−β−1·eylij;6: end for7:end for8:Select thekl data with the smallest RW between the Nl data and the query vector, and use most of the classification results in the kldata as the pre-diagnostic resultR;9:returnR.


## 4.5. Query Result Analysis

After receivingRlSigCTS3 from the cloud, the hospital verifies the validity of the message by using the following formula:
(10)eg,SigC=?ePKC,HashRlTS3The prediagnosis resultR can be obtained if the equation holds. The hospital gives some advice Al for this result and calculates RAl=EPKURAl. Then, the hospital uses private key to create a signature SigH=HashRAlTS4SKH and sends RAlSigHTS4 to the user.


## 4.6. Result Acquisition

After receivingRAlSigHTS4 from the hospital, the user verifies the validity of the message by using the following formula:
(11)eg,SigH=?ePKH,HashRAlTS4If the equation holds, the user can obtain the pre-diagnosis resultR and the advice Al.


## 5. Accuracy and Security Analysis

This section analyzes the accuracy and security of OMPD. We verify that the data preprocessing of OMPD does not affect the original classification accuracy and can ensure privacy security.


### 5.1. Accuracy Analysis

If it can be verified that the Relief-Wasserstein distanceRW2 between the preprocessed data calculated by Algorithm 3 and the Relief-Wasserstein distance RW between the original data are approximately a fixed multiple, it can be proved that our scheme does not require decryption to obtain the original data and also provides relatively accurate prediagnosis services.Theorem 3.
Assuming thatRW1 represents the Relief-Wasserstein distance between IIIX and IIIYlj, RW represents the Relief-Wasserstein distance between the two original data, then RW is equal to RW1.
Proof.The calculation process of the Relief-Wasserstein distance RW between the original data is as follows:
(12)θ0=0,θ1=θ0+w1∗x1−yl1j=w1x1−w1yl1j,θ2=θ1+w2∗x2−yl2j=w1x1+w2x2−w1yl1j+w2yl2j,⋯,θnl=θnl−1+wnl∗xnl−ylnlj=w1x1+⋯+wnlxnl−w1yl1j+⋯+wnlylnlj,RW=∑i=1nlθi=θ1+θ2+⋯+θnl=w1x1−w1yl1j+w1x1+w2x2−w1yl1j+w2yl2j+⋯+w1x1+⋯+wnlxnl−w1yl1j+⋯+wnlylnlj.
RW1 represents the Relief-Wasserstein distance between IIIX and IIIYlj, and then the calculation process of RW1 is as follows:
(13)θ1=IIIx1−IIIyl1j=0−0=0,θ2=IIIx2−IIIyl2j=0−0=0,θ3=IIIx3−IIIyl3j=w1x1−w1yl1j,θ4=IIIx4−IIIyl4j=w1x1+w2x2−w1yl1j+w2yl2j,⋯,θnl+2=IIIxnl+2−IIIylnl+2j=w1x1+w2x2+⋯+wnlxnl−w1yl1j+w2yl2j+⋯+wnlylnlj,RW1=∑i=1nl+2θi=θ1+θ2+⋯+θnl+2=0+0+w1x1−w1yl1j+w1x1+w2x2−w1yl1j+w2yl2j+⋯+w1x1+⋯+wnlxnl−w1yl1j+⋯+wnlylnlj=RW.
In summary, by Theorem3, we can sssget that RW1 is equal to RW.Theorem 4.
Assuming thatRW1 represents the Relief-Wasserstein distance between IIIX and IIIYlj, RW2 represents the Relief-Wasserstein distance between EX and EYlj, and then RW1 and RW2 are approximately in a fixed multiple relationship.
Proof.RW1 represents the Relief-Wasserstein distance between IIIX and IIIYlj, and then the calculation process of RW1 is as follows:
(14)θ1=IIIx1−IIIyl1j,θ2=IIIx2−IIIyl2j,θ4=IIIx4−IIIyl4j,⋯,θnl+2=IIIxnl+2−IIIylnl+2j,RW1=∑i=1nl+2θi=θ1+θ2+⋯+θnl+2=IIIx1−IIIyl1j+IIIx2−IIIyl2j+⋯+IIIxnl+2−IIIylnl+2j.
RW2 represents the Relief-Wasserstein distance between EX and EYlj, and then the calculation of RW2 is as follows:
(15)θ1=γ−1·ex1−β−1·eyl1j=γ−1·γa·IIIx1+b1modp−β−1·βa·IIIyl1j+b1jmodp=a·IIIx1−IIIyl1j+b1−b1jmodp,θ2=γ−1·ex2−β−1·eyl2j=γ−1·γa·IIIx2+b2modp−β−1·βa·IIIyl2j+b2jmodp=a·IIIx2−IIIyl2j+b2−b2jmodp,⋯,θnl+2=γ−1·exnl+2−β−1·eylnl+2j=γ−1·γa·IIIxnl+2+bnl+2modp−β−1·βa·IIIylnl+2j+bnl+2jmodp=a·IIIxnl+2−IIIylnl+2j+bnl+2−bnl+2jmodp,RW2=∑i=1nl+2θi=θ1+θ2+⋯+θnl+2=a·IIIx1−IIIyl1j+b1−b1jmodp+a·IIIx2−IIIyl2j+b2−b2jmodp+⋯+a·IIIxnl+2−IIIylnl+2j+bnl+2−bnl+2jmodp.
Available fromt1>t2>t3, we can get the followings:
(16)RW2=a·IIIx1−IIIyl1j+b1−b1j+a·IIIx2−IIIyl2j+b2−b2j+⋯+a·IIIxnl+2−IIIylnl+2j+bnl+2−bnl+2jFromt1>t2>t3, we can get that bi−bij is negligible relative to the large prime number a, and then
(17)RW2≈a·IIIx1−IIIyl1j+a·IIIx2−IIIyl2j+⋯+a·IIIxnl+2−IIIylnl+2j=a·IIIx1−IIIyl1j+IIIx2−IIIyl2j+⋯+IIIxnl+2−IIIylnl+2j=a·RW1.Finally, Theorem4 holds. And we can get that RW1 and RW2 are approximately in a fixed multiple relationship. It can be obtained from Theorems 3 and 4 that the cloud can still obtain accurate pre-diagnosis results through Algorithm 3 without obtaining the original data.


### 5.2. Security Analysis

The focus of security analysis is whether OMPD can protect the privacy of users’ medical data, the privacy of medical instances in hospitals, and the confidentiality of cloud diagnostic models.The user’s query vectorX=x1,x2,⋯,xnl and the medical instance Ylj=yl1j,yl2j,⋯,ylnlj, j∈1,Nl in the hospital data subset Dl are privacy-preserving. In the initialization stage, in order to prevent the privacy of medical instances from leaking, the hospital expands two dimensions with 0 for each medical instance after feature weight distribution and vector value iteration, which can prevent the cloud and illegal users from obtaining real medical instances. Each blij in the encryption calculation is randomly generated; so, IIIylij is protected. When p, a, blij, and weightl are unknown, the cloud cannot obtain the original medical data. And the random number blij generated is independent of each other at each time. Only the hospital knows the data processing rules, and the cloud cannot infer the original medical data. Therefore, the medical instance set Dataset=Dl=Ylj,j∈1,Nl,l∈1,L is kept secret during the calculation process. Similarly, the query vector of the user X=x1,x2,⋯,xnl is also kept secret.The Relief-kMW classifier is confidential. In the operating calculation phase, each medical instance Ylj=yl1j,yl2j,⋯,ylnlj, j∈1,Nl and query vector X=x1,x2,⋯,xnl are preprocessed by the hospital before sending to the cloud. For two same query vectors, they should have the same Relief-Wasserstein distance between the same medical instances, but the random number blij and bi generated by each data processing are different and the Relief-Wasserstein distance calculated by the query vector is also different, which ensures that even the same user cannot obtain medical instance information after multiple queries. And each RW calculated by the Relief-kMW classifier is confidential, and the cloud uses the hospital’s public key PKH to encrypt the query result. The hospital uses the user’s public key PKU to encrypt the query result and the advice; so, only the corresponding user can decrypt the query result. Moreover, the user and the cloud cannot communicate directly during the query. Although the cloud knows the final prediction result, it cannot obtain the corresponding user’s information. And the user cannot obtain the detailed information of the Relief-kMW classifier in the cloud. Therefore, the Relief-kMW classifier is confidential.OMPD ensures communication security. Our scheme uses BLS signature to protect the information of each interaction. The signature is proved to be safe under the Diffie-Hellman problem of the random prediction model [36]. In addition, any illegal user cannot successfully submit a query request to the hospital because there is no key. Signature authentication can ensure that the message is not maliciously tampered with during transmission. Even if someone maliciously intercepts the message, the effective information in the message cannot be obtained because there is no key.In summary, our OMPD can provide privacy-preserving medical prediagnosis services.


## 5.1. Accuracy Analysis

If it can be verified that the Relief-Wasserstein distanceRW2 between the preprocessed data calculated by Algorithm 3 and the Relief-Wasserstein distance RW between the original data are approximately a fixed multiple, it can be proved that our scheme does not require decryption to obtain the original data and also provides relatively accurate prediagnosis services.Theorem 3.
Assuming thatRW1 represents the Relief-Wasserstein distance between IIIX and IIIYlj, RW represents the Relief-Wasserstein distance between the two original data, then RW is equal to RW1.
Proof.The calculation process of the Relief-Wasserstein distance RW between the original data is as follows:
(12)θ0=0,θ1=θ0+w1∗x1−yl1j=w1x1−w1yl1j,θ2=θ1+w2∗x2−yl2j=w1x1+w2x2−w1yl1j+w2yl2j,⋯,θnl=θnl−1+wnl∗xnl−ylnlj=w1x1+⋯+wnlxnl−w1yl1j+⋯+wnlylnlj,RW=∑i=1nlθi=θ1+θ2+⋯+θnl=w1x1−w1yl1j+w1x1+w2x2−w1yl1j+w2yl2j+⋯+w1x1+⋯+wnlxnl−w1yl1j+⋯+wnlylnlj.
RW1 represents the Relief-Wasserstein distance between IIIX and IIIYlj, and then the calculation process of RW1 is as follows:
(13)θ1=IIIx1−IIIyl1j=0−0=0,θ2=IIIx2−IIIyl2j=0−0=0,θ3=IIIx3−IIIyl3j=w1x1−w1yl1j,θ4=IIIx4−IIIyl4j=w1x1+w2x2−w1yl1j+w2yl2j,⋯,θnl+2=IIIxnl+2−IIIylnl+2j=w1x1+w2x2+⋯+wnlxnl−w1yl1j+w2yl2j+⋯+wnlylnlj,RW1=∑i=1nl+2θi=θ1+θ2+⋯+θnl+2=0+0+w1x1−w1yl1j+w1x1+w2x2−w1yl1j+w2yl2j+⋯+w1x1+⋯+wnlxnl−w1yl1j+⋯+wnlylnlj=RW.
In summary, by Theorem3, we can sssget that RW1 is equal to RW.Theorem 4.
Assuming thatRW1 represents the Relief-Wasserstein distance between IIIX and IIIYlj, RW2 represents the Relief-Wasserstein distance between EX and EYlj, and then RW1 and RW2 are approximately in a fixed multiple relationship.
Proof.RW1 represents the Relief-Wasserstein distance between IIIX and IIIYlj, and then the calculation process of RW1 is as follows:
(14)θ1=IIIx1−IIIyl1j,θ2=IIIx2−IIIyl2j,θ4=IIIx4−IIIyl4j,⋯,θnl+2=IIIxnl+2−IIIylnl+2j,RW1=∑i=1nl+2θi=θ1+θ2+⋯+θnl+2=IIIx1−IIIyl1j+IIIx2−IIIyl2j+⋯+IIIxnl+2−IIIylnl+2j.
RW2 represents the Relief-Wasserstein distance between EX and EYlj, and then the calculation of RW2 is as follows:
(15)θ1=γ−1·ex1−β−1·eyl1j=γ−1·γa·IIIx1+b1modp−β−1·βa·IIIyl1j+b1jmodp=a·IIIx1−IIIyl1j+b1−b1jmodp,θ2=γ−1·ex2−β−1·eyl2j=γ−1·γa·IIIx2+b2modp−β−1·βa·IIIyl2j+b2jmodp=a·IIIx2−IIIyl2j+b2−b2jmodp,⋯,θnl+2=γ−1·exnl+2−β−1·eylnl+2j=γ−1·γa·IIIxnl+2+bnl+2modp−β−1·βa·IIIylnl+2j+bnl+2jmodp=a·IIIxnl+2−IIIylnl+2j+bnl+2−bnl+2jmodp,RW2=∑i=1nl+2θi=θ1+θ2+⋯+θnl+2=a·IIIx1−IIIyl1j+b1−b1jmodp+a·IIIx2−IIIyl2j+b2−b2jmodp+⋯+a·IIIxnl+2−IIIylnl+2j+bnl+2−bnl+2jmodp.
Available fromt1>t2>t3, we can get the followings:
(16)RW2=a·IIIx1−IIIyl1j+b1−b1j+a·IIIx2−IIIyl2j+b2−b2j+⋯+a·IIIxnl+2−IIIylnl+2j+bnl+2−bnl+2jFromt1>t2>t3, we can get that bi−bij is negligible relative to the large prime number a, and then
(17)RW2≈a·IIIx1−IIIyl1j+a·IIIx2−IIIyl2j+⋯+a·IIIxnl+2−IIIylnl+2j=a·IIIx1−IIIyl1j+IIIx2−IIIyl2j+⋯+IIIxnl+2−IIIylnl+2j=a·RW1.Finally, Theorem4 holds. And we can get that RW1 and RW2 are approximately in a fixed multiple relationship. It can be obtained from Theorems 3 and 4 that the cloud can still obtain accurate pre-diagnosis results through Algorithm 3 without obtaining the original data.


## 5.2. Security Analysis

The focus of security analysis is whether OMPD can protect the privacy of users’ medical data, the privacy of medical instances in hospitals, and the confidentiality of cloud diagnostic models.The user’s query vectorX=x1,x2,⋯,xnl and the medical instance Ylj=yl1j,yl2j,⋯,ylnlj, j∈1,Nl in the hospital data subset Dl are privacy-preserving. In the initialization stage, in order to prevent the privacy of medical instances from leaking, the hospital expands two dimensions with 0 for each medical instance after feature weight distribution and vector value iteration, which can prevent the cloud and illegal users from obtaining real medical instances. Each blij in the encryption calculation is randomly generated; so, IIIylij is protected. When p, a, blij, and weightl are unknown, the cloud cannot obtain the original medical data. And the random number blij generated is independent of each other at each time. Only the hospital knows the data processing rules, and the cloud cannot infer the original medical data. Therefore, the medical instance set Dataset=Dl=Ylj,j∈1,Nl,l∈1,L is kept secret during the calculation process. Similarly, the query vector of the user X=x1,x2,⋯,xnl is also kept secret.The Relief-kMW classifier is confidential. In the operating calculation phase, each medical instance Ylj=yl1j,yl2j,⋯,ylnlj, j∈1,Nl and query vector X=x1,x2,⋯,xnl are preprocessed by the hospital before sending to the cloud. For two same query vectors, they should have the same Relief-Wasserstein distance between the same medical instances, but the random number blij and bi generated by each data processing are different and the Relief-Wasserstein distance calculated by the query vector is also different, which ensures that even the same user cannot obtain medical instance information after multiple queries. And each RW calculated by the Relief-kMW classifier is confidential, and the cloud uses the hospital’s public key PKH to encrypt the query result. The hospital uses the user’s public key PKU to encrypt the query result and the advice; so, only the corresponding user can decrypt the query result. Moreover, the user and the cloud cannot communicate directly during the query. Although the cloud knows the final prediction result, it cannot obtain the corresponding user’s information. And the user cannot obtain the detailed information of the Relief-kMW classifier in the cloud. Therefore, the Relief-kMW classifier is confidential.OMPD ensures communication security. Our scheme uses BLS signature to protect the information of each interaction. The signature is proved to be safe under the Diffie-Hellman problem of the random prediction model [36]. In addition, any illegal user cannot successfully submit a query request to the hospital because there is no key. Signature authentication can ensure that the message is not maliciously tampered with during transmission. Even if someone maliciously intercepts the message, the effective information in the message cannot be obtained because there is no key.In summary, our OMPD can provide privacy-preserving medical prediagnosis services.


## 6. Performance Evaluation

In this section, multiple experiments are conducted to verify the accuracy and efficiency of OMPD from multiple dimensions of accuracy, computation overhead, and communication overhead.


### 6.1. Experiment Configuration

We implement OMPD with Python programming language and evaluate the computation and communication overhead of OMPD. We carry out our experiments on the device with CPU Intel(R) Xeon(R) Silver 4114, 2.20GHz, and Memory 32G. We choose two real data sets: Wisconsin Breast Cancer (WBC) and Mammographic Mass (MM) in the UCI machine learning library to evaluate the accuracy of the OMPD. In the comparative experiment, OMPD uses the Relief-kMW classifier, while OMPD-kMW uses the kMW classifier, EPDK [33] is a two-party interaction pre-diagnosis program using kNN classifiers, and PPDP [32] is a three-party interaction prediagnostic program using a single-layer perceptron trained with encryption matrices as the classifier.The WBC contains 683 instances, including 444 benign instances and 239 malignant instances. Each instance contains 9 attributes. The MM contains 830 instances, of which 427 instances are benign and 403 instances are malignant. Each instance contains 5 attributes.


### 6.2. Selection of the Optimal Value ofk

For WBC and MM, we randomly selected 100 malignant instances and 100 benign instances as the test data set to evaluate the accuracy of OMPD. And the rest were used as the training data set. Then, we performed 100 calculations to compare the average accuracy and computation time under different values ofk. As shown in Table 2, when kWBC=9 and kMM=11, the classification accuracy of OMPD is the highest, and the calculation time-consuming swing is the smallest. Therefore, in the following experiment, the values of kWBC and kMM are 9 and 11, respectively.Table 2
Selection of the optimalk value.
kAccuracy (%)Computation time (s)kWBC=597.870.3359±0.0197kWBC=798.990.3438±0.0156kMM=999.500.3672±0.0134kWBC=1199.500.3828±0.0245kWBC=1399.500.3984±0.0234kWBC=1599.500.4063±0.0313kMM=594.040.6094±0.1094kMM=797.070.6641±0.1328kMM=997.090.6953±0.1328kMM=1197.780.6718±0.0938kMM=1396.520.7109±0.1016kMM=1596.500.7734±0.1484


### 6.3. Evaluation of Accuracy

In order to verify the accuracy of our method, we conducted an accuracy comparison experiment, as shown in Table3. The results show that the classification accuracy of OMPD is significantly higher than the other three schemes. This means that our OMPD still has a high classification accuracy after the data is preprocessed by feature weight distribution, iteration, expansion, and encryption. And it can provide high-precision online medical prediagnosis services for medical users. Please note that the accuracy of OMPD is higher than OMPD-kMW, which means that the feature weights obtained by OMPD using the Relief feature weight distribution algorithm, which increases the impact of features that have a greater contribution to the classification and reduces the impact of features with low contributions. The experimental results verify that the accuracy of using Relief-kMW is higher than that of kMW.Table 3
Comparison of accuracy.
AccuracyOMPDOMPD-kMWEPDKPPDPWBCMalignant (100)99 (99.0%)97 (97.0%)93 (93.0%)85 (85.0%)Benign (100)97 (97.0%)95 (95.0%)94 (94.0%)81 (81.0%)Overall (200)196 (98.0%)192 (96.0%)187 (93.5%)166 (83.0%)MMMalignant (100)97 (97.0%)97 (97.0%)95 (95.0%)83 (83.0%)Benign (100)98 (98.0%)96 (96.0%)98 (98.0%)86 (86.0%)Overall (200)195 (97.5%)193 (96.5%)193 (96.5%)169 (84.5%)


### 6.4. Evaluation of Computational Efficiency

In order to verify that OMPD can provide efficient online medical prediagnosis services for medical users, this section evaluates the efficiency of computation. During the system operation, when the user generates the query vector and sends it to the hospital, the hospital needs to preprocess the query vector through3nl+2 multiplication (division) and 2nl−1 addition (subtraction) operation. After the cloud receives the query request, it needs to go through Nlnl+2Nl+nl+2 multiplication (division) and 2Nlnl+4Nl addition (subtraction) operation to calculate the diagnosis result. Let Ca and Cm denote the running time of addition and multiplication, respectively. Then, the overall computation complexity of OMPD is Cm·Nlnl+2Nl+4nl+4+Ca·2Nlnl+4Nl+2nl−1 during system operation. As shown in Table 4, it can be seen that OMPD-kMW only lacks a multiplication operation (the calculation of multiplying feature weights and feature values) than our OMPD. The computational complexity of PPDP in the operating phase of the system has nothing to do with the amount of data Nl. Its computational complexity is concentrated in the system initialization stage, and a lot of calculations are required to continuously update the weights to converge. The multiplication (division) in OMPD is far less than that in EPDK, while Cm is more than Ca. Therefore, the computational complexity of OMPD is lower than that of EPDK, and the gap becomes more obvious with the increase of data.Table 4
Comparison of computation complexity.
ComplexityOMPDOMPD-kMWEPDKPPDPUser——Cm·Nl+3nl+2+Ca·Nl+2nl−1—HospitalCm·3nl+2+Ca·2nl−1Cm·2nl+2+Ca·2nl−1—Cm·2nl3+nl2+nl+Ca·2nl3−2nl2+nl−1Cloud/serverCm·Nlnl+2Nl+nl+2+Ca·2Nlnl+4NlCm·Nlnl+2Nl+nl+2+Ca·2Nlnl+4NlCm·4Nlnl+4Nl+Ca·Nlnl+Nl+nl+1Cm·2nl3+Ca·2nl3−2nl2+nl−1TotalCm·Nlnl+2Nl+4nl+4+Ca·2Nlnl+4Nl+2nl−1Cm·Nlnl+2Nl+3nl+4+Ca·2Nlnl+4Nl+2nl−1Cm·4Nlnl+5Nl+3nl+2+Ca·Nlnl+2Nl+3nlCm·4nl3+nl2+nl+Ca·4nl3−4nl2+2nl−2However, we cannot intuitively see the comparison of the computational time from Table4. So, we conducted a comparison experiment of computational overhead. As shown in Figure 2, as the number of medical instances increases, the computation time of EPDK has grown rapidly, and OMPD and OMPD-kMW have grown slowly, while PPDP has remained almost unchanged. This is because EPDK takes more time to perform operations such as multiplication (division). In addition, a large number of medical data stored by EPDK providers are collected directly from various medical service sites without encryption and other privacy protection measures, and there is a serious risk of privacy leakage. Our OMPD and OMPD-kMW, as shown in Table 4, require significantly less calculations than EPDK. However, PPDP only needs to calculate the query data and the weight to get the diagnosis result; so, the computation time of PPDP in the running phase remains unchanged, but PPDP generates a lot of computation and communication overhead in the initialization phase to update the weights to converge. And PPDP ignores the protection of the communication process. Users send sensitive information directly to the hospital, which is vulnerable to attacks and theft by malicious third parties.Figure 2
Comparison of computation overhead.


### 6.5. Evaluation of Communication Overhead

The communication overhead comparison of the four schemes in the system operation phase is shown in Figure3. Assuming that the medical advice contains 100 words, each word contains an average of 5 characters, plus punctuation and spaces, one word approximately contains 6 characters, and each character occupies 1 byte. The total communication overhead of OMPD is about 0.735 KB (including 600B medical advice). As the number of medical instances increases, the total communication overhead of OMPD, OMPD-kMW, and PPDP remains unchanged, while EPDK is much higher than the other three schemes. Because these three schemes obtain the diagnosis results directly in the cloud, only the results need to be sent during the communication process. The server in the EPDK only calculates the two intermediate values of the Spearman distance between the query vector and Nl medical instances in database. The server needs to send 2Nl intermediate values to the user, and the user finally calculates the diagnosis result. Therefore, the larger the Nl, the greater the communication overhead of EPDK. And users cannot get corresponding medical advice in time.Figure 3
Comparison of communication overhead.In summary, OMPD can balance accuracy and efficiency to achieve high-precision online medical prediagnosis with lower computational complexity and communication overhead. At the same time, it also provides timely professional medical advice.


## 6.1. Experiment Configuration

We implement OMPD with Python programming language and evaluate the computation and communication overhead of OMPD. We carry out our experiments on the device with CPU Intel(R) Xeon(R) Silver 4114, 2.20GHz, and Memory 32G. We choose two real data sets: Wisconsin Breast Cancer (WBC) and Mammographic Mass (MM) in the UCI machine learning library to evaluate the accuracy of the OMPD. In the comparative experiment, OMPD uses the Relief-kMW classifier, while OMPD-kMW uses the kMW classifier, EPDK [33] is a two-party interaction pre-diagnosis program using kNN classifiers, and PPDP [32] is a three-party interaction prediagnostic program using a single-layer perceptron trained with encryption matrices as the classifier.The WBC contains 683 instances, including 444 benign instances and 239 malignant instances. Each instance contains 9 attributes. The MM contains 830 instances, of which 427 instances are benign and 403 instances are malignant. Each instance contains 5 attributes.


## 6.2. Selection of the Optimal Value ofk

For WBC and MM, we randomly selected 100 malignant instances and 100 benign instances as the test data set to evaluate the accuracy of OMPD. And the rest were used as the training data set. Then, we performed 100 calculations to compare the average accuracy and computation time under different values ofk. As shown in Table 2, when kWBC=9 and kMM=11, the classification accuracy of OMPD is the highest, and the calculation time-consuming swing is the smallest. Therefore, in the following experiment, the values of kWBC and kMM are 9 and 11, respectively.Table 2
Selection of the optimalk value.
kAccuracy (%)Computation time (s)kWBC=597.870.3359±0.0197kWBC=798.990.3438±0.0156kMM=999.500.3672±0.0134kWBC=1199.500.3828±0.0245kWBC=1399.500.3984±0.0234kWBC=1599.500.4063±0.0313kMM=594.040.6094±0.1094kMM=797.070.6641±0.1328kMM=997.090.6953±0.1328kMM=1197.780.6718±0.0938kMM=1396.520.7109±0.1016kMM=1596.500.7734±0.1484


## 6.3. Evaluation of Accuracy

In order to verify the accuracy of our method, we conducted an accuracy comparison experiment, as shown in Table3. The results show that the classification accuracy of OMPD is significantly higher than the other three schemes. This means that our OMPD still has a high classification accuracy after the data is preprocessed by feature weight distribution, iteration, expansion, and encryption. And it can provide high-precision online medical prediagnosis services for medical users. Please note that the accuracy of OMPD is higher than OMPD-kMW, which means that the feature weights obtained by OMPD using the Relief feature weight distribution algorithm, which increases the impact of features that have a greater contribution to the classification and reduces the impact of features with low contributions. The experimental results verify that the accuracy of using Relief-kMW is higher than that of kMW.Table 3
Comparison of accuracy.
AccuracyOMPDOMPD-kMWEPDKPPDPWBCMalignant (100)99 (99.0%)97 (97.0%)93 (93.0%)85 (85.0%)Benign (100)97 (97.0%)95 (95.0%)94 (94.0%)81 (81.0%)Overall (200)196 (98.0%)192 (96.0%)187 (93.5%)166 (83.0%)MMMalignant (100)97 (97.0%)97 (97.0%)95 (95.0%)83 (83.0%)Benign (100)98 (98.0%)96 (96.0%)98 (98.0%)86 (86.0%)Overall (200)195 (97.5%)193 (96.5%)193 (96.5%)169 (84.5%)


## 6.4. Evaluation of Computational Efficiency

In order to verify that OMPD can provide efficient online medical prediagnosis services for medical users, this section evaluates the efficiency of computation. During the system operation, when the user generates the query vector and sends it to the hospital, the hospital needs to preprocess the query vector through3nl+2 multiplication (division) and 2nl−1 addition (subtraction) operation. After the cloud receives the query request, it needs to go through Nlnl+2Nl+nl+2 multiplication (division) and 2Nlnl+4Nl addition (subtraction) operation to calculate the diagnosis result. Let Ca and Cm denote the running time of addition and multiplication, respectively. Then, the overall computation complexity of OMPD is Cm·Nlnl+2Nl+4nl+4+Ca·2Nlnl+4Nl+2nl−1 during system operation. As shown in Table 4, it can be seen that OMPD-kMW only lacks a multiplication operation (the calculation of multiplying feature weights and feature values) than our OMPD. The computational complexity of PPDP in the operating phase of the system has nothing to do with the amount of data Nl. Its computational complexity is concentrated in the system initialization stage, and a lot of calculations are required to continuously update the weights to converge. The multiplication (division) in OMPD is far less than that in EPDK, while Cm is more than Ca. Therefore, the computational complexity of OMPD is lower than that of EPDK, and the gap becomes more obvious with the increase of data.Table 4
Comparison of computation complexity.
ComplexityOMPDOMPD-kMWEPDKPPDPUser——Cm·Nl+3nl+2+Ca·Nl+2nl−1—HospitalCm·3nl+2+Ca·2nl−1Cm·2nl+2+Ca·2nl−1—Cm·2nl3+nl2+nl+Ca·2nl3−2nl2+nl−1Cloud/serverCm·Nlnl+2Nl+nl+2+Ca·2Nlnl+4NlCm·Nlnl+2Nl+nl+2+Ca·2Nlnl+4NlCm·4Nlnl+4Nl+Ca·Nlnl+Nl+nl+1Cm·2nl3+Ca·2nl3−2nl2+nl−1TotalCm·Nlnl+2Nl+4nl+4+Ca·2Nlnl+4Nl+2nl−1Cm·Nlnl+2Nl+3nl+4+Ca·2Nlnl+4Nl+2nl−1Cm·4Nlnl+5Nl+3nl+2+Ca·Nlnl+2Nl+3nlCm·4nl3+nl2+nl+Ca·4nl3−4nl2+2nl−2However, we cannot intuitively see the comparison of the computational time from Table4. So, we conducted a comparison experiment of computational overhead. As shown in Figure 2, as the number of medical instances increases, the computation time of EPDK has grown rapidly, and OMPD and OMPD-kMW have grown slowly, while PPDP has remained almost unchanged. This is because EPDK takes more time to perform operations such as multiplication (division). In addition, a large number of medical data stored by EPDK providers are collected directly from various medical service sites without encryption and other privacy protection measures, and there is a serious risk of privacy leakage. Our OMPD and OMPD-kMW, as shown in Table 4, require significantly less calculations than EPDK. However, PPDP only needs to calculate the query data and the weight to get the diagnosis result; so, the computation time of PPDP in the running phase remains unchanged, but PPDP generates a lot of computation and communication overhead in the initialization phase to update the weights to converge. And PPDP ignores the protection of the communication process. Users send sensitive information directly to the hospital, which is vulnerable to attacks and theft by malicious third parties.Figure 2
Comparison of computation overhead.


## 6.5. Evaluation of Communication Overhead

The communication overhead comparison of the four schemes in the system operation phase is shown in Figure3. Assuming that the medical advice contains 100 words, each word contains an average of 5 characters, plus punctuation and spaces, one word approximately contains 6 characters, and each character occupies 1 byte. The total communication overhead of OMPD is about 0.735 KB (including 600B medical advice). As the number of medical instances increases, the total communication overhead of OMPD, OMPD-kMW, and PPDP remains unchanged, while EPDK is much higher than the other three schemes. Because these three schemes obtain the diagnosis results directly in the cloud, only the results need to be sent during the communication process. The server in the EPDK only calculates the two intermediate values of the Spearman distance between the query vector and Nl medical instances in database. The server needs to send 2Nl intermediate values to the user, and the user finally calculates the diagnosis result. Therefore, the larger the Nl, the greater the communication overhead of EPDK. And users cannot get corresponding medical advice in time.Figure 3
Comparison of communication overhead.In summary, OMPD can balance accuracy and efficiency to achieve high-precision online medical prediagnosis with lower computational complexity and communication overhead. At the same time, it also provides timely professional medical advice.


## 7. Conclusions

In this article, we propose an efficient online multiparty interactive medical prediagnosis scheme with privacy protection, called OMPD, which can protect the privacy with low computation and communication overhead. Accuracy analysis showed that our OMPD can obtain more accurate classification results without decryption. The security analysis demonstrated its security strength and privacy protection capabilities. And its effectiveness was verified through comparative experiments. Future work is to further improve the classification accuracy and operating efficiency of the program while ensuring the strength and security of privacy protection.



---

*Source: 7746286-2021-12-15.xml*