# Analysis and Improvement of Blockchain-Based Multilevel Privacy-Preserving Location Sharing Scheme for Telecare Medical Information Systems

Authors: Zhenjie Huang; Yafeng Guo; Hui Huang; Runlong Duan; Xiaolong Zhao
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Patient location sharing is an important part of modern smart healthcare and mobile medical services. Blockchain has many attractive properties and is suitable for managing patient locations in telecare medical information systems (TMIS). Recently, Ji et al. proposed a blockchain-based multilevel privacy-preserving location sharing (BMPLS) scheme for TMIS. In this paper, we show that Ji et al.’s BMPLS scheme does not achieve confidentiality and multilevel privacy-preserving. An adversary outside the system can use an ordinary personal computer to completely break the system within a dozen hours and obtain the location of any patient at any time. The adversary inside the system can use an ordinary personal computer to obtain the location of the designated patient within tens of seconds. Using salting technology, we propose an improved BMPLS scheme to fix our attacks. We also optimized the BMLS scheme to make it correct and executable. The security analysis shows that the improved BMPLS scheme achieves decentralization, untamperability, confidentiality, multilevel privacy-preserving, retrievability, and verifiability. The simulation shows that the improved BMPLS scheme is practical, the computational overhead of the location record phase is within 10 ms, and the computational overheads of the location sharing and location extraction phases are both within 30 ms.


---

## Body

## 1. Introduction

Blockchain is a new decentralized infrastructure and distributed computing paradigm, and it is one of the most revolutionary emerging technologies [1]. In a narrow sense, blockchain is a decentralized shared general ledger that combines data blocks in a chain into a specific data structure in chronological order and uses cryptography technology to ensure that data are untamperable and unforgeable. In a broad sense, blockchain technology is a new decentralized computing paradigm. It uses an encrypted chain block structure to store and verify data, consensus algorithms to update data, and smart contracts to manipulate data. Blockchain has the advantages of decentralization, trustless, anonymity, and untamperability. It can break through the limitations of traditional centralized systems and find important applications in a wide range of fields. More meaningful applications will appear with the further integration of blockchain with cloud computing, edge computing, and the Internet of Things [2–6].With the rapid development of information technology, medical management has become more intelligent and real-time. Wireless mobile networks and wearable technology enable mobile medical services and telemedicine to be realized. For example, IBM has integrated a real-time asset locator (RTAL) for mobile medical and telecare medical to track the location of patients, equipment, and medical staff. Location management plays a significant role in remote patient service and monitoring, such as monitoring particular patients, handling emergencies, and analyzing epidemic distribution. Blockchain has many attractive properties and is suitable for managing patient locations in telecare medical information systems (TMIS).Based on blockchain technology, Zyskind et al. [7] proposed a data storage scheme to protect sensitive data such as user’s location. In their scheme, user data needs to be encrypted before being stored on the blockchain to achieve confidentiality. Amoretti et al. [8] proposed a blockchain-based location proof scheme. Different from [7], in this scheme, the location information is signed before being put on the blockchain to achieve verifiability. Ji et al. [9] comprehensively analyzed the security requirements of blockchain-based location sharing for TMIS and proposed a blockchain-based multilevel privacy-preserving location sharing scheme (BMPLS). They claim that their scheme achieves decentralization, untamperability, confidentiality, multilevel privacy-preserving, retrievability, and verifiability. Unfortunately, we found that their scheme is insecure in practice. The adversary can recover any user’s location effectively. Recently, Lee et al. [10] proposed a blockchain-based medical data preservation scheme for TMIS. Their scheme consists of a medical sensor area authentication protocol and a social network information transfer protocol.


### 1.1. Related Works

With the development of Internet technology, telemedicine has gradually replaced the traditional treatment model. Electronic medical records (EMR) and electronic health records (EHR) are generated in large quantities and frequently exchanged and shared among legitimate users. The protection of electronic medical information is related to patients’ privacy and related to their life safety. Therefore, the security and privacy protection of electronic medical records are significant for the development of telemedicine.Blockchain technology has the potential to improve the medical ecosystem. It provides a novel, efficient, and secure model for exchanging EMRs and EHRs and enhances medical data security, privacy, and interoperability [11, 12]. Using blockchain technology, Cao et al. [13] proposed a secure cloud-assisted electronic health system to protect outsourced electronic health records from illegal modification. Wang et al. [14] proposed a blockchain-based eHealthcare system interoperating with wireless body area networks. Using proxy reencryption, Huang et al. [15] proposed a blockchain-based decentralized medical data sharing scheme with privacy-preserving. Zhuang et al. [16] proposed a patient-centric health information exchange framework. Shamshad et al. [17] proposed a novel blockchain-based privacy and security preserving EHR sharing protocol. Huang et al. [18] proposed a blockchain-based eHealth system, in which the manipulation of EHRs can be audited. Zhu et al. [19] proposed an improved convolution Merkle tree-based blockchain electronic medical record secure storage scheme. Uddin et al. [20] proposed a blockchain leveraged decentralized eHealth architecture. Tanwar et al. [21] explored several solutions that use blockchain technology to improve the current limitations of medical systems, including frameworks and tools for measuring the performance of such systems. Using off-chain and on-chain blockchain system design, Miyachi et al. [22] proposed a modular hybrid privacy-preserving framework. Chen et al. [23] proposed a complete medical information system model based on blockchain technology to realize the goal of safe storage and sharing of medical data. Hossein et al. [24] proposed a novel blockchain-based privacy-preserving architecture for IoT healthcare applications. A summary of related works is shown in Table 1.Table 1
Summary of related works.
Ref.ContributionTechnologies usedKey features[11]A blockchain-based data preservation system for medical dataBlockchain and EthereumEnsuring the primitiveness and verifiability of stored data while preserving privacy for users[12]An APP for health data sharing based on blockchainBlockchain and secure multiparty computingPatients own and control their healthcare data and use the indicator centric schema to organize personal healthcare data[13]A cloud-assisted secure eHealth systemsBlockchain and cloud storageEvery operation of the outsourced EHRs is recorded on the blockchain[14]An eHealthcare system interoperating with WBANsBlockchain and wireless body area networkProviding a secure and low-power healthcare solution; utilizing the WBAN and blockchain technology[15]A blockchain-based privacy-preserving schemeBlockchain, smart contract, zero-knowledge proof, and proxy reencryptionAchieving the data availability and consistency between patients and research institutions; using zero-knowledge proof to protect patient’s privacy[16]A patient-centric health information exchange frameworkBlockchain, data segmentation, and smart contractUtilizing the smart contract feature to protect data security and patients privacy, ensure data provenance, and provide patients full control of their health records[17]A secure blockchain-based eHealth records storage and sharing schemePrivate and consortium blockchain and proxy reencryptionAll EHRs are public-key encrypted and searchable, using private blockchain to store EHRs and consortium blockchain to store secure indexes[18]A blockchain-based eHealth systemBlockchain, cloud computing, and attributes-based proxy reencryptionEach legitimate manipulation will be written into the blockchain, and any threatening behavior will be discovered[19]Improved convolution Merkle treeBlockchain and convolution operationUsing the convolutional layer structure to replace the original binary tree structure[20]An IoT eHealth framework based on blockchainBlockchain, fog computing, edge computing, fuzzy inference, and task offloadingA patient agent (PA) software processes medical data, executes consensus mechanism, and utilizes a task-offloading algorithm to ensure patient’s privacy[21]Blockchain-based electronic healthcare record systemHyperledger fabric and Wireshark capture engineAdopting chain code to ensure proper operation of blockchain ledger[22]Blockchain framework using on-chain and off-chain designBlockchain and on-chain and off-chain designUnpluggable components in the face of different data types to cope with different policy requirements[23]A blockchain-based preserving and sharing systemProxy reencryption and hyperledger fabricReal-time patient data collection and managing data with chain code[24]A blockchain-based architecture for IoT healthcare applicationsBlockchainUsing a dual-chain architecture to develop access control policies that isolate data and policies


### 1.2. Motivation and Contributions

Among the previous blockchain-based location sharing schemes, Zyskind et al.’s scheme only provides decentralization, untamperability, and confidentiality [7], while Amoretti et al.’s scheme only provides decentralization, untamperability, and verifiability [8]. These are far from enough. Ji et al. [9] considered decentralization, untamperability, confidentiality, multilevel privacy protection, retrievability, and verifiability, but their scheme is insecure in practice. The adversary can recover any user’s location effectively. Thus, it is of great significance to propose secure and practical blockchain-based multilevel privacy-preserving location sharing schemes. The comparison of previous blockchain-based location sharing schemes is shown in Table 2, where “√” means satisfied, “×” means dissatisfied, and “−” means uninvolved.Table 2
Comparison of previous schemes.
SchemesZyskind et al.’s [7]Amoretti et al.’s [8]Ji et al.’s [9]Our schemeDecentralization√√√√Untamperability√√√√Confidentiality√××√Multilevel protection×××√Retrievability——√√Verifiability—√√√The main contributions of this paper are as follows:(1)
We analyze the security of Ji et al.’s BMPLS scheme [9] and show that it has fatal flaws in confidentiality and multilevel privacy-preserving. An adversary outside the system can use an ordinary personal computer to completely break the system within a dozen hours and obtain the location information of any patient at any time. The adversary inside the system can use an ordinary personal computer to obtain the location information of the designated patient within tens of seconds. In addition, in some cases, their scheme cannot be executed.(2)
Using salting technology, we propose an improved BMPLS scheme to fix our attacks. We addSetup and Key generation phases to the scheme to provide the foundation for other phases and replace the Location verification phase with the Location extraction phase. We also optimized the BMLS scheme to make it correct and executable. The security analysis shows that the improved BMPLS scheme achieves decentralization, untamperability, confidentiality, multilevel privacy-preserving, retrievability, and verifiability. The simulation shows that the improved BMPLS scheme is practical, the computational overhead of the location record phase is within 10 ms, and the computational overheads of the location sharing and location extraction phases are both within 30 ms.


### 1.3. Organization

The rest of this paper is organized as follows. Section2 presents preliminaries. Section 3 presents the architecture of BMPLS and reviews Ji et al.’s BMPLS scheme. Section 4 analyzes the scheme of Ji et al. Section 5 proposes an improvement to fix our attacks with security and performance analysis. Section 6 concludes this paper.


## 1.1. Related Works

With the development of Internet technology, telemedicine has gradually replaced the traditional treatment model. Electronic medical records (EMR) and electronic health records (EHR) are generated in large quantities and frequently exchanged and shared among legitimate users. The protection of electronic medical information is related to patients’ privacy and related to their life safety. Therefore, the security and privacy protection of electronic medical records are significant for the development of telemedicine.Blockchain technology has the potential to improve the medical ecosystem. It provides a novel, efficient, and secure model for exchanging EMRs and EHRs and enhances medical data security, privacy, and interoperability [11, 12]. Using blockchain technology, Cao et al. [13] proposed a secure cloud-assisted electronic health system to protect outsourced electronic health records from illegal modification. Wang et al. [14] proposed a blockchain-based eHealthcare system interoperating with wireless body area networks. Using proxy reencryption, Huang et al. [15] proposed a blockchain-based decentralized medical data sharing scheme with privacy-preserving. Zhuang et al. [16] proposed a patient-centric health information exchange framework. Shamshad et al. [17] proposed a novel blockchain-based privacy and security preserving EHR sharing protocol. Huang et al. [18] proposed a blockchain-based eHealth system, in which the manipulation of EHRs can be audited. Zhu et al. [19] proposed an improved convolution Merkle tree-based blockchain electronic medical record secure storage scheme. Uddin et al. [20] proposed a blockchain leveraged decentralized eHealth architecture. Tanwar et al. [21] explored several solutions that use blockchain technology to improve the current limitations of medical systems, including frameworks and tools for measuring the performance of such systems. Using off-chain and on-chain blockchain system design, Miyachi et al. [22] proposed a modular hybrid privacy-preserving framework. Chen et al. [23] proposed a complete medical information system model based on blockchain technology to realize the goal of safe storage and sharing of medical data. Hossein et al. [24] proposed a novel blockchain-based privacy-preserving architecture for IoT healthcare applications. A summary of related works is shown in Table 1.Table 1
Summary of related works.
Ref.ContributionTechnologies usedKey features[11]A blockchain-based data preservation system for medical dataBlockchain and EthereumEnsuring the primitiveness and verifiability of stored data while preserving privacy for users[12]An APP for health data sharing based on blockchainBlockchain and secure multiparty computingPatients own and control their healthcare data and use the indicator centric schema to organize personal healthcare data[13]A cloud-assisted secure eHealth systemsBlockchain and cloud storageEvery operation of the outsourced EHRs is recorded on the blockchain[14]An eHealthcare system interoperating with WBANsBlockchain and wireless body area networkProviding a secure and low-power healthcare solution; utilizing the WBAN and blockchain technology[15]A blockchain-based privacy-preserving schemeBlockchain, smart contract, zero-knowledge proof, and proxy reencryptionAchieving the data availability and consistency between patients and research institutions; using zero-knowledge proof to protect patient’s privacy[16]A patient-centric health information exchange frameworkBlockchain, data segmentation, and smart contractUtilizing the smart contract feature to protect data security and patients privacy, ensure data provenance, and provide patients full control of their health records[17]A secure blockchain-based eHealth records storage and sharing schemePrivate and consortium blockchain and proxy reencryptionAll EHRs are public-key encrypted and searchable, using private blockchain to store EHRs and consortium blockchain to store secure indexes[18]A blockchain-based eHealth systemBlockchain, cloud computing, and attributes-based proxy reencryptionEach legitimate manipulation will be written into the blockchain, and any threatening behavior will be discovered[19]Improved convolution Merkle treeBlockchain and convolution operationUsing the convolutional layer structure to replace the original binary tree structure[20]An IoT eHealth framework based on blockchainBlockchain, fog computing, edge computing, fuzzy inference, and task offloadingA patient agent (PA) software processes medical data, executes consensus mechanism, and utilizes a task-offloading algorithm to ensure patient’s privacy[21]Blockchain-based electronic healthcare record systemHyperledger fabric and Wireshark capture engineAdopting chain code to ensure proper operation of blockchain ledger[22]Blockchain framework using on-chain and off-chain designBlockchain and on-chain and off-chain designUnpluggable components in the face of different data types to cope with different policy requirements[23]A blockchain-based preserving and sharing systemProxy reencryption and hyperledger fabricReal-time patient data collection and managing data with chain code[24]A blockchain-based architecture for IoT healthcare applicationsBlockchainUsing a dual-chain architecture to develop access control policies that isolate data and policies


## 1.2. Motivation and Contributions

Among the previous blockchain-based location sharing schemes, Zyskind et al.’s scheme only provides decentralization, untamperability, and confidentiality [7], while Amoretti et al.’s scheme only provides decentralization, untamperability, and verifiability [8]. These are far from enough. Ji et al. [9] considered decentralization, untamperability, confidentiality, multilevel privacy protection, retrievability, and verifiability, but their scheme is insecure in practice. The adversary can recover any user’s location effectively. Thus, it is of great significance to propose secure and practical blockchain-based multilevel privacy-preserving location sharing schemes. The comparison of previous blockchain-based location sharing schemes is shown in Table 2, where “√” means satisfied, “×” means dissatisfied, and “−” means uninvolved.Table 2
Comparison of previous schemes.
SchemesZyskind et al.’s [7]Amoretti et al.’s [8]Ji et al.’s [9]Our schemeDecentralization√√√√Untamperability√√√√Confidentiality√××√Multilevel protection×××√Retrievability——√√Verifiability—√√√The main contributions of this paper are as follows:(1)
We analyze the security of Ji et al.’s BMPLS scheme [9] and show that it has fatal flaws in confidentiality and multilevel privacy-preserving. An adversary outside the system can use an ordinary personal computer to completely break the system within a dozen hours and obtain the location information of any patient at any time. The adversary inside the system can use an ordinary personal computer to obtain the location information of the designated patient within tens of seconds. In addition, in some cases, their scheme cannot be executed.(2)
Using salting technology, we propose an improved BMPLS scheme to fix our attacks. We addSetup and Key generation phases to the scheme to provide the foundation for other phases and replace the Location verification phase with the Location extraction phase. We also optimized the BMLS scheme to make it correct and executable. The security analysis shows that the improved BMPLS scheme achieves decentralization, untamperability, confidentiality, multilevel privacy-preserving, retrievability, and verifiability. The simulation shows that the improved BMPLS scheme is practical, the computational overhead of the location record phase is within 10 ms, and the computational overheads of the location sharing and location extraction phases are both within 30 ms.


## 1.3. Organization

The rest of this paper is organized as follows. Section2 presents preliminaries. Section 3 presents the architecture of BMPLS and reviews Ji et al.’s BMPLS scheme. Section 4 analyzes the scheme of Ji et al. Section 5 proposes an improvement to fix our attacks with security and performance analysis. Section 6 concludes this paper.


## 2. Preliminaries

### 2.1. Order-Preserving Encryption

Order-preserving encryption (OPE) is deterministic encryption that can preserve numerical ordering on their plaintext space [25].An order-preserving encryption schemeΠOPE consists of the following algorithms OP‐KeyGen and OP‐Enc:(1)
OP‐KeyGen is the key generation algorithm, takes as input the security parameter λ, and outputs a secret key opk.(2)
OP‐Enc is the encryption algorithm, takes as input a secret key opk and a plaintext x∈0,1n interpreted as a numerical value 0≤x≤2n−1, and outputs ciphertext c∈0,1m interpreted as a numerical value 0≤c≤2m−1.They satisfy thatOP‐Encopk,i<OP‐Encopk,j, for all opk←OP‐KeyGen1λ,0≤i<j≤2n−1.ForN,M⊆ℕ with N≤M, a function f:N⟶M is order-preserving if for all i,j∈N, fi>fj iff i>j. If an order-preserving encryption scheme ΠOPE is secure, then OP‐Enc is a pseudorandom order-preserving function [25].


### 2.2. Merkle Tree

Merkle tree [26] provides efficient data authentication. A Merkle tree is based on a binary tree and a one-way hash function. The value of its leaf node is the data, and the value of its nonleaf node is the hash of the values of its two child nodes. If the Merkle tree has n leaf nodes, it only needs at most log2n data to authenticate a leaf node, not all n data.In our improved scheme, we need to calculate the Merkle tree ofnode0x,node1x,node2x,…,node2Nx, and Figure 1 is an illustrative example. In order to authenticate h3, we only need to provide h4 and h6, then calculate h7′=Hashh3‖h4 and h8′=Hashh6‖h7′ in sequence, and finally verify whether h8′  =  h8.Figure 1
Merkle tree with leaf nodesnode0x,node1x,node2x,node3x,and node4x.


## 2.1. Order-Preserving Encryption

Order-preserving encryption (OPE) is deterministic encryption that can preserve numerical ordering on their plaintext space [25].An order-preserving encryption schemeΠOPE consists of the following algorithms OP‐KeyGen and OP‐Enc:(1)
OP‐KeyGen is the key generation algorithm, takes as input the security parameter λ, and outputs a secret key opk.(2)
OP‐Enc is the encryption algorithm, takes as input a secret key opk and a plaintext x∈0,1n interpreted as a numerical value 0≤x≤2n−1, and outputs ciphertext c∈0,1m interpreted as a numerical value 0≤c≤2m−1.They satisfy thatOP‐Encopk,i<OP‐Encopk,j, for all opk←OP‐KeyGen1λ,0≤i<j≤2n−1.ForN,M⊆ℕ with N≤M, a function f:N⟶M is order-preserving if for all i,j∈N, fi>fj iff i>j. If an order-preserving encryption scheme ΠOPE is secure, then OP‐Enc is a pseudorandom order-preserving function [25].


## 2.2. Merkle Tree

Merkle tree [26] provides efficient data authentication. A Merkle tree is based on a binary tree and a one-way hash function. The value of its leaf node is the data, and the value of its nonleaf node is the hash of the values of its two child nodes. If the Merkle tree has n leaf nodes, it only needs at most log2n data to authenticate a leaf node, not all n data.In our improved scheme, we need to calculate the Merkle tree ofnode0x,node1x,node2x,…,node2Nx, and Figure 1 is an illustrative example. In order to authenticate h3, we only need to provide h4 and h6, then calculate h7′=Hashh3‖h4 and h8′=Hashh6‖h7′ in sequence, and finally verify whether h8′  =  h8.Figure 1
Merkle tree with leaf nodesnode0x,node1x,node2x,node3x,and node4x.


## 3. Review of Ji Et Al.’s BMPLS Scheme

This section reviews the architecture of BMLS and Ji et al.’s scheme.


### 3.1. Architecture of BMPLS

BMLS can be used as a module of TMIS to manage and share patient location information. The architecture of BMPLS is shown in Figure2. There are two types of entities in the system: location data owner (LDO) and location data requestor (LDR). LDOs, such as infectious disease or chronic disease patients, record their location information in the blockchain. LDRs request LDOs’ location information in different levels according to their trust levels and actual needs. For example, mobile clinics need to know the precise location of patients to provide them with on-site services; the medical center also requires an exact location to deliver the medicine. In contrast, infectious disease investigators only need to know the range of the patient, not the precise location.Figure 2
Architecture of BMPLS.


### 3.2. Ji Et Al.’s BMPLS Scheme

Ji et al.’s BMPLS scheme consists of the following three phases [9].


#### 3.2.1. Initialization

The location data owner (LDO) represents his visit region as a coordinate regionS=x,y|0≤x≤X,0≤y≤Y , runs Algorithm 1 to generate the registration record regRec, and puts it into the blockchain.Algorithm 1: Generation of registration record.
Input:RegionS=x,y|0≤x≤X,0≤y≤Y; Maximum level of location partition N; LDO’s secret key kLDO=kLDOx‖kLDOyOutput:Registration recordregRec(1)x1,x2,…,x2N∪y1,,y2,…,y2N⟵PartiS,N;(2)fori=1;i≤2N;i++do(3)ciphix=OP‐EnckLDOx,xi;(4)ciphiy=OP‐EnckLDOy,yi;(5)nodeix=Hashixiciphix;(6)nodeiy=Hashiyiciphiy;(7)end for(8)horTree⟵genMTnode1x,node2x,…,node2Nx;(9)verTree⟵genMTnode1y,node2y,…,node2Ny;(10)regRec⟵SigLDOTranslate−1horTreerootverTreeroot;(11)returnregRec.In Algorithm1, the partition function PartiS,N=xi=i×X/2N,1≤i≤2N∪yi=i×Y/2N,1≤i≤2N. OP‐Enc·,· is the encryption algorithm of an order-preserving encryption scheme ΠOPE and Hash is a hash function. genMT⋅ denotes the function of using leaf nodes to generate the complete Merkle tree, Translate−1 denotes the function of converting the location record into the actual geographic location, and SigLDO⋅ denotes the LDO’s signature.


#### 3.2.2. Location Record

The LDO runs Algorithm2 to generate a location record recordjLDO and puts it into the blockchain.Algorithm 2: Generation of location record.
Input:LDO’sj-th location xj,yj; LDO’s secret keys kLDO=kLDOx‖kLDOy,ksym; LDO’s public-key pubLDOOutput:Location recordrecordjLDO(1)LDO executes:(2)ciphjx=OP‐EnckLDOx,xj;(3)ciphjy=OP‐EnckLDOy,yj;(4)ciphj⟵ciphjxciphjy;(5)OpeHashj⟵Hashciphj;(6)LocHashj⟵Hashxjyj;(7)SymCihj⟵Encksym,xjyj;(8)LocInfoj⟵OpeHashjLocHashjSymCihjtimetampj;(9)recordjLDO⟵pubLDOLocInfojrecIdj−1LDOsignatureLDO;(10)returnrecordjLDO;In Algorithm2, Enc⋅ is the encryption algorithm of the symmetric encryption scheme.


#### 3.2.3. Location Sharing

The location sharing phase consists of the location sharing stage and location verification stage.(1) Location Sharing. When the location data requestor (LDR) wants to obtain the location corresponding to recordkLDO, he generates a request request←pubLDRrecoIdkLDOnsignatureLDR and sends it to LDO.The LDO returns location with corresponding granularity according to the trust level of the LDR. (1) If the LDR is fully trusted (leveln=∞), the LDO returns an accurate location. (2) If the LDR is semitrusted with level n, the LDO returns a rectangular border with side length 2n. See Algorithm 3 for details.Algorithm 3: Location sharing.
Input:Location record IDrecoIdkLDO; Session key between LDO and LDR kses; Privacy protection level n; LDR’s public-key pubLDROutput:Shared location informationresponse(1)
LDR executes:(2)
request⟵pubLDRrecoIdkLDOnsignatureLDR;(3)
LDR sendsrequest to LDO;(4)
LDO executes:(5)
ifn=∞then(6)
response⟵Enckses,xkykPK‐EncpubLDR,kses(7)
else if0≤n≤Nthen(8)
find the borderxmin,xmax,ymin,ymax in level n(9)
borInfoid1⟵id1xminciphid1x;(10)
borInfoid2⟵id2xmaxciphid2x;(11)
borInfoid3⟵id3yminciphid3y;(12)
borInfoid4⟵id4xmaxciphid4y;(13)
borInfo⟵borInfoid1borInfoid2borInfoid3borInfoid4;(14)
nodesx⟵nodex1x,nodex2x,…;(15)
nodesy⟵nodey1y,nodey2y,…;(16)
response⟵Enckses,ciphkborInfonodesxnodesyPK‐EncpubLDR,kses;(17)
end if(18)
returnresponse.In Algorithm3, PK‐Enc⋅,⋅ is the encryption algorithm of a public-key encryption scheme. id1,id2,id3, and id4 are the subscripts of xmin,xmax,ymin, and ymax, respectively. nodesx and nodesy are the Merkle tree data subsets required to authenticate nodeid1x,nodeid2x and nodeid3y,nodeid4y, respectively.(2) Location Verification. After receiving the response response, LDR runs Algorithm 4 to verify it.Algorithm 4:Location verification.
Input:Response from LDO response; Record in the blockchainrecoldkLDO; Session key with LDOksesOutput:Boolean variableb(1)
initializeb←False;(2)
ifxk′yk′←Deckses,responsethen(3)
if Hashxk′yk′recoldkLDO.LocInfok LocHashkthen(4)
b←True(5)
end if(6)
else ifciphk‖borInfo‖nodesx‖nodesy‖←Deckses,responsethen(7)
borInfoid1borInfoid2borInfoid3borInfoid4←borInfo(8)
nodeid1x←HashborInfoid1;(9)
nodeid2x←HashborInfoid2;(10)
nodeid3x←HashborInfoid3;(11)
nodeid4x←HashborInfoid4;(12)
horTreeroot′←MerkleHashnodesx,nodeid1x,nodeid2x;(13)
vorTreeroot′←MerkleHashnodesy,nodeid3y,nodeid4y(14)
ifhorTreetoot′=horTreerootandvorTreetoot′=verTreerootthen(15)
ifHashciphk=recoIdkLDO.LocInfok.OpeHashkandborInfoid1.ciphid1x<ciphk.ciphkx<borInfoid2.ciphid2xand    borInfoid3.ciphid3x<ciphk.ciphky<borInfoid4.ciphid4xthen(16)
b←True(17)
end if(18)
end if(19)
end if(20)
returnb;In Algorithm4, Dec⋅,⋅ is the decryption algorithm corresponding to Enc⋅,⋅. A.c denotes c in A=b‖c and MerkleHash denotes the function that uses a Merkle tree data subset to calculate its root value.


## 3.1. Architecture of BMPLS

BMLS can be used as a module of TMIS to manage and share patient location information. The architecture of BMPLS is shown in Figure2. There are two types of entities in the system: location data owner (LDO) and location data requestor (LDR). LDOs, such as infectious disease or chronic disease patients, record their location information in the blockchain. LDRs request LDOs’ location information in different levels according to their trust levels and actual needs. For example, mobile clinics need to know the precise location of patients to provide them with on-site services; the medical center also requires an exact location to deliver the medicine. In contrast, infectious disease investigators only need to know the range of the patient, not the precise location.Figure 2
Architecture of BMPLS.


## 3.2. Ji Et Al.’s BMPLS Scheme

Ji et al.’s BMPLS scheme consists of the following three phases [9].


### 3.2.1. Initialization

The location data owner (LDO) represents his visit region as a coordinate regionS=x,y|0≤x≤X,0≤y≤Y , runs Algorithm 1 to generate the registration record regRec, and puts it into the blockchain.Algorithm 1: Generation of registration record.
Input:RegionS=x,y|0≤x≤X,0≤y≤Y; Maximum level of location partition N; LDO’s secret key kLDO=kLDOx‖kLDOyOutput:Registration recordregRec(1)x1,x2,…,x2N∪y1,,y2,…,y2N⟵PartiS,N;(2)fori=1;i≤2N;i++do(3)ciphix=OP‐EnckLDOx,xi;(4)ciphiy=OP‐EnckLDOy,yi;(5)nodeix=Hashixiciphix;(6)nodeiy=Hashiyiciphiy;(7)end for(8)horTree⟵genMTnode1x,node2x,…,node2Nx;(9)verTree⟵genMTnode1y,node2y,…,node2Ny;(10)regRec⟵SigLDOTranslate−1horTreerootverTreeroot;(11)returnregRec.In Algorithm1, the partition function PartiS,N=xi=i×X/2N,1≤i≤2N∪yi=i×Y/2N,1≤i≤2N. OP‐Enc·,· is the encryption algorithm of an order-preserving encryption scheme ΠOPE and Hash is a hash function. genMT⋅ denotes the function of using leaf nodes to generate the complete Merkle tree, Translate−1 denotes the function of converting the location record into the actual geographic location, and SigLDO⋅ denotes the LDO’s signature.


### 3.2.2. Location Record

The LDO runs Algorithm2 to generate a location record recordjLDO and puts it into the blockchain.Algorithm 2: Generation of location record.
Input:LDO’sj-th location xj,yj; LDO’s secret keys kLDO=kLDOx‖kLDOy,ksym; LDO’s public-key pubLDOOutput:Location recordrecordjLDO(1)LDO executes:(2)ciphjx=OP‐EnckLDOx,xj;(3)ciphjy=OP‐EnckLDOy,yj;(4)ciphj⟵ciphjxciphjy;(5)OpeHashj⟵Hashciphj;(6)LocHashj⟵Hashxjyj;(7)SymCihj⟵Encksym,xjyj;(8)LocInfoj⟵OpeHashjLocHashjSymCihjtimetampj;(9)recordjLDO⟵pubLDOLocInfojrecIdj−1LDOsignatureLDO;(10)returnrecordjLDO;In Algorithm2, Enc⋅ is the encryption algorithm of the symmetric encryption scheme.


### 3.2.3. Location Sharing

The location sharing phase consists of the location sharing stage and location verification stage.(1) Location Sharing. When the location data requestor (LDR) wants to obtain the location corresponding to recordkLDO, he generates a request request←pubLDRrecoIdkLDOnsignatureLDR and sends it to LDO.The LDO returns location with corresponding granularity according to the trust level of the LDR. (1) If the LDR is fully trusted (leveln=∞), the LDO returns an accurate location. (2) If the LDR is semitrusted with level n, the LDO returns a rectangular border with side length 2n. See Algorithm 3 for details.Algorithm 3: Location sharing.
Input:Location record IDrecoIdkLDO; Session key between LDO and LDR kses; Privacy protection level n; LDR’s public-key pubLDROutput:Shared location informationresponse(1)
LDR executes:(2)
request⟵pubLDRrecoIdkLDOnsignatureLDR;(3)
LDR sendsrequest to LDO;(4)
LDO executes:(5)
ifn=∞then(6)
response⟵Enckses,xkykPK‐EncpubLDR,kses(7)
else if0≤n≤Nthen(8)
find the borderxmin,xmax,ymin,ymax in level n(9)
borInfoid1⟵id1xminciphid1x;(10)
borInfoid2⟵id2xmaxciphid2x;(11)
borInfoid3⟵id3yminciphid3y;(12)
borInfoid4⟵id4xmaxciphid4y;(13)
borInfo⟵borInfoid1borInfoid2borInfoid3borInfoid4;(14)
nodesx⟵nodex1x,nodex2x,…;(15)
nodesy⟵nodey1y,nodey2y,…;(16)
response⟵Enckses,ciphkborInfonodesxnodesyPK‐EncpubLDR,kses;(17)
end if(18)
returnresponse.In Algorithm3, PK‐Enc⋅,⋅ is the encryption algorithm of a public-key encryption scheme. id1,id2,id3, and id4 are the subscripts of xmin,xmax,ymin, and ymax, respectively. nodesx and nodesy are the Merkle tree data subsets required to authenticate nodeid1x,nodeid2x and nodeid3y,nodeid4y, respectively.(2) Location Verification. After receiving the response response, LDR runs Algorithm 4 to verify it.Algorithm 4:Location verification.
Input:Response from LDO response; Record in the blockchainrecoldkLDO; Session key with LDOksesOutput:Boolean variableb(1)
initializeb←False;(2)
ifxk′yk′←Deckses,responsethen(3)
if Hashxk′yk′recoldkLDO.LocInfok LocHashkthen(4)
b←True(5)
end if(6)
else ifciphk‖borInfo‖nodesx‖nodesy‖←Deckses,responsethen(7)
borInfoid1borInfoid2borInfoid3borInfoid4←borInfo(8)
nodeid1x←HashborInfoid1;(9)
nodeid2x←HashborInfoid2;(10)
nodeid3x←HashborInfoid3;(11)
nodeid4x←HashborInfoid4;(12)
horTreeroot′←MerkleHashnodesx,nodeid1x,nodeid2x;(13)
vorTreeroot′←MerkleHashnodesy,nodeid3y,nodeid4y(14)
ifhorTreetoot′=horTreerootandvorTreetoot′=verTreerootthen(15)
ifHashciphk=recoIdkLDO.LocInfok.OpeHashkandborInfoid1.ciphid1x<ciphk.ciphkx<borInfoid2.ciphid2xand    borInfoid3.ciphid3x<ciphk.ciphky<borInfoid4.ciphid4xthen(16)
b←True(17)
end if(18)
end if(19)
end if(20)
returnb;In Algorithm4, Dec⋅,⋅ is the decryption algorithm corresponding to Enc⋅,⋅. A.c denotes c in A=b‖c and MerkleHash denotes the function that uses a Merkle tree data subset to calculate its root value.


## 3.2.1. Initialization

The location data owner (LDO) represents his visit region as a coordinate regionS=x,y|0≤x≤X,0≤y≤Y , runs Algorithm 1 to generate the registration record regRec, and puts it into the blockchain.Algorithm 1: Generation of registration record.
Input:RegionS=x,y|0≤x≤X,0≤y≤Y; Maximum level of location partition N; LDO’s secret key kLDO=kLDOx‖kLDOyOutput:Registration recordregRec(1)x1,x2,…,x2N∪y1,,y2,…,y2N⟵PartiS,N;(2)fori=1;i≤2N;i++do(3)ciphix=OP‐EnckLDOx,xi;(4)ciphiy=OP‐EnckLDOy,yi;(5)nodeix=Hashixiciphix;(6)nodeiy=Hashiyiciphiy;(7)end for(8)horTree⟵genMTnode1x,node2x,…,node2Nx;(9)verTree⟵genMTnode1y,node2y,…,node2Ny;(10)regRec⟵SigLDOTranslate−1horTreerootverTreeroot;(11)returnregRec.In Algorithm1, the partition function PartiS,N=xi=i×X/2N,1≤i≤2N∪yi=i×Y/2N,1≤i≤2N. OP‐Enc·,· is the encryption algorithm of an order-preserving encryption scheme ΠOPE and Hash is a hash function. genMT⋅ denotes the function of using leaf nodes to generate the complete Merkle tree, Translate−1 denotes the function of converting the location record into the actual geographic location, and SigLDO⋅ denotes the LDO’s signature.


## 3.2.2. Location Record

The LDO runs Algorithm2 to generate a location record recordjLDO and puts it into the blockchain.Algorithm 2: Generation of location record.
Input:LDO’sj-th location xj,yj; LDO’s secret keys kLDO=kLDOx‖kLDOy,ksym; LDO’s public-key pubLDOOutput:Location recordrecordjLDO(1)LDO executes:(2)ciphjx=OP‐EnckLDOx,xj;(3)ciphjy=OP‐EnckLDOy,yj;(4)ciphj⟵ciphjxciphjy;(5)OpeHashj⟵Hashciphj;(6)LocHashj⟵Hashxjyj;(7)SymCihj⟵Encksym,xjyj;(8)LocInfoj⟵OpeHashjLocHashjSymCihjtimetampj;(9)recordjLDO⟵pubLDOLocInfojrecIdj−1LDOsignatureLDO;(10)returnrecordjLDO;In Algorithm2, Enc⋅ is the encryption algorithm of the symmetric encryption scheme.


## 3.2.3. Location Sharing

The location sharing phase consists of the location sharing stage and location verification stage.(1) Location Sharing. When the location data requestor (LDR) wants to obtain the location corresponding to recordkLDO, he generates a request request←pubLDRrecoIdkLDOnsignatureLDR and sends it to LDO.The LDO returns location with corresponding granularity according to the trust level of the LDR. (1) If the LDR is fully trusted (leveln=∞), the LDO returns an accurate location. (2) If the LDR is semitrusted with level n, the LDO returns a rectangular border with side length 2n. See Algorithm 3 for details.Algorithm 3: Location sharing.
Input:Location record IDrecoIdkLDO; Session key between LDO and LDR kses; Privacy protection level n; LDR’s public-key pubLDROutput:Shared location informationresponse(1)
LDR executes:(2)
request⟵pubLDRrecoIdkLDOnsignatureLDR;(3)
LDR sendsrequest to LDO;(4)
LDO executes:(5)
ifn=∞then(6)
response⟵Enckses,xkykPK‐EncpubLDR,kses(7)
else if0≤n≤Nthen(8)
find the borderxmin,xmax,ymin,ymax in level n(9)
borInfoid1⟵id1xminciphid1x;(10)
borInfoid2⟵id2xmaxciphid2x;(11)
borInfoid3⟵id3yminciphid3y;(12)
borInfoid4⟵id4xmaxciphid4y;(13)
borInfo⟵borInfoid1borInfoid2borInfoid3borInfoid4;(14)
nodesx⟵nodex1x,nodex2x,…;(15)
nodesy⟵nodey1y,nodey2y,…;(16)
response⟵Enckses,ciphkborInfonodesxnodesyPK‐EncpubLDR,kses;(17)
end if(18)
returnresponse.In Algorithm3, PK‐Enc⋅,⋅ is the encryption algorithm of a public-key encryption scheme. id1,id2,id3, and id4 are the subscripts of xmin,xmax,ymin, and ymax, respectively. nodesx and nodesy are the Merkle tree data subsets required to authenticate nodeid1x,nodeid2x and nodeid3y,nodeid4y, respectively.(2) Location Verification. After receiving the response response, LDR runs Algorithm 4 to verify it.Algorithm 4:Location verification.
Input:Response from LDO response; Record in the blockchainrecoldkLDO; Session key with LDOksesOutput:Boolean variableb(1)
initializeb←False;(2)
ifxk′yk′←Deckses,responsethen(3)
if Hashxk′yk′recoldkLDO.LocInfok LocHashkthen(4)
b←True(5)
end if(6)
else ifciphk‖borInfo‖nodesx‖nodesy‖←Deckses,responsethen(7)
borInfoid1borInfoid2borInfoid3borInfoid4←borInfo(8)
nodeid1x←HashborInfoid1;(9)
nodeid2x←HashborInfoid2;(10)
nodeid3x←HashborInfoid3;(11)
nodeid4x←HashborInfoid4;(12)
horTreeroot′←MerkleHashnodesx,nodeid1x,nodeid2x;(13)
vorTreeroot′←MerkleHashnodesy,nodeid3y,nodeid4y(14)
ifhorTreetoot′=horTreerootandvorTreetoot′=verTreerootthen(15)
ifHashciphk=recoIdkLDO.LocInfok.OpeHashkandborInfoid1.ciphid1x<ciphk.ciphkx<borInfoid2.ciphid2xand    borInfoid3.ciphid3x<ciphk.ciphky<borInfoid4.ciphid4xthen(16)
b←True(17)
end if(18)
end if(19)
end if(20)
returnb;In Algorithm4, Dec⋅,⋅ is the decryption algorithm corresponding to Enc⋅,⋅. A.c denotes c in A=b‖c and MerkleHash denotes the function that uses a Merkle tree data subset to calculate its root value.


## 4. Cryptanalysis of Ji Et Al.’s BMPLS Scheme

Ji et al. [9] claim that their BMPLS scheme achieves decentralization, untamperability, confidentiality, multilevel privacy-preserving, retrievability, and verifiability. Unfortunately, we find that their scheme has fatal flaws in confidentiality and multilevel privacy-preserving. In addition, in some cases, their scheme cannot be executed.


### 4.1. On Confidentiality

The adversary can recover any LDO’s location effectively.Ji et al.’s BMPLS scheme uses the one-way property of the hash function to protect location. It is feasible and secure in the case of infinite (enough) locations. However, it is insecure in current practical applications because the amount of user locations is not enough to resist brute force attacks. The attack is as follows:(1)
Calculate the coordinate hash tableT of all possible locations of the LDO’s visit region.(2)
Obtain a recordrecordjLDO from the blockchain, and extract the hash value LocHashj .(3)
Find out the locationxjyj corresponding to LocHashj in table T.We take the commonly used Global Positioning System (GPS) as an example to evaluate the feasibility of the above attack. In the GPS, the longitude and latitude output formats aredddmm.mmmm and ddmm.mmmm, respectively. So there are only 3.60×1011 positions in a square area of 1° in longitude and latitude. If estimated by 40°’ north latitude where New York City is located, 1 degree of longitude and 1 degree of latitude are equivalent to 85 and 111 kilometers, respectively, and a square area with 1 degree of longitude and latitude is 9,435 square kilometers. The land area of New York City is 789 square kilometers, so the number of available GPS locations is about 3.01×1010.We experiment on a personal computer using Python-3.9.7 and PyCharm Community Edition 2021.2.2 (64 bits). The configuration is CPU: Intel(R) Core(TM) i9-10900 CPU @ 2.80 GHz∼2.81 GHz, RAM: 64 G, and OS: Windows 10 Home (Chinese) 64 bits (10.0.19041). As in [9], we also choose SHA-256 as the hash function. The simulation result shows that the time cost to calculate the hash values of 109 position coordinates is 27.01 minutes, and the size of the coordinate hash table is 77.20 GB. Therefore, using such a personal computer can calculate the hash value of all locations of New York City in about 13 hours and 33 minutes.The above analysis and experiments show that if Ji et al.’s BMPLS scheme is used for New York City, the adversary can completely break the system in about 13.55 hours using a personal computer.If we use supercomputers or adopt distributed computing or cloud computing technology, we can break the system with very little time overhead.


### 4.2. On Multilevel Privacy-Preserving

Semitrusted LDR Can Obtain Accurate Location. Ji et al. claim that, in their scheme [9], semitrusted LDR is impossible to reduce the privacy protection region. Unfortunately, we found that semitrusted LDR can recover the LDO’s accurate location effectively. This is a more severe attack than reducing the privacy protection region. The attack is as follows:(1)
Obtain a recordrecordjLDO from the blockchain, and extract the hash value LocHashj.(2)
Run Algorithm3 interactively with LDO to obtain the response response.(3)
Run Algorithm4 to verify the response response, and extract the rectangular border xmin,xmax,ymin,ymax.(4)
Search for the location where the hash value is equal torecordjLDO.LocInfoj.LocHashj in the rectangular border xmin,xmax,ymin,ymax; that is, run Algorithm 5 to obtain the accurate location information xjyj.Algorithm 5: Location information extraction.
Input:Location hash valueLocHashj; Rectangular border xmin,xmax,ymin,ymax,Output:Location informationxjyj(1)
forxinxmin,xmaxdo(2)
foryinymin,ymaxdo(3)
Hash⟵Hashxy;(4)
ifHash=LocHashjthen(5)
returnxy;(6)
end if(7)
end for(8)
end forTakexmin=00587654,xmax=01012345 as an example to illustrate how to make x traverse xmin,xmax. Because order-preserving encryption requires the plaintext to be a positive integer, the format of the location needs to be changed from ddmm.mmmm to ddmmmmmm. Note that there are no location coordinates like dd60mmmm,dd61mmmm, … dd99mmmm, and 00587654,01012345 must be divided into 00587654,00599999 and 01000000,01012345. Then, the former is expressed as “x=00587655;x≤0059999;x++” and the latter as “x=01000000;x≤01012344;x++.”We evaluated the feasibility of this attack in the above environment. Assume that the rectangular borderxmin,xmax,ymin,ymax is a square area with a longitude and latitude of 0.5 minutes each. This is a rectangular area with a length of 928 meters and a width of 710 meters. The simulation result shows that the average cost to calculate the accurate location xjyj in such an area is 20.75 seconds.If a supercomputer is used or distributed computing or cloud computing technology is adopted, the time for LDR to find the accurate location will be milliseconds.


### 4.3. Other Weaknesses

(1)
In [9], the coordinates xi=i×X/2N and yi=i×Y/2N may not be integers. But in Definition 1 of [9], the plaintext space is clearly defined as the integer set m=i|1≤i≤m. Therefore, it will not be feasible to encryptxiandyiin Algorithm 1(lines 3 and 4).(2)
The LDO’s location coordinatexk or yk may happen to be a position grid coordinate xi or yi . If it happens, multilevel privacy protection will not be achieved. For example, if xk=x2N−1, then we have xk=xmin or xk=xmax for any trust level n. Then, the inequality in line 15 of Algorithm 4 will not hold, so LDR will not accept any rectangular border provided by LDO. Further, because borInfoid1.ciphid1x=ciphk.ciphkx or ciphk.ciphkx=borInfoid2.ciphid2x, LDR will determine that the x-coordinate of LDO is xmin or xmax.(3)
Then-level rectangular border xmin,xmax,ymin,ymax must be in the form of xi×2n,xi+1×2n,yj×2n,yj+1×2n, to ensure that the privacy protection region will not be reduced. If the LDO’s location coordinate xk or yk satisfies xk<x1 or yk<y1, then have xmin=x0=0 or ymin=y0=0. In this case, both Algorithms 3 and 4cannot be executed.(a)
Because 0 is not in the plaintext space of order-preserving encryption, Algorithm3 cannot generate the ciphertext ciphid1x (or ciphid3y) of xmin=0 (or ymin=0) (see Definition 1 of [9]).(b)
node0x and node0y are used when calculating horTreeroot' and vorTreeroot', but they are not used when calculating horTree and verTree, which will make neither horTreetoot'=horTreeroot nor vorTreetoot'=verTreeroot holds.


## 4.1. On Confidentiality

The adversary can recover any LDO’s location effectively.Ji et al.’s BMPLS scheme uses the one-way property of the hash function to protect location. It is feasible and secure in the case of infinite (enough) locations. However, it is insecure in current practical applications because the amount of user locations is not enough to resist brute force attacks. The attack is as follows:(1)
Calculate the coordinate hash tableT of all possible locations of the LDO’s visit region.(2)
Obtain a recordrecordjLDO from the blockchain, and extract the hash value LocHashj .(3)
Find out the locationxjyj corresponding to LocHashj in table T.We take the commonly used Global Positioning System (GPS) as an example to evaluate the feasibility of the above attack. In the GPS, the longitude and latitude output formats aredddmm.mmmm and ddmm.mmmm, respectively. So there are only 3.60×1011 positions in a square area of 1° in longitude and latitude. If estimated by 40°’ north latitude where New York City is located, 1 degree of longitude and 1 degree of latitude are equivalent to 85 and 111 kilometers, respectively, and a square area with 1 degree of longitude and latitude is 9,435 square kilometers. The land area of New York City is 789 square kilometers, so the number of available GPS locations is about 3.01×1010.We experiment on a personal computer using Python-3.9.7 and PyCharm Community Edition 2021.2.2 (64 bits). The configuration is CPU: Intel(R) Core(TM) i9-10900 CPU @ 2.80 GHz∼2.81 GHz, RAM: 64 G, and OS: Windows 10 Home (Chinese) 64 bits (10.0.19041). As in [9], we also choose SHA-256 as the hash function. The simulation result shows that the time cost to calculate the hash values of 109 position coordinates is 27.01 minutes, and the size of the coordinate hash table is 77.20 GB. Therefore, using such a personal computer can calculate the hash value of all locations of New York City in about 13 hours and 33 minutes.The above analysis and experiments show that if Ji et al.’s BMPLS scheme is used for New York City, the adversary can completely break the system in about 13.55 hours using a personal computer.If we use supercomputers or adopt distributed computing or cloud computing technology, we can break the system with very little time overhead.


## 4.2. On Multilevel Privacy-Preserving

Semitrusted LDR Can Obtain Accurate Location. Ji et al. claim that, in their scheme [9], semitrusted LDR is impossible to reduce the privacy protection region. Unfortunately, we found that semitrusted LDR can recover the LDO’s accurate location effectively. This is a more severe attack than reducing the privacy protection region. The attack is as follows:(1)
Obtain a recordrecordjLDO from the blockchain, and extract the hash value LocHashj.(2)
Run Algorithm3 interactively with LDO to obtain the response response.(3)
Run Algorithm4 to verify the response response, and extract the rectangular border xmin,xmax,ymin,ymax.(4)
Search for the location where the hash value is equal torecordjLDO.LocInfoj.LocHashj in the rectangular border xmin,xmax,ymin,ymax; that is, run Algorithm 5 to obtain the accurate location information xjyj.Algorithm 5: Location information extraction.
Input:Location hash valueLocHashj; Rectangular border xmin,xmax,ymin,ymax,Output:Location informationxjyj(1)
forxinxmin,xmaxdo(2)
foryinymin,ymaxdo(3)
Hash⟵Hashxy;(4)
ifHash=LocHashjthen(5)
returnxy;(6)
end if(7)
end for(8)
end forTakexmin=00587654,xmax=01012345 as an example to illustrate how to make x traverse xmin,xmax. Because order-preserving encryption requires the plaintext to be a positive integer, the format of the location needs to be changed from ddmm.mmmm to ddmmmmmm. Note that there are no location coordinates like dd60mmmm,dd61mmmm, … dd99mmmm, and 00587654,01012345 must be divided into 00587654,00599999 and 01000000,01012345. Then, the former is expressed as “x=00587655;x≤0059999;x++” and the latter as “x=01000000;x≤01012344;x++.”We evaluated the feasibility of this attack in the above environment. Assume that the rectangular borderxmin,xmax,ymin,ymax is a square area with a longitude and latitude of 0.5 minutes each. This is a rectangular area with a length of 928 meters and a width of 710 meters. The simulation result shows that the average cost to calculate the accurate location xjyj in such an area is 20.75 seconds.If a supercomputer is used or distributed computing or cloud computing technology is adopted, the time for LDR to find the accurate location will be milliseconds.


## 4.3. Other Weaknesses

(1)
In [9], the coordinates xi=i×X/2N and yi=i×Y/2N may not be integers. But in Definition 1 of [9], the plaintext space is clearly defined as the integer set m=i|1≤i≤m. Therefore, it will not be feasible to encryptxiandyiin Algorithm 1(lines 3 and 4).(2)
The LDO’s location coordinatexk or yk may happen to be a position grid coordinate xi or yi . If it happens, multilevel privacy protection will not be achieved. For example, if xk=x2N−1, then we have xk=xmin or xk=xmax for any trust level n. Then, the inequality in line 15 of Algorithm 4 will not hold, so LDR will not accept any rectangular border provided by LDO. Further, because borInfoid1.ciphid1x=ciphk.ciphkx or ciphk.ciphkx=borInfoid2.ciphid2x, LDR will determine that the x-coordinate of LDO is xmin or xmax.(3)
Then-level rectangular border xmin,xmax,ymin,ymax must be in the form of xi×2n,xi+1×2n,yj×2n,yj+1×2n, to ensure that the privacy protection region will not be reduced. If the LDO’s location coordinate xk or yk satisfies xk<x1 or yk<y1, then have xmin=x0=0 or ymin=y0=0. In this case, both Algorithms 3 and 4cannot be executed.(a)
Because 0 is not in the plaintext space of order-preserving encryption, Algorithm3 cannot generate the ciphertext ciphid1x (or ciphid3y) of xmin=0 (or ymin=0) (see Definition 1 of [9]).(b)
node0x and node0y are used when calculating horTreeroot' and vorTreeroot', but they are not used when calculating horTree and verTree, which will make neither horTreetoot'=horTreeroot nor vorTreetoot'=verTreeroot holds.


## 5. Improvement

We present an improvement to fix our attacks in this section and optimize the BMLS scheme to make it correct and executable.


### 5.1. Ideas for Improvement

The main improvement ideas are as follows:(1)
AddSetup and Key generation phases to the scheme to provide the foundation for other phases.(2)
Replace theLocation verification phase with the Location extraction phase. The original location verification algorithm only returns the verification result but not the location, while our extraction algorithm returns the location with the verification result.(3)
Use “Salt” to prevent brute force attacks. When calculating the hash valueLocHashj of the location xj‖yj, select a random number (salt) rj and let LocHashj=Hashxj‖yj‖rj. As long as the length of the random number is large enough, the brute force attacks in Sections 4.1 and 4.2 cannot be implemented, even with supercomputers or cloud computing.(4)
Use integer steps to generate grid coordinates to ensure that the coordinate values are positive integers.(5)
When the LDO’s location coordinatexk or yk is equal to the grid coordinate xi or yi, we make a minimum positive disturbance to the location coordinates to ensure they are not equal. In GPS, the minimum positive disturbance is 0.0001 minutes. This disturbance is only 18.5 cm and does not affect the actual performance of the system.


### 5.2. Improved Scheme

The improved BMPLS scheme consists of the following five phases.


#### 5.2.1. Setup

(1)
Choose an order-preserving encryption schemeΠOPE=OP‐KeyGen,OP‐Enc and set up public parameters [25].(2)
Choose a public-key encryption schemeΠPKE=PK‐KeyGen,PK‐Enc,PK‐Dec, such as RSA1024 and RSA2048, and set up public parameters.(3)
Choose a signature schemeΠSig=Sig‐KeyGen,Sig,Ver, such as DSA1024 and DSA2048, and set up public parameters.(4)
Choose a symmetric encryption schemeΠSE=S‐Enc,S‐Dec, such as AES128 and AES256, and set up public parameters.(5)
Choose a one-way collision resistance hash functionHash, such as SHA256 and SHA512.(6)
Set up and deploy a membership service provider (MSP) to maintain the identity of all users in the system and issue certificates for authentication and signature verification [27].(7)
Set up and deploy a trust level service provider (TLSP) to maintain the trust level of all users in the system and provide trust level query services [28].


#### 5.2.2. Key Generation

(1)
LDO runsΠOPE’s key generation algorithm OP‐KeyGen twice and obtains his x-coordinate encryption secret key opkLDOx and y-coordinate encryption secret key opkLDOy, respectively.(2)
LDO runsΠSig’s key generation algorithm Sig‐KeyGen and obtains his public-key pkLDO and signing key skLDO.(3)
LDO chooses his secret keykLDO for ΠSE.(4)
LDR runsΠPKE’s key generation algorithm PK‐KeyGen and obtains his public-key pkLDR and private key skLDR.


#### 5.2.3. Initialization

LDO selects the originx^0,y^0, step lengths xsl,ysl, and partition level N such that x,y|x^0≤x≤x^0+2N×xsl,y^0≤y≤y^0+2N×ysl can cover his visit region properly. Assume that x^0,y^0,xsl, and ysl have all been converted into positive integers. For example, convert dddmm.mmmm and ddmm.mmmm into dddmmmmmm and ddmmmmmm, respectively. We choose the order-preserving encryption scheme ΠOPE that allows the plaintext to be 0.Denote the visit region asregion=x^0,y^0,xsl,ysl,N. LDO executes Algorithm 6 to generate the registration record regRec and puts it into the blockchain.Algorithm 6: Registration record generation.
Input:Regionregion=x^0,y^0,xsl,ysl,N; LDO’s secret keys opkLDOx and opkLDOy; LDO′ signing key skLDOOutput:Registration recordregRec(1)
fori=0;i≤2N;i++do;(2)
xi=i×xsl;(3)
yi=i×ysl;(4)
ciphix=OP‐EncopkLDOx,xi;(5)
ciphiy=OP‐EncopkLDOy,yi;(6)
nodeix=Hashixiciphix;(7)
nodeiy=Hashiyiciphiy;(8)
end for(9)
horTree⟵genMTnode0x,node1x,node2x,…,node2Nx;(10)
verTree⟵genMTnode0y,node1y,node2y,…,node2Ny;(11)
regRec⟵regionhorTreerootverTreerootSigskLDO,regionhorTreerootverTreeroot;(12)
returnregRec.


#### 5.2.4. Location Record

Suppose that thej-th location of the LDO is x^0+xj,y^0+yj. LDO runs Algorithm 7 to generate a location record recordjLDO and puts it into the blockchain.Algorithm 7: Location record generation.
Input:LDO’sj-th location xj,yj; Region region=x^0,y^0,xsl,ysl,N; LDO’s secret keys opkLDOx,opkLDOy and kLDO; LDO’s signing key skLDOOutput:Location recordrecordjLDO(1)
fori=0;i≤2N;i++do;(2)
ifxj=i×xslthen(3)
xj⟵xj+1;(4)
end if(5)
ifyj=i×yslthen(6)
yj⟵yj+1;(7)
end if(8)
end for(9)
ciphjx=OP‐EncopkLDOx,xj;(10)
ciphjy=OP‐EncopkLDOy,yj;(11)
ciphj⟵ciphjxciphjy;(12)
OpeHashj⟵Hashciphj;(13)
Generate a random numberrj;(14)
LocHashj⟵Hashxj‖yj‖rj;(15)
SymCihj⟵S−EnckLDO,xj‖yj‖rj;(16)
LocInfoj⟵OpeHashjLocHashjSymCihjtimetampj;(17)
recordjLDO⟵LocInfoj‖recIdj−1LDOSigskLDO,LocInfoj‖recIdj−1LDO;(18)
returnrecordjLDO;


#### 5.2.5. Location Sharing

The location sharing phase consists of the location sharing stage and location extraction stage.(1) Location Sharing. When LDR wants to obtain the location corresponding to recordkLDO, he generates a request request=recoIdkLDOnSigskLDR,recoIdkLDO‖n and sends it to LDO.LDO generates a responseresponse and returns it to LDR as follows:(1)
It requests the LDR’s certificate from the membership service provider (MSP) and then verifies therequest. If it is invalid, it returns response=⊥ and aborts.(2)
It requests the LDR’s privacy protection levelnLDR from the trust level service provider (TLSP). If nLDR≠∞ and n<nLDR, it returns response=⊥ and aborts.(3)
It gets the location recordrecordkLDO from the blockchain.(4)
It runs Algorithm8 and returns response to LDR.Algorithm 8: Location sharing.
Input:Location recordrecordkLDO; LDO’s secret keys kLDO and (opkLDOx,opkLDOy); Privacy protection level n; LDR’s public-key pkLDROutput:Shared location informationrespons(1)
xk‖yk‖rk⟵S−DeckLDO,recordkLDO.LocInfok.SymCihk;(2)
choose a session keykses(3)
ifn=∞then(4)
response⟵S‐Enckses,xk‖yk‖rkPK‐EncpkLDR,kses(5)
else if0≤n≤Nthen(6)
findi such that i×2n×xsl<xk<i+1×2n×xsl(7)
id1⟵i×2n;id2⟵i+1×2n;(8)
xmin⟵i×2n×xsl;xmax⟵i+1×2n×xsl;(9)
findj such that j×2n×ysl<yk<j+1×2n×ysl(10)
id3⟵j×2n;id4⟵j+1×2n;(11)
ymin⟵j×2n×ysl;ymax⟵j+1×2n×ysl;(12)
ciphid1x=OP‐EncopkLDOx,xmin; ciphid2x=OP‐EncopkLDOx,xmax;(13)
ciphid3y=OP‐EncopkLDOy,ymin; ciphid4y=OP‐EncopkLDOy,ymax;(14)
borInfoid1⟵id1xminciphid1x; borInfoid2⟵id2xmaxciphid2x;(15)
borInfoid3⟵id3yminciphid3y; borInfoid4⟵id4xmaxciphid4y;(16)
borInfo⟵borInfoid1borInfoid2borInfoid3borInfoid4;(17)
nodesx⟵nodex1x,nodex2x,…; nodesy⟵nodey1y,nodey2y,…;(18)
ciphkx=OP‐EncopkLDOx,xk;ciphky=OP‐EncopkLDOy,yk;(19)
ciphk⟵ciphkxciphky;(20)
response⟵S‐Enckses,ciphkborInfonodesxnodesyPK‐EncpkLDR,kses;(21)
end if(22)
returnresponse.(2) Location Extraction. Receiving the response response, LDR gets the record recordkLDO from the blockchain and then runs Algorithm 9 to extract the location information.Algorithm 9: Location extraction.
Input:Response from LDOresponse; Record in the blockchain recordkLDO; LDR’s private key skLDROutput:Locationxk‖yk or rectangular border xmin,xmax,ymin,ymax, or False(1)
kses⟵PK‐DecskLDR,response.PK‐EncpkLDR,kses;(2)
ifxk′yk′rk′⟵S‐Deckses,responsethen(3)
ifHashxk′yk′rk′=recordkLDO. LocInfok⋅LocHashkthen(4)
returnxk′yk′;(5)
end if(6)
else ifciphkborInfonodesxnodesy⟵Deckses,responsethen(7)
borInfoid1borInfoid2borInfoid3borInfoid4⟵borInfo(8)
nodeid1x⟵HashborInfoid1; nodeid2x⟵HashborInfoid2;(9)
nodeid3y⟵HashborInfoid3; nodeid4y⟵HashborInfoid4;(10)
horTreeroot′⟵MerkleHashnodesx,nodeid1x,nodeid2x;(11)
vorTreeroot′⟵MerkleHashnodesy,nodeid3y,nodeid4y;(12)
ifhorTreetoot′=horTreerootandvorTreetoot′=verTreerootthen(13)
ifHashciphk=recoIdkLDO.LocInfok.OpeHashkandborInfoid1.ciphid1x<ciphk.ciphkx<borInfoid2.ciphid2xandborInfoid3.ciphid3x<ciphk.ciphky<borInfoid4.ciphid4xthen(14)
xmin⟵borInfoid1.xmin; xmax⟵borInfoid2.xmax;(15)
ymin⟵borInfoid3.ymin; ymax⟵borInfoid4.ymax;(16)
returnxmin,xmax,ymin,ymax;(17)
end if(18)
end if(19)
end if(20)
returnFalse.


### 5.3. Security and Performance Analysis

#### 5.3.1. Security Analysis

We follow the definitions of [9] to analyze the security of the improved BMPLS scheme as follows:(1) Decentralization. One of the main advantages of blockchain is decentralization. The BMLS scheme uses blockchain to manage and store location information, so it inherits decentralization.(2) Untamperability. The unforgeability mentioned in [9] is just untamperability, which is another main property of blockchain. For the same reason as above, the BMLS scheme also inherits untamperability.(3) Confidentiality. In the improved BMPLS scheme, the only data that needs confidentiality protection is LDO’s location coordinate xj,yj. The scheme uses four different cryptographic techniques to protect it: hash function, symmetric encryption, order-preserving encryption, and hybrid encryption. Because the hash function cannot achieve indistinguishable security, the improved BMPLS scheme can only achieve confidentiality in the “all-or-nothing” sense, that is, prevent the adversary from recovering the location coordinates. We analyze the probability of a successful attack in different situations as follows:(1)
Getxj,yjfromLocHashj=Hashxj‖yj‖rj. Let k be the binary bit length of rj. According to the one-way property of the hash function, the probability that the adversary obtains xj‖yj from LocHashj is less than 2−k, even if he knows a small rectangular border. When k is large enough, such as k=160, the probability is negligible.(2)
Getxj,yjfromSymCihj=S‐EnckLDO,xj‖yj‖rj. Under the assumption that the symmetric encryption scheme ΠSE is secure, the probability that the adversary obtains xj‖yj from SymCihj is negligible.(3)
Getxk,ykfromresponse=S‐Enckses,xj‖yj‖rjPK‐EncpkLDR,kses. If the selected symmetric encryption scheme ΠSE and public-key encryption scheme ΠPKE are secure, then the probability that the adversary obtains xk,yk from S‐Enckses,xk‖yk‖rkPK‐EncpkLDR,kses is also negligible.(4)
Getxk,ykfromciphkx=OP‐EncopkLDO,xk;ciphky=OP‐EncopkLDO,yk. Similarly, if the selected order-preserving encryption scheme ΠOPE is secure, the probability of recovering the plaintext from the ciphertext is also negligible.Therefore, the probability that the adversary obtains the LDO’s location coordinatexj,yj is negligible, and the improved BMPLS scheme achieves confidentiality.(4) Multilevel Location Privacy Protection. Multilevel location privacy protection aims to ensure that the semitrusted LDR cannot reduce the rectangular border of the LDO’s location.Firstly, confidentiality guarantees that semitrusted LDR cannot obtain the exact location coordinates of LDO.Secondly, then-level rectangular border obtained by LDR is xmin,xmax,ymin,ymax, where xmin=i×2n×xsl, xmax=i+1×2n×xsl, ymin=j×2n×ysl, and ymax=j+1×2n×ysl. Requesting n-level rectangular borders at different times will get the same results, which will not help reduce the rectangular border. In addition, when n1<n2, the n1-level rectangular border must be included in the n2-level rectangular border. It is impossible to reduce the rectangular border by finding the intersection of the rectangular borders of different levels.Thirdly, because the order-preserving encryption algorithmOP‐Enc is a pseudorandom order-preserving function controlled by a key, as long as the ciphertext space is large enough, such as 2160, the probability of reversing ciphix (or ciphiy) from nodeix=Hashixiciphix (or nodeiy=Hashiyiciphiy) will be negligible. Therefore, the adversary’s probability of reducing the rectangular border by finding the coordinate ciphertext is negligible.Finally, thex-coordinate and y-coordinate are encrypted with different keys, so there is no order-preserving relationship between the ciphertext of the x-coordinate and the ciphertext of the y-coordinate. ciphkx<ciphiy (or ciphky>ciphiy) does not imply xk<yi (or xk>yi). It is impossible for the adversary to use ymin and ymax to narrow the range of xk. The same is true for yk.(5) Retrievability. Retrievability means that the LDO’s location coordinates can be retrieved effectively [9]. In the improved BMPLS scheme, the location coordinate xj,yj is stored in the blockchain via ciphertext SymCihj=S‐EnckLDO,xj‖yj‖rj. LDO knows the decryption key kLDO and can retrieve the location coordinate efficiently. On the other hand, in the location sharing phase, the LDO sends the location coordinate xk,yk to the LDR in the form of response=S‐Enckses,xk‖yk‖rkPK‐EncpkLDR,kses. LDR can use its decryption key skLDR to decrypt the location coordinate xk,yk. So, the improved BMPLS scheme achieves retrievability.(6) Verifiability. Verifiability means that LDR can use blockchain to verify whether the location information he gets is correct. The improved BMPLS scheme provides different verification methods in two cases:(1)
The trusted LDR firstly decrypts the location coordinates and random numberxk′yk′rk′ and calculates the hash value Hashxk′yk′rk′. Then, he extracts the hash value LocHashk corresponding to the coordinate from the blockchain and checks whether Hashxk′yk′rk′=LocHashk . The untamperability of the blockchain and the signature of the LDO ensure that LocHashk will not be tampered with, and the collision resistance of the hash function ensures that xk′yk′rk′ will not be replaced, so xk′,yk′ is correct.(2)
The semitrusted LDR gets the coordinates of a rectangular borderxmin,xmax,ymin,ymax, with their order-preserving ciphertext ciphid1x,ciphid2x,ciphid3y,ciphid4y, and then verifies it by the Merkle tree and comparing the order of the ciphertext. Similarly, the untamperability and the signature ensure that horTreeroot and verTreeroot will not be tampered with, and the collision resistance of the Merkle tree ensures that ciphid1x,ciphid2x,ciphid3y,andciphid4y are correct. Finally, the property of order-preserving encryption ensures that LDO’s location xk,yk is in the rectangular border xmin,xmax,ymin,ymax.The security comparison of related schemes is shown in Table2. It shows that our improved scheme has apparent advantages in security.


#### 5.3.2. Performance Analysis

We perform performance simulations under the same environment in Section4. To ensure security, we set the ciphertext space of order-preserving encryption to be 2160, denoted as OPE 2160. Choose SHA, AES, RSA, and DSA as hash, symmetric encryption, public-key encryption, and digital signature algorithms. We simulate on two data scales, AES128 + RSA1024 + DSA1024 and AES256 + RSA2048 + DSA2048. We also use two hash functions, SHA256 and SHA512. Since the time cost of the hash function is very small, it has no significant impact on the simulation. The simulation results of each phase are as follows:(1) Initialization. For initialization, we simulated the partition level N from 8 to 15. The result is shown in Figure 3. When N  = 10, the LDO’s initialization time is only 3.87 seconds. Estimated with a step length of 10 meters, the visit region region is a rectangle with a side length of 10.24 kilometers in this case. When N  = 13, the LDO’s initialization time is 30.89 seconds. In this case, the visit region’s side length is 81.92 kilometers, which can meet the needs of most scenarios. When N  = 15, the initialization of the LDO takes 123.53 seconds. At this time, the side length of the visit region has been as long as 327.68 kilometers.Figure 3
Initialization overhead.The simulation shows that the initialization time is generally tens of seconds. Because each LDO only needs to be initialized once, this overhead is acceptable.(2) Location Record. We conducted eight simulations of location record generation, and the results are shown in Figure 4. In the case of OPE(2160), AES128, and DSA1024, the minimum overhead is 7.81 ms, the maximum is 8.17 ms, and the average is 8.00 ms. When the case of OPE(2160), AES256, and DSA2048, the minimum is 8.53 ms, the maximum is 9.05 ms, and the average is 8.78 ms. In both cases, the overheads of location record generation are very small.Figure 4
Record generation overhead.(3) Location Sharing. There are two cases of location sharing: n=∞ (trusted LDR) and 0≤n≤N (semitrusted LDR). The simulation results are shown in Figures 5(a) and 5(b).Figure 5
Location sharing overhead, (a)n=∞; (b) n=3.
(a)(b)Case ofn=∞. When using AES128, RSA1024, and DSA1024, the average overhead is 2.43 ms. While using AES256, RSA2048, and DSA2048, it is 5.25 ms.Case of0≤n≤N. The computational overheads increase to 25.35 ms and 28.07 ms, respectively. Most of the overhead is used to calculate six order-preserving encryption, which is about 22.70 ms. In this case, the computational overhead of our scheme is greater than that of [9] since we use order-preserving encryption with large ciphertext space, and [9] uses small ciphertext space. This is the time cost to improve security.(4) Location Extraction. There are also two cases for location extraction, and the simulation results are shown in Figures 6(a) and 6(b). Unlike location sharing, there is little difference in overheads between the two cases. When using AES128, RSA1024, and DSA1024, the average overheads are 3.67 ms and 4.16 ms, respectively. While using AES256, RSA2048, and DSA2048, they are 21.41 ms and 21.741 ms, respectively.Figure 6
Location extraction overhead, (a)n=∞; (b) n=3.
(a)(b)The above simulation shows that the computational overhead of the location record phase is within 10 ms, and the computational overheads of the location sharing and location extraction phases are both within 30 ms. Therefore, our improved BMPLS scheme is practical.


## 5.1. Ideas for Improvement

The main improvement ideas are as follows:(1)
AddSetup and Key generation phases to the scheme to provide the foundation for other phases.(2)
Replace theLocation verification phase with the Location extraction phase. The original location verification algorithm only returns the verification result but not the location, while our extraction algorithm returns the location with the verification result.(3)
Use “Salt” to prevent brute force attacks. When calculating the hash valueLocHashj of the location xj‖yj, select a random number (salt) rj and let LocHashj=Hashxj‖yj‖rj. As long as the length of the random number is large enough, the brute force attacks in Sections 4.1 and 4.2 cannot be implemented, even with supercomputers or cloud computing.(4)
Use integer steps to generate grid coordinates to ensure that the coordinate values are positive integers.(5)
When the LDO’s location coordinatexk or yk is equal to the grid coordinate xi or yi, we make a minimum positive disturbance to the location coordinates to ensure they are not equal. In GPS, the minimum positive disturbance is 0.0001 minutes. This disturbance is only 18.5 cm and does not affect the actual performance of the system.


## 5.2. Improved Scheme

The improved BMPLS scheme consists of the following five phases.


### 5.2.1. Setup

(1)
Choose an order-preserving encryption schemeΠOPE=OP‐KeyGen,OP‐Enc and set up public parameters [25].(2)
Choose a public-key encryption schemeΠPKE=PK‐KeyGen,PK‐Enc,PK‐Dec, such as RSA1024 and RSA2048, and set up public parameters.(3)
Choose a signature schemeΠSig=Sig‐KeyGen,Sig,Ver, such as DSA1024 and DSA2048, and set up public parameters.(4)
Choose a symmetric encryption schemeΠSE=S‐Enc,S‐Dec, such as AES128 and AES256, and set up public parameters.(5)
Choose a one-way collision resistance hash functionHash, such as SHA256 and SHA512.(6)
Set up and deploy a membership service provider (MSP) to maintain the identity of all users in the system and issue certificates for authentication and signature verification [27].(7)
Set up and deploy a trust level service provider (TLSP) to maintain the trust level of all users in the system and provide trust level query services [28].


### 5.2.2. Key Generation

(1)
LDO runsΠOPE’s key generation algorithm OP‐KeyGen twice and obtains his x-coordinate encryption secret key opkLDOx and y-coordinate encryption secret key opkLDOy, respectively.(2)
LDO runsΠSig’s key generation algorithm Sig‐KeyGen and obtains his public-key pkLDO and signing key skLDO.(3)
LDO chooses his secret keykLDO for ΠSE.(4)
LDR runsΠPKE’s key generation algorithm PK‐KeyGen and obtains his public-key pkLDR and private key skLDR.


### 5.2.3. Initialization

LDO selects the originx^0,y^0, step lengths xsl,ysl, and partition level N such that x,y|x^0≤x≤x^0+2N×xsl,y^0≤y≤y^0+2N×ysl can cover his visit region properly. Assume that x^0,y^0,xsl, and ysl have all been converted into positive integers. For example, convert dddmm.mmmm and ddmm.mmmm into dddmmmmmm and ddmmmmmm, respectively. We choose the order-preserving encryption scheme ΠOPE that allows the plaintext to be 0.Denote the visit region asregion=x^0,y^0,xsl,ysl,N. LDO executes Algorithm 6 to generate the registration record regRec and puts it into the blockchain.Algorithm 6: Registration record generation.
Input:Regionregion=x^0,y^0,xsl,ysl,N; LDO’s secret keys opkLDOx and opkLDOy; LDO′ signing key skLDOOutput:Registration recordregRec(1)
fori=0;i≤2N;i++do;(2)
xi=i×xsl;(3)
yi=i×ysl;(4)
ciphix=OP‐EncopkLDOx,xi;(5)
ciphiy=OP‐EncopkLDOy,yi;(6)
nodeix=Hashixiciphix;(7)
nodeiy=Hashiyiciphiy;(8)
end for(9)
horTree⟵genMTnode0x,node1x,node2x,…,node2Nx;(10)
verTree⟵genMTnode0y,node1y,node2y,…,node2Ny;(11)
regRec⟵regionhorTreerootverTreerootSigskLDO,regionhorTreerootverTreeroot;(12)
returnregRec.


### 5.2.4. Location Record

Suppose that thej-th location of the LDO is x^0+xj,y^0+yj. LDO runs Algorithm 7 to generate a location record recordjLDO and puts it into the blockchain.Algorithm 7: Location record generation.
Input:LDO’sj-th location xj,yj; Region region=x^0,y^0,xsl,ysl,N; LDO’s secret keys opkLDOx,opkLDOy and kLDO; LDO’s signing key skLDOOutput:Location recordrecordjLDO(1)
fori=0;i≤2N;i++do;(2)
ifxj=i×xslthen(3)
xj⟵xj+1;(4)
end if(5)
ifyj=i×yslthen(6)
yj⟵yj+1;(7)
end if(8)
end for(9)
ciphjx=OP‐EncopkLDOx,xj;(10)
ciphjy=OP‐EncopkLDOy,yj;(11)
ciphj⟵ciphjxciphjy;(12)
OpeHashj⟵Hashciphj;(13)
Generate a random numberrj;(14)
LocHashj⟵Hashxj‖yj‖rj;(15)
SymCihj⟵S−EnckLDO,xj‖yj‖rj;(16)
LocInfoj⟵OpeHashjLocHashjSymCihjtimetampj;(17)
recordjLDO⟵LocInfoj‖recIdj−1LDOSigskLDO,LocInfoj‖recIdj−1LDO;(18)
returnrecordjLDO;


### 5.2.5. Location Sharing

The location sharing phase consists of the location sharing stage and location extraction stage.(1) Location Sharing. When LDR wants to obtain the location corresponding to recordkLDO, he generates a request request=recoIdkLDOnSigskLDR,recoIdkLDO‖n and sends it to LDO.LDO generates a responseresponse and returns it to LDR as follows:(1)
It requests the LDR’s certificate from the membership service provider (MSP) and then verifies therequest. If it is invalid, it returns response=⊥ and aborts.(2)
It requests the LDR’s privacy protection levelnLDR from the trust level service provider (TLSP). If nLDR≠∞ and n<nLDR, it returns response=⊥ and aborts.(3)
It gets the location recordrecordkLDO from the blockchain.(4)
It runs Algorithm8 and returns response to LDR.Algorithm 8: Location sharing.
Input:Location recordrecordkLDO; LDO’s secret keys kLDO and (opkLDOx,opkLDOy); Privacy protection level n; LDR’s public-key pkLDROutput:Shared location informationrespons(1)
xk‖yk‖rk⟵S−DeckLDO,recordkLDO.LocInfok.SymCihk;(2)
choose a session keykses(3)
ifn=∞then(4)
response⟵S‐Enckses,xk‖yk‖rkPK‐EncpkLDR,kses(5)
else if0≤n≤Nthen(6)
findi such that i×2n×xsl<xk<i+1×2n×xsl(7)
id1⟵i×2n;id2⟵i+1×2n;(8)
xmin⟵i×2n×xsl;xmax⟵i+1×2n×xsl;(9)
findj such that j×2n×ysl<yk<j+1×2n×ysl(10)
id3⟵j×2n;id4⟵j+1×2n;(11)
ymin⟵j×2n×ysl;ymax⟵j+1×2n×ysl;(12)
ciphid1x=OP‐EncopkLDOx,xmin; ciphid2x=OP‐EncopkLDOx,xmax;(13)
ciphid3y=OP‐EncopkLDOy,ymin; ciphid4y=OP‐EncopkLDOy,ymax;(14)
borInfoid1⟵id1xminciphid1x; borInfoid2⟵id2xmaxciphid2x;(15)
borInfoid3⟵id3yminciphid3y; borInfoid4⟵id4xmaxciphid4y;(16)
borInfo⟵borInfoid1borInfoid2borInfoid3borInfoid4;(17)
nodesx⟵nodex1x,nodex2x,…; nodesy⟵nodey1y,nodey2y,…;(18)
ciphkx=OP‐EncopkLDOx,xk;ciphky=OP‐EncopkLDOy,yk;(19)
ciphk⟵ciphkxciphky;(20)
response⟵S‐Enckses,ciphkborInfonodesxnodesyPK‐EncpkLDR,kses;(21)
end if(22)
returnresponse.(2) Location Extraction. Receiving the response response, LDR gets the record recordkLDO from the blockchain and then runs Algorithm 9 to extract the location information.Algorithm 9: Location extraction.
Input:Response from LDOresponse; Record in the blockchain recordkLDO; LDR’s private key skLDROutput:Locationxk‖yk or rectangular border xmin,xmax,ymin,ymax, or False(1)
kses⟵PK‐DecskLDR,response.PK‐EncpkLDR,kses;(2)
ifxk′yk′rk′⟵S‐Deckses,responsethen(3)
ifHashxk′yk′rk′=recordkLDO. LocInfok⋅LocHashkthen(4)
returnxk′yk′;(5)
end if(6)
else ifciphkborInfonodesxnodesy⟵Deckses,responsethen(7)
borInfoid1borInfoid2borInfoid3borInfoid4⟵borInfo(8)
nodeid1x⟵HashborInfoid1; nodeid2x⟵HashborInfoid2;(9)
nodeid3y⟵HashborInfoid3; nodeid4y⟵HashborInfoid4;(10)
horTreeroot′⟵MerkleHashnodesx,nodeid1x,nodeid2x;(11)
vorTreeroot′⟵MerkleHashnodesy,nodeid3y,nodeid4y;(12)
ifhorTreetoot′=horTreerootandvorTreetoot′=verTreerootthen(13)
ifHashciphk=recoIdkLDO.LocInfok.OpeHashkandborInfoid1.ciphid1x<ciphk.ciphkx<borInfoid2.ciphid2xandborInfoid3.ciphid3x<ciphk.ciphky<borInfoid4.ciphid4xthen(14)
xmin⟵borInfoid1.xmin; xmax⟵borInfoid2.xmax;(15)
ymin⟵borInfoid3.ymin; ymax⟵borInfoid4.ymax;(16)
returnxmin,xmax,ymin,ymax;(17)
end if(18)
end if(19)
end if(20)
returnFalse.


## 5.2.1. Setup

(1)
Choose an order-preserving encryption schemeΠOPE=OP‐KeyGen,OP‐Enc and set up public parameters [25].(2)
Choose a public-key encryption schemeΠPKE=PK‐KeyGen,PK‐Enc,PK‐Dec, such as RSA1024 and RSA2048, and set up public parameters.(3)
Choose a signature schemeΠSig=Sig‐KeyGen,Sig,Ver, such as DSA1024 and DSA2048, and set up public parameters.(4)
Choose a symmetric encryption schemeΠSE=S‐Enc,S‐Dec, such as AES128 and AES256, and set up public parameters.(5)
Choose a one-way collision resistance hash functionHash, such as SHA256 and SHA512.(6)
Set up and deploy a membership service provider (MSP) to maintain the identity of all users in the system and issue certificates for authentication and signature verification [27].(7)
Set up and deploy a trust level service provider (TLSP) to maintain the trust level of all users in the system and provide trust level query services [28].


## 5.2.2. Key Generation

(1)
LDO runsΠOPE’s key generation algorithm OP‐KeyGen twice and obtains his x-coordinate encryption secret key opkLDOx and y-coordinate encryption secret key opkLDOy, respectively.(2)
LDO runsΠSig’s key generation algorithm Sig‐KeyGen and obtains his public-key pkLDO and signing key skLDO.(3)
LDO chooses his secret keykLDO for ΠSE.(4)
LDR runsΠPKE’s key generation algorithm PK‐KeyGen and obtains his public-key pkLDR and private key skLDR.


## 5.2.3. Initialization

LDO selects the originx^0,y^0, step lengths xsl,ysl, and partition level N such that x,y|x^0≤x≤x^0+2N×xsl,y^0≤y≤y^0+2N×ysl can cover his visit region properly. Assume that x^0,y^0,xsl, and ysl have all been converted into positive integers. For example, convert dddmm.mmmm and ddmm.mmmm into dddmmmmmm and ddmmmmmm, respectively. We choose the order-preserving encryption scheme ΠOPE that allows the plaintext to be 0.Denote the visit region asregion=x^0,y^0,xsl,ysl,N. LDO executes Algorithm 6 to generate the registration record regRec and puts it into the blockchain.Algorithm 6: Registration record generation.
Input:Regionregion=x^0,y^0,xsl,ysl,N; LDO’s secret keys opkLDOx and opkLDOy; LDO′ signing key skLDOOutput:Registration recordregRec(1)
fori=0;i≤2N;i++do;(2)
xi=i×xsl;(3)
yi=i×ysl;(4)
ciphix=OP‐EncopkLDOx,xi;(5)
ciphiy=OP‐EncopkLDOy,yi;(6)
nodeix=Hashixiciphix;(7)
nodeiy=Hashiyiciphiy;(8)
end for(9)
horTree⟵genMTnode0x,node1x,node2x,…,node2Nx;(10)
verTree⟵genMTnode0y,node1y,node2y,…,node2Ny;(11)
regRec⟵regionhorTreerootverTreerootSigskLDO,regionhorTreerootverTreeroot;(12)
returnregRec.


## 5.2.4. Location Record

Suppose that thej-th location of the LDO is x^0+xj,y^0+yj. LDO runs Algorithm 7 to generate a location record recordjLDO and puts it into the blockchain.Algorithm 7: Location record generation.
Input:LDO’sj-th location xj,yj; Region region=x^0,y^0,xsl,ysl,N; LDO’s secret keys opkLDOx,opkLDOy and kLDO; LDO’s signing key skLDOOutput:Location recordrecordjLDO(1)
fori=0;i≤2N;i++do;(2)
ifxj=i×xslthen(3)
xj⟵xj+1;(4)
end if(5)
ifyj=i×yslthen(6)
yj⟵yj+1;(7)
end if(8)
end for(9)
ciphjx=OP‐EncopkLDOx,xj;(10)
ciphjy=OP‐EncopkLDOy,yj;(11)
ciphj⟵ciphjxciphjy;(12)
OpeHashj⟵Hashciphj;(13)
Generate a random numberrj;(14)
LocHashj⟵Hashxj‖yj‖rj;(15)
SymCihj⟵S−EnckLDO,xj‖yj‖rj;(16)
LocInfoj⟵OpeHashjLocHashjSymCihjtimetampj;(17)
recordjLDO⟵LocInfoj‖recIdj−1LDOSigskLDO,LocInfoj‖recIdj−1LDO;(18)
returnrecordjLDO;


## 5.2.5. Location Sharing

The location sharing phase consists of the location sharing stage and location extraction stage.(1) Location Sharing. When LDR wants to obtain the location corresponding to recordkLDO, he generates a request request=recoIdkLDOnSigskLDR,recoIdkLDO‖n and sends it to LDO.LDO generates a responseresponse and returns it to LDR as follows:(1)
It requests the LDR’s certificate from the membership service provider (MSP) and then verifies therequest. If it is invalid, it returns response=⊥ and aborts.(2)
It requests the LDR’s privacy protection levelnLDR from the trust level service provider (TLSP). If nLDR≠∞ and n<nLDR, it returns response=⊥ and aborts.(3)
It gets the location recordrecordkLDO from the blockchain.(4)
It runs Algorithm8 and returns response to LDR.Algorithm 8: Location sharing.
Input:Location recordrecordkLDO; LDO’s secret keys kLDO and (opkLDOx,opkLDOy); Privacy protection level n; LDR’s public-key pkLDROutput:Shared location informationrespons(1)
xk‖yk‖rk⟵S−DeckLDO,recordkLDO.LocInfok.SymCihk;(2)
choose a session keykses(3)
ifn=∞then(4)
response⟵S‐Enckses,xk‖yk‖rkPK‐EncpkLDR,kses(5)
else if0≤n≤Nthen(6)
findi such that i×2n×xsl<xk<i+1×2n×xsl(7)
id1⟵i×2n;id2⟵i+1×2n;(8)
xmin⟵i×2n×xsl;xmax⟵i+1×2n×xsl;(9)
findj such that j×2n×ysl<yk<j+1×2n×ysl(10)
id3⟵j×2n;id4⟵j+1×2n;(11)
ymin⟵j×2n×ysl;ymax⟵j+1×2n×ysl;(12)
ciphid1x=OP‐EncopkLDOx,xmin; ciphid2x=OP‐EncopkLDOx,xmax;(13)
ciphid3y=OP‐EncopkLDOy,ymin; ciphid4y=OP‐EncopkLDOy,ymax;(14)
borInfoid1⟵id1xminciphid1x; borInfoid2⟵id2xmaxciphid2x;(15)
borInfoid3⟵id3yminciphid3y; borInfoid4⟵id4xmaxciphid4y;(16)
borInfo⟵borInfoid1borInfoid2borInfoid3borInfoid4;(17)
nodesx⟵nodex1x,nodex2x,…; nodesy⟵nodey1y,nodey2y,…;(18)
ciphkx=OP‐EncopkLDOx,xk;ciphky=OP‐EncopkLDOy,yk;(19)
ciphk⟵ciphkxciphky;(20)
response⟵S‐Enckses,ciphkborInfonodesxnodesyPK‐EncpkLDR,kses;(21)
end if(22)
returnresponse.(2) Location Extraction. Receiving the response response, LDR gets the record recordkLDO from the blockchain and then runs Algorithm 9 to extract the location information.Algorithm 9: Location extraction.
Input:Response from LDOresponse; Record in the blockchain recordkLDO; LDR’s private key skLDROutput:Locationxk‖yk or rectangular border xmin,xmax,ymin,ymax, or False(1)
kses⟵PK‐DecskLDR,response.PK‐EncpkLDR,kses;(2)
ifxk′yk′rk′⟵S‐Deckses,responsethen(3)
ifHashxk′yk′rk′=recordkLDO. LocInfok⋅LocHashkthen(4)
returnxk′yk′;(5)
end if(6)
else ifciphkborInfonodesxnodesy⟵Deckses,responsethen(7)
borInfoid1borInfoid2borInfoid3borInfoid4⟵borInfo(8)
nodeid1x⟵HashborInfoid1; nodeid2x⟵HashborInfoid2;(9)
nodeid3y⟵HashborInfoid3; nodeid4y⟵HashborInfoid4;(10)
horTreeroot′⟵MerkleHashnodesx,nodeid1x,nodeid2x;(11)
vorTreeroot′⟵MerkleHashnodesy,nodeid3y,nodeid4y;(12)
ifhorTreetoot′=horTreerootandvorTreetoot′=verTreerootthen(13)
ifHashciphk=recoIdkLDO.LocInfok.OpeHashkandborInfoid1.ciphid1x<ciphk.ciphkx<borInfoid2.ciphid2xandborInfoid3.ciphid3x<ciphk.ciphky<borInfoid4.ciphid4xthen(14)
xmin⟵borInfoid1.xmin; xmax⟵borInfoid2.xmax;(15)
ymin⟵borInfoid3.ymin; ymax⟵borInfoid4.ymax;(16)
returnxmin,xmax,ymin,ymax;(17)
end if(18)
end if(19)
end if(20)
returnFalse.


## 5.3. Security and Performance Analysis

### 5.3.1. Security Analysis

We follow the definitions of [9] to analyze the security of the improved BMPLS scheme as follows:(1) Decentralization. One of the main advantages of blockchain is decentralization. The BMLS scheme uses blockchain to manage and store location information, so it inherits decentralization.(2) Untamperability. The unforgeability mentioned in [9] is just untamperability, which is another main property of blockchain. For the same reason as above, the BMLS scheme also inherits untamperability.(3) Confidentiality. In the improved BMPLS scheme, the only data that needs confidentiality protection is LDO’s location coordinate xj,yj. The scheme uses four different cryptographic techniques to protect it: hash function, symmetric encryption, order-preserving encryption, and hybrid encryption. Because the hash function cannot achieve indistinguishable security, the improved BMPLS scheme can only achieve confidentiality in the “all-or-nothing” sense, that is, prevent the adversary from recovering the location coordinates. We analyze the probability of a successful attack in different situations as follows:(1)
Getxj,yjfromLocHashj=Hashxj‖yj‖rj. Let k be the binary bit length of rj. According to the one-way property of the hash function, the probability that the adversary obtains xj‖yj from LocHashj is less than 2−k, even if he knows a small rectangular border. When k is large enough, such as k=160, the probability is negligible.(2)
Getxj,yjfromSymCihj=S‐EnckLDO,xj‖yj‖rj. Under the assumption that the symmetric encryption scheme ΠSE is secure, the probability that the adversary obtains xj‖yj from SymCihj is negligible.(3)
Getxk,ykfromresponse=S‐Enckses,xj‖yj‖rjPK‐EncpkLDR,kses. If the selected symmetric encryption scheme ΠSE and public-key encryption scheme ΠPKE are secure, then the probability that the adversary obtains xk,yk from S‐Enckses,xk‖yk‖rkPK‐EncpkLDR,kses is also negligible.(4)
Getxk,ykfromciphkx=OP‐EncopkLDO,xk;ciphky=OP‐EncopkLDO,yk. Similarly, if the selected order-preserving encryption scheme ΠOPE is secure, the probability of recovering the plaintext from the ciphertext is also negligible.Therefore, the probability that the adversary obtains the LDO’s location coordinatexj,yj is negligible, and the improved BMPLS scheme achieves confidentiality.(4) Multilevel Location Privacy Protection. Multilevel location privacy protection aims to ensure that the semitrusted LDR cannot reduce the rectangular border of the LDO’s location.Firstly, confidentiality guarantees that semitrusted LDR cannot obtain the exact location coordinates of LDO.Secondly, then-level rectangular border obtained by LDR is xmin,xmax,ymin,ymax, where xmin=i×2n×xsl, xmax=i+1×2n×xsl, ymin=j×2n×ysl, and ymax=j+1×2n×ysl. Requesting n-level rectangular borders at different times will get the same results, which will not help reduce the rectangular border. In addition, when n1<n2, the n1-level rectangular border must be included in the n2-level rectangular border. It is impossible to reduce the rectangular border by finding the intersection of the rectangular borders of different levels.Thirdly, because the order-preserving encryption algorithmOP‐Enc is a pseudorandom order-preserving function controlled by a key, as long as the ciphertext space is large enough, such as 2160, the probability of reversing ciphix (or ciphiy) from nodeix=Hashixiciphix (or nodeiy=Hashiyiciphiy) will be negligible. Therefore, the adversary’s probability of reducing the rectangular border by finding the coordinate ciphertext is negligible.Finally, thex-coordinate and y-coordinate are encrypted with different keys, so there is no order-preserving relationship between the ciphertext of the x-coordinate and the ciphertext of the y-coordinate. ciphkx<ciphiy (or ciphky>ciphiy) does not imply xk<yi (or xk>yi). It is impossible for the adversary to use ymin and ymax to narrow the range of xk. The same is true for yk.(5) Retrievability. Retrievability means that the LDO’s location coordinates can be retrieved effectively [9]. In the improved BMPLS scheme, the location coordinate xj,yj is stored in the blockchain via ciphertext SymCihj=S‐EnckLDO,xj‖yj‖rj. LDO knows the decryption key kLDO and can retrieve the location coordinate efficiently. On the other hand, in the location sharing phase, the LDO sends the location coordinate xk,yk to the LDR in the form of response=S‐Enckses,xk‖yk‖rkPK‐EncpkLDR,kses. LDR can use its decryption key skLDR to decrypt the location coordinate xk,yk. So, the improved BMPLS scheme achieves retrievability.(6) Verifiability. Verifiability means that LDR can use blockchain to verify whether the location information he gets is correct. The improved BMPLS scheme provides different verification methods in two cases:(1)
The trusted LDR firstly decrypts the location coordinates and random numberxk′yk′rk′ and calculates the hash value Hashxk′yk′rk′. Then, he extracts the hash value LocHashk corresponding to the coordinate from the blockchain and checks whether Hashxk′yk′rk′=LocHashk . The untamperability of the blockchain and the signature of the LDO ensure that LocHashk will not be tampered with, and the collision resistance of the hash function ensures that xk′yk′rk′ will not be replaced, so xk′,yk′ is correct.(2)
The semitrusted LDR gets the coordinates of a rectangular borderxmin,xmax,ymin,ymax, with their order-preserving ciphertext ciphid1x,ciphid2x,ciphid3y,ciphid4y, and then verifies it by the Merkle tree and comparing the order of the ciphertext. Similarly, the untamperability and the signature ensure that horTreeroot and verTreeroot will not be tampered with, and the collision resistance of the Merkle tree ensures that ciphid1x,ciphid2x,ciphid3y,andciphid4y are correct. Finally, the property of order-preserving encryption ensures that LDO’s location xk,yk is in the rectangular border xmin,xmax,ymin,ymax.The security comparison of related schemes is shown in Table2. It shows that our improved scheme has apparent advantages in security.


### 5.3.2. Performance Analysis

We perform performance simulations under the same environment in Section4. To ensure security, we set the ciphertext space of order-preserving encryption to be 2160, denoted as OPE 2160. Choose SHA, AES, RSA, and DSA as hash, symmetric encryption, public-key encryption, and digital signature algorithms. We simulate on two data scales, AES128 + RSA1024 + DSA1024 and AES256 + RSA2048 + DSA2048. We also use two hash functions, SHA256 and SHA512. Since the time cost of the hash function is very small, it has no significant impact on the simulation. The simulation results of each phase are as follows:(1) Initialization. For initialization, we simulated the partition level N from 8 to 15. The result is shown in Figure 3. When N  = 10, the LDO’s initialization time is only 3.87 seconds. Estimated with a step length of 10 meters, the visit region region is a rectangle with a side length of 10.24 kilometers in this case. When N  = 13, the LDO’s initialization time is 30.89 seconds. In this case, the visit region’s side length is 81.92 kilometers, which can meet the needs of most scenarios. When N  = 15, the initialization of the LDO takes 123.53 seconds. At this time, the side length of the visit region has been as long as 327.68 kilometers.Figure 3
Initialization overhead.The simulation shows that the initialization time is generally tens of seconds. Because each LDO only needs to be initialized once, this overhead is acceptable.(2) Location Record. We conducted eight simulations of location record generation, and the results are shown in Figure 4. In the case of OPE(2160), AES128, and DSA1024, the minimum overhead is 7.81 ms, the maximum is 8.17 ms, and the average is 8.00 ms. When the case of OPE(2160), AES256, and DSA2048, the minimum is 8.53 ms, the maximum is 9.05 ms, and the average is 8.78 ms. In both cases, the overheads of location record generation are very small.Figure 4
Record generation overhead.(3) Location Sharing. There are two cases of location sharing: n=∞ (trusted LDR) and 0≤n≤N (semitrusted LDR). The simulation results are shown in Figures 5(a) and 5(b).Figure 5
Location sharing overhead, (a)n=∞; (b) n=3.
(a)(b)Case ofn=∞. When using AES128, RSA1024, and DSA1024, the average overhead is 2.43 ms. While using AES256, RSA2048, and DSA2048, it is 5.25 ms.Case of0≤n≤N. The computational overheads increase to 25.35 ms and 28.07 ms, respectively. Most of the overhead is used to calculate six order-preserving encryption, which is about 22.70 ms. In this case, the computational overhead of our scheme is greater than that of [9] since we use order-preserving encryption with large ciphertext space, and [9] uses small ciphertext space. This is the time cost to improve security.(4) Location Extraction. There are also two cases for location extraction, and the simulation results are shown in Figures 6(a) and 6(b). Unlike location sharing, there is little difference in overheads between the two cases. When using AES128, RSA1024, and DSA1024, the average overheads are 3.67 ms and 4.16 ms, respectively. While using AES256, RSA2048, and DSA2048, they are 21.41 ms and 21.741 ms, respectively.Figure 6
Location extraction overhead, (a)n=∞; (b) n=3.
(a)(b)The above simulation shows that the computational overhead of the location record phase is within 10 ms, and the computational overheads of the location sharing and location extraction phases are both within 30 ms. Therefore, our improved BMPLS scheme is practical.


## 5.3.1. Security Analysis

We follow the definitions of [9] to analyze the security of the improved BMPLS scheme as follows:(1) Decentralization. One of the main advantages of blockchain is decentralization. The BMLS scheme uses blockchain to manage and store location information, so it inherits decentralization.(2) Untamperability. The unforgeability mentioned in [9] is just untamperability, which is another main property of blockchain. For the same reason as above, the BMLS scheme also inherits untamperability.(3) Confidentiality. In the improved BMPLS scheme, the only data that needs confidentiality protection is LDO’s location coordinate xj,yj. The scheme uses four different cryptographic techniques to protect it: hash function, symmetric encryption, order-preserving encryption, and hybrid encryption. Because the hash function cannot achieve indistinguishable security, the improved BMPLS scheme can only achieve confidentiality in the “all-or-nothing” sense, that is, prevent the adversary from recovering the location coordinates. We analyze the probability of a successful attack in different situations as follows:(1)
Getxj,yjfromLocHashj=Hashxj‖yj‖rj. Let k be the binary bit length of rj. According to the one-way property of the hash function, the probability that the adversary obtains xj‖yj from LocHashj is less than 2−k, even if he knows a small rectangular border. When k is large enough, such as k=160, the probability is negligible.(2)
Getxj,yjfromSymCihj=S‐EnckLDO,xj‖yj‖rj. Under the assumption that the symmetric encryption scheme ΠSE is secure, the probability that the adversary obtains xj‖yj from SymCihj is negligible.(3)
Getxk,ykfromresponse=S‐Enckses,xj‖yj‖rjPK‐EncpkLDR,kses. If the selected symmetric encryption scheme ΠSE and public-key encryption scheme ΠPKE are secure, then the probability that the adversary obtains xk,yk from S‐Enckses,xk‖yk‖rkPK‐EncpkLDR,kses is also negligible.(4)
Getxk,ykfromciphkx=OP‐EncopkLDO,xk;ciphky=OP‐EncopkLDO,yk. Similarly, if the selected order-preserving encryption scheme ΠOPE is secure, the probability of recovering the plaintext from the ciphertext is also negligible.Therefore, the probability that the adversary obtains the LDO’s location coordinatexj,yj is negligible, and the improved BMPLS scheme achieves confidentiality.(4) Multilevel Location Privacy Protection. Multilevel location privacy protection aims to ensure that the semitrusted LDR cannot reduce the rectangular border of the LDO’s location.Firstly, confidentiality guarantees that semitrusted LDR cannot obtain the exact location coordinates of LDO.Secondly, then-level rectangular border obtained by LDR is xmin,xmax,ymin,ymax, where xmin=i×2n×xsl, xmax=i+1×2n×xsl, ymin=j×2n×ysl, and ymax=j+1×2n×ysl. Requesting n-level rectangular borders at different times will get the same results, which will not help reduce the rectangular border. In addition, when n1<n2, the n1-level rectangular border must be included in the n2-level rectangular border. It is impossible to reduce the rectangular border by finding the intersection of the rectangular borders of different levels.Thirdly, because the order-preserving encryption algorithmOP‐Enc is a pseudorandom order-preserving function controlled by a key, as long as the ciphertext space is large enough, such as 2160, the probability of reversing ciphix (or ciphiy) from nodeix=Hashixiciphix (or nodeiy=Hashiyiciphiy) will be negligible. Therefore, the adversary’s probability of reducing the rectangular border by finding the coordinate ciphertext is negligible.Finally, thex-coordinate and y-coordinate are encrypted with different keys, so there is no order-preserving relationship between the ciphertext of the x-coordinate and the ciphertext of the y-coordinate. ciphkx<ciphiy (or ciphky>ciphiy) does not imply xk<yi (or xk>yi). It is impossible for the adversary to use ymin and ymax to narrow the range of xk. The same is true for yk.(5) Retrievability. Retrievability means that the LDO’s location coordinates can be retrieved effectively [9]. In the improved BMPLS scheme, the location coordinate xj,yj is stored in the blockchain via ciphertext SymCihj=S‐EnckLDO,xj‖yj‖rj. LDO knows the decryption key kLDO and can retrieve the location coordinate efficiently. On the other hand, in the location sharing phase, the LDO sends the location coordinate xk,yk to the LDR in the form of response=S‐Enckses,xk‖yk‖rkPK‐EncpkLDR,kses. LDR can use its decryption key skLDR to decrypt the location coordinate xk,yk. So, the improved BMPLS scheme achieves retrievability.(6) Verifiability. Verifiability means that LDR can use blockchain to verify whether the location information he gets is correct. The improved BMPLS scheme provides different verification methods in two cases:(1)
The trusted LDR firstly decrypts the location coordinates and random numberxk′yk′rk′ and calculates the hash value Hashxk′yk′rk′. Then, he extracts the hash value LocHashk corresponding to the coordinate from the blockchain and checks whether Hashxk′yk′rk′=LocHashk . The untamperability of the blockchain and the signature of the LDO ensure that LocHashk will not be tampered with, and the collision resistance of the hash function ensures that xk′yk′rk′ will not be replaced, so xk′,yk′ is correct.(2)
The semitrusted LDR gets the coordinates of a rectangular borderxmin,xmax,ymin,ymax, with their order-preserving ciphertext ciphid1x,ciphid2x,ciphid3y,ciphid4y, and then verifies it by the Merkle tree and comparing the order of the ciphertext. Similarly, the untamperability and the signature ensure that horTreeroot and verTreeroot will not be tampered with, and the collision resistance of the Merkle tree ensures that ciphid1x,ciphid2x,ciphid3y,andciphid4y are correct. Finally, the property of order-preserving encryption ensures that LDO’s location xk,yk is in the rectangular border xmin,xmax,ymin,ymax.The security comparison of related schemes is shown in Table2. It shows that our improved scheme has apparent advantages in security.


## 5.3.2. Performance Analysis

We perform performance simulations under the same environment in Section4. To ensure security, we set the ciphertext space of order-preserving encryption to be 2160, denoted as OPE 2160. Choose SHA, AES, RSA, and DSA as hash, symmetric encryption, public-key encryption, and digital signature algorithms. We simulate on two data scales, AES128 + RSA1024 + DSA1024 and AES256 + RSA2048 + DSA2048. We also use two hash functions, SHA256 and SHA512. Since the time cost of the hash function is very small, it has no significant impact on the simulation. The simulation results of each phase are as follows:(1) Initialization. For initialization, we simulated the partition level N from 8 to 15. The result is shown in Figure 3. When N  = 10, the LDO’s initialization time is only 3.87 seconds. Estimated with a step length of 10 meters, the visit region region is a rectangle with a side length of 10.24 kilometers in this case. When N  = 13, the LDO’s initialization time is 30.89 seconds. In this case, the visit region’s side length is 81.92 kilometers, which can meet the needs of most scenarios. When N  = 15, the initialization of the LDO takes 123.53 seconds. At this time, the side length of the visit region has been as long as 327.68 kilometers.Figure 3
Initialization overhead.The simulation shows that the initialization time is generally tens of seconds. Because each LDO only needs to be initialized once, this overhead is acceptable.(2) Location Record. We conducted eight simulations of location record generation, and the results are shown in Figure 4. In the case of OPE(2160), AES128, and DSA1024, the minimum overhead is 7.81 ms, the maximum is 8.17 ms, and the average is 8.00 ms. When the case of OPE(2160), AES256, and DSA2048, the minimum is 8.53 ms, the maximum is 9.05 ms, and the average is 8.78 ms. In both cases, the overheads of location record generation are very small.Figure 4
Record generation overhead.(3) Location Sharing. There are two cases of location sharing: n=∞ (trusted LDR) and 0≤n≤N (semitrusted LDR). The simulation results are shown in Figures 5(a) and 5(b).Figure 5
Location sharing overhead, (a)n=∞; (b) n=3.
(a)(b)Case ofn=∞. When using AES128, RSA1024, and DSA1024, the average overhead is 2.43 ms. While using AES256, RSA2048, and DSA2048, it is 5.25 ms.Case of0≤n≤N. The computational overheads increase to 25.35 ms and 28.07 ms, respectively. Most of the overhead is used to calculate six order-preserving encryption, which is about 22.70 ms. In this case, the computational overhead of our scheme is greater than that of [9] since we use order-preserving encryption with large ciphertext space, and [9] uses small ciphertext space. This is the time cost to improve security.(4) Location Extraction. There are also two cases for location extraction, and the simulation results are shown in Figures 6(a) and 6(b). Unlike location sharing, there is little difference in overheads between the two cases. When using AES128, RSA1024, and DSA1024, the average overheads are 3.67 ms and 4.16 ms, respectively. While using AES256, RSA2048, and DSA2048, they are 21.41 ms and 21.741 ms, respectively.Figure 6
Location extraction overhead, (a)n=∞; (b) n=3.
(a)(b)The above simulation shows that the computational overhead of the location record phase is within 10 ms, and the computational overheads of the location sharing and location extraction phases are both within 30 ms. Therefore, our improved BMPLS scheme is practical.


## 6. Conclusion

In the telecare medical information systems, patient location information is sensitive data that needs to be protected. Blockchain technology provides a new method for patient location privacy protection and secure sharing. Recently, Ji et al. [9] proposed a blockchain-based multilevel privacy-preserving location sharing (BMPLS) scheme for telecare medical information systems. In this paper, we show that Ji et al.’s BMPLS scheme does not achieve confidentiality and multilevel privacy-preserving. Using salting technology, we propose an improved BMPLS scheme to fix our attacks. We also optimized the BMLS scheme to make it correct and executable. Analysis shows that the improved BMPLS scheme achieves all security while maintaining its high performance. Our improved BMPLS scheme is currently based on the general blockchain, and we may further study the use of edge-of-thing blockchain to enhance system performance [2, 3]. For different scenarios, designing an applicable trust level management scheme is another future research direction.



---

*Source: 1926902-2022-01-18.xml*