# Privacy-Preserving Minority Oversampling Protocols with Fully Homomorphic Encryption

Authors: Maohua Sun; Ruidi Yang; Mengying Liu
Journal: Security and Communication Networks
 (2022)

---

## Abstract

In recent years, blockchain and machine-learning techniques have received increasing attention both in theoretical and practical aspects. However, the applications of these techniques have many challenges, one of which is the privacy-preserving issue. In this paper, we focus on, specifically, the privacy-preserving issue of imbalanced datasets, a commonly found problem in real-world applications. Built based on the fully homomorphic encryption technique, this paper presents two new secure protocols, Privacy-Preserving Synthetic Minority Oversampling Protocol (PPSMOS) and Borderline Privacy-Preserving Synthetic Minority Oversampling Protocol (Borderline-PPSMOS). Our analysis reveals that PPSMOS is generally more efficient in performance than Borderline-PPSMOS. However, Borderline-PPSMOS achieves a better TP rate and F-Value than PPSMOS.


---

## Body

## 1. Introduction

In the past few years, new information technology techniques, such as blockchain [1–4] and machine-learning [5–15], have been developing rapidly and used successfully in various real-life applications. However, they still face a critical challenge in the privacy-preserving issue. For example, the openness of a blockchain system poses a serious threat to the privacy and security of any user transactions. Thus, research for privacy-preserving techniques is becoming even more crucial.Datasets in the wild come with a variety of problems. One of the most common problems is the imbalanced issue of the datasets. Imbalanced datasets issue arises in many real-world sectors, such as disease detection [16], bankruptcy prediction [17], fraud detection [18], etc. As the distribution of samples is incorrect in imbalanced datasets, it may cause the classification algorithms to produce inaccurate results and further issues. An imbalanced dataset usually consists of a number of classes, which falls into one of these two types: majority classes, which has a bigger number of examples, and minority classes, in which there are fewer examples. In this paper, we consider the situation where there are only two classes in a dataset, i.e., one majority class and one minority class.The existing solutions proposed to solve the imbalanced dataset problem are categorized according to which level the technique is solving the problem from, e.g., data level, feature level, and machine-learning algorithm level. In this paper, we focus on fixing the problems at the data level. There are two known data level techniques, namely undersampling and oversampling methods. The undersampling method works by removing parts of the samples from the majority class to balance the ratio of majority and minority samples, whereas oversampling method balances the majority and minority samples by generating new minority samples. In 1972, Wilson [19] proposed an undersampling method, in which a majority sample should be deleted if all of its neighbors are minority samples. In 2020, Wang et al. [20] proposed a novel entropy and confidence-based undersampling boosting framework to solve imbalanced dataset issues, which could be applied to noniterating algorithms such as decision trees.Random oversampling of minority classes is the simplest oversampling method. Through sampling with replacement, samples are continuously drawn from the minority class. This method, however, can easily lead to data overfitting. In 2002, Chawla et al. [21] proposed the Synthetic Minority Oversampling Technique (SMOTE) algorithm, which is one of the best-known oversampling methods to date. The algorithm works by generating artificial data using bootstrapping and the K-nearest neighbor algorithm. Further improvising SMOTE algorithm, Han et al. [22] proposed Borderline-SMOTE in 2005. The algorithm focuses on working on samples that are on the boundary of both majority and minority classes. The demonstration showed that Borderline-SMOTE achieved a better TP rate and F-Value than its predecessor. In 2008, Douzas et al. [23] presented a simple and effective oversampling method based on K-means clustering and SMOTE, which is able to eliminate noise generation and effectively overcome imbalances between and within classes. Furthermore, Li et al. [24] presented three sampling approaches for imbalanced learning in 2020. Unlike the previous solutions, their approaches considered a new class-imbalance metric, which contains the differences of information contents between classes, instead of the traditional imbalance ratio.Although so many solutions have been proposed to solve the imbalanced data sets problem, the privacy-preserving issue has not been well resolved. To the best of our knowledge, Hong et al. [25] proposed a secure collaborative machine-learning solution in which they used secure multiparty computation to adjust the class weight for the imbalanced dataset. That is, the privacy-preserving issue of the imbalanced dataset was tackled at the machine-learning algorithm level. The privacy-preserving solution in the machine-learning level is specific. That is, when we change the machine-learning algorithm, a new privacy-preserving solution to the imbalanced data set problem should be proposed. By contrast, as the privacy-preserving solutions in the data level solve the problem in the preprocessing stage, the output of these solutions can be widely used as they are independent of the machine-learning algorithms. So, in this paper, we focus on the privacy-preserving issue of imbalanced data sets at the data level.Despite the numerous solutions proposed to solve the imbalanced data sets problems, there is almost none of them attempted to resolve the privacy-preserving issue. To the best of our knowledge, Hong et al. invented a secure collaborative machine-learning solution, in which they used a secure multiparty computation to adjust the class weight of the imbalanced dataset. They tackled the privacy-preserving issue of the imbalanced dataset on the machine-learning algorithm level. This solution, however, is sensitive to the algorithm used for machine-learning, i.e., when the machine-learning algorithm is changed, a new privacy-preserving solution must be proposed for the imbalanced dataset problem. In contrast, as the privacy-preserving solutions at the data level work by solving the problem in the preprocessing stage, their output can be used widely, regardless of the machine-learning algorithm adopted in the system. Hence, in this paper, we focus on tackling the privacy-preserving issue of imbalanced datasets on the data level.Currently, Secure Multiparty Computation (SMC) is one of the most widely used techniques to tackle the privacy-preserving issue. In SMC, multiple parties participate in the game with their individual secure inputs and nobody knows anything of each other’s inputs. When the game ends, according to the game rules, some of the parties will obtain the output. The first SMC solution [26] to the millionaire problem was first presented by Yao. Since then, SMC has been developing rapidly. In 2017, Makri et al. [27] proposed SPDZ, a private image classification with SVM using the SMC framework. Mohassel et al. [28] presented a privacy-preserving machine-learning framework, SecureML, in which the privacy-preserving issue of the linear regression, logistic regression, and neural network training using the stochastic gradient descent method was considered.In SMC, there are various underlying cryptographic tools, such as garbled circuit, homomorphic encryption scheme, oblivious transfer, and secret sharing scheme. In this paper, we focus on handling the imbalanced dataset problem with the privacy-preserving two-party computation using the homomorphic encryption scheme. Homomorphic encryption is one of the most active research areas in the field of cryptography. Homomorphic encryption was initially proposed by Rivest et al. [29] in 1978. In 1985, ElGamal et al. [30] proposed a widely used multiplicatively homomorphic encryption scheme, known as ElGamal scheme. In 2001, Damgard et al. [31] promoted an additively homomorphic encryption scheme, named Paillier scheme. In 2009, Gentry [32] proposed a fully homomorphic encryption scheme, a ground-breaking development to homomorphic encryption study. Currently, the two most widely used fully homomorphic encryption schemes are the BGV scheme [33] by Brakerski et al. and BFV scheme [34] by Fan et al. In 2021, Chen et al. [35] presented a dynamic multikey fully homomorphic encryption scheme based on LWE assumption in the public key setting.


### 1.1. Contributions

In this paper, we propose two novel privacy-preserving oversampling protocols, namely PPSMOS and Borderline-PPSMOS. Both PPSMOS and Borderline-PPSMOS are aimed to solve the problem of the imbalanced dataset while preserving the participants’ input and output privacies. With the client and the service denoted as Bob and Alice, respectively, the work in this paper can be generally viewed as follows.(1)
PPSMOS: This algorithm works in a distributed architecture, where Bob inputs no examples at the beginning of the protocol. All the examples, both majority and minority, are provided by Alice. After the protocol, Bob gets the synthetic minority example while he learns nothing of Alice’s examples. At the same time, Alice learns nothing of the output Bob receives. PPSMOS shows to be a good solution with a privacy-preserving manner for data balance problems encountered in the cold start phase of many real-life applications.(2)
Borderline-PPSMOS: In this algorithm, at the start of the protocol, Bob has some majority examples as his input. Meanwhile, Alice has a number of minority examples. After the protocol, Bob receives synthetic minority examples, while he learns nothing of Alice’s minority examples, and Alice learns nothing of Bob’s input and output.(3)
PPSMOS and Borderline-PPSMOS performance analysis: Our analysis shows that PPSMOS generally works more efficiently than Borderline-PPSMOS, while Borderline-PPSMOS achieves a better TP rate and F-Value than PPSMOS. We also found that PPSMOS and Borderline-PPSMOS are both secure in the semihonest model.


### 1.2. Roadmap of This Paper

The rest of this paper is organized as follows. In Section 2, we introduce the preliminaries. We present the Privacy-Preserving Synthetic Minority Oversampling (PPSMOS) protocol in Section 3 and Borderline-PPSMOS in Section 4. We compare and analyse our protocols in Section 5. We, then, give our concluding remarks in Section 6.


## 1.1. Contributions

In this paper, we propose two novel privacy-preserving oversampling protocols, namely PPSMOS and Borderline-PPSMOS. Both PPSMOS and Borderline-PPSMOS are aimed to solve the problem of the imbalanced dataset while preserving the participants’ input and output privacies. With the client and the service denoted as Bob and Alice, respectively, the work in this paper can be generally viewed as follows.(1)
PPSMOS: This algorithm works in a distributed architecture, where Bob inputs no examples at the beginning of the protocol. All the examples, both majority and minority, are provided by Alice. After the protocol, Bob gets the synthetic minority example while he learns nothing of Alice’s examples. At the same time, Alice learns nothing of the output Bob receives. PPSMOS shows to be a good solution with a privacy-preserving manner for data balance problems encountered in the cold start phase of many real-life applications.(2)
Borderline-PPSMOS: In this algorithm, at the start of the protocol, Bob has some majority examples as his input. Meanwhile, Alice has a number of minority examples. After the protocol, Bob receives synthetic minority examples, while he learns nothing of Alice’s minority examples, and Alice learns nothing of Bob’s input and output.(3)
PPSMOS and Borderline-PPSMOS performance analysis: Our analysis shows that PPSMOS generally works more efficiently than Borderline-PPSMOS, while Borderline-PPSMOS achieves a better TP rate and F-Value than PPSMOS. We also found that PPSMOS and Borderline-PPSMOS are both secure in the semihonest model.


## 1.2. Roadmap of This Paper

The rest of this paper is organized as follows. In Section 2, we introduce the preliminaries. We present the Privacy-Preserving Synthetic Minority Oversampling (PPSMOS) protocol in Section 3 and Borderline-PPSMOS in Section 4. We compare and analyse our protocols in Section 5. We, then, give our concluding remarks in Section 6.


## 2. Preliminaries

### 2.1. Homomorphic Encryption

The homomorphic encryption scheme allows us to operate the ciphertext directly. The result obtained after the application of this scheme is equivalent to the ciphertext obtained after performing an operation on a plaintext. Homomorphic encryption algorithms are divided into three categories: additive homomorphism, multiplicative homomorphism, and full homomorphism. For our protocols, we adopt the fully homomorphic encryption scheme. We describe the fully homomorphic encryption algorithm as follows.We denotepk,sk as the system keys, where pk is the public key and sk is the secret key. Furthermore, Eα is the encryption operation on the plaintext α and Dβ is the decryption operation on the ciphertext β. The fully homomorphic encryption scheme follows the properties below.(1)Eα+Eγ=Eα+γ,Eα∗Eγ=Eα∗γ.


### 2.2. Semihonest Model

There are two widely used adversarial models in SMC, the semihonest model, and the malicious model. In this work, we design our protocols in the semihonest model.In the semihonest model, there are two kinds of participants, the honest participants and the semihonest participants. The honest participants follow the protocol without doing any other activities. At the same time, the semihonest participants followed the protocol and collected the data they obtained during the process of the protocol. After the protocol, they may want to infer information from the data they collected. A protocol is secure in the semihonest model if the semihonest participants get no valuable information from the data they collected.


## 2.1. Homomorphic Encryption

The homomorphic encryption scheme allows us to operate the ciphertext directly. The result obtained after the application of this scheme is equivalent to the ciphertext obtained after performing an operation on a plaintext. Homomorphic encryption algorithms are divided into three categories: additive homomorphism, multiplicative homomorphism, and full homomorphism. For our protocols, we adopt the fully homomorphic encryption scheme. We describe the fully homomorphic encryption algorithm as follows.We denotepk,sk as the system keys, where pk is the public key and sk is the secret key. Furthermore, Eα is the encryption operation on the plaintext α and Dβ is the decryption operation on the ciphertext β. The fully homomorphic encryption scheme follows the properties below.(1)Eα+Eγ=Eα+γ,Eα∗Eγ=Eα∗γ.


## 2.2. Semihonest Model

There are two widely used adversarial models in SMC, the semihonest model, and the malicious model. In this work, we design our protocols in the semihonest model.In the semihonest model, there are two kinds of participants, the honest participants and the semihonest participants. The honest participants follow the protocol without doing any other activities. At the same time, the semihonest participants followed the protocol and collected the data they obtained during the process of the protocol. After the protocol, they may want to infer information from the data they collected. A protocol is secure in the semihonest model if the semihonest participants get no valuable information from the data they collected.


## 3. Privacy-Preserving Synthetic Minority Oversampling Protocol

In this section, we present our Privacy-Preserving Synthetic Minority Oversampling Protocol (PPSMOS) and analyze its security aspect.Suppose that Alice has the total datasetP=p1,p2,…,phT with pi=pi1,pi2,…,pin with 1≤i≤t. To simplify, Alice puts all the minority samples in front of P. In other words, we denote the minority subclass by Pmin=p1,p2,…,pmT where m is the number of the minority samples. Both Alice and Bob wish to generate a minority sample pnew based on P. After the protocol, Bob gets the output pnew under the condition that Alice and Bob cannot know any information about pnew and P, respectively.


### 3.1. PPSMOS

#### 3.1.1. Input

Alice inputsP=p1,p2,…,phT, where pi=pi1,pi2,…,pin and 1≤i≤h, with the first m elements Pmin=p1,p2,…,pmT belonging to the minority class. Bob inputs nothing.


#### 3.1.2. Output

Bob obtains a newly synthesized minority samplepnew while Alice gets nothing.


#### 3.1.3. Preprocessing Stage

(1)
Alice calls the key generation algorithm of the fully homomorphic encryption system to generate the system keypk,sk.(2)
Alice computes the ciphertextEP as follows.(i)
EP=Ep1,Ep2,…,EphT where Epi=Epi1,Epi2,…,Epin(3)
Alice constructs a matrixS that contains the indices of the k-nearest neighbors of every element in Pmin, i.e., every sij in S presents the index of the jth nearest neighbor of pi in the minority class Pmin.(2)S=s11⋯s1k⋮⋱⋮sm1⋯smk.(4)
Alice disclosespk,EP and S on the network.(5)
Bob getspk,EP and S published by Alice.


#### 3.1.4. Processing Stage

(1)
Bob generates two random integers,α and β, where 1≤α≤m and 1≤β≤k.(2)
Bob generates two random numbersgap and noise where 0<gap<1. Then, using the public key pk and the encryption algorithm E∗, he computes the ciphertext Egap and Enoise.(3)
Using both ciphertexts obtained in (2), Bob does the following operation to produceX. Then he sends X to Alice.(3)X=Egap∗Epsαβ−Epα+Epα∗Enoise=Egap∗Epsαβ1−Epα1+Epα1∗EnoiseEgap∗Epsαβ2−Epα2+Epα2∗Enoise⋯Egap∗Epsαβn−Epαn+Epαn∗EnoiseT.(4)
Alice decryptsX using the secret key sk and obtains DX=γ1,γ2,…,γn , before sending it to Bob.(5)
Bob gets the final resultpnew as follows.(4)pnew=γ1noise,γ2noise,…,γnnoise.


### 3.2. Security Analysis

Theorem 1.
Under the assumption that the underlying fully homomorphic encryption scheme is secure, PPSMOS securely generates the minority samples in the semihonest model.Proof.
First, we analyse the situation where Alice is corrupted. In PPSMOS, Alice receivesX from Bob. Using the secret key, Alice is able to recover the plaintext:(5)DX=γ1,γ2,…,γn=gap∗psαβ−pα+pα∗noise.
Asα, β, and gap are random numbers, Alice does not have the ability to infer the matchup between DX and its samples. Furthermore, since DX are confused by the random number noise, Alice has no way of knowing Bob's newly generated point pnew. Hence, even if Alice is corrupted, Bob’s output is isolated from Alice and, thus, secure.
Next, we analyze the case that Bob is corrupted. In the preprocessing stage, Bob gets the ciphertextEP and a matrix S, which are both disclosed by Alice. As the underlying homomorphic encryption scheme is secure in the semihonest model, Bob will not be able to infer any information regarding Alice’s private input from EP. As S presents the index of the jth nearest neighbor of pi in the minority class Pmin, Bob is unable to get any information of the specific point of P through S. Therefore, even if Bob is corrupted, Alice’s private information is still secure and undisclosed from Bob.
Thus, we can deduct that that Theorem1 holds.


## 3.1. PPSMOS

### 3.1.1. Input

Alice inputsP=p1,p2,…,phT, where pi=pi1,pi2,…,pin and 1≤i≤h, with the first m elements Pmin=p1,p2,…,pmT belonging to the minority class. Bob inputs nothing.


### 3.1.2. Output

Bob obtains a newly synthesized minority samplepnew while Alice gets nothing.


### 3.1.3. Preprocessing Stage

(1)
Alice calls the key generation algorithm of the fully homomorphic encryption system to generate the system keypk,sk.(2)
Alice computes the ciphertextEP as follows.(i)
EP=Ep1,Ep2,…,EphT where Epi=Epi1,Epi2,…,Epin(3)
Alice constructs a matrixS that contains the indices of the k-nearest neighbors of every element in Pmin, i.e., every sij in S presents the index of the jth nearest neighbor of pi in the minority class Pmin.(2)S=s11⋯s1k⋮⋱⋮sm1⋯smk.(4)
Alice disclosespk,EP and S on the network.(5)
Bob getspk,EP and S published by Alice.


### 3.1.4. Processing Stage

(1)
Bob generates two random integers,α and β, where 1≤α≤m and 1≤β≤k.(2)
Bob generates two random numbersgap and noise where 0<gap<1. Then, using the public key pk and the encryption algorithm E∗, he computes the ciphertext Egap and Enoise.(3)
Using both ciphertexts obtained in (2), Bob does the following operation to produceX. Then he sends X to Alice.(3)X=Egap∗Epsαβ−Epα+Epα∗Enoise=Egap∗Epsαβ1−Epα1+Epα1∗EnoiseEgap∗Epsαβ2−Epα2+Epα2∗Enoise⋯Egap∗Epsαβn−Epαn+Epαn∗EnoiseT.(4)
Alice decryptsX using the secret key sk and obtains DX=γ1,γ2,…,γn , before sending it to Bob.(5)
Bob gets the final resultpnew as follows.(4)pnew=γ1noise,γ2noise,…,γnnoise.


## 3.1.1. Input

Alice inputsP=p1,p2,…,phT, where pi=pi1,pi2,…,pin and 1≤i≤h, with the first m elements Pmin=p1,p2,…,pmT belonging to the minority class. Bob inputs nothing.


## 3.1.2. Output

Bob obtains a newly synthesized minority samplepnew while Alice gets nothing.


## 3.1.3. Preprocessing Stage

(1)
Alice calls the key generation algorithm of the fully homomorphic encryption system to generate the system keypk,sk.(2)
Alice computes the ciphertextEP as follows.(i)
EP=Ep1,Ep2,…,EphT where Epi=Epi1,Epi2,…,Epin(3)
Alice constructs a matrixS that contains the indices of the k-nearest neighbors of every element in Pmin, i.e., every sij in S presents the index of the jth nearest neighbor of pi in the minority class Pmin.(2)S=s11⋯s1k⋮⋱⋮sm1⋯smk.(4)
Alice disclosespk,EP and S on the network.(5)
Bob getspk,EP and S published by Alice.


## 3.1.4. Processing Stage

(1)
Bob generates two random integers,α and β, where 1≤α≤m and 1≤β≤k.(2)
Bob generates two random numbersgap and noise where 0<gap<1. Then, using the public key pk and the encryption algorithm E∗, he computes the ciphertext Egap and Enoise.(3)
Using both ciphertexts obtained in (2), Bob does the following operation to produceX. Then he sends X to Alice.(3)X=Egap∗Epsαβ−Epα+Epα∗Enoise=Egap∗Epsαβ1−Epα1+Epα1∗EnoiseEgap∗Epsαβ2−Epα2+Epα2∗Enoise⋯Egap∗Epsαβn−Epαn+Epαn∗EnoiseT.(4)
Alice decryptsX using the secret key sk and obtains DX=γ1,γ2,…,γn , before sending it to Bob.(5)
Bob gets the final resultpnew as follows.(4)pnew=γ1noise,γ2noise,…,γnnoise.


## 3.2. Security Analysis

Theorem 1.
Under the assumption that the underlying fully homomorphic encryption scheme is secure, PPSMOS securely generates the minority samples in the semihonest model.Proof.
First, we analyse the situation where Alice is corrupted. In PPSMOS, Alice receivesX from Bob. Using the secret key, Alice is able to recover the plaintext:(5)DX=γ1,γ2,…,γn=gap∗psαβ−pα+pα∗noise.
Asα, β, and gap are random numbers, Alice does not have the ability to infer the matchup between DX and its samples. Furthermore, since DX are confused by the random number noise, Alice has no way of knowing Bob's newly generated point pnew. Hence, even if Alice is corrupted, Bob’s output is isolated from Alice and, thus, secure.
Next, we analyze the case that Bob is corrupted. In the preprocessing stage, Bob gets the ciphertextEP and a matrix S, which are both disclosed by Alice. As the underlying homomorphic encryption scheme is secure in the semihonest model, Bob will not be able to infer any information regarding Alice’s private input from EP. As S presents the index of the jth nearest neighbor of pi in the minority class Pmin, Bob is unable to get any information of the specific point of P through S. Therefore, even if Bob is corrupted, Alice’s private information is still secure and undisclosed from Bob.
Thus, we can deduct that that Theorem1 holds.


## 4. Borderline Privacy-Preserving Synthetic Minority Oversampling Protocol

In this section, we present our Borderline Privacy-Preserving Synthetic Minority Oversampling Protocol (Borderline-PPSMOS) and analyze its security aspect.Suppose that Alice has a minority classP=p1,p2,…,pmT, where pi=pi1,pi2,…,pin. Bob has a majority class Q=q1,q2,…,qtT, where qi=qi1,qi2,…,qin. Both Alice and Bob wish to generate a minority sample pnew based on P and Q. After the protocol, Bob gets the output pnew. Meanwhile, Alice cannot know any information about pnew and Q, and Bob cannot know any information about P.


### 4.1. Borderline-PPSMOS

#### 4.1.1. Input

Alice inputsP=p1,p2,…,pmT where pi=pi1,pi2,…,pin. Bob inputs Q=q1,q2,…,qtT where qi=qi1,qi2,…,qin.


#### 4.1.2. Output

Alice gets nothing. Bob obtains a newly synthesized minority samplepnew.


#### 4.1.3. Preprocessing Stage

(1)
Alice generates the keyspk,sk of the fully homomorphic encryption system.(2)
Alice computes the ciphertextEP as follows.(i)
EP=Ep1,Ep2,…,EpmT where Epi=Epi1,Epi2,…,Epin(3)
Alice constructs a matrixD, where dij in D represents the square power of the Euclidean distance between the point pi and its jth-nearest neighbors.(6)D=d11⋯d1k⋮⋱⋮dm1⋯dmk.(4)
Alice encrypts every element inD and obtains ED.(5)
Alice disclosespk,EP and ED on the network.(6)
Bob getspk,EP and ED which were published by Alice.


#### 4.1.4. Processing Stage

(1)
Bob computesEQ using pk and the encryption algorithm E∗.(i)
EQ=Eq1,Eq2,…,EqtT, where Eqi=Eqi1,Eqi2,…,Eqn(2)
For every elementpi in P, Bob calculates the ciphertext of the square power of the Euclidean distance between the pi and the elements in Q.(7)EV=Ev11⋯Ev1t⋮⋱⋮Evm1⋯Evmt.(i)
whereEvij=Epi1−Eqj12+Epi2−Eqj22+⋯+Epin−Eqjn2(3)
Bob generatesm random numbers σ1,σ2,…,σm. Then, he obtains the ciphertext Eσ1,Eσ2,…,Eσm, using the public key pk and the encryption algorithm E∗.(4)
Bob connectsEV to the encryption matrix ED to form a new matrix EG.(8)EG=Ed11+Eσ1⋯Ed1k+Eσ1Ev11+Eσ1⋯Ev1t+Eσ1⋮⋱⋮⋮⋱⋮Edm1+Eσm⋯Edmk+EσmEvm1+Eσm⋯Evmt+Eσm.(5)
Bob performs row and column confusion onEG to obtain the confused matrix EG′. Then he sends EG′ to Alice.(6)
Alice receivesEG′ and decrypts it with the private key sk to obtain the matrix G′.(9)G′=g11g12⋯g1n+t⋮⋮⋱⋮gm1gm2⋯gmn+t.(7)
For every row inG′, Alice computes the k-smallest value and denotes the position of these elements in the matrix R. Then, Alice sends R to Bob.(10)R=r11⋯r1k⋮⋱⋮rm1⋯rmk.(8)
Bob performs the inverse obfuscation on matrixR to get matrix B.(11)B=b11⋯b1k⋮⋱⋮bm1⋯bmk.(9)
For theith row in B, where 1≤i≤k, Bob counts the number cnti of the elements smaller than k+1. Similar to that in Borderline-SMOTE, we call the point pi∈Danger, if k/2≤cnti<k.(10)
Bob randomly selects a pointpi from the class Danger and randomly selects an element bix, which is greater than k from the ith row of B.(11)
Bob generates two random numbers,gap and noise, where 0<gap<1. Next, he generates the ciphertext Egap and Enoise by using the public key pk and the encryption algorithm E∗.(12)
Bob performs an operation using the ciphertextEgap and Enoise to obtain X as follows. Then he sends X to Alice.(12)X=Egap∗Eqbix−Epi+Epi∗Enoise=Egap∗Eqbix1−Epi1+Epi1∗EnoiseEgap∗Eqbix2−Epi2+Epi2∗Enoise,…,Egap∗Eqbixn−Epin+Epin∗EnoiseT.(13)
Alice decryptsX using the secret key sk and obtains DX=γ1,γ2,…,γn. She then proceeds to send DX to Bob.(14)
Bob gets the final resultpnew as follows.(13)pnew=γ1noise,γ2noise,…,γnnoise.


### 4.2. Security Analysis

Theorem 2.
Under the assumption that the underlying fully homomorphic encryption scheme is secure, Borderline-PPSMOS securely generates the minority sample in the semihonest model.Proof.
First, we analyse the situation where Alice is corrupted. In Borderline-PPSMOS, Alice receivesEG′ from Bob. Alice is able to recover the plaintext using the private key. However, since Bob obtained EG′ by applying row and column confusion operation on EG, Alice will not be able to infer the true rank order of EG. Furthermore, as EG′ is confused by using Eσ1,Eσ2,…,Eσm, where σ1,σ2,…,σm are random numbers, Alice will not be able to know the information of set Q owned by Bob.
Also, when Alice receivesX from Bob, she can recover the plaintext:(14)DX=γ1,γ2,…,γn=gap∗qbix−pi+pi∗noise.
However, asi,x and gap are random numbers, Alice does not have the ability to infer the matchup between DX and its samples. In addition, as DX is confused by the random number noise, Alice has no way of knowing Bob’s newly generated point pnew. Hence, even if Alice is corrupted, Bob’s input and output are totally isolated from Alice and still secure.
Next, we analyze the case where Bob is corrupted. In the preprocessing stage, Bob gets the ciphertextEP, ED and public key pk. As the underlying homomorphic encryption scheme is secure in the semihonest model, Bob is unable to infer any information regarding Alice’ private input from EP and ED. In the processing stage, Alice computes the k-smallest value and denotes the position of these elements in matrix R. During this step, Alice only sends the location index to Bob, which does not reveal any information of Alice’s input. Next, Bob gets DX=γ1,γ2,…,γn from Alice. Similarly, as the homomorphic encryption scheme is secure in the semihonest model, Bob cannot infer pi from gap∗qbix−pi+pi. Thus, even if Bob is corrupted, Alice’s private information is still secure and undisclosed from Bob.
Therefore, we can deduce that Borderline-PPSMOS is secure in the semihonest model, under the fully homomorphic encryption scheme, i.e., Theorem2 holds.


## 4.1. Borderline-PPSMOS

### 4.1.1. Input

Alice inputsP=p1,p2,…,pmT where pi=pi1,pi2,…,pin. Bob inputs Q=q1,q2,…,qtT where qi=qi1,qi2,…,qin.


### 4.1.2. Output

Alice gets nothing. Bob obtains a newly synthesized minority samplepnew.


### 4.1.3. Preprocessing Stage

(1)
Alice generates the keyspk,sk of the fully homomorphic encryption system.(2)
Alice computes the ciphertextEP as follows.(i)
EP=Ep1,Ep2,…,EpmT where Epi=Epi1,Epi2,…,Epin(3)
Alice constructs a matrixD, where dij in D represents the square power of the Euclidean distance between the point pi and its jth-nearest neighbors.(6)D=d11⋯d1k⋮⋱⋮dm1⋯dmk.(4)
Alice encrypts every element inD and obtains ED.(5)
Alice disclosespk,EP and ED on the network.(6)
Bob getspk,EP and ED which were published by Alice.


### 4.1.4. Processing Stage

(1)
Bob computesEQ using pk and the encryption algorithm E∗.(i)
EQ=Eq1,Eq2,…,EqtT, where Eqi=Eqi1,Eqi2,…,Eqn(2)
For every elementpi in P, Bob calculates the ciphertext of the square power of the Euclidean distance between the pi and the elements in Q.(7)EV=Ev11⋯Ev1t⋮⋱⋮Evm1⋯Evmt.(i)
whereEvij=Epi1−Eqj12+Epi2−Eqj22+⋯+Epin−Eqjn2(3)
Bob generatesm random numbers σ1,σ2,…,σm. Then, he obtains the ciphertext Eσ1,Eσ2,…,Eσm, using the public key pk and the encryption algorithm E∗.(4)
Bob connectsEV to the encryption matrix ED to form a new matrix EG.(8)EG=Ed11+Eσ1⋯Ed1k+Eσ1Ev11+Eσ1⋯Ev1t+Eσ1⋮⋱⋮⋮⋱⋮Edm1+Eσm⋯Edmk+EσmEvm1+Eσm⋯Evmt+Eσm.(5)
Bob performs row and column confusion onEG to obtain the confused matrix EG′. Then he sends EG′ to Alice.(6)
Alice receivesEG′ and decrypts it with the private key sk to obtain the matrix G′.(9)G′=g11g12⋯g1n+t⋮⋮⋱⋮gm1gm2⋯gmn+t.(7)
For every row inG′, Alice computes the k-smallest value and denotes the position of these elements in the matrix R. Then, Alice sends R to Bob.(10)R=r11⋯r1k⋮⋱⋮rm1⋯rmk.(8)
Bob performs the inverse obfuscation on matrixR to get matrix B.(11)B=b11⋯b1k⋮⋱⋮bm1⋯bmk.(9)
For theith row in B, where 1≤i≤k, Bob counts the number cnti of the elements smaller than k+1. Similar to that in Borderline-SMOTE, we call the point pi∈Danger, if k/2≤cnti<k.(10)
Bob randomly selects a pointpi from the class Danger and randomly selects an element bix, which is greater than k from the ith row of B.(11)
Bob generates two random numbers,gap and noise, where 0<gap<1. Next, he generates the ciphertext Egap and Enoise by using the public key pk and the encryption algorithm E∗.(12)
Bob performs an operation using the ciphertextEgap and Enoise to obtain X as follows. Then he sends X to Alice.(12)X=Egap∗Eqbix−Epi+Epi∗Enoise=Egap∗Eqbix1−Epi1+Epi1∗EnoiseEgap∗Eqbix2−Epi2+Epi2∗Enoise,…,Egap∗Eqbixn−Epin+Epin∗EnoiseT.(13)
Alice decryptsX using the secret key sk and obtains DX=γ1,γ2,…,γn. She then proceeds to send DX to Bob.(14)
Bob gets the final resultpnew as follows.(13)pnew=γ1noise,γ2noise,…,γnnoise.


## 4.1.1. Input

Alice inputsP=p1,p2,…,pmT where pi=pi1,pi2,…,pin. Bob inputs Q=q1,q2,…,qtT where qi=qi1,qi2,…,qin.


## 4.1.2. Output

Alice gets nothing. Bob obtains a newly synthesized minority samplepnew.


## 4.1.3. Preprocessing Stage

(1)
Alice generates the keyspk,sk of the fully homomorphic encryption system.(2)
Alice computes the ciphertextEP as follows.(i)
EP=Ep1,Ep2,…,EpmT where Epi=Epi1,Epi2,…,Epin(3)
Alice constructs a matrixD, where dij in D represents the square power of the Euclidean distance between the point pi and its jth-nearest neighbors.(6)D=d11⋯d1k⋮⋱⋮dm1⋯dmk.(4)
Alice encrypts every element inD and obtains ED.(5)
Alice disclosespk,EP and ED on the network.(6)
Bob getspk,EP and ED which were published by Alice.


## 4.1.4. Processing Stage

(1)
Bob computesEQ using pk and the encryption algorithm E∗.(i)
EQ=Eq1,Eq2,…,EqtT, where Eqi=Eqi1,Eqi2,…,Eqn(2)
For every elementpi in P, Bob calculates the ciphertext of the square power of the Euclidean distance between the pi and the elements in Q.(7)EV=Ev11⋯Ev1t⋮⋱⋮Evm1⋯Evmt.(i)
whereEvij=Epi1−Eqj12+Epi2−Eqj22+⋯+Epin−Eqjn2(3)
Bob generatesm random numbers σ1,σ2,…,σm. Then, he obtains the ciphertext Eσ1,Eσ2,…,Eσm, using the public key pk and the encryption algorithm E∗.(4)
Bob connectsEV to the encryption matrix ED to form a new matrix EG.(8)EG=Ed11+Eσ1⋯Ed1k+Eσ1Ev11+Eσ1⋯Ev1t+Eσ1⋮⋱⋮⋮⋱⋮Edm1+Eσm⋯Edmk+EσmEvm1+Eσm⋯Evmt+Eσm.(5)
Bob performs row and column confusion onEG to obtain the confused matrix EG′. Then he sends EG′ to Alice.(6)
Alice receivesEG′ and decrypts it with the private key sk to obtain the matrix G′.(9)G′=g11g12⋯g1n+t⋮⋮⋱⋮gm1gm2⋯gmn+t.(7)
For every row inG′, Alice computes the k-smallest value and denotes the position of these elements in the matrix R. Then, Alice sends R to Bob.(10)R=r11⋯r1k⋮⋱⋮rm1⋯rmk.(8)
Bob performs the inverse obfuscation on matrixR to get matrix B.(11)B=b11⋯b1k⋮⋱⋮bm1⋯bmk.(9)
For theith row in B, where 1≤i≤k, Bob counts the number cnti of the elements smaller than k+1. Similar to that in Borderline-SMOTE, we call the point pi∈Danger, if k/2≤cnti<k.(10)
Bob randomly selects a pointpi from the class Danger and randomly selects an element bix, which is greater than k from the ith row of B.(11)
Bob generates two random numbers,gap and noise, where 0<gap<1. Next, he generates the ciphertext Egap and Enoise by using the public key pk and the encryption algorithm E∗.(12)
Bob performs an operation using the ciphertextEgap and Enoise to obtain X as follows. Then he sends X to Alice.(12)X=Egap∗Eqbix−Epi+Epi∗Enoise=Egap∗Eqbix1−Epi1+Epi1∗EnoiseEgap∗Eqbix2−Epi2+Epi2∗Enoise,…,Egap∗Eqbixn−Epin+Epin∗EnoiseT.(13)
Alice decryptsX using the secret key sk and obtains DX=γ1,γ2,…,γn. She then proceeds to send DX to Bob.(14)
Bob gets the final resultpnew as follows.(13)pnew=γ1noise,γ2noise,…,γnnoise.


## 4.2. Security Analysis

Theorem 2.
Under the assumption that the underlying fully homomorphic encryption scheme is secure, Borderline-PPSMOS securely generates the minority sample in the semihonest model.Proof.
First, we analyse the situation where Alice is corrupted. In Borderline-PPSMOS, Alice receivesEG′ from Bob. Alice is able to recover the plaintext using the private key. However, since Bob obtained EG′ by applying row and column confusion operation on EG, Alice will not be able to infer the true rank order of EG. Furthermore, as EG′ is confused by using Eσ1,Eσ2,…,Eσm, where σ1,σ2,…,σm are random numbers, Alice will not be able to know the information of set Q owned by Bob.
Also, when Alice receivesX from Bob, she can recover the plaintext:(14)DX=γ1,γ2,…,γn=gap∗qbix−pi+pi∗noise.
However, asi,x and gap are random numbers, Alice does not have the ability to infer the matchup between DX and its samples. In addition, as DX is confused by the random number noise, Alice has no way of knowing Bob’s newly generated point pnew. Hence, even if Alice is corrupted, Bob’s input and output are totally isolated from Alice and still secure.
Next, we analyze the case where Bob is corrupted. In the preprocessing stage, Bob gets the ciphertextEP, ED and public key pk. As the underlying homomorphic encryption scheme is secure in the semihonest model, Bob is unable to infer any information regarding Alice’ private input from EP and ED. In the processing stage, Alice computes the k-smallest value and denotes the position of these elements in matrix R. During this step, Alice only sends the location index to Bob, which does not reveal any information of Alice’s input. Next, Bob gets DX=γ1,γ2,…,γn from Alice. Similarly, as the homomorphic encryption scheme is secure in the semihonest model, Bob cannot infer pi from gap∗qbix−pi+pi. Thus, even if Bob is corrupted, Alice’s private information is still secure and undisclosed from Bob.
Therefore, we can deduce that Borderline-PPSMOS is secure in the semihonest model, under the fully homomorphic encryption scheme, i.e., Theorem2 holds.


## 5. Performance Analysis

In this section, we present the performance analysis of both PPSMOS and Borderline-PPSMOS. On the efficiency analysis, we look at computational complexity and communication complexity. Given thath is the size of Alice’s input in PPSMOS, n is the feature size, t is the size of the majority class, m is the size of the minority class, and k is a parameter, we analyze the protocols’ performances as follows.First, we analyze the performance of PPSMOS. During the preprocessing stage, Alice performs the encryption operation forhn times while Bob gets hn ciphertexts. Furthermore, in the processing stage, Bob performs encryption operation 2 times and 2n times for each homomorphic additive operation and homomorphic multiplicative operation. Alice, then, performs decryption operations for n times. Bob sends n ciphertexts to Alice.Secondly, we analyze the efficiency of Borderline-PPSMOS. In the preprocessing stage, Alice performs the encryption operations formn+mk times, while Bob gets tn+mk ciphertexts. Next, in the processing stage, Bob performs encryption operation for tn+m+2 times, homomorphic additive operation for mtn+t+km+2n times, and homomorphic multiplicative operation for mtn+2n times. Alice performs decryption operations for mk+t+n times. Finally, Bob transferred mk+t+n ciphertexts to Alice.We summarise the computational complexity and communication complexity of both protocols below in Table1.Table 1
Performance analysis of PPSMOS and Borderline-PPSMOS.
ProtocolPreprocessing stageProcessing stageComputational complexityCommunication complexityComputational complexityCommunication complexityPPSMOShnhn5n + 2nBorderline-PPSMOSmn+mktn+mkm+mt+2t+3n+4mk+2mt+m+2mk+t+nWe visualize the operational efficiency of both PPSMOS and Borderline-PPSMOS during the processing stage by instantiating the parameters, as shown below in Figures1–4.Figure 1
Computational Complexity (left) and Communication Complexity (right) of PPSMOS and Borderline-PPSMOS by varyingn when m=100,t=50,k=5.
(a)(b)Figure 2
Computational Complexity (left) and Communication Complexity (right) of PPSMOS and Borderline-PPSMOS by varyingk when m=100,t=50,n=25.
(a)(b)Figure 3
Computational Complexity (left) and Communication Complexity (right) of PPSMOS and Borderline-PPSMOS by varyingm when n=25,t=50,k=5.
(a)(b)Figure 4
Computational Complexity (left) and Communication Complexity (right) of PPSMOS and Borderline-PPSMOS for the cost by varyingt when m=100,n=25,k=5.
(a)(b)From these figures, we can conclude the following: (1) the computational complexity and communication complexity of PPSMOS are lower than those of Borderline-PPSMOS; (2) the computational complexity and communication complexity of PPSMOS depend only on the feature sizen; (3) the computational complexity and communication complexity of Borderline-PPSMOS depend on almost all of the parameters, i.e., n, t, m and k; (4) Borderline Synthetic Minority Oversampling Protocol achieves better TP rate and F-Value than Synthetic Minority Oversampling Protocol [22]. Furthermore, as our privacy-preserving schemes do not affect the TP rate and F-Value of the underlying Minority Oversampling protocol, we can further deduct that Borderline-PPSMOS achieves a better TP rate and F-Value than PPSMOS.


## 6. Conclusion

In this paper, we propose two novel privacy-preserving oversampling protocols, PPSMOS and Borderline-PPSMOS, that are aimed to address the imbalanced dataset issue while preserving the privacy of the participants’ input and output.PPSMOS works in a manner where the client inputs no majority examples, as opposed to Borderline-PPSMOS, where the client has some majority examples. Both PPSMOS and Borderline-PPSMOS are secure in the semihonest model. This means that both methods are suitable for the preprocessing stage of machine-learning and applicable to any cases where synthesizing minority examples in a privacy-preserving manner is needed. Our results show that PPSMOS is more efficient than Borderline-PPSMOS in general, while Borderline-PPSMOS achieves better TP rate and F-Value than PPSMOS.While doing our work in the semihonest model and through our analysis, we found that our protocols are unable to resist malicious attacks, and their efficiency needs improvements. As future work, we will continue improving our research on these two aspects, as well as focusing on designing better privacy-preserving protocols that are to be used in the preprocessing stage of machine-learning.



---

*Source: 3068199-2022-03-10.xml*