# Lattice-Based Self-Enhancement Authorized Accessible Privacy Authentication for Cyber-Physical Systems

Authors: Jinhui Liu; Yong Yu; Houzhen Wang; Huanguo Zhang
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Healthcare cyber-physical system significantly facilitates healthcare services and patient treatment effectiveness by analyzing patients’ health information data conveniently. Nevertheless, it also develops the threats to the confidentiality of health information, patients’ privacy, and decidability of medical disputes. And, with the advances of quantum computing technology, most existing anonymous authentication schemes are becoming a growing threat to traditional cryptosystems. To address these problems, for healthcare cyber-physical systems, we propose a new lattice-based self-enhancement authorized accessible privacy authentication scheme by using a strong designated verifier double-authentication-preventing signature technique, called SEAPA. The SEAPA achieves three security and privacy requirements including unforgeability, anonymity for patients’ information, and self-enhancement for patients themselves. A detailed security proof shows our proposal achieves those required security goals. Finally, our construction is demonstrated by parameter analysis and performance evaluation to have reasonable efficiency.


---

## Body

## 1. Introduction

Cyber-physical system is an integration of computational resources, physical processes, and communication capabilities, which is a multidimensional complex system combined by sensors, embedded devices, and wireless links. The advances in medical sensors, cloud computing, Internet of things, and wireless sensor networks (WSN) have witnessed CPS a powerful candidate for healthcare applications [1–6]. For example, COVID-19 has been causing incalculable damage to human health, economy, and life, and it is worth noting that wireless medical sensor network plays an important role in China’s activity in resisting COVID-19. To provide a more convenient service and healthcare environment, a healthcare cyber-physical system (HCPS) is proposed [1]. Taking a patient at anywhere as an example, his privacy information can be collected by various sensors and then it can be sent to a third party cloud server. At the same time, doctors in a hospital can monitor the patient’s physical condition and give some prescriptions or suggestions. Although each aspect of HCPS has made a great progress, security and privacy of patients’ personal health information in HCPS have always been in the spotlight.In a general HCPS system model, there occur components, including the medical sensor node of the patient, data sink which can collect patient’s privacy information, and healthcare centers which have different hospitals, databases, and doctors. The system model of the healthcare cyber-physical system is shown in Figure1. It has advantages of remote consultation system and mobile senor system. On the one hand, the privacy information of patients can be collected in data sink and uploaded to database in corresponding hospitals. On the other hand, multiple remote doctors can provide some timely and accurate medical services by analyzing patients’ physiological data.Figure 1
A system model of HCPS.Although the HCPS system model provides convenience for the patients’ treatment, it still faces some defects and potential treatments. For instance, in our daily life, there exist some misbehavior patients who want to see a doctor and do not want doctors to know her (or his) disease characteristics completely. The patient tells some ambiguous assertion to two kinds of authorized physicians, so she has to sign a pair of colliding messages with the same personal information and some different assertions. If there exist some medical disputes between them, the patient’s misbehavior can be found. At present, all related digital signatures cannot provide a method to solve this problem and thus, we have to use another technique called double-authentication-preventing signature.In addition, “Sycamore” quantum computer from the United States and the “Nine Chapter” quantum computer designed by China have been an important milestone. Since classical cryptographic protocols in HCPS will be broken by malicious adversary using quantum computers, private information of patients used to diagnose disease will be let out, which will result in loss of property and life. Lattice-based signatures have two kinds of advantages. One is that the hardness of some average-case lattice hard problems is equivalent to that of NP hard problem; the other is that lattice-based signatures have high efficiency, because it is based on operations between matrix additions and multiplications.To realize these issues above, a novel privacy-preserving model for HCPS is established to allow patients to authorize privileges to different kinds of physicians located in the healthcare centers. Based on the model above, a self-enhancement postquantum secure privacy-preserving authentication scheme (SEAPA for short) in HCPS is proposed and it satisfies security requirements for patients. If the patient misbehaves, he (or she) will be punished by extracting his (or her) private keys. A rigorous security proof is shown that our proposed scheme is secure under the assumption of computational shortest integer solution problem in the random oracle model. Security proof and performance evaluation show that our scheme has reasonable efficiency for real applications.


## 2. Related Work

Digital signatures that provide message integrity, message authenticity, and nonrepudiation are publicly verifiable. However, in the HCPS model, the signed messages may infer signer’s health information which reflects emotions and life of patients. In our daily life, if these signatures of messages are publicly verified, it will reveal the patients’ personal health information and make some troubles for the patient. To solve these issues, Jakobsson et al. proposed an idea of designated verifier signature (DVS) that it convinces one, and only one (the designated verifier), to prove the validity of a signature [7]. Since the proposed DVS cannot resist an adversary to get the signature before it is obtained by the designated verifier, Jakobsson et al. also proposed a strong designated verifier signature (SDVS) [7]. As building blocks, DVSs are widely used in privacy-preserving security protocols such as cloud computing [8, 9], big data [10], Internet of things [11, 12], electronic voting systems [13, 14], and healthcare information systems [15, 16].A series of designated verifier signatures with particular functions were proposed [17–25]. For example, to solve the key management problem, Huang et al. proposed an identity-based SDVS [26]. To solve the key-escrow problem of identity-based SDVS, Chen et al. proposed a certificateless SDVS with nondelegatability [22]. In recent years, He et al. proposed a certificateless designated verifier proxy signature scheme for unmanned aerial vehicle networks [27]. Zheng et al. presented a practical quantum designated verifier signature scheme for E-voting applications [28]. However, those properties may not be desirable. Consider such a scenario that a patient wants to see a doctor, while in our daily life, there exist many misbehaved patients who do not want others to know her (or his) disease characteristics completely. The patient tells some ambiguous assertion to two kinds of authorized physicians, so he/she has to sign a pair of colliding messages with the same personal information and some different assertions. If there exist some medical disputes between them, the patient’s misbehavior can be found.There are three categories in our proposed HCPS including directly authorized physicians, indirectly authorized physicians, and unauthorized physicians. By a new designated verifier signature called a designated verifier double-authentication-preventing signature (DVDAPS), which is derived from a double-authentication-preventing signature (DAPS) and a designated verifier signature (DVS), it realizes three different privacy-preserving requirements. DVDAPS can be deterrable (or punishable) by extracting the patients’ secret keys of a signature on colliding messages if there exists a dispute. If patients’ secret keys are extracted, their personal health information will be revealed to anyone. The DVDAPS can be considered as an attack algorithm or as a self-enhancement digital signature scheme.


### 2.1. Motivations

In practice, a signer may maliciously sign the messages twice to spread inappropriate contents or even sell patents more than once to gain illegal profits. Such actions must be punished as the actions impact the security, reputation, and robustness of the entire system. However, to the best of our knowledge, current digital signatures cannot provide the property of punishability. To address this issue, a double-authentication-preventing signature (DAPS for short) can be used to realize the requirement with deterrability. However, one cannot employ the existing general DAPS to solve the confidentiality and identity privacy of patients’ personal health information in HCPS.


### 2.2. Contributions

In this paper, we give an affirmative answer to the above problem by introducing the first formal treatment for deterrability. We present a new deterrable digital signature, which is proven secure under a standard assumption on lattice, and then based on it, we realize a practical construction of DVDAPS in SEAPA. The major contributions of the paper are three-fold. Firstly, we give a formal definition of DVDAPS and propose the notions of unforgeability, anonymity, and self-enhancement in presence of attacks. Secondly, DVDAPS serves as the fundamental building blocks to offer the properties of privacy and deterrability simultaneously. To instantiate an efficient construction, we propose a secure construction under the assumption of lattice hard problems. Finally, we provide a concrete construction of SEAPA with performance evaluation.


### 2.3. Organization

In this paper, we propose a lattice-based self-enhancement authorized accessible privacy authentication scheme for HCPS. First, we introduce some notions, cryptographic primitives, and a security model of HCPS used in this paper. Second, we establish an authorized accessible privacy model for HCPS. Third, we present a concrete lattice-based privacy-preserving authentication scheme with properties of completeness, unforgeability, nontransferability, and extractability. Finally, we analyze our proposal from aspects of security and parameter settings.


## 2.1. Motivations

In practice, a signer may maliciously sign the messages twice to spread inappropriate contents or even sell patents more than once to gain illegal profits. Such actions must be punished as the actions impact the security, reputation, and robustness of the entire system. However, to the best of our knowledge, current digital signatures cannot provide the property of punishability. To address this issue, a double-authentication-preventing signature (DAPS for short) can be used to realize the requirement with deterrability. However, one cannot employ the existing general DAPS to solve the confidentiality and identity privacy of patients’ personal health information in HCPS.


## 2.2. Contributions

In this paper, we give an affirmative answer to the above problem by introducing the first formal treatment for deterrability. We present a new deterrable digital signature, which is proven secure under a standard assumption on lattice, and then based on it, we realize a practical construction of DVDAPS in SEAPA. The major contributions of the paper are three-fold. Firstly, we give a formal definition of DVDAPS and propose the notions of unforgeability, anonymity, and self-enhancement in presence of attacks. Secondly, DVDAPS serves as the fundamental building blocks to offer the properties of privacy and deterrability simultaneously. To instantiate an efficient construction, we propose a secure construction under the assumption of lattice hard problems. Finally, we provide a concrete construction of SEAPA with performance evaluation.


## 2.3. Organization

In this paper, we propose a lattice-based self-enhancement authorized accessible privacy authentication scheme for HCPS. First, we introduce some notions, cryptographic primitives, and a security model of HCPS used in this paper. Second, we establish an authorized accessible privacy model for HCPS. Third, we present a concrete lattice-based privacy-preserving authentication scheme with properties of completeness, unforgeability, nontransferability, and extractability. Finally, we analyze our proposal from aspects of security and parameter settings.


## 3. Preliminaries

### 3.1. Notations

For a setS, a←S indicates that a is selected randomly from the set S.Ring isℛ=ℤx/xn+1.Column vectora=a1⋮ak could be represented as a1;…;ak.a1=∑i=0n−1ai, a=∑i=0n−1ai2, and a∞=maxiai.For a full-rank integer lattice∧, the discrete distribution is(1)D∧,c,σ=e−v−c2/2σ2∑w∈Λ−v−c2/2σ2.Definition 1.
(R-SISq,β,m). Given m uniform elements ai∈Rq at random and let a=a1,…,am∈Rqm, find out a nonzero vector z∈Rm with norm z≤β such that(2)a⋅z=0∈Rq.
Note that in Ring-SIS, eachai∈Rq corresponds to n-related vectors ai∈ℤqn in SIS, where n is the degree of R over ℤ. Each zi∈R of a Ring-SIS solution corresponds to a block of n integers. That is to say, a∈ℤqm×m and z∈ℤm×m.


### 3.2. Ring-SIS Signature Scheme

Lyubashevsky’s signature scheme is given as follows [29].Secret key:S←−d,…,dm×mPublic key:A←Zqm×m, T←AS and H1:0,1∗⟶v:v∈−1,0,1m,v1≤κSign: given a messageμ, compute the following:(i)
y←Dσm(ii)
c←H1Ay,μ(iii)
z←Sc+y(iv)
Outputz,c with probability min Dσmz/MDSc,σmz,1, where M=O1Verify(i)
Accept iffz≤2σm and c=H1Az−Tc,μWe transform the signature scheme above to Ring-SIS signature scheme as follows:Secret key:s←R−d,dm, where let R−d,dm be −d,…,0,…,dm×mPublic key:a←Rqm, t←as and H:0,1∗⟶v:v∈R−1,1,v1≤κSign: given a messageμ, compute the following(i)
y←Dσm(ii)
c←Hay,μ(iii)
z←sc+y(iv)
Outputz,c with probability min Dσmz/MDSc,σmz,1, where M=O1Verify(i)
Accept iffz≤2σm and c=Haz−tc,μ


### 3.3. System Model Description

Our system model is illustrated in Figure2, which mainly includes three parts as follows. Healthcare providers are equipped with cloud servers, wireless transmission networks, and body area networks. The health information of a patient is transmitted to two different healthcare providers to different kinds of authorized physicians for accessing and making some medical treatments, respectively. There are two healthcare centers with healthcare providers A and B and the medical research institutions C, where Dr. Alice, Dr. Bob, and Dr. Eve are working in Hospital 1. Each of them have their cloud server. If a patient registers at Hospital 1, his (or her) health information will stored in the cloud server of the Hospital 1, while his health information will not be seen in Hospital 2 and Dr. Alice is one of his authorized physicians. Besides, for other purposes (e.g., research and medical consultation) in cooperation with Hospital 2 and research institutions C, Dr. Alice needs to generate two indistinguishable transcript simulations to Hospital 2 and research institutions C. In some cases, the patient may register at other hospitals with ambiguous assertion about his or her healthcare information; if there exists a medical dispute, the patient can traced.Figure 2
Our constructed HCPS system model.Remark 1.
If the patient does not register twice, our system model is correct directly and the purpose of the twice registration is to solve some medical disputes.


## 3.1. Notations

For a setS, a←S indicates that a is selected randomly from the set S.Ring isℛ=ℤx/xn+1.Column vectora=a1⋮ak could be represented as a1;…;ak.a1=∑i=0n−1ai, a=∑i=0n−1ai2, and a∞=maxiai.For a full-rank integer lattice∧, the discrete distribution is(1)D∧,c,σ=e−v−c2/2σ2∑w∈Λ−v−c2/2σ2.Definition 1.
(R-SISq,β,m). Given m uniform elements ai∈Rq at random and let a=a1,…,am∈Rqm, find out a nonzero vector z∈Rm with norm z≤β such that(2)a⋅z=0∈Rq.
Note that in Ring-SIS, eachai∈Rq corresponds to n-related vectors ai∈ℤqn in SIS, where n is the degree of R over ℤ. Each zi∈R of a Ring-SIS solution corresponds to a block of n integers. That is to say, a∈ℤqm×m and z∈ℤm×m.


## 3.2. Ring-SIS Signature Scheme

Lyubashevsky’s signature scheme is given as follows [29].Secret key:S←−d,…,dm×mPublic key:A←Zqm×m, T←AS and H1:0,1∗⟶v:v∈−1,0,1m,v1≤κSign: given a messageμ, compute the following:(i)
y←Dσm(ii)
c←H1Ay,μ(iii)
z←Sc+y(iv)
Outputz,c with probability min Dσmz/MDSc,σmz,1, where M=O1Verify(i)
Accept iffz≤2σm and c=H1Az−Tc,μWe transform the signature scheme above to Ring-SIS signature scheme as follows:Secret key:s←R−d,dm, where let R−d,dm be −d,…,0,…,dm×mPublic key:a←Rqm, t←as and H:0,1∗⟶v:v∈R−1,1,v1≤κSign: given a messageμ, compute the following(i)
y←Dσm(ii)
c←Hay,μ(iii)
z←sc+y(iv)
Outputz,c with probability min Dσmz/MDSc,σmz,1, where M=O1Verify(i)
Accept iffz≤2σm and c=Haz−tc,μ


## 3.3. System Model Description

Our system model is illustrated in Figure2, which mainly includes three parts as follows. Healthcare providers are equipped with cloud servers, wireless transmission networks, and body area networks. The health information of a patient is transmitted to two different healthcare providers to different kinds of authorized physicians for accessing and making some medical treatments, respectively. There are two healthcare centers with healthcare providers A and B and the medical research institutions C, where Dr. Alice, Dr. Bob, and Dr. Eve are working in Hospital 1. Each of them have their cloud server. If a patient registers at Hospital 1, his (or her) health information will stored in the cloud server of the Hospital 1, while his health information will not be seen in Hospital 2 and Dr. Alice is one of his authorized physicians. Besides, for other purposes (e.g., research and medical consultation) in cooperation with Hospital 2 and research institutions C, Dr. Alice needs to generate two indistinguishable transcript simulations to Hospital 2 and research institutions C. In some cases, the patient may register at other hospitals with ambiguous assertion about his or her healthcare information; if there exists a medical dispute, the patient can traced.Figure 2
Our constructed HCPS system model.Remark 1.
If the patient does not register twice, our system model is correct directly and the purpose of the twice registration is to solve some medical disputes.


## 4. Authorized Accessible Privacy Model

In this section, we introduce an authorized accessible privacy model for HCPS which includes a strong designated verifier double-authentication-preventing signature (SDVDAPS for short) and the corresponding security models.


### 4.1. Strong Designated Verifier Double-Authentication-Preventing Signatures

We provide a self-enhancement privacy-preserving authentication scheme based on a SDVDAPS to satisfy three security and privacy requirements in healthcare cyber-physical systems. Our SEAPA algorithm is described as follows:KeyGen: on inputting public parameters Param and security parameterκ, the algorithm outputs public-private keys PKA,SKA of a patient (Alice, for example) and public-private keys PKB,SKB and PKC,SKC of two designated physicians (Bob and Eve, for example) in two different hospitals.DVDAPSig: on inputting Alice’s colliding personal healthcare informationm0,p1andm0,p2, Alice’s secret key SKA, Bob’s public key SKB, and Eve’s public key PKC, the algorithm generates a signature σ1 on m0,p1 by using SKAand PKB and a signature σ2 on m0,p2 by using SKAand PKC.DVDAPVer: on inputting Alice’s colliding personal healthcare informationm0,p1andm0,p2, σ1,σ2, and PKA,SKB,and SKC, the algorithm outputs 0 which means reject or outputs 1 which means accept.Sim: the algorithm generates a signature onm0,p1 by using PKA,SKB,PKB of an authorized physician Bob in Hospital 1 and a signature on m0,p2 by using PKA,SKC,PKC of an authorized physician Bob in other hospitals which are indistinguishable from those produced by DVDAPSig m0,p1,SKA,PKB and DVDAPSig m0,p2,SKA,PKC, respectively.Extract: on inputting Alice’s colliding personal healthcare informationm0,p1andm0,p2 and a valid signature pair σ1,σ2, the algorithm could extract Alice’s secret key SKA.Remark 2.
If the patient does not register twice, the SDVDAPS will degenerate into a general designated verifier signature (DVS for short). Hence, we can get that our construction is correct directly:Correctness. We need the SEAPA to be correct which means that any honestly computed signature can be verified by directly authorized physicians. That is to say, for any κ>0, PKi,SKi← KeyGen 1κ for i=A,B,C and m0,pi∈ℳ for i=1,2, for δ1← DVDAPSig m0,p1,SKA,PKB and δ2← DVDAPSig m0,p2,SKA,PKC, it holds that(3)PrDVDAPVerm0,p1,σ1,PKA,SKB=1=1,PrDVDAPVerm0,p2,σ2,PKA,SKC=1=1.


### 4.2. Security Models

#### 4.2.1. Unforgeability

In the DVDAPS, unforgeability under chosen message attack is a basic security property, which means it is infeasible to produce a valid signature for any adversary who does not know secret keys of the signer. Then, we provide a formal description of existential unforgeability of the SEAPA.(1) Definition 1 (Unforgeability). Our construction SEAPA shows unforgeability under chosen message attack if any adversaryA could not win the following game.C constructs public/private key pairs PKi,SKi←Key Gen1κ for i=A,B,C, where κ is a security parameter and sends PKA,SKB and PKA,SKC to A, where A is the patient and B and C are corresponding authorized physicians in different hospitals, respectively.A queries the signing oracle qs1 times for the message m0,pi1 and qs2 times for the message m0,pi2, respectively.C answers A’s queries by(4)σi1=DVDAPSignPKA,SKA,PKB,m0,pi1,and(5)σi2=DVDAPSignPKA,SKA,PKC,m0,pi2,respectively.Finally,A is successful if he outputs two new signatures σ1∗ and σ2∗ for message m0,μ∗.For running the above games in timet, the SEAPA shows t,ε unforgeability (EUF-CMA secure) if there exists a negligible function εκ>0 such that the following equation holds:(6)PrDVDAPVerSEAPA,AEUF−CMAm0,μ1∗,m0,μ2∗,σ1∗,σ2∗=1≤εκ.


#### 4.2.2. Anonymity for the Patient

Only the authorized physicians could generate an indistinguishable signature from the one that could be produced by the signer.(2). Definition 2 (Anonymity for the Patient). The SEAPA shows anonymity for the patient if the game is successful between a PPT adversary A and a distinguisher D as follows.C constructs public/private key pairs PKi,SKi←Key Gen1κ for i=A,B,C, where κ is a security parameter and sends public key pairs PKA,PKB and PKA,PKC to D, where A is the patient and B and C are corresponding physicians in different hospitals, respectively.D queries the signing oracle qs1 times for the message m0,pi1 and qs2 times for the message m0,pi2, respectively, where qs=maxqs1,qs2.C answers A’s query by(7)σi1=DVDAPSignPKA,SKA,PKB,m0,pi1,(8)σi2=DVDAPSignPKA,SKA,PKC,m0,pi2,respectively.D makes queries on new messages m0,p1∗ and m0,p2∗ to obtain corresponding challenging signatures σ1∗ and σ2∗.C tosses a coin b∈0,1. If b=0, C runs DVDAPSign algorithm and returns corresponding signatures:(9)σ1∗=DVDAPSignPKA,SKA,PKB,m0,p1∗,(10)σ2∗=DVDAPSignPKA,SKA,PKC,m0,p2∗,Else,C runs Sim algorithm and returns(11)σ1∗=SimPKA,PKB,SKA,m0,p1∗,(12)σ2∗=SimPKA,PKC,SKA,m0,p2∗,respectively.D is able to query other new messages except for m0,p1∗ and m0,p2∗ after receiving challenging signatures σ1∗ and σ2∗.Finally,D is successful if he outputs b′=b.For running the above games in timet, the construction SEAPA shows t,qs anonymity for the patient against a chosen message distinguisher if there exists a negligible function εκ>0 such that the following equation holds:(13)AdvDVDAPS,DNT−CMA=Prb′=b−12≤εκ.The security model of anonymity for the patient means that the probability of the signature produced by the DVDAPSign algorithm and theSim algorithm is the same.Extractability (or punishability) could be interpreted as Alice’s secret keys can be extracted if there exists a medical dispute between Bob and Eve. To some extent, extractability can be considered as a self-enhancement mechanism for the patient.(3). Definition 3 (Self-Enhancement for the Patient). A SEAPA provides self-enhancement for the patient, if for any PPT adversary A, there exists a negligible function εκ such that the following probability is negligible:(14)PrSKi,PKi←Key Gen1κfori=A,B,Cm0,p1,σ1←APKA,SKA,PKBm0,p2,σ2←APKA,SKA,PKCSK′≠SK,p1≠p2∧p1≠0,p2≠0∧SK′←Extractm0,p1,p2,σ1,σ2∧DVDAPVerm0,p1,δ1,PKA,SKB=1∧DVDAPVerm0,p2,δ2,PKA,SKC=1≤εκ.


## 4.1. Strong Designated Verifier Double-Authentication-Preventing Signatures

We provide a self-enhancement privacy-preserving authentication scheme based on a SDVDAPS to satisfy three security and privacy requirements in healthcare cyber-physical systems. Our SEAPA algorithm is described as follows:KeyGen: on inputting public parameters Param and security parameterκ, the algorithm outputs public-private keys PKA,SKA of a patient (Alice, for example) and public-private keys PKB,SKB and PKC,SKC of two designated physicians (Bob and Eve, for example) in two different hospitals.DVDAPSig: on inputting Alice’s colliding personal healthcare informationm0,p1andm0,p2, Alice’s secret key SKA, Bob’s public key SKB, and Eve’s public key PKC, the algorithm generates a signature σ1 on m0,p1 by using SKAand PKB and a signature σ2 on m0,p2 by using SKAand PKC.DVDAPVer: on inputting Alice’s colliding personal healthcare informationm0,p1andm0,p2, σ1,σ2, and PKA,SKB,and SKC, the algorithm outputs 0 which means reject or outputs 1 which means accept.Sim: the algorithm generates a signature onm0,p1 by using PKA,SKB,PKB of an authorized physician Bob in Hospital 1 and a signature on m0,p2 by using PKA,SKC,PKC of an authorized physician Bob in other hospitals which are indistinguishable from those produced by DVDAPSig m0,p1,SKA,PKB and DVDAPSig m0,p2,SKA,PKC, respectively.Extract: on inputting Alice’s colliding personal healthcare informationm0,p1andm0,p2 and a valid signature pair σ1,σ2, the algorithm could extract Alice’s secret key SKA.Remark 2.
If the patient does not register twice, the SDVDAPS will degenerate into a general designated verifier signature (DVS for short). Hence, we can get that our construction is correct directly:Correctness. We need the SEAPA to be correct which means that any honestly computed signature can be verified by directly authorized physicians. That is to say, for any κ>0, PKi,SKi← KeyGen 1κ for i=A,B,C and m0,pi∈ℳ for i=1,2, for δ1← DVDAPSig m0,p1,SKA,PKB and δ2← DVDAPSig m0,p2,SKA,PKC, it holds that(3)PrDVDAPVerm0,p1,σ1,PKA,SKB=1=1,PrDVDAPVerm0,p2,σ2,PKA,SKC=1=1.


## 4.2. Security Models

### 4.2.1. Unforgeability

In the DVDAPS, unforgeability under chosen message attack is a basic security property, which means it is infeasible to produce a valid signature for any adversary who does not know secret keys of the signer. Then, we provide a formal description of existential unforgeability of the SEAPA.(1) Definition 1 (Unforgeability). Our construction SEAPA shows unforgeability under chosen message attack if any adversaryA could not win the following game.C constructs public/private key pairs PKi,SKi←Key Gen1κ for i=A,B,C, where κ is a security parameter and sends PKA,SKB and PKA,SKC to A, where A is the patient and B and C are corresponding authorized physicians in different hospitals, respectively.A queries the signing oracle qs1 times for the message m0,pi1 and qs2 times for the message m0,pi2, respectively.C answers A’s queries by(4)σi1=DVDAPSignPKA,SKA,PKB,m0,pi1,and(5)σi2=DVDAPSignPKA,SKA,PKC,m0,pi2,respectively.Finally,A is successful if he outputs two new signatures σ1∗ and σ2∗ for message m0,μ∗.For running the above games in timet, the SEAPA shows t,ε unforgeability (EUF-CMA secure) if there exists a negligible function εκ>0 such that the following equation holds:(6)PrDVDAPVerSEAPA,AEUF−CMAm0,μ1∗,m0,μ2∗,σ1∗,σ2∗=1≤εκ.


### 4.2.2. Anonymity for the Patient

Only the authorized physicians could generate an indistinguishable signature from the one that could be produced by the signer.(2). Definition 2 (Anonymity for the Patient). The SEAPA shows anonymity for the patient if the game is successful between a PPT adversary A and a distinguisher D as follows.C constructs public/private key pairs PKi,SKi←Key Gen1κ for i=A,B,C, where κ is a security parameter and sends public key pairs PKA,PKB and PKA,PKC to D, where A is the patient and B and C are corresponding physicians in different hospitals, respectively.D queries the signing oracle qs1 times for the message m0,pi1 and qs2 times for the message m0,pi2, respectively, where qs=maxqs1,qs2.C answers A’s query by(7)σi1=DVDAPSignPKA,SKA,PKB,m0,pi1,(8)σi2=DVDAPSignPKA,SKA,PKC,m0,pi2,respectively.D makes queries on new messages m0,p1∗ and m0,p2∗ to obtain corresponding challenging signatures σ1∗ and σ2∗.C tosses a coin b∈0,1. If b=0, C runs DVDAPSign algorithm and returns corresponding signatures:(9)σ1∗=DVDAPSignPKA,SKA,PKB,m0,p1∗,(10)σ2∗=DVDAPSignPKA,SKA,PKC,m0,p2∗,Else,C runs Sim algorithm and returns(11)σ1∗=SimPKA,PKB,SKA,m0,p1∗,(12)σ2∗=SimPKA,PKC,SKA,m0,p2∗,respectively.D is able to query other new messages except for m0,p1∗ and m0,p2∗ after receiving challenging signatures σ1∗ and σ2∗.Finally,D is successful if he outputs b′=b.For running the above games in timet, the construction SEAPA shows t,qs anonymity for the patient against a chosen message distinguisher if there exists a negligible function εκ>0 such that the following equation holds:(13)AdvDVDAPS,DNT−CMA=Prb′=b−12≤εκ.The security model of anonymity for the patient means that the probability of the signature produced by the DVDAPSign algorithm and theSim algorithm is the same.Extractability (or punishability) could be interpreted as Alice’s secret keys can be extracted if there exists a medical dispute between Bob and Eve. To some extent, extractability can be considered as a self-enhancement mechanism for the patient.(3). Definition 3 (Self-Enhancement for the Patient). A SEAPA provides self-enhancement for the patient, if for any PPT adversary A, there exists a negligible function εκ such that the following probability is negligible:(14)PrSKi,PKi←Key Gen1κfori=A,B,Cm0,p1,σ1←APKA,SKA,PKBm0,p2,σ2←APKA,SKA,PKCSK′≠SK,p1≠p2∧p1≠0,p2≠0∧SK′←Extractm0,p1,p2,σ1,σ2∧DVDAPVerm0,p1,δ1,PKA,SKB=1∧DVDAPVerm0,p2,δ2,PKA,SKC=1≤εκ.


## 4.2.1. Unforgeability

In the DVDAPS, unforgeability under chosen message attack is a basic security property, which means it is infeasible to produce a valid signature for any adversary who does not know secret keys of the signer. Then, we provide a formal description of existential unforgeability of the SEAPA.(1) Definition 1 (Unforgeability). Our construction SEAPA shows unforgeability under chosen message attack if any adversaryA could not win the following game.C constructs public/private key pairs PKi,SKi←Key Gen1κ for i=A,B,C, where κ is a security parameter and sends PKA,SKB and PKA,SKC to A, where A is the patient and B and C are corresponding authorized physicians in different hospitals, respectively.A queries the signing oracle qs1 times for the message m0,pi1 and qs2 times for the message m0,pi2, respectively.C answers A’s queries by(4)σi1=DVDAPSignPKA,SKA,PKB,m0,pi1,and(5)σi2=DVDAPSignPKA,SKA,PKC,m0,pi2,respectively.Finally,A is successful if he outputs two new signatures σ1∗ and σ2∗ for message m0,μ∗.For running the above games in timet, the SEAPA shows t,ε unforgeability (EUF-CMA secure) if there exists a negligible function εκ>0 such that the following equation holds:(6)PrDVDAPVerSEAPA,AEUF−CMAm0,μ1∗,m0,μ2∗,σ1∗,σ2∗=1≤εκ.


## 4.2.2. Anonymity for the Patient

Only the authorized physicians could generate an indistinguishable signature from the one that could be produced by the signer.(2). Definition 2 (Anonymity for the Patient). The SEAPA shows anonymity for the patient if the game is successful between a PPT adversary A and a distinguisher D as follows.C constructs public/private key pairs PKi,SKi←Key Gen1κ for i=A,B,C, where κ is a security parameter and sends public key pairs PKA,PKB and PKA,PKC to D, where A is the patient and B and C are corresponding physicians in different hospitals, respectively.D queries the signing oracle qs1 times for the message m0,pi1 and qs2 times for the message m0,pi2, respectively, where qs=maxqs1,qs2.C answers A’s query by(7)σi1=DVDAPSignPKA,SKA,PKB,m0,pi1,(8)σi2=DVDAPSignPKA,SKA,PKC,m0,pi2,respectively.D makes queries on new messages m0,p1∗ and m0,p2∗ to obtain corresponding challenging signatures σ1∗ and σ2∗.C tosses a coin b∈0,1. If b=0, C runs DVDAPSign algorithm and returns corresponding signatures:(9)σ1∗=DVDAPSignPKA,SKA,PKB,m0,p1∗,(10)σ2∗=DVDAPSignPKA,SKA,PKC,m0,p2∗,Else,C runs Sim algorithm and returns(11)σ1∗=SimPKA,PKB,SKA,m0,p1∗,(12)σ2∗=SimPKA,PKC,SKA,m0,p2∗,respectively.D is able to query other new messages except for m0,p1∗ and m0,p2∗ after receiving challenging signatures σ1∗ and σ2∗.Finally,D is successful if he outputs b′=b.For running the above games in timet, the construction SEAPA shows t,qs anonymity for the patient against a chosen message distinguisher if there exists a negligible function εκ>0 such that the following equation holds:(13)AdvDVDAPS,DNT−CMA=Prb′=b−12≤εκ.The security model of anonymity for the patient means that the probability of the signature produced by the DVDAPSign algorithm and theSim algorithm is the same.Extractability (or punishability) could be interpreted as Alice’s secret keys can be extracted if there exists a medical dispute between Bob and Eve. To some extent, extractability can be considered as a self-enhancement mechanism for the patient.(3). Definition 3 (Self-Enhancement for the Patient). A SEAPA provides self-enhancement for the patient, if for any PPT adversary A, there exists a negligible function εκ such that the following probability is negligible:(14)PrSKi,PKi←Key Gen1κfori=A,B,Cm0,p1,σ1←APKA,SKA,PKBm0,p2,σ2←APKA,SKA,PKCSK′≠SK,p1≠p2∧p1≠0,p2≠0∧SK′←Extractm0,p1,p2,σ1,σ2∧DVDAPVerm0,p1,δ1,PKA,SKB=1∧DVDAPVerm0,p2,δ2,PKA,SKC=1≤εκ.


## 5. Our Lattice-Based SEAPA Construction

In this section, we will introduce our lattice-based SEAPA construction in detail. Our protocol consists of the following five phases.


### 5.1. KeyGen

si←R−d,dm for the patient A (name Alice) and directly authorized physicians B (name Bob) and C (name Eve) in different hospitals:(1)
a←Rqm, t←as, and cryptographically collision-resistant hash functions H:0,1∗⟶v:v∈R−1,1,v1≤ι.(2)
ComputeyA=aTsA,yB=asB, and yC=asC. Let a,H,d,m,R,ι be public parameters.(3)
Alice’s public/private pair isyA,sA, Bob’s public/private pair is yB,sB, and Eve’s public/private pair is yC,sC.


### 5.2. DVDAPSig

Given the colliding patient’s personal health informationm0,p1 and m0,p2 which can only be verified and recovered by B and C, respectively, Alice computes a signature σ1 on m0,p1 by using sA,yB and a signature σ2 on m0,p2 by using sA,yC in the following:(1)
r←Dσm(2)
ifr is irreversible, goto step 1(3)
y←Dσm(4)
c1←Hm0yBTy,p1(5)
c2←Hm0yCTy,p2(6)
Fori=1,2, compute(7)
zi←sAci+m0yr−1(8)
Outputzi,ci,r with probability min Dσmzi/MDsci,σmzi,1, where Mi=O1 and M  = max M1,M2(9)
Then, Alice sendsσ1=z1,c1,r to Bob and sends σ2=z2,c2,r to Eve


### 5.3. DVDAPVer

After receiving signatures, physicians Bob and Eve working in the different local healthcare providers do the following things respectively:(i)
Bob accepts iffz1≤2σm and c1=HsBTaz1−yAc1r,p1(ii)
Eve accepts iffz2≤2σm and c2=HsCTaz2−yAc2r,p2


### 5.4. Sim

(i)
SincesBTaz1r−yAc1r=sBTaz1′−sAc1′, Bob computes simulated signature σ1′=z1′,c1′,r, where z1′=z1r,c1′=c1r(ii)
SincesCTaz1r−yAc1r=sCTaz2′−yAc2′, Eve computes simulated signature σ2′=z2′,c2′,r


### 5.5. Extract

(i)
When there exists a medical dispute between authorized physicians and the patient, they provide their valid signaturez1,c1,r and z2,c2,r to the public and anyone can compute the patient’s secret key sA=z1−z2/c1−c2.


## 5.1. KeyGen

si←R−d,dm for the patient A (name Alice) and directly authorized physicians B (name Bob) and C (name Eve) in different hospitals:(1)
a←Rqm, t←as, and cryptographically collision-resistant hash functions H:0,1∗⟶v:v∈R−1,1,v1≤ι.(2)
ComputeyA=aTsA,yB=asB, and yC=asC. Let a,H,d,m,R,ι be public parameters.(3)
Alice’s public/private pair isyA,sA, Bob’s public/private pair is yB,sB, and Eve’s public/private pair is yC,sC.


## 5.2. DVDAPSig

Given the colliding patient’s personal health informationm0,p1 and m0,p2 which can only be verified and recovered by B and C, respectively, Alice computes a signature σ1 on m0,p1 by using sA,yB and a signature σ2 on m0,p2 by using sA,yC in the following:(1)
r←Dσm(2)
ifr is irreversible, goto step 1(3)
y←Dσm(4)
c1←Hm0yBTy,p1(5)
c2←Hm0yCTy,p2(6)
Fori=1,2, compute(7)
zi←sAci+m0yr−1(8)
Outputzi,ci,r with probability min Dσmzi/MDsci,σmzi,1, where Mi=O1 and M  = max M1,M2(9)
Then, Alice sendsσ1=z1,c1,r to Bob and sends σ2=z2,c2,r to Eve


## 5.3. DVDAPVer

After receiving signatures, physicians Bob and Eve working in the different local healthcare providers do the following things respectively:(i)
Bob accepts iffz1≤2σm and c1=HsBTaz1−yAc1r,p1(ii)
Eve accepts iffz2≤2σm and c2=HsCTaz2−yAc2r,p2


## 5.4. Sim

(i)
SincesBTaz1r−yAc1r=sBTaz1′−sAc1′, Bob computes simulated signature σ1′=z1′,c1′,r, where z1′=z1r,c1′=c1r(ii)
SincesCTaz1r−yAc1r=sCTaz2′−yAc2′, Eve computes simulated signature σ2′=z2′,c2′,r


## 5.5. Extract

(i)
When there exists a medical dispute between authorized physicians and the patient, they provide their valid signaturez1,c1,r and z2,c2,r to the public and anyone can compute the patient’s secret key sA=z1−z2/c1−c2.


## 6. Security Proof

In this section, we use the random oracle model to prove the security of our proposed scheme based on the security model of SEAPA.Theorem 1.
The proposed SEAPA is correct.Proof.
Fori=B,j=1 and i=C,j=2, the correctness is given as follows:(15)siTazj−yAcjr=siTasAcj+m0yr−1−yAcjr=siTasAcj+m0siTayr−1−siTayAcjr=yiTym0.
Hence, it follows that(16)HyBTym0,p1=c1=HsBTaz1−yAc1r,p1,(17)HyCTym0,p2=c2=HsCTaz2−yAc2r,p2.Theorem 2.
The proposed SEAPA is unforgeable against chosen message attack under the hardness of the Ring-SIS.Proof.
Suppose that a PPT adversaryA is able to produce a valid signature σ∗=z1∗,c1∗,z2∗,c2∗,r∗. According to EUF-CMA game, σ∗ can be correctly verified which means that A can compute the following equation.
Fori=B,j=1 and i=C,j=2,(18)siTazj∗−yAcj∗r∗r−∗−yiTzj∗=−siTyAcj∗modq=−yiTsAcj∗modq.
LetX=−yiTsAcj∗ mod q. If sAcj∗≤β, A obtains a solution for Ring-SIS problem.
If an adversaryA could obtain a valid SEAPA signature by EUF-CMA game in time t, he can solve the Ring-SIS problem in polynomial time. Hence, we have(19)PrDVDAPVerSEAPA,AEUF−CMAm0,μ1∗,m0,μ2∗,σ1∗,σ2∗=1=PrX=−yiTsAcj∗:sAcj∗≤β≤εκ.Theorem 3.
The proposed SEAPA shows anonymity for the patient.Proof.
According to the proposed scheme, anonymity for the patient means that any valid signature on a message produced by the Sim algorithm in SEAPA is indistinguishable from the signature produced by the DVDAPSign algorithm. That is to say, the probability of the signature produced by the two algorithms are the same.
Letσ¯=z¯1,c¯1,z¯2,c¯2,r¯ be a valid signature, and some signatures are chosen randomly from the set of DVDAPS. The probability of the signature σ=z1,c1,r produced by the DVDAPSign is given by(20)Prr←Dσm,y←Dσm,σ¯=σ:c1←Hm0yBTy,p1z1←sAc1+m0yr−1=1γmγm−1.
For randomly selectedy′←Dσm, the signature σ′=z1′,v,c1′,r produced by the Sim is given by(21)Prz1′,c1′←Dσm,σ¯=σ′:c1←HsBTaz1′−yAc1′,p1z1=z1′r−1=1γmγm−1.
In a similar way,(22)Prr←Dσm,y←Dσm,σ¯=σ:c2←Hm0yCTy,p2z2←sAc2+m0yr−1,Prz2′,c2′←Dσm,σ¯=σ′:c2←HsCTaz2′−yAc2′,p2z2=z2′r−1.
Therefore,(23)AdvSEAPA,D=Prb′=b−12≤εκ.
That is, the proposed SEAPA scheme shows anonymity for the patient.Theorem 4.
The proposed SEAPA scheme shows self-enhancement for the patient.Proof.
It is easy to verify the extractability from the algorithm Extract based on Theorem1. So, if the signature private keys are important for her, she will not make some ambiguous assertions which means that there does not exist colliding personal health information m0,p1 and m0,p2; that is to say, p1=p2. To some extent, there will not occur some medical disputes. Hence, our proposed scheme shows self-enhancement for the patient.
By going through the criteria of Wang et al., Hussain et al., and Bonneau et al. [30–32], we propose some major categories that our scheme satisfies as shown in Table 1, where “Must Have” category is related to providing robust security, “May or May Not Have” category is dealing with user experience, and “Nice to Have” category has one criterion related to user experience which is sound repairability while the other is related to security. Besides these criteria, our scheme also satisfies postquantum security.Table 1
Criterion categorization.
CriterionCategoryC1-No verifier tableMust haveC2-Password friendlyMust HaveC3-No password exposureMust HaveC4-No smart card loss attackMust HaveC5-Resistance to known attacksMust HaveC7-Provision of key agreementMust HaveC10-Mutual authenticationMust HaveC11-User anonymityMust HaveC6-Sound repairabilityNice to HaveC12-Forward secrecyNice to HaveC8-No clock synchronizationNice to HaveC9-Timely typo detectionMay or May Not Have


## 7. Concrete Parameters Analysis

### 7.1. Communication Cost

In our SEAPA scheme, we set up some parametersq,n,m,η,Φ,d,β,andγ for postquantum computational security [33]. The security of our scheme is based on the hardness of the Ring-SISq,n,d,m,β problem. In the scheme, we set m=2n and 4dβ≤q, and the Ring-SISq,n,d,m problem can reduce to ℓ2−Ring-SISq,n,d,m,β. The definition of its parameters are listed in Table 2.Table 2
Parameter size in the SEAPA scheme.
n5125121024m102410242048q2242338380417d1311k102410242048κ s.t. 2κnκ≥2100141414σ≈12⋅d⋅κ⋅m53761666565376M≈exp12dκm/σ+dκm/2σ22.722.722.72Size of signature≈2mlog12σ bits330004110082200Size of secret key≈2m2log2d+1 bits220.5222.5223.7Size of public key≈1/2m2logq bits221.5222225.5From Table2, we can see that the signature size of the SEAPA scheme is about 4 KB, 5 KB, and 10 KB for different parameters, respectively.


### 7.2. Computational Cost

We execute our algorithms on Intel Core i7-4710 processor with 12 GB memory and Ubuntu Linux operating system. Some important cryptographic operations are implemented with NFLlib, which is a NTT-based fast lattice library. By statistics, these important algorithm operations mainly consist of one polynomial addition, one polynomial multiplication, and one polynomial Gaussian. Since the implementation of any hash function is not included in NFLlib, we test the running time of the hash function by a HMAC based on SM3 algorithm. The execution time of each cryptographic operation is shown in Table3.Table 3
The cryptographic operation time in the SEAPA scheme (microseconds).
nqmPoly additionPoly subtractionPoly multiplicationPoly GaussianHash function860160.004560.002500.003330.002430.105128142160.003350.002300.002430.002620.110010246020480.002480.003690.002270.002560.1758192124163840.004540.004750.006520.004740.17732768124655360.01200.01200.026780.03750.287We use KG, Sig, Ver, Sim, and Ext to represent the five algorithms KeyGen, DVDAPSig, DVDAPVer, Sim, and Extract, respectively. The degree of polynomial we choose is 8, 128, 1024, 8192, and 32768, and the corresponding size of integer ring is 14 bits, 60 bits, 124 bits, and 124 bits. So the total running time of our algorithm for different parameters is about 0.096711 ms in keygen phase, 0.076315 ms in signature phase, 0.078821 ms in simulation phase, 0.184251 ms in extraction phase, and 0.784562 ms in verification phase. The execution result is depicted in Figure3.Figure 3
Time cost of each algorithm in SEAPA.


## 7.1. Communication Cost

In our SEAPA scheme, we set up some parametersq,n,m,η,Φ,d,β,andγ for postquantum computational security [33]. The security of our scheme is based on the hardness of the Ring-SISq,n,d,m,β problem. In the scheme, we set m=2n and 4dβ≤q, and the Ring-SISq,n,d,m problem can reduce to ℓ2−Ring-SISq,n,d,m,β. The definition of its parameters are listed in Table 2.Table 2
Parameter size in the SEAPA scheme.
n5125121024m102410242048q2242338380417d1311k102410242048κ s.t. 2κnκ≥2100141414σ≈12⋅d⋅κ⋅m53761666565376M≈exp12dκm/σ+dκm/2σ22.722.722.72Size of signature≈2mlog12σ bits330004110082200Size of secret key≈2m2log2d+1 bits220.5222.5223.7Size of public key≈1/2m2logq bits221.5222225.5From Table2, we can see that the signature size of the SEAPA scheme is about 4 KB, 5 KB, and 10 KB for different parameters, respectively.


## 7.2. Computational Cost

We execute our algorithms on Intel Core i7-4710 processor with 12 GB memory and Ubuntu Linux operating system. Some important cryptographic operations are implemented with NFLlib, which is a NTT-based fast lattice library. By statistics, these important algorithm operations mainly consist of one polynomial addition, one polynomial multiplication, and one polynomial Gaussian. Since the implementation of any hash function is not included in NFLlib, we test the running time of the hash function by a HMAC based on SM3 algorithm. The execution time of each cryptographic operation is shown in Table3.Table 3
The cryptographic operation time in the SEAPA scheme (microseconds).
nqmPoly additionPoly subtractionPoly multiplicationPoly GaussianHash function860160.004560.002500.003330.002430.105128142160.003350.002300.002430.002620.110010246020480.002480.003690.002270.002560.1758192124163840.004540.004750.006520.004740.17732768124655360.01200.01200.026780.03750.287We use KG, Sig, Ver, Sim, and Ext to represent the five algorithms KeyGen, DVDAPSig, DVDAPVer, Sim, and Extract, respectively. The degree of polynomial we choose is 8, 128, 1024, 8192, and 32768, and the corresponding size of integer ring is 14 bits, 60 bits, 124 bits, and 124 bits. So the total running time of our algorithm for different parameters is about 0.096711 ms in keygen phase, 0.076315 ms in signature phase, 0.078821 ms in simulation phase, 0.184251 ms in extraction phase, and 0.784562 ms in verification phase. The execution result is depicted in Figure3.Figure 3
Time cost of each algorithm in SEAPA.


## 8. Conclusion and Future Work

In this paper, we presented an authorized accessible privacy model and provided a concept of the patient self-enhancement privacy-preserving authentication scheme. Our construction is derived from strong designated verifier signatures and double-authentication-preventing signatures based on lattice. Security proof shows that our construction satisfies different levels of security requirements in the HCPS system model. Concrete parameters analysis and performance evaluation demonstrated that our construction has reasonable efficiency for real applications. In future work, on the basis of lattice-based strong designated verifier signatures, we will provide some comparisons on the concrete parameters and the communication cost.



---

*Source: 8995704-2022-02-09.xml*