# PPSEB: A Postquantum Public-Key Searchable Encryption Scheme on Blockchain for E-Healthcare Scenarios

Authors: Gang Xu; Shiyuan Xu; Yibo Cao; Fan Yun; Yu Cui; Yiying Yu; Ke Xiao
Journal: Security and Communication Networks
 (2022)

---

## Abstract

In the current E-healthcare scenarios, medical institutions are used to encrypt the information and store it in an Electronic Health Record (EHR) system in order to ensure the privacy of medical information. To realize data sharing, a Public-key Encryption with Keyword Search (PEKS) scheme is indispensable, ensuring doctors search for medical information in the state of ciphertext. However, the traditional PEKS scheme cannot resist the keyword guessing quantum computing attacks, and its security depends on the confidentiality of the secret key. In addition, classical PEKS hand over the search process to a third party, affecting the search results’ accuracy. Therefore, we proposed a postquantum Public-key Searchable Encryption scheme on Blockchain (PPSEB) for E-healthcare scenarios. Firstly, we utilized a lattice-based cryptographic primitive to ensure the security of the search process and achieve forward security to avoid key leakage of medical information. Secondly, we introduced blockchain technology to solve the problem of third-party untrustworthiness in the search process. Finally, through security analysis, we prove the correctness and forward security of the solution in the E-healthcare scenarios, and the comprehensive performance evaluation demonstrates the efficiency of our scheme compared with other existing schemes.


---

## Body

## 1. Introduction

In the current medical scenarios, medical institutions generate a large amount of patient medical data. These data are difficult to supervise, lack necessary technical support, and cost medical institutions many resources. To solve this problem, many medical institutions have adopted EHR systems to reduce the burden and cost of maintaining medical information [1]. The EHR system is a digital health file with medical information as the main body and information sharing as the core. It aims to realize that patients can manage their medical data, and doctors can also access the patient’s medical data if they have permission. However, outsourcing management of the EHR system is not an ideal choice. Because the third-party organization responsible for storing the EHR system has too much power, once a malicious attacker buys it, it can launch a collision attack on the medical data in the system to threaten the privacy of medical data. To avoid this situation, medical institutions usually encrypt medical data through various encryption schemes [2] and store it in the EHR system. Therefore, how to realize the sharing of medical data between patients and doctors in the ciphertext state is a problem to be solved. Thus, Public Key Encryption with Keyword Search (PEKS) [3]is a marvelous candidate in cloud-assisted E-healthcare scenarios, realizing medical data retrieval without privacy leakage. As efficient encryption primitive, it ensures searchable encrypted medical data through keywords.Although the existing proposed PEKS schemes [4–6]have brought significant benefits to the Internet of Things, there are four significant obstacles to the widespread PEKS in systems in recent decades. Initially, most PEKS schemes were established based on traditional hardness cryptography problems. Nevertheless, with the advent of quantum computers [7] and quantum information [8], the PEKS scheme will be threatened exponentially. Recent breakthrough articles [7] indicate that shortly, it is possible to adopt quantum computers in a realistic view, putting forward higher requirements for postquantum cryptographic searchable encryption schemes than before. Secondly, the most computational cost of cloud servers is to search target data from the third-party service agency since cloud servers need to execute a verification procedure for the corresponding keyword. Due to the exorbitant public-key encryption operations, the existing PEKS scheme introduces a significant calculation overhead. In the E-healthcare scenarios, the cloud server can work with medical data from mobile medical detection devices simultaneously to retrieve the data of multiple doctors. Therefore, it has a performance bottleneck on the medical cloud servers. Thirdly, with the explosive utilization of mobile medical detection equipment, most schemes have key exposure problems [9]. The existing PEKS scheme cannot guarantee the forward privacy of the key. The existing PEKS scheme cannot guarantee the forward privacy of the key. Once the doctor’s secret key is compromised, the attacker can trace the trapdoor content previously submitted by the doctor, thereby further infringing on the confidentiality of the outsourced data [10]. In this regard, we optimize the lattice cryptography in our scheme to make the key have relations with period to ensure that the key exposure at the previous period will not affect the medical data confidentiality at the later period and achieve the forward security of the key [11]. Last but not least, the search function of the traditional PEKS scheme is generally delivered to the service party. However, the untrustworthiness of the service party will cause attackers to generate Keyword Guess Attacks (KGA) on medical information. Fortunately, blockchain can effectively solve this problem [12–17]. Blockchain is a new database technology that can realize decentralized distributed architecture design. Its core technical concept was proposed by Satoshi Nakamoto [18] in 2008. Blockchain, as a distributed public ledger, records all transactions packaged in the block without the need for third-party control and ensures the safety and traceability of each transaction record [19]. After a single block is generated, all nodes in the blockchain network use a consensus algorithm to determine whether the block is on the chain, and each block is connected by a hash function, thereby effectively ensuring the immutability of transaction information. Therefore, using blockchain technology to replace the service party in PEKS is an effective way to solve the problem of the untrustworthiness of the service party. For example, [20] replaces the traditional centralized server with a decentralized blockchain system, supports forward and backward privacy, and realizes privacy protection. [21] proposed a novel PEKS scheme, which eliminates the reliance on third-party institutions and makes the entire program completely decentralized. Therefore, to solve the above-mentioned hindrances, we propose a postquantum public-key searchable encryption on blockchain for cloud-assisted E-healthcare scenarios, called PPSEB, based on lattice cryptography [22, 23], one of the postquantum cryptographic primitives, ensuring a robust security level. In addition, we reduce the security of PPSEB to the Learning WithError (LWE) hardness assumption, which can oppose keyword guessing attacks based on quantum computing launched by malicious attackers effectively.In our proposed scheme, the patient initially encrypts medical data and its keywords under the public key of the doctor and transmits the corresponding ciphertext to the cloud server for storage. Then, the medical doctor will utilize his/her secret key to compute a trapdoor corresponding to the keyword and then uploads it to the blockchain. Further, the smart contracts on blockchain search for the keyword ciphertext corresponding to the trapdoor and return its number to the cloud server. Finally, the cloud server sends the ciphertext of medical information matching the keyword to the doctor. In summary, we elaborate our main contributions as follows:(1)
We propose a postquantum Public-key Searchable Encryption on Blockchain (PPSEB) for the E-healthcare scenarios. PPSEB is constructed on lattice-based public-key searchable encryption based on the LWE hardness assumption.(2)
We then introduce blockchain technology into our proposed scheme in response to the untrustworthiness of third parties during the search process. Therefore, we achieve the decentralization architecture of the PPSEB oracle and enhance the security level.(3)
PPSEB achieves forward security in order to solve the key leakage of various existing public-key searchable encryption algorithms.(4)
We give the computational proof of the correctness and forward security of PPSEB. Furthermore, the comprehensive implementation performance evaluation represents that our scheme is efficient in terms of testing time and computational cost compared with existing outperforming E-healthcare schemes and is suitable for medical scenarios.The structure of our paper is organized as follows. In Section2, we propose the design goals and security models of our scheme, considering three existing challenges for the proposed PPSEB scheme and the solution to make PPSEB work better in the medical scenarios. In Section 3, we propose our preliminaries of lattice and trapdoor. In Section 4, we present our PPSEB scheme and the main steps of our scheme, including, PPSEB.Initialization, PPSEB.KeyExt, PPSEB.Encrypt, PPSEB.PEKS, PPSEB.Trapdoor, PPSEB.Verification, and PPSEB.Decrypt. In Section 5, we provide the security analysis of PPSEB based on correctness and provable security. In Section 6, a precise performance evaluation is proposed by our paper. Finally, we conclude this paper in Section 7.


## 2. Design Goals and Security Models

### 2.1. Design Goals

In this paper, we propose three existing challenges for the proposed PPSEB scheme:(1)
How to make PPSEB resistant to the untrustworthy problem of the service party. In the traditional searchable encryption scheme, a third-party organization is generally responsible for searching medical information, which makes malicious attackers collude with third-party organizations to provide unreliable search results. Therefore, we use blockchain to replace traditional third-party agencies.(2)
How to achieve the forward security of PPSEB. Key exposure is a thorny problem faced by existing searchable encryption schemes. Once the private key of the doctor is lost, the attacker can forge the doctor to initiate an inquiry for medical information, and the privacy of medical information cannot be guaranteed. Therefore, how to use lattice-based cryptography to ensure that the leakage of the master key used at this time will not result in the leakage of the past session key is a problem to be solved.(3)
How to realize PPSEB to resist KGA under quantum computing. The existing searchable encryption scheme cannot guarantee the security of the search process under the attack of quantum computing, and there is a significant commonality between the keywords of medical information. Once the attacker is equipped with a quantum computer, it is possible to launch KGA on medical information through quantum computing, which severely threatens the blockchain system based on traditional cryptography and then exposes the private information contained in the medical information. Consequently, resisting KGA launched by quantum opponents is also a challenging problem. In order to make PPSEB work better in the medical scenarios, the solution in this article should have the following characteristics:(1)
Postquantum KGA: PPSEB can resist KGA attacks under quantum computing.(2)
Forward security: PPSEB achieves forward security to solve the problem of private key exposure.(3)
Efficiency: PPSEB has a higher computational efficiency by reducing the size of the trapdoor.


### 2.2. Security Model

In this section, we show the ciphertext indistinguishability of our scheme. We can describe several scenarios through games between challenger S and adversary A, in which S generates system security public parameters, initializes the public keys of patient and doctor. A will receive them from S and is permitted to access the oracles as below.Hash Oracle(HO): A has been permitted to access all values of HO in time t, wheret=1,2,…,η and is the total number in the period. Then, A will receive the corresponding hash value.Break-in phase: After obtaining the query aboutSKr‖t of the doctor in time t by A, S will return the corresponding SKr‖t in t time to A. We note that t∗ is the break-in period, which satisfies t>t∗.Trapdoor Oracle(TO): A inputs a keywordw to ask S for a trapdoor Tw. Then, we make the restriction t>t∗ in order to make sure the forward security, where t∗ is break-in period.Challenge phase: A takesw0∗,w1∗ in t∗ and then submits them to S to be the challenge keywords. S then selects b at random and obtains CTt∗∗. Consequently, S returns CTt∗∗ to A.Guess phase: At last, A will outputb′∈0,1. It wins the game iff b′=b.We define AdvASk=Probb′=b−1/2, which means the benefit of A to distinguish ciphertexts in t∗ successfully.


## 2.1. Design Goals

In this paper, we propose three existing challenges for the proposed PPSEB scheme:(1)
How to make PPSEB resistant to the untrustworthy problem of the service party. In the traditional searchable encryption scheme, a third-party organization is generally responsible for searching medical information, which makes malicious attackers collude with third-party organizations to provide unreliable search results. Therefore, we use blockchain to replace traditional third-party agencies.(2)
How to achieve the forward security of PPSEB. Key exposure is a thorny problem faced by existing searchable encryption schemes. Once the private key of the doctor is lost, the attacker can forge the doctor to initiate an inquiry for medical information, and the privacy of medical information cannot be guaranteed. Therefore, how to use lattice-based cryptography to ensure that the leakage of the master key used at this time will not result in the leakage of the past session key is a problem to be solved.(3)
How to realize PPSEB to resist KGA under quantum computing. The existing searchable encryption scheme cannot guarantee the security of the search process under the attack of quantum computing, and there is a significant commonality between the keywords of medical information. Once the attacker is equipped with a quantum computer, it is possible to launch KGA on medical information through quantum computing, which severely threatens the blockchain system based on traditional cryptography and then exposes the private information contained in the medical information. Consequently, resisting KGA launched by quantum opponents is also a challenging problem. In order to make PPSEB work better in the medical scenarios, the solution in this article should have the following characteristics:(1)
Postquantum KGA: PPSEB can resist KGA attacks under quantum computing.(2)
Forward security: PPSEB achieves forward security to solve the problem of private key exposure.(3)
Efficiency: PPSEB has a higher computational efficiency by reducing the size of the trapdoor.


## 2.2. Security Model

In this section, we show the ciphertext indistinguishability of our scheme. We can describe several scenarios through games between challenger S and adversary A, in which S generates system security public parameters, initializes the public keys of patient and doctor. A will receive them from S and is permitted to access the oracles as below.Hash Oracle(HO): A has been permitted to access all values of HO in time t, wheret=1,2,…,η and is the total number in the period. Then, A will receive the corresponding hash value.Break-in phase: After obtaining the query aboutSKr‖t of the doctor in time t by A, S will return the corresponding SKr‖t in t time to A. We note that t∗ is the break-in period, which satisfies t>t∗.Trapdoor Oracle(TO): A inputs a keywordw to ask S for a trapdoor Tw. Then, we make the restriction t>t∗ in order to make sure the forward security, where t∗ is break-in period.Challenge phase: A takesw0∗,w1∗ in t∗ and then submits them to S to be the challenge keywords. S then selects b at random and obtains CTt∗∗. Consequently, S returns CTt∗∗ to A.Guess phase: At last, A will outputb′∈0,1. It wins the game iff b′=b.We define AdvASk=Probb′=b−1/2, which means the benefit of A to distinguish ciphertexts in t∗ successfully.


## 3. Preliminary

Definition 1 (Lattice).
LetA=a1,a2,…,an∈ℝm be n linearly independent vectors in m-dimensional space. A lattice L is composed of the linear combination of all integer coefficients of a1,a2,…,an, and we can define: LA=∑i=1nxiai:i=1,2,…,n,xi∈ℤ, a1,a2,…,an is known as a basis of L. Given a prime number q, a matrix A∈ℤqn×m, we define LqA=y∈ℤm:y=ATxmodq,x∈ℤ, Lq⊥A=y∈ℤm:Ay=0modq.Definition 2 (LWE).
Assumeq be a prime number, given a random matrix A∈ℤqn×m, vector b∈ℤqm and the error distribution D on ℤq, find that the vector s∈ℤqn satisfies b=ATs+emodq, where e∈Dm.Definition 3 (Statistical Distance).
Given two variablesX, Y over a domain D, we define the statistical distance of X and Y: DX,Y=1/2⋅∑b∈DPrX=a−PrY=a.Definition 4 (Discrete Gaussian Distribution).
Letρc,σx=exp−πx−c2/σ2 be the standard
The Gaussian functionc represents the center and σ represents the standard deviation. Then we define: DL,c,σx=ρc,σx/ρc,σL, which is a Gaussian Distribution over Lattice L.Lemma 1 (TrapGen) [24].
Letq≥3, m≥2nlogq. There is a polynomial-time algorithm TrapGen, which outputs a matrix A∈ℤqn×m statistically close to the uniform distribution and a trapdoor base TrA∈ℤm×m, such that TrA≤Onlogq and TrA˜≤Onlogq.Lemma 2 (SamplePre) [25].
GivenLq⊥A, a trapdoor base TrA∈ℤm×m, a parameter s≥TrA˜ωlogm, and a vector v∈ℤqn. Then, the SamplePrealgorithm outputs a vector w statistically close to DLq⊥A,s, such that Aw=vmodq.Lemma 3 (SampleL) [26].
Set a positive integerm>n, q≥3. Given Lq⊥A and its trapdoor base TA, matrix B∈ℤqn×m′, parameter s≥TA˜ωlogm+m′ , and vector u∈ℤqn. The Sample Lalgorithm computes e∈ℤm+m′ statistically close to DLquA|B,s such that A|Be=umodq.Lemma 4 (SampleR) [26].
Set a positive integerm>n, q≥3. Given Lq⊥B and its trapdoor base TB∈ℤm×m, matrix A∈ℤqn×m′, R∈ℤqm′×m, s≥TB˜s′ωlogm and vector u∈ℤqn. The SampleRalgorithm outputs a vector e∈ℤm+m′ over DLquA|AR+B,s and satisfies A|AR+Be=umodq, where s′=maxx=1Rx.Lemma 5 (NewBasisDel) [27].
Set a positive integerm>2nlogq, q≥3. Given Lq⊥A and a trapdoor base TA∈ℤm×m, an invertible matrix R∈Dm×m, Dm×m is invertible on ℤqm×m, s≥TA˜⋅nlogq⋅ωlogm⋅m⋅ωlog1.5m. The NewBasisDel algorithm outputs Lq⊥B and a trapdoor base TB∈ℤm×m responding to Lq⊥B, where B=AR−1.Lemma 6 (SampleRwithBasis) [27].
Given a positive integerm>2nlogq, q≥3, and a random matrix A∈ℤqn×m, its column vector can generate ℤqn. The Sample R with Basis algorithm outputs an invertible matrix R∈Dm×m, a lattice Lq⊥B and its trapdoor base TB∈ℤm×m, where B=AR−1modq, TB satisfies TB˜≤Onlogq.Definition 5.
(PEKS scheme): One general PEKS scheme includes five algorithms asPEKS=Initialization,KeyExt,PEKS,Trapdoor,Verification, these algorithms are defined in the following sentences:s,X⟵Initialization⊥: In this step, it generally initializes some security parameters s, and parameters regard to the Gaussian Distribution X in one time period j. The output is just these parameters which will utilize in the next step.pk,sk⟵KeyExts: After inputting the parameter s, it will output the public key pk and secret key sk, which consist pk,sk.sε⟵PEKSpk,ε:The algorithm takes a public key pk and one keyword ε as input, and outputs a ciphertext sε of ε.tε⟵Trapdoorsk,sε: Having input the secret key sk and one keyword ε, it outputs one trapdoor tε in this algorithm.1or 0⟵Verificationtε,sε: With the input of a trapdoor tε′ and a searchable ciphertext sε, this algorithm designs to output the comparison decision bit 1 if ε′=ε, or 0 otherwise.


## 4. Our Proposed Scheme

### 4.1. Blockchain Architecture

Blockchain is essentially a decentralized database, which is a string of blocks that are associated using cryptography methods. Each transaction includes hash function, Merkle tree, and so on. In this paper, we replace the search party in searchable encryption with blockchain to ensure the credibility of the search process. As shown in Figure1, our paper optimizes and adjusts the five-layer architecture of the original blockchain and adds a data retrieval function to the application layer to ensure that the blockchain network can base on the algorithm written in the smart contract realizing the retrieval of the keyword ciphertext.Figure 1
Blockchain architecture.


### 4.2. System Model

In this section, we give an introduction to the system model of our PPSEB scheme in Figure2, with four main entities, including patient, doctor, a cloud server, and blockchain network.(1)
Patient: The patient integrates Electronic Health Record (EHR), including various medical information such as drug-using records as a patient. Moreover, the patient encrypts the EHR and uploads it to the Cloud Server. Then the patient generates a set of keywordskeywords,sequencenumber related to the specified keyword and adds blocks to the blockchain.(2)
Doctor: The doctor needs to generate a trapdoor to search for information about patients. The doctor submits the corresponding trapdoor to the blockchain.(3)
Blockchain: After receiving the trapdoor from the doctor, the blockchain network will start chain code retrieval to search the corresponding sequence number and submit it to the CloudServer.(4)
Cloud Server: After receiving the query request, the Cloud Server can use trapdoor to search for all encrypted data and return the query results of the ciphertext corresponding to the keywords to the doctor. During the entire process, the server is unable to obtain any information about the data and keywords.Figure 2
System architecture.


### 4.3. The Scheme of PPSEB

In this section, we present our proposed scheme in detail. There are mainly seven steps of our scheme, includingPPSEB.Initialization, PPSEB.KeyExt, PPSEB.Encrypt, PPSEB.PEKS, PPSEB.Trapdoor, PPSEB.Verification, and PPSEB.Decrypt, which are elaborated in the following paragraphs and algorithms.X,δ,σ,μ,H1,H2,skr,sks⟵PPSEB.Initializationk,X,δ,σ: Firstly, we have to input one security parameter k, the discrete Gaussian Distribution X and its parameters δ=δ1,δ2,…,δη, σ=σ1,σ2,…,ση in one period j, where j=1,2,…,η. After that, the initialization step is shown as follows.SKr‖j,pkr‖j⟵PPSEB.KeyExtX,δ,σ,μ,H1,H2,skr,sks,j,skr||i,i: After inputting the set Algorithm 1.Algorithm 1:X,δ,σ,μ,H1,H2,skr,sks⟵PPSEB.Initializationk,X,δ,σ.
Input: security parameter k, discrete Gaussian Distribution X, security Gaussian Distribution δ, σ.Output: The set X,δ,σ,μ,H1,H2,skr,sks(1)
Select one uniform vector randomlyμ⟵ℤqn(2)
Assume thatN=0,1,…,η and compute ℤqn×m×N⟶ℤqm×m and 0,1l1×N⟶ℤqm×m(3)
Set these two hash functions:H1:ℤqn×m×N and H2:0,1l1×N(4)
Call TrapGen(q,n) algorithm to generate pks∈ℤqn×m and sks∈ℤqm×m, where pks and sks are public key and secret key of patient, respectively(5)
Call TrapGen(q,n) algorithm to generate pkr∈ℤqn×m and skr∈ℤqm×m, where pkr and skr are public key and secret key of doctor, respectively(6)
Return the set X,δ,σ,μ,H1,H2,skr,sksX,δ,σ,μ,H1,H2,skr,sks obtained from the Initialization step, we also have to input the current period j together with the secret key skr||i in the previous period i. Then, the doctor will procedure the following operations, which shows in Algorithm 2.Algorithm 2:SKr‖j,pkr‖j⟵PPSEB.KeyExtX,δ,σ,μ,H1,H2,skr,sks,j,skr‖i,i.
Input: set X,δ,σ,μ,H1,H2,skr,sks, current time period j, secret key skr‖i in previous time period iOutput: SKr‖j and pkr‖j, where is the secret key during this period j(1)
ComputeH1pkr‖iH1pkr‖i−1…H1pkr‖1∈ℤqm×m(2)
SetRr‖j=H1pkr‖iH1pkr‖i−1...H1pkr‖1(3)
ComputepkrRr‖j−1=pkrH1pkr‖iH1pkr‖i−1...H1pkr‖1−1∈ℤqn×m(4)
Setpkr‖i=pkrRr‖i−1=pkrH1pkr‖iH1pkr‖i−1…H1pkr‖1−1(5)
ComputeH1pkr‖jH1pkr‖j−1…H1pkr‖i+1∈ℤqm×m(6)
SetRr‖i⟶j=H1pkr‖jH1pkr‖j−1…H1pkr‖i+1(7)
Call NewBasisDel pkr‖i,Rr‖i⟶j,skr‖j,δj to compute SKr‖j⟵skr‖j, where SKr||j is the secret key during this period j(8)
Computepkr‖iRr‖i⟶j−1=pkrRr‖j−1∈ℤqn×m(9)
Setpkr‖j=pkrRr‖j−1(10)
ReturnSKr‖j and pkr‖jN,W,IM⟵PPSEB.EncryptM,pkr‖j: Firstly, the patient divides the medical data M into groups, named M=M1,M2,…,Mn, and generates an index N=1,2,…,n for each group. After that, the patient extracts keywords from each group of medical data and records them as W=w1,w2,…,wn. Finally, the patient encrypts each group of medical data with the doctor’s public key pkr‖j at time j, obtains a ciphertext set CM=CM1,CM2,…,CMn, and generates an index set of the medical data ciphertext IM=1,CM1,2,CM2,…,n,CMn, and it will be stored in the cloud server.CTj⟵PPSEB.PEKSX,δ,σ,μ,H1,H2,skr,sks,j,SKr‖j,w: The patient will procedure PPSEB.PEKS algorithm and input the set X,δ,σ,μ,H1,H2,skr,sks , the public key pkr‖j, the current time j, and keyword w. This Probabilistic Polynomial Time (PPT) algorithm shows in detail as below. For each keyword wi∈W, the patient executes PPSEB.PEKS algorithm, obtains CTW=CTj1,CTj2,…,CTjn, and pairs each keyword ciphertext with the number to generate keyword index set IW=1,CTj1,2,CTj2,…,n,CTjn. When we get IW, the patient calculates the hash value H1 of I with his own private key to generate a digital signature, writes down the transaction ID and timestamp, generates the corresponding transaction, and submits it to the master node for verification. After that, all nodes of the blockchain network execute the consensus algorithm, and the master node jointly packs the transaction orders in a period of time to form a block and then sends it to the affiliate node. Then, the affiliate node receives the block sent by the master node and verifies the transaction slip contained in the block. Firstly, the affiliate node extracts the public key of the patient stored in the transaction sheet from the node and decrypts the digital signature and get the hash value H2 of IW. If H1=H2, the affiliate node declares that the verification is successful. Otherwise, it means that the data may be tampered with and return this transaction to the patient. Assuming that the maximum number of malicious nodes that can exist in the consensus algorithm is f, if the number of verifications passes Num=f+1, the block will be stored in each node of the blockchain network Algorithm 3.Algorithm 3:CTj⟵PPSEB.PEKSX,δ,σ,μ,H1,H2,skr,sks,j,SKr||j,w.
Input: set X,δ,σ,μ,H1,H2,skr,sks, current time period j, secret key SKr‖j in current period jOutput: CTj(1)
Set a binary stringBj⟵ℤqn×l, where l is the security level of test in medical data cloud storage(2)
Select a unitive matrixBj⟵ℤqn×l of n×l dimension(3)
Select noisenoij1,noij2,…,noijl⟵ℤq through X(4)
Setnoij=noij1,noij2,…,noijl(5)
Select each noise vectornoivj1,noivj2,…,noivjl⟵ℤq on the basis of Xm(6)
Set the noise vector matrixnoivj=noivj1,noivj2,…,noivjl∈ℤqm×l(7)
Assumeβj=H2w‖j and then compute CTj1=μΤBj+noij+yj⌊q/2⌋ and CTj2=pkr‖jβj−1ΤBj+noivj as ciphertext(8)
Set ciphertextCTj=CTj1,CTj2=μΤBj+noij+yj⌊q/2⌋,pkr||jβj−1ΤBj+noivj(9)
ReturnCTj to doctorTrapw‖j⟵PPSEB.TrapdoorX,δ,σ,μ,H1,H2,skr,sks,pkr‖j,skr‖j,j,w: The doctor will procedure this algorithm after inputting the set X,δ,σ,μ,H1,H2,skr,sks, the public key and secret key pair pkr‖j,skr‖j of the medical doctor during this period j , and one keyword w∈W. The detailed description is shown in Algorithm 4.Finally, the doctor will sendTrapw‖j to the blockchain through an efficient and secure communication channel.Algorithm 4:Trapw‖j⟵PPSEB.TrapdoorX,δ,σ,μ,H1,H2,skr,sks,pkr‖j,skr‖j,j,w.
Input: set X,δ,σ,μ,H1,H2,skr,sks, current period j, public-secret key pair pkr‖j,skr‖j, one keyword wOutput: skw‖j and Trapw‖j(1)
Computeβj=H2w‖j(2)
SetRr‖j=H1pkr‖iH1pkr‖i−1…H1pkr‖1(3)
Call NewBasisDel pkr‖j,βj,skr‖j,δj to generate one short lattice basis skw‖j∈ℤqm×m in random(4)
Call SamplePre pkr‖jβj−1,skw‖j,μ,σj to generate the trapdoor Trapw‖j∈ℤqm(5)
ReturnTrapw‖jN0orFalse⟵PPSEB.VerificationX,δ,σ,μ,H1,H2,skr,sks,CTj,tw‖j: This PPT algorithm produced by the blockchain inputs including the set X,δ,σ,μ,H1,H2,skr,sks, the ciphertext CTj, one trapdoor Trapw‖j in this period j of the doctor. If it outputs true; it means that the trapdoor Trapw||j and the ciphertext CTj contain the uniform keyword w. Then, the blockchain returns the number N0 of the ciphertext corresponding to the keyword to the cloud server. The cloud server finds the ciphertext of the keyword according to N0 and returns it to the doctor Algorithm 5.Algorithm 5:TrueorFalse⟵PPSEB.VerificationX,δ,σ,μ,H1,H2,skr,sks,CTj,tw‖j.
Input: set X,δ,σ,μ,H1,H2,skr,sks, ciphertext CTj, current period j, trapdoor Trapw‖jOutput: N0or False(1)
Computeyj1,yj2,…,yjl=CTj1−Trapw‖jTCTj2(2)
Setyj=yj1,yj2,…,yjl(3)
Select integerq satisfies 1,2,…,q⊂ℤ+(4)
fori=1,2,…,ldo(5)
ifyji−⌊q/2⌋≥⌊q/4⌋then(6)
The medical cloud sever will abort it and Return False.(7)
else(8)
Setyji=1 up to yjl=1(9)
end if(10)
endfor(11)
ifyj=1,1,…,1∈1lthen(12)
ReturnN0(13)
else(14)
Return False(15)
end ifM0⟵PPSEB.DecryptCM0,j,SKr‖j: After the doctor obtains the ciphertext CM0 of the medical data returned by the cloud server, he/she decrypts it with his SKr‖j at time j to obtain the plaintext of medical data M0.


## 4.1. Blockchain Architecture

Blockchain is essentially a decentralized database, which is a string of blocks that are associated using cryptography methods. Each transaction includes hash function, Merkle tree, and so on. In this paper, we replace the search party in searchable encryption with blockchain to ensure the credibility of the search process. As shown in Figure1, our paper optimizes and adjusts the five-layer architecture of the original blockchain and adds a data retrieval function to the application layer to ensure that the blockchain network can base on the algorithm written in the smart contract realizing the retrieval of the keyword ciphertext.Figure 1
Blockchain architecture.


## 4.2. System Model

In this section, we give an introduction to the system model of our PPSEB scheme in Figure2, with four main entities, including patient, doctor, a cloud server, and blockchain network.(1)
Patient: The patient integrates Electronic Health Record (EHR), including various medical information such as drug-using records as a patient. Moreover, the patient encrypts the EHR and uploads it to the Cloud Server. Then the patient generates a set of keywordskeywords,sequencenumber related to the specified keyword and adds blocks to the blockchain.(2)
Doctor: The doctor needs to generate a trapdoor to search for information about patients. The doctor submits the corresponding trapdoor to the blockchain.(3)
Blockchain: After receiving the trapdoor from the doctor, the blockchain network will start chain code retrieval to search the corresponding sequence number and submit it to the CloudServer.(4)
Cloud Server: After receiving the query request, the Cloud Server can use trapdoor to search for all encrypted data and return the query results of the ciphertext corresponding to the keywords to the doctor. During the entire process, the server is unable to obtain any information about the data and keywords.Figure 2
System architecture.


## 4.3. The Scheme of PPSEB

In this section, we present our proposed scheme in detail. There are mainly seven steps of our scheme, includingPPSEB.Initialization, PPSEB.KeyExt, PPSEB.Encrypt, PPSEB.PEKS, PPSEB.Trapdoor, PPSEB.Verification, and PPSEB.Decrypt, which are elaborated in the following paragraphs and algorithms.X,δ,σ,μ,H1,H2,skr,sks⟵PPSEB.Initializationk,X,δ,σ: Firstly, we have to input one security parameter k, the discrete Gaussian Distribution X and its parameters δ=δ1,δ2,…,δη, σ=σ1,σ2,…,ση in one period j, where j=1,2,…,η. After that, the initialization step is shown as follows.SKr‖j,pkr‖j⟵PPSEB.KeyExtX,δ,σ,μ,H1,H2,skr,sks,j,skr||i,i: After inputting the set Algorithm 1.Algorithm 1:X,δ,σ,μ,H1,H2,skr,sks⟵PPSEB.Initializationk,X,δ,σ.
Input: security parameter k, discrete Gaussian Distribution X, security Gaussian Distribution δ, σ.Output: The set X,δ,σ,μ,H1,H2,skr,sks(1)
Select one uniform vector randomlyμ⟵ℤqn(2)
Assume thatN=0,1,…,η and compute ℤqn×m×N⟶ℤqm×m and 0,1l1×N⟶ℤqm×m(3)
Set these two hash functions:H1:ℤqn×m×N and H2:0,1l1×N(4)
Call TrapGen(q,n) algorithm to generate pks∈ℤqn×m and sks∈ℤqm×m, where pks and sks are public key and secret key of patient, respectively(5)
Call TrapGen(q,n) algorithm to generate pkr∈ℤqn×m and skr∈ℤqm×m, where pkr and skr are public key and secret key of doctor, respectively(6)
Return the set X,δ,σ,μ,H1,H2,skr,sksX,δ,σ,μ,H1,H2,skr,sks obtained from the Initialization step, we also have to input the current period j together with the secret key skr||i in the previous period i. Then, the doctor will procedure the following operations, which shows in Algorithm 2.Algorithm 2:SKr‖j,pkr‖j⟵PPSEB.KeyExtX,δ,σ,μ,H1,H2,skr,sks,j,skr‖i,i.
Input: set X,δ,σ,μ,H1,H2,skr,sks, current time period j, secret key skr‖i in previous time period iOutput: SKr‖j and pkr‖j, where is the secret key during this period j(1)
ComputeH1pkr‖iH1pkr‖i−1…H1pkr‖1∈ℤqm×m(2)
SetRr‖j=H1pkr‖iH1pkr‖i−1...H1pkr‖1(3)
ComputepkrRr‖j−1=pkrH1pkr‖iH1pkr‖i−1...H1pkr‖1−1∈ℤqn×m(4)
Setpkr‖i=pkrRr‖i−1=pkrH1pkr‖iH1pkr‖i−1…H1pkr‖1−1(5)
ComputeH1pkr‖jH1pkr‖j−1…H1pkr‖i+1∈ℤqm×m(6)
SetRr‖i⟶j=H1pkr‖jH1pkr‖j−1…H1pkr‖i+1(7)
Call NewBasisDel pkr‖i,Rr‖i⟶j,skr‖j,δj to compute SKr‖j⟵skr‖j, where SKr||j is the secret key during this period j(8)
Computepkr‖iRr‖i⟶j−1=pkrRr‖j−1∈ℤqn×m(9)
Setpkr‖j=pkrRr‖j−1(10)
ReturnSKr‖j and pkr‖jN,W,IM⟵PPSEB.EncryptM,pkr‖j: Firstly, the patient divides the medical data M into groups, named M=M1,M2,…,Mn, and generates an index N=1,2,…,n for each group. After that, the patient extracts keywords from each group of medical data and records them as W=w1,w2,…,wn. Finally, the patient encrypts each group of medical data with the doctor’s public key pkr‖j at time j, obtains a ciphertext set CM=CM1,CM2,…,CMn, and generates an index set of the medical data ciphertext IM=1,CM1,2,CM2,…,n,CMn, and it will be stored in the cloud server.CTj⟵PPSEB.PEKSX,δ,σ,μ,H1,H2,skr,sks,j,SKr‖j,w: The patient will procedure PPSEB.PEKS algorithm and input the set X,δ,σ,μ,H1,H2,skr,sks , the public key pkr‖j, the current time j, and keyword w. This Probabilistic Polynomial Time (PPT) algorithm shows in detail as below. For each keyword wi∈W, the patient executes PPSEB.PEKS algorithm, obtains CTW=CTj1,CTj2,…,CTjn, and pairs each keyword ciphertext with the number to generate keyword index set IW=1,CTj1,2,CTj2,…,n,CTjn. When we get IW, the patient calculates the hash value H1 of I with his own private key to generate a digital signature, writes down the transaction ID and timestamp, generates the corresponding transaction, and submits it to the master node for verification. After that, all nodes of the blockchain network execute the consensus algorithm, and the master node jointly packs the transaction orders in a period of time to form a block and then sends it to the affiliate node. Then, the affiliate node receives the block sent by the master node and verifies the transaction slip contained in the block. Firstly, the affiliate node extracts the public key of the patient stored in the transaction sheet from the node and decrypts the digital signature and get the hash value H2 of IW. If H1=H2, the affiliate node declares that the verification is successful. Otherwise, it means that the data may be tampered with and return this transaction to the patient. Assuming that the maximum number of malicious nodes that can exist in the consensus algorithm is f, if the number of verifications passes Num=f+1, the block will be stored in each node of the blockchain network Algorithm 3.Algorithm 3:CTj⟵PPSEB.PEKSX,δ,σ,μ,H1,H2,skr,sks,j,SKr||j,w.
Input: set X,δ,σ,μ,H1,H2,skr,sks, current time period j, secret key SKr‖j in current period jOutput: CTj(1)
Set a binary stringBj⟵ℤqn×l, where l is the security level of test in medical data cloud storage(2)
Select a unitive matrixBj⟵ℤqn×l of n×l dimension(3)
Select noisenoij1,noij2,…,noijl⟵ℤq through X(4)
Setnoij=noij1,noij2,…,noijl(5)
Select each noise vectornoivj1,noivj2,…,noivjl⟵ℤq on the basis of Xm(6)
Set the noise vector matrixnoivj=noivj1,noivj2,…,noivjl∈ℤqm×l(7)
Assumeβj=H2w‖j and then compute CTj1=μΤBj+noij+yj⌊q/2⌋ and CTj2=pkr‖jβj−1ΤBj+noivj as ciphertext(8)
Set ciphertextCTj=CTj1,CTj2=μΤBj+noij+yj⌊q/2⌋,pkr||jβj−1ΤBj+noivj(9)
ReturnCTj to doctorTrapw‖j⟵PPSEB.TrapdoorX,δ,σ,μ,H1,H2,skr,sks,pkr‖j,skr‖j,j,w: The doctor will procedure this algorithm after inputting the set X,δ,σ,μ,H1,H2,skr,sks, the public key and secret key pair pkr‖j,skr‖j of the medical doctor during this period j , and one keyword w∈W. The detailed description is shown in Algorithm 4.Finally, the doctor will sendTrapw‖j to the blockchain through an efficient and secure communication channel.Algorithm 4:Trapw‖j⟵PPSEB.TrapdoorX,δ,σ,μ,H1,H2,skr,sks,pkr‖j,skr‖j,j,w.
Input: set X,δ,σ,μ,H1,H2,skr,sks, current period j, public-secret key pair pkr‖j,skr‖j, one keyword wOutput: skw‖j and Trapw‖j(1)
Computeβj=H2w‖j(2)
SetRr‖j=H1pkr‖iH1pkr‖i−1…H1pkr‖1(3)
Call NewBasisDel pkr‖j,βj,skr‖j,δj to generate one short lattice basis skw‖j∈ℤqm×m in random(4)
Call SamplePre pkr‖jβj−1,skw‖j,μ,σj to generate the trapdoor Trapw‖j∈ℤqm(5)
ReturnTrapw‖jN0orFalse⟵PPSEB.VerificationX,δ,σ,μ,H1,H2,skr,sks,CTj,tw‖j: This PPT algorithm produced by the blockchain inputs including the set X,δ,σ,μ,H1,H2,skr,sks, the ciphertext CTj, one trapdoor Trapw‖j in this period j of the doctor. If it outputs true; it means that the trapdoor Trapw||j and the ciphertext CTj contain the uniform keyword w. Then, the blockchain returns the number N0 of the ciphertext corresponding to the keyword to the cloud server. The cloud server finds the ciphertext of the keyword according to N0 and returns it to the doctor Algorithm 5.Algorithm 5:TrueorFalse⟵PPSEB.VerificationX,δ,σ,μ,H1,H2,skr,sks,CTj,tw‖j.
Input: set X,δ,σ,μ,H1,H2,skr,sks, ciphertext CTj, current period j, trapdoor Trapw‖jOutput: N0or False(1)
Computeyj1,yj2,…,yjl=CTj1−Trapw‖jTCTj2(2)
Setyj=yj1,yj2,…,yjl(3)
Select integerq satisfies 1,2,…,q⊂ℤ+(4)
fori=1,2,…,ldo(5)
ifyji−⌊q/2⌋≥⌊q/4⌋then(6)
The medical cloud sever will abort it and Return False.(7)
else(8)
Setyji=1 up to yjl=1(9)
end if(10)
endfor(11)
ifyj=1,1,…,1∈1lthen(12)
ReturnN0(13)
else(14)
Return False(15)
end ifM0⟵PPSEB.DecryptCM0,j,SKr‖j: After the doctor obtains the ciphertext CM0 of the medical data returned by the cloud server, he/she decrypts it with his SKr‖j at time j to obtain the plaintext of medical data M0.


## 5. Security Analysis

In this section, we will demonstrate our scheme’s correctness and provable security to achieve the security of the keyword ciphertext in our scheme under random oracle.


### 5.1. Correctness

In this section, we suppose that the key pair at timej of doctors and patients are pkr‖j,skr‖j, pks‖j,sks‖j, respectively. Then, we set w as the keyword of the ciphertext CTj and then w′ is a keyword that matches the trapdoor Trapw′‖j. It is well known that the cloud server can use Trapw′‖j at a time j to recover yj1′,yj2′,…,yjl′=CTj1−Trapw′‖jTCTj2 in PPSEB.Verification. Since the relationship between w and w′ is uncertain, we divide the discussion into the following two situations:Case 1: Ifw≠w′, then CTj1−Trapw′‖jTCTj2≠CTj1−Trapw‖jTCTj2, so we can decrypt the ciphertext CTj and obtain that: for i=1,2,…,l, there must be yji≠1.Case 2: Ifw=w′, then there is CTj1−Trapw′‖jTCTj2=CTj1−Trapw‖jTCTj2=noij+yj1,yj2,…,yjl⌊q/2⌋−Trapw‖jTCTj2. Among them, noij−Trapw‖jTCTj2 is a noise vector. According to [25], we need to ensure that the error vector is less than q/5, so that the decryption process does not make mistakes. Consequently, we can compute that: for i=1,2,…,l, yji′=1.So, the cloud server can ensure that the keywordw can correspond to the ciphertext CTj=CTj1,CTj2 and the trapdoor Trapw′‖jT; that is, PPSEB can achieve correctness. Last but not least, the cloud server sends the encrypted medical data corresponding to the keyword w to the doctor, and the doctor obtains the corresponding plaintext data after decrypting it according to its key.


### 5.2. Provable Security

Theorem 1.
In the PPSEB, the difficulty of the attacker to crack the indistinguishability of the ciphertext can be reduced to the difficulty of the LWE problem.Proof.
Suppose that there is an attacker A under the random oracle model, which can crack the indistinguishability of the ciphertext in polynomial time. On this basis, we have created a challenger C having the ability to solve the LWE problem.


#### 5.2.1. Setup

To begin with, challenger C sendsuk,vk1,vk2,…,vkl, k=0,1,…,m from a random oracle machine. Then, C guesses τ=j∗ as a point in time when A breaks the indistinguishability of the ciphertext. After that, C creates two lists, named L1 and L2. Finally, C interacts with attacker A. The steps are as follows:(1)
Challenger C runs the SampleR algorithm to obtain R, then C selectsτ+1 vectors from R∗,R1∗,…,Rτ∗ and assembles it into a matrix F∗∈ℤqn×m, making uk the k-th column of F∗.(2)
Challenger C obtainspkr=F∗R∗R1∗⋯Rτ∗. Because F∗ is independent of ℤqn×m and R1∗,R2∗,⋯,Rτ∗ are irreversible matrices, pkr is independent of ℤqn×m. Then, C selects a matrix as pks∈ℤqn×m and sets μ=u0∈ℤqn to get a set pkr,pks,μ,H1,H2. Last but not least, C sends pkr,pks,μ,H1,H2 to attacker A.After receiving the set pkr,pks,μ,H1,H2, A executives H1 query and H2 query.H1 query: A initiates an inquiry to each pkr‖j, where j=1,2,…,τ. C computes Rj∗=H1pkr‖j and sends Rj∗ to A.Case 1:j=τ+1. Challenger C gets pkr‖j−1=pkr⋅R∗R1∗⋯Rτ∗−1 and runs Sample R with Basis algorithm to get Rj and the basis skr‖j of lattice Lq⊥Ar||j, where Ar‖j=Rj−1⋅Ar‖j−1. Then, C appends pkr‖j,pkr‖j,Rj,skr‖j to the list L1. Consequently, C transmits Rj to attacker A.Case 2:j>τ+1. Challenger C finds pkr‖j−1,pkr‖j−1,Rj−1,skr‖j−1 from the L1. Then, C selects a matrix Rj, and carries out the New Basis Del algorithm to compute skr||j as the basis of Lq⊥pkr‖j, where pkr‖j=pkr‖j−1⋅Rj−1. Consequently, C appends pkr‖j,pkr‖j,Rj,skr‖j to L1, and transmits Rj to attacker A.H2 query: The attacker A queries w, at the same time challenger C performs the following operations:Case 1:w=w∗ and j=j∗. The challenger C calculates R∗=H2w‖j and sends R∗ to A.Case 2:w≠w∗ or j≠j∗. The challenger C looks for pkr‖j,pkr‖j,Rj,skr‖j in L1, selects a matrix Rw‖j, and executes the NewBasisDel algorithm to generate a basis skw‖j of Lq⊥pkr‖j⋅Rw‖j−1. Finally, C saves w‖j,pkr‖j⋅Rw‖j−1,Rw‖j,skw‖j in L2, and sends Rw‖j to A.


#### 5.2.2. Trapdoor Query

When C receives a query for a keywordw from A, C first looks at L2, and if there is no w‖j,pkr‖j⋅Rw‖j−1,Rw‖j,skw‖j in L2; then this process will be restarted. Otherwise, C gets the private key skw‖j, runs the SamplePre algorithm to generate a trapdoor Trapw‖j, and sends it to A.


#### 5.2.3. Break-In Phase

In this process, attacker A can query the private key of the doctor in thej>j∗ period, and j∗=τ is set a break-in time. After A queries H1 on pkr‖j, C sends the private key skr‖j to A.In timei, which is the prior period, we can find pkr‖j,pkr‖i,Ri,skr‖i from L1 because the attacker A will perform H1 queries on pkr‖i. Further, we calculate pkr‖i=pkr‖τ+1=pkr⋅Rτ∗⋯R2∗R1∗−1⋅H1pkr‖τ+1−1, which skr‖i is the basis of the lattice Lq⊥pkr‖i. After that, challenger C calculates Rr‖i⟶j=H1pkr‖j⋯H1pkr‖i⟶1 and runs the NewBasisDel algorithm to obtain pkr‖j=pkr‖i⋅Rr‖i⟶j−1 and skr‖j in time j. Consequently, C sends skr‖j to attacker A.


#### 5.2.4. Challenge Phase

Assuming thatw0∗ and w1∗ are two keywords, challenger C randomly selects a quantity from 0,1 and assigns it to b. Then we need to divide into the following cases according to the value of b.Case 1:b=0. The challenger C sends ciphertext CTτ1∗,CTτ2∗ of w0∗ to A.Case 2:b=1. We create v0=v01,v02,…,v0l, v∗=v1,v2,…,vmT, and yj∗=1,1,…,1. Then, CTτ1∗=v0+⌊q/2⌋⋅yj∗ and CTτ2∗=v∗ can be obtained. Consequently, C sends the ciphertext CTτ1∗,CTτ2∗ of w1∗ to A.


#### 5.2.5. Guess Phase

In this process, attacker A outputsb′=0 or b′=1 as the response of theChallenge phase.Analysis: To begin with, according to the basic probability knowledge, the probability of C outputting the ciphertext of the keywordw1 is 1/2.Suppose that A can break the indistinguishability of the ciphertext with the probabilityp. In addition, the probability that challenger C can correctly obtain the break time is 1/m. Consequently, C can solve the LWE hardness with the probability of p/2m. In a nutshell, the difficulty of the attacker to crack the indistinguishability of the ciphertext can be reduced to the difficulty of the LWEhardness.


## 5.1. Correctness

In this section, we suppose that the key pair at timej of doctors and patients are pkr‖j,skr‖j, pks‖j,sks‖j, respectively. Then, we set w as the keyword of the ciphertext CTj and then w′ is a keyword that matches the trapdoor Trapw′‖j. It is well known that the cloud server can use Trapw′‖j at a time j to recover yj1′,yj2′,…,yjl′=CTj1−Trapw′‖jTCTj2 in PPSEB.Verification. Since the relationship between w and w′ is uncertain, we divide the discussion into the following two situations:Case 1: Ifw≠w′, then CTj1−Trapw′‖jTCTj2≠CTj1−Trapw‖jTCTj2, so we can decrypt the ciphertext CTj and obtain that: for i=1,2,…,l, there must be yji≠1.Case 2: Ifw=w′, then there is CTj1−Trapw′‖jTCTj2=CTj1−Trapw‖jTCTj2=noij+yj1,yj2,…,yjl⌊q/2⌋−Trapw‖jTCTj2. Among them, noij−Trapw‖jTCTj2 is a noise vector. According to [25], we need to ensure that the error vector is less than q/5, so that the decryption process does not make mistakes. Consequently, we can compute that: for i=1,2,…,l, yji′=1.So, the cloud server can ensure that the keywordw can correspond to the ciphertext CTj=CTj1,CTj2 and the trapdoor Trapw′‖jT; that is, PPSEB can achieve correctness. Last but not least, the cloud server sends the encrypted medical data corresponding to the keyword w to the doctor, and the doctor obtains the corresponding plaintext data after decrypting it according to its key.


## 5.2. Provable Security

Theorem 1.
In the PPSEB, the difficulty of the attacker to crack the indistinguishability of the ciphertext can be reduced to the difficulty of the LWE problem.Proof.
Suppose that there is an attacker A under the random oracle model, which can crack the indistinguishability of the ciphertext in polynomial time. On this basis, we have created a challenger C having the ability to solve the LWE problem.


### 5.2.1. Setup

To begin with, challenger C sendsuk,vk1,vk2,…,vkl, k=0,1,…,m from a random oracle machine. Then, C guesses τ=j∗ as a point in time when A breaks the indistinguishability of the ciphertext. After that, C creates two lists, named L1 and L2. Finally, C interacts with attacker A. The steps are as follows:(1)
Challenger C runs the SampleR algorithm to obtain R, then C selectsτ+1 vectors from R∗,R1∗,…,Rτ∗ and assembles it into a matrix F∗∈ℤqn×m, making uk the k-th column of F∗.(2)
Challenger C obtainspkr=F∗R∗R1∗⋯Rτ∗. Because F∗ is independent of ℤqn×m and R1∗,R2∗,⋯,Rτ∗ are irreversible matrices, pkr is independent of ℤqn×m. Then, C selects a matrix as pks∈ℤqn×m and sets μ=u0∈ℤqn to get a set pkr,pks,μ,H1,H2. Last but not least, C sends pkr,pks,μ,H1,H2 to attacker A.After receiving the set pkr,pks,μ,H1,H2, A executives H1 query and H2 query.H1 query: A initiates an inquiry to each pkr‖j, where j=1,2,…,τ. C computes Rj∗=H1pkr‖j and sends Rj∗ to A.Case 1:j=τ+1. Challenger C gets pkr‖j−1=pkr⋅R∗R1∗⋯Rτ∗−1 and runs Sample R with Basis algorithm to get Rj and the basis skr‖j of lattice Lq⊥Ar||j, where Ar‖j=Rj−1⋅Ar‖j−1. Then, C appends pkr‖j,pkr‖j,Rj,skr‖j to the list L1. Consequently, C transmits Rj to attacker A.Case 2:j>τ+1. Challenger C finds pkr‖j−1,pkr‖j−1,Rj−1,skr‖j−1 from the L1. Then, C selects a matrix Rj, and carries out the New Basis Del algorithm to compute skr||j as the basis of Lq⊥pkr‖j, where pkr‖j=pkr‖j−1⋅Rj−1. Consequently, C appends pkr‖j,pkr‖j,Rj,skr‖j to L1, and transmits Rj to attacker A.H2 query: The attacker A queries w, at the same time challenger C performs the following operations:Case 1:w=w∗ and j=j∗. The challenger C calculates R∗=H2w‖j and sends R∗ to A.Case 2:w≠w∗ or j≠j∗. The challenger C looks for pkr‖j,pkr‖j,Rj,skr‖j in L1, selects a matrix Rw‖j, and executes the NewBasisDel algorithm to generate a basis skw‖j of Lq⊥pkr‖j⋅Rw‖j−1. Finally, C saves w‖j,pkr‖j⋅Rw‖j−1,Rw‖j,skw‖j in L2, and sends Rw‖j to A.


### 5.2.2. Trapdoor Query

When C receives a query for a keywordw from A, C first looks at L2, and if there is no w‖j,pkr‖j⋅Rw‖j−1,Rw‖j,skw‖j in L2; then this process will be restarted. Otherwise, C gets the private key skw‖j, runs the SamplePre algorithm to generate a trapdoor Trapw‖j, and sends it to A.


### 5.2.3. Break-In Phase

In this process, attacker A can query the private key of the doctor in thej>j∗ period, and j∗=τ is set a break-in time. After A queries H1 on pkr‖j, C sends the private key skr‖j to A.In timei, which is the prior period, we can find pkr‖j,pkr‖i,Ri,skr‖i from L1 because the attacker A will perform H1 queries on pkr‖i. Further, we calculate pkr‖i=pkr‖τ+1=pkr⋅Rτ∗⋯R2∗R1∗−1⋅H1pkr‖τ+1−1, which skr‖i is the basis of the lattice Lq⊥pkr‖i. After that, challenger C calculates Rr‖i⟶j=H1pkr‖j⋯H1pkr‖i⟶1 and runs the NewBasisDel algorithm to obtain pkr‖j=pkr‖i⋅Rr‖i⟶j−1 and skr‖j in time j. Consequently, C sends skr‖j to attacker A.


### 5.2.4. Challenge Phase

Assuming thatw0∗ and w1∗ are two keywords, challenger C randomly selects a quantity from 0,1 and assigns it to b. Then we need to divide into the following cases according to the value of b.Case 1:b=0. The challenger C sends ciphertext CTτ1∗,CTτ2∗ of w0∗ to A.Case 2:b=1. We create v0=v01,v02,…,v0l, v∗=v1,v2,…,vmT, and yj∗=1,1,…,1. Then, CTτ1∗=v0+⌊q/2⌋⋅yj∗ and CTτ2∗=v∗ can be obtained. Consequently, C sends the ciphertext CTτ1∗,CTτ2∗ of w1∗ to A.


### 5.2.5. Guess Phase

In this process, attacker A outputsb′=0 or b′=1 as the response of theChallenge phase.Analysis: To begin with, according to the basic probability knowledge, the probability of C outputting the ciphertext of the keywordw1 is 1/2.Suppose that A can break the indistinguishability of the ciphertext with the probabilityp. In addition, the probability that challenger C can correctly obtain the break time is 1/m. Consequently, C can solve the LWE hardness with the probability of p/2m. In a nutshell, the difficulty of the attacker to crack the indistinguishability of the ciphertext can be reduced to the difficulty of the LWEhardness.


## 5.2.1. Setup

To begin with, challenger C sendsuk,vk1,vk2,…,vkl, k=0,1,…,m from a random oracle machine. Then, C guesses τ=j∗ as a point in time when A breaks the indistinguishability of the ciphertext. After that, C creates two lists, named L1 and L2. Finally, C interacts with attacker A. The steps are as follows:(1)
Challenger C runs the SampleR algorithm to obtain R, then C selectsτ+1 vectors from R∗,R1∗,…,Rτ∗ and assembles it into a matrix F∗∈ℤqn×m, making uk the k-th column of F∗.(2)
Challenger C obtainspkr=F∗R∗R1∗⋯Rτ∗. Because F∗ is independent of ℤqn×m and R1∗,R2∗,⋯,Rτ∗ are irreversible matrices, pkr is independent of ℤqn×m. Then, C selects a matrix as pks∈ℤqn×m and sets μ=u0∈ℤqn to get a set pkr,pks,μ,H1,H2. Last but not least, C sends pkr,pks,μ,H1,H2 to attacker A.After receiving the set pkr,pks,μ,H1,H2, A executives H1 query and H2 query.H1 query: A initiates an inquiry to each pkr‖j, where j=1,2,…,τ. C computes Rj∗=H1pkr‖j and sends Rj∗ to A.Case 1:j=τ+1. Challenger C gets pkr‖j−1=pkr⋅R∗R1∗⋯Rτ∗−1 and runs Sample R with Basis algorithm to get Rj and the basis skr‖j of lattice Lq⊥Ar||j, where Ar‖j=Rj−1⋅Ar‖j−1. Then, C appends pkr‖j,pkr‖j,Rj,skr‖j to the list L1. Consequently, C transmits Rj to attacker A.Case 2:j>τ+1. Challenger C finds pkr‖j−1,pkr‖j−1,Rj−1,skr‖j−1 from the L1. Then, C selects a matrix Rj, and carries out the New Basis Del algorithm to compute skr||j as the basis of Lq⊥pkr‖j, where pkr‖j=pkr‖j−1⋅Rj−1. Consequently, C appends pkr‖j,pkr‖j,Rj,skr‖j to L1, and transmits Rj to attacker A.H2 query: The attacker A queries w, at the same time challenger C performs the following operations:Case 1:w=w∗ and j=j∗. The challenger C calculates R∗=H2w‖j and sends R∗ to A.Case 2:w≠w∗ or j≠j∗. The challenger C looks for pkr‖j,pkr‖j,Rj,skr‖j in L1, selects a matrix Rw‖j, and executes the NewBasisDel algorithm to generate a basis skw‖j of Lq⊥pkr‖j⋅Rw‖j−1. Finally, C saves w‖j,pkr‖j⋅Rw‖j−1,Rw‖j,skw‖j in L2, and sends Rw‖j to A.


## 5.2.2. Trapdoor Query

When C receives a query for a keywordw from A, C first looks at L2, and if there is no w‖j,pkr‖j⋅Rw‖j−1,Rw‖j,skw‖j in L2; then this process will be restarted. Otherwise, C gets the private key skw‖j, runs the SamplePre algorithm to generate a trapdoor Trapw‖j, and sends it to A.


## 5.2.3. Break-In Phase

In this process, attacker A can query the private key of the doctor in thej>j∗ period, and j∗=τ is set a break-in time. After A queries H1 on pkr‖j, C sends the private key skr‖j to A.In timei, which is the prior period, we can find pkr‖j,pkr‖i,Ri,skr‖i from L1 because the attacker A will perform H1 queries on pkr‖i. Further, we calculate pkr‖i=pkr‖τ+1=pkr⋅Rτ∗⋯R2∗R1∗−1⋅H1pkr‖τ+1−1, which skr‖i is the basis of the lattice Lq⊥pkr‖i. After that, challenger C calculates Rr‖i⟶j=H1pkr‖j⋯H1pkr‖i⟶1 and runs the NewBasisDel algorithm to obtain pkr‖j=pkr‖i⋅Rr‖i⟶j−1 and skr‖j in time j. Consequently, C sends skr‖j to attacker A.


## 5.2.4. Challenge Phase

Assuming thatw0∗ and w1∗ are two keywords, challenger C randomly selects a quantity from 0,1 and assigns it to b. Then we need to divide into the following cases according to the value of b.Case 1:b=0. The challenger C sends ciphertext CTτ1∗,CTτ2∗ of w0∗ to A.Case 2:b=1. We create v0=v01,v02,…,v0l, v∗=v1,v2,…,vmT, and yj∗=1,1,…,1. Then, CTτ1∗=v0+⌊q/2⌋⋅yj∗ and CTτ2∗=v∗ can be obtained. Consequently, C sends the ciphertext CTτ1∗,CTτ2∗ of w1∗ to A.


## 5.2.5. Guess Phase

In this process, attacker A outputsb′=0 or b′=1 as the response of theChallenge phase.Analysis: To begin with, according to the basic probability knowledge, the probability of C outputting the ciphertext of the keywordw1 is 1/2.Suppose that A can break the indistinguishability of the ciphertext with the probabilityp. In addition, the probability that challenger C can correctly obtain the break time is 1/m. Consequently, C can solve the LWE hardness with the probability of p/2m. In a nutshell, the difficulty of the attacker to crack the indistinguishability of the ciphertext can be reduced to the difficulty of the LWEhardness.


## 6. Performance Evaluation

In this section, to guarantee the forward security, antiquantum KGA, and suitability in the medical scenarios of our PPSEB scheme, we analyze the computational expense, security property, and network communication costs of our scheme and compare our scheme with existing PEKS schemes [3, 5, 28, 29]on the actual performance in the medical background through experiments and numerical simulation technique. The experiments evaluating and testing the actual performance of our scheme are operated on a MacOS with an Intel Core i7 CPU and 16 GB RAM. The implementation of schemes is based on the C++ language, and we use medical data extremely close to actual applications of daily life to complete the experiments. Meanwhile, in order to realize the security of the q-arylattices, the parameters satisfy m>2nlogq, q≥3, since the algorithms counting on lattice-based cryptography are relied on q, m, n. The notations of the following specific descriptions in the experiments are provided in Table 1. The accurate experimental data of 200 trials on average are shown in the following figures, and the results accord with our design objective extremely.Table 1
Notations of descriptions.
NotationsDescriptionsTimemeThe modular exponentiation timeTimesmThe scalar multiplication timeTimehpThe hash-to-point timeTimepaThe point addition timeTimebpThe bilinear pairing timeTimehfThe hash function timeTimemThe multiplication timeS1One element bit size inG1STOne element bit size inGTSpOne element bit size inℤpSqOne element bit size inℤqSlThe security level with a value of 10Our PPSEB is highly efficient compared with other PEKS schemes. As is illustrated in Table2, the theoretical communication costs of each scheme are listed accurately.Table 2
Communication costs.
SchemesSize of PEKS algorithmSize of trapdoor algorithmOur schemeSl+mSlSqmSqBoneh et al. [3]Sp+S1S1Ma et al. [5]5S1+3ST3S1Ma et al. [28]Sp+S1S1Shao et al. [29]Sl+S1S1We prove the theoretical value, and the experimental result reflects in Figure3, demonstrating that the trapdoor size of the PPSEB scheme is the least one among the whole schemes. Along with the stabilizing growth in communication costs, our algorithm is superior to the others, indicating a hidden potential to reduce network resource consumption.Figure 3
Communication costs comparison corresponding to trapdoor size.As to the actual performance, Figure3 indicates that the PPSEB scheme reveals a considerable efficiency advantage. The PEKS size of PPSEB is relatively close to the scheme [3, 5, 28]and much less than the scheme [29]. The trapdoor size in our scheme is a quarter of [29]. However, in terms of postquantum, our proposed PPSEB is more secure than the scheme [3, 5, 28] while being applied in medical data encryption protection. Thus, it is pretty sound and acceptable for PPSEB to increase the nominal communication costs corresponding to PEKS size.In addition, we not only analyze the computational expense and security property of our scheme but also compare it with existing PEKS schemes [3, 5, 28] through experimental medical data. As shown in Figure 4, the testing time of our scheme is also much shorter than the other existing PEKS schemes. Significantly, the more the number of retrieving keywords increases, the more apparent the superiority becomes.Figure 4
Communication costs comparison corresponding to PEKS size.Besides, we test the testing time and computational expense of the PEKS schemes and record the results in Table3.Table 3
Testing time and computational expense.
SchemesTesting timePEKS computational expenseOur schememSlTimemmnSl+nSl+m2nTimem+TimehfBoneh et al. [3]Timehf+Timebp2Timepa+Timehp+4Timesm+Timebp+3TimehfMa et al. [5]5Timeme+4Timebp+Timehf3Timehf+9Timeme+3TimebpMa et al. [28]Timehf+Timebp+Timesm+2Timepa+2TimehpTimehf+3Timebp+2Timem+Timepa+4Timesm+3TimehpShao et al. [29]Timehf+Timebp2Timehf+2Timeme+TimebpOur scheme realizes nearly the same as a scheme [3] in saving the computational expense and searching efficiency according to the comparison in Figure 5. When the number of retrieving keywords is 180, the testing time of [5] is 7.2s, and ours is 0.477s, which is 15.09 times that of PPSEB. As a result, our scheme is not only advantageous in terms of postquantum property, but also relatively efficient than the other schemes. Consequently, although the introduction of blockchain technology has brought a certain amount of complexity and extra overhead to our system, it is certified that our PPSEB scheme can realize the property of postquantum, forward security on maintaining the confidentiality of medical data and superiority in the applications of medical scenarios. From a more practical view, it is both convenient and swift for doctors to master the patient’s physical condition, obtain the patient’s medical records, and make the correct diagnosis promptly in practical medical scenarios. In addition, the more profound performance of PPSEB on managing medical data of Electronic Health Records systems, such as electronic medical record and electronic prescription, need to be tested experimentally and further study in development.Figure 5
The testing time comparison.In Figure6, we compared the PEKS computational expense of PPESB with [3, 5, 28, 29]. Among them, the PEKS computational expense of our scheme is much smaller than other schemes, which shows that our scheme has higher efficiency under the same number of retrieving keywords.Figure 6
PEKS computational expense comparison.


## 7. Conclusion

In our paper, we proposed postquantum Public-key Searchable Encryption on Blockchain (PPSEB) for E-healthcare scenarios. PPSEB is capable of resisting keyword-guessing quantum computing attacks. Moreover, our proposed scheme combines public-key searchable encryption and blockchain, avoiding turning over the searching process to a third party and enhancing the security level. Furthermore, we assure forward security, maintaining the confidentiality of medical data. Both security analysis and comprehensive performance evaluation demonstrate that PPSEB can achieve the property of searching efficiency and lightweight of lower computational cost in retrieving keywords and generating trapdoor compared with other existing E-healthcare schemes.



---

*Source: 3368819-2022-03-29.xml*