Provably Secure Linearly Homomorphic Aggregate Signature Scheme for Electronic Healthcare System

Abstract

In recent years, deploying Internet of Things (IoT) in electronic healthcare systems (EHS) has made great progress in healthcare detection. It is extremely important to reduce the cost of communication and ensure the authenticity and integrity of data. A linearly homomorphic signature scheme can solve the above problems. However, when the scale of EHS is too large, the transmission, storage and verification of signatures need a high cost. An aggregate signature can combine many signatures generated by many different users into a short one. Therefore, only one aggregate signature needs to be processed during verification, transmission and storage. Combining the advantages of aggregate signature and linearly homomorphic signature, this paper proposes an aggregate signature scheme based on a linearly homomorphic signature for EHS, which has both linear homomorphism and aggregation, and realizes double data compression. Moreover, our scheme can resist a potential real attack, named a coalition attack. The security of this scheme is rigorously demonstrated based on the computational Diffie–Hellman assumption in the random oracle model.

1. Introduction

Recently, the vigorous development of IoT has brought more and more convenience to our daily life. The typical IoT technology connects intelligent devices such as sensors, mobile terminals and intelligent facilities to the network through wireless or wired means. The application of IoT technology in medical treatment makes the intelligent electronic healthcare system possible. The EHS using IoT technology breaks through the limitation of time and place. Patients can get medical advice through IoT network at anytime and anywhere. The sensors are deployed on the patient, collect various medical data of the patient, such as blood pressure, temperature, pulse, PH value, etc., and transmit these data to Medical-Server through the IoT network instantly. Medical Staff judge the patient’s status according to the received data and provide the best medical advice. The Medical Staff can provide the best treatment for patients as soon as possible without a face-to-face with patients.

In order to obtain the information about patients as soon as possible so that Medical Staff can provide the best treatment suggestions to patients soon enough, it is extremely important to reduce the cost of communication. The network coding method proposed by Ahlswede et al. in 2000 is an effective technology for reducing the cost of communication and improving the robustness and fault tolerance [1]. Although network coding has many advantages compared with traditional routing, it is also vulnerable to the pollution attack. If the data are polluted, the paths of the data packet will be polluted, and the destination node cannot correctly parse the original data. To a certain extent, the transmission of the polluted data packets to the Medical-Server will result in the waste of medical resources.

At present, in order to solve the problem of pollution attacks, a large number of researchers have put forward many solutions. According to different research methods, it can be divided into three categories: network-based error correction code, information theory and cryptography. Cryptographic methods are employed most extensively. Most of the cryptography methods use a linearly homomorphic signature, so that both the intermediate node and the destination node can detect whether the malicious information exists. The intermediate node can also discard the polluted data packets, which greatly reduces the waste of resources in the communication process. Previously, many linearly homomorphic signature schemes were proposed in [2,3,4,5,6,7,8]. However, most of the existing linearly homomorphic signature schemes, when the scale of the medical system is too large, not only need to pay high transmission and storage costs, but also need to verify each signature from the users one by one. In the real world, if a Medical-Server verifies the signature sent by each patient one by one, it will inevitably increase the burden of the Medical-Server and reduce the efficiency of medical services to a certain extent.

In order to tackle the above issues, we propose an aggregate signature scheme based on a linearly homomorphic signature proposed by Boneh et al. [3]. The homomorphic signature can be used for data compression. An aggregate signature can compress multiple signatures generated by different users on different messages into a short one, which has great advantages in reducing bandwidth and storage cost. Combining the advantages of the linearly homomorphic signature scheme and the aggregate signature scheme, our scheme has good properties and can realize double data compression. The Medical-Server can verify the validity of the multiple patient-generated signature by verifying only one aggregate signature, so as to improve the efficiency of medical services. However, there is a potentially powerful attack in the aggregate signature scheme, the coalition attack, which may destroy the authenticity and integrity of the aggregate signature. A coalition attack means that some signers use a set of single signatures, including at least one invalid single signature, which can generate a valid aggregate signature. Therefore, considering the influence of the above situations, we propose an aggregate signature scheme based on a linear homomorphic signature scheme which can resist a coalition attack for EHS.

1.1. Related Work

With the development of IoT technology, more and more electronic healthcare systems apply this technology, which makes wireless smart healthcare treatment possible. At present, many various electronic healthcare systems have been proposed [9,10,11,12,13,14,15,16,17,18]. A typical EHS model is shown in Figure 1. No matter where the patient is or who has deployed the sensors, the patient can forward collected medical data to the Medical-Server with the aim of obtaining medical suggestions in time. In order to obtain the best treatment time, it is very important to reduce the cost of communication and ensure the security of medical data.

The concept of the homomorphic signature was proposed by Johnson et al. in CT-RSA 2002 [2]. With the further study of the linearly homomorphic signature [4,5,19,20], it is found that the linearly homomorphic signature can be used to address the above problems. In Boneh et al.’s scheme [3], the signature on any vector of a linear combination of the basis vectors for a linear subspace V can be publicly derived by the signatures on those basis vectors. That is to say, once receiving the signatures on a set of basis vectors for V and the corresponding linear coefficients, a signature on any vector of V can be computed. Attrapadung et al. presented a homomorphic network coding signature scheme in the standard model [6]. A homomorphic subspace signature for network coding was introduced by Cheng et al. [7]. Then, Chang et al. first described the definition and security model of a certificateless homomorphic signature (CLHS) and proposed a CLHS scheme for network coding [8]. Subsequently, many researchers applied a linearly homomorphic signature to the electronic healthcare system which was deployed with the IoT. Li et al. proposed a lightweight certificateless linearly homomorphic network coding signature scheme for EHS [9] which required a relatively low computational cost to sign and verify data packets. However, when the scale of the EHS is too large, the Medical-Server needs to verify the message signature from each patient one by one, which will inevitably increase the storage cost and bandwidth burden of the EHS.

In 2003, the conception of the aggregate signature was introduced by Boneh et al. [21]. The aggregate signature can compress multiple signatures generated by different users on different messages into a single short aggregate signature. Hence, it is useful in reducing storage cost and bandwidth, and can be an important primitive to improve the efficiency of EHS. Many researchers are interested in designing efficient and secure aggregate signature schemes. Many aggregate signature schemes have been put forward, such as aggregate signature schemes in public key infrastructures [22,23], identity-based aggregate signature schemes [24,25,26], certificateless aggregate signature schemes [27,28,29] and certificate-based aggregate signature schemes [30,31]. Many aggregate signature schemes have been used in the IoT, such as the anonymous traceable aggregate signature scheme proposed by Li et al. [32]. Unfortunately, many of the existing aggregate signature schemes can not resist coalition attacks, which can destroy the aggregate messages’ validity and integrity. In recent years, some aggregate signature schemes have been able to resist coalition attacks [13,33,34,35,36,37]. In 2020, a potential and realistic attack called fully chosen-key attacks was introduced by Wu et al. [37]. Meanwhile, they gave a certificateless aggregate signature scheme secure against these coalition attacks. Combining the advantages of linearly homomorphic signatures and aggregate signatures, many researchers proposed linearly homomorphic aggregate signature (LHAS) schemes in various cryptographic systems to realize double data compression. The diagram of the LHAS scheme is shown in Figure 2. The patients sign data to generate data packets, which are transmitted to the Aggregator-Server through the IoT network. Then the data packets are submitted to the verifier for verification.

To guarantee the security of multi-source network coding and secure sensor data aggregation, Zhang et al. proposed a homomorphic aggregate signature (HAS) scheme [38] which is secure under the lattice-based in homogeneous smallest integer solution assumption, and then Jing gives another lattice-based HAS scheme [39] which has a shorter signature length and high efficiency. This paper gives an LHAS scheme for EHS based on the linearly homomorphic signature described in [3]. This LHAS scheme holds both linearly homomorphic property and aggregate property, can achieve double data compression. One is that the linearly homomorphic signature can be used in data compression, and the other is the aggregation of homomorphic signatures can realize the batch validation for data integrity. So, the LHAS scheme is very helpful in batch verification for data integrity in IoT.

1.2. Our Contributions

The new deployment of IoT in electronic healthcare systems reduces the need for medical professionals and improves the efficiency of the diagnosis. In this system, it is very crucial to ensure the authenticity, integrity of medical data and transmit it to Medical Staff in real time. In the limited network throughput and computing efficiency, how to improve the transmission rate of medical data while ensuring the authenticity and integrity of data is an urgent problem to be solved. Therefore, we construct an LHAS scheme that can resist a coalition attack. The main contributions are as follows:

• A security model of the LHAS scheme is proposed. The security model guarantees an aggregate signature is valid if and only if all the individual signatures generating the aggregate signature are valid;
• An aggregate signature scheme based on a linearly homomorphic signature is proposed, which makes the scheme have both a linearly homomorphic property and an aggregate property, and realizes double data compression. The transmission efficiency is further improved and the storage cost of medical data in EHS is reduced.
• The security of our LHAS scheme is rigorously presented under the proposed security model. Moreover, through the analysis of comparative performance, we show that the scheme is effective in reducing transmission and storage overhead.

1.3. Organization

In the following section, we introduce the preliminaries demanded in this paper, including some basic notions such as bilinear pairing and complexity assumptions. Section 3 presents the definition and security model of the LHAS scheme. In Section 4, we give our LHAS scheme with a designated verifier, then in Section 5 we provide the detailed security analysis. We present the performance analysis in Section 6. Finally, Section 7 is the conclusion.

2. Preliminaries

This section revisits some basic notions required in this paper.

2.1. Bilinear Pairing

Let $\mathbb{G}$ and ${\mathbb{G}}_T$ be two multiplicative cyclic groups of the same prime order p, and let h be a generator in $\mathbb{G}$.

Definition 1.

If a map $\widehat{e}:\mathbb{G}\times \mathbb{G}\to {\mathbb{G}}_T$ satisfies the following properties, it is called a bilinear pairing:

• Bilinear: for all $\zeta ,\eta \in \mathbb{G}$ and $\iota ,\tau \in {\mathbb{Z}}_p^{*}$, $\widehat{e}({\zeta }^{\iota },{\eta }^{\tau })=\widehat{e}{(\zeta ,\eta )}^{\iota \tau }$.
• Non-degenerate: $\widehat{e}(h,h)\ne 1_T$, where $1_T$ is the identity element of ${\mathbb{G}}_T$.
• Computable: for all $\zeta ,\eta \in \mathbb{G}$, $\widehat{e}(\zeta ,\eta )$ is efficiently computable.

2.2. Complexity Assumptions

Definition 2.

Computational Diffie–Hellman problem (CDH problem): Given the elements $g,g^{\iota },g^{\tau }\in \mathbb{G}$, to compute $g^{\iota \tau }\in \mathbb{G}$.

The CDH assumption states that the CDH problem is hard, i.e., there is no probabilistic polynomial-time (PPT) algorithm that can solve the CDH problem.

3. Outline of Linearly Homomorphic Aggregate Signature Schemes

3.1. Definition of LHAS Schemes

A linearly homomorphic aggregate signature scheme consists of seven PPT algorithms: Setup, Key Extract, Sign, Combine, Verify, Agg and AggVerify which satisfy the following functionality:

• Setup: Given a security parameter k and output the system parameters $SP$;
• KeyExtract: Given the $SP$, output a public key $PK$ and a secret key $SK$. ($SP$ is the input to the following algorithms);
• Sign: Given a secret key $SK$, a file identifier $name\in {\{0,1\}}^k$, a vector ${\mathit{v}}_j\in {\mathbb{Z}}_p^N$, outputs a signature ${\sigma }_j$;
• Combine: Given a public key $PK$, a file identifier $name\in {\{0,1\}}^k$ and a set of tuples $\{({\beta }_j,{\sigma }_j),{\beta }_j\in {\mathbb{Z}}_p\}$, where ${\sigma }_j$ is the signature on vector ${\mathit{v}}_j$, outputs a signature $\sigma$ on the linear combination $\sum {\beta }_j{\mathit{v}}_j$ without knowledge of $SK$;
• Verify: Given a public key $PK$, a file identifier $name\in {\{0,1\}}^k$, a signature $\sigma$ and a vector $\mathit{y}\in {\mathbb{Z}}_p^N(\mathit{y}=\sum {\beta }_j{\mathit{v}}_j)$, outputs either 1 or 0 ($accept$ or $reject$);
• Agg: Given an aggregating subset of users $U\in \mathfrak{U}\left(\right|U|=l)$, and the signatures ${\sigma }_i$ on the linear combination ${\mathit{y}}_i=\sum {\beta }_{ij}{\mathit{v}}_{ij}$ ($i=1,\dots ,l$), outputs the aggregate signature;
• AggVerify: Given an aggregating subset U of l aggregating signers with their public keys, an aggregate signature on the vectors ${\mathit{y}}_i=\sum {\beta }_{ij}{\mathit{v}}_{ij}$ ($i=1,\dots ,l$) with file identifiers, where vectors ${\mathit{v}}_{i1},{\mathit{v}}_{i2},\dots ,{\mathit{v}}_{i{m}_i}$ is a set of basis of subspaces ${\mathit{V}}_i$ ($i=1,\dots ,l$), outputs $accept$ if the aggregate signature is valid, or $reject$ otherwise.

3.2. System Model of LHAS-EHS

The LHAS-EHS model we proposed mainly includes five components, i.e., Health-Center, User-Sensor, Combine-Node, Aggregator-Server and Medical-Server. Health-Center initializes the system and generates the various public parameters required. The sensor node, User-Sensor, deployed on the patient, is used as the source node of the EHS. The source node collects various data from patients and regards the collected medical data packet as a subspace V with the file identifier $name\in {\{0,1\}}^{*}$. The subspace is split into m vectors. The source node should sign the vector ${\mathit{v}}_j$ before sending the data packets to the next node. Let $\mathit{V}$=$\{{\mathit{v}}_1,{\mathit{v}}_2,\dots ,{\mathit{v}}_m\}$$\subset {\mathbb{F}}_p^N$ ($0<m<N$) denote the subspace with the file identifier $name\in {\{0,1\}}^{*}$, where ${\mathit{v}}_1,{\mathit{v}}_2,\dots ,{\mathit{v}}_m$ is any basis of V. Then, the User-Sensor loads the vector and its associated signature information into a data packet. The node sends data packets to the Combine-Node (such as router and repeater). The Combine-Node encodes the received data packets and combines them. Then, the Combine-Node forwards the merged data packets to the next node. When the Aggregator-Server receives a certain number of data packets, it generates an aggregate signature and randomly forwards the aggregate information to a destination Medical-Server, which may come from a different medical domain. (In order to ensure the sharing of medical data between Medical-Servers, blockchain technology can be considered to establish a medical alliance chain to ensure the information exchange between Medical-Servers and improve the efficiency.) Then, the Medical-Server checks the received aggregate signature’s validity and decodes the data packets. If the verification is passed, the medical staff will judge the patient’s physical state according to the received medical data and provide corresponding medical suggestions. Meanwhile, ensuring the security of the feedback path of medical suggestions is also a matter of concern. If necessary, we can use a classical signature scheme to solve this problem, such as the BLS signature scheme [40]. The LHAS-EHS system model is shown in Figure 3.

• Health-Center: The Health-Center generates the system public parameters by running the algorithm Setup. In the initialization phase, it generates the required public-private key pairs for User-Sensor and Medical-Server;
• User-Sensor: The User-Sensor as the source node connects the patient’s body to obtain various medical information. It is a resource-limited device, which belongs to a care district. The node divides the collected data packet into m vectors and signs them. Then, the node loads vectors and related signature information into a data packet. After processing the collected data, the node sends data packets to the neighbor nodes, the Combine-Node;
• Combine-Node: The nodes combine all data packets and the corresponding signatures with the coding coefficient. Then, the nodes forward merged data packet to the Aggregator-Server;
• Aggregator-Server: A device that is honest but curious and has certain calculation and communication capabilities. The device can randomly obtain a Medical-Server’s public key, collect and aggregate a set of the merged data packets. Finally, send the generated aggregate signature to the destination Medical-Server;
• Medical-Server: A device that has strong computing power and storage space can process all medical data collected by the User-Sensors. The device works as a designated verifier who can verify the aggregate signature using its secret key. If the aggregate signature can pass the verification, the Medical-Server provides the patients’ data information to the medical staff. Then, the medical staff will provide corresponding medical suggestions to patients according to the data received.

3.3. Security Model

Obviously, the goal of an adversary is the existential forgery of an aggregate signature. A linearly homomorphic aggregate signature scheme is secure if the following conditions are satisfied:

-

The basic signature scheme involved is existentially unforgeable against adaptive chosen message attacks (EUF-CMA secure);

-

The security of aggregate algorithm should stand up against all kinds of coalition attacks.

A detailed instruction for the basic linearly homomorphic signature scheme’s security model was provided in [3], so we mainly focus on the security of the aggregation algorithm. An adversary’s purpose is to use a set of individual single signatures with at least one invalid single signature to forge a valid aggregate signature. The security model is similar to the one in [13], the adversary can access relevant oracles to obtain all signer’s secret keys. Now we revisit the security model in [13] through the following game between an adversary $\mathcal{A}$ and a challenger $\mathcal{B}$. The game consists of three steps: Setup, Queries and Forge.

• Setup: When inputting the security parameter k, the challenger $\mathcal{B}$ generates the system parameters $SP$. Furthermore, $\mathcal{B}$ randomly generates the public-secret key pair $(P{K}_{ver},S{K}_{ver})$ for a designated verifier, then $\mathcal{B}$ gives $\mathcal{A}$ the $SP$ and $P{K}_{ver}$;
• Queries:$\mathcal{A}$ can access the following queries:

  –

  Secret key request query${\mathcal{O}}_{SK}\left(u_i\right)$: $\mathcal{A}$ requests such a query, $\mathcal{B}$ generates the key pairs $(P{K}_{u_i},S{K}_{u_i})$ by running the algorithm Key Extract, then returns $S{K}_{u_i}$ to $\mathcal{A}$;

  –

  AggVerify request query${\mathcal{O}}_{AggV}\left(\right\{SP,u_i,P{K}_{u_i},{\mathit{V}}_i,{\beta }_j^i,$$i=1,\dots ,l\},\sigma )$: On receiving such a query, $\mathcal{B}$ responds whether $\sigma$ is valid by running algorithm AggVerify. Where subspace ${\mathit{V}}_i$ is depicted as a set of basis vectors ${\mathit{v}}_1^i,{\mathit{v}}_2^i,\dots ,{\mathit{v}}_{m_i}^i$, $i=1,\dots ,l$;

• Forge: Finally, $\mathcal{A}$ outputs its forgery $(\{u_i,{\mathit{V}}_i,{\beta }_j^i,{\sigma }_j^i,i=1,\dots ,l\},{\sigma }^{*}).$

If the following two conditions are satisfied, $\mathcal{A}$ will win the game:

-

The aggregate signature ${\sigma }^{*}$ is valid;

-

At least one single signature is invalid.

4. The Linearly Homomorphic Aggregate Signature Scheme

In this section, we adopt the homomorphic signature scheme [3] as the basis for constructing our LHAS scheme. Our scheme can guarantee that if the aggregate signature is valid then all signers involved in the Aggregate algorithm signed the corresponding message correctly. The LHAS scheme consists of seven algorithms: Sign, KeyExtract, Combine, Verify, Agg and AggVerify.

• Setup: Given a security parameter k, Health-Center runs this algorithm:

  –

  Generate a bilinear group $(\mathbb{G},{\mathbb{G}}_T,p,\widehat{e})$, where $p>2^k$. $\mathbb{G},{\mathbb{G}}_T$ are two multiplicative cyclic groups with the same prime order p;

  –

  Generate a generator h in $\mathbb{G}$;

  –

  Let $H:{\{0,1\}}^{*}\to \mathbb{G}$ and $H_0:{\{0,1\}}^{*}\to {\mathbb{Z}}_p^{*}$ be two collision resistant hash functions.

  The system parameters $SP=\{\mathbb{G},{\mathbb{G}}_T,p,\widehat{e},h,H,H_0,N\}$, where N is the maximum dimension of a subspace.
• KeyExtract: A specific User-Sensor picks $\alpha \in {\mathbb{Z}}_p^{*}$ randomly, then computes $u=h^{\alpha }\in \mathbb{G}$. The sensor’s public-secret key pair is $(PK,SK)=(u,\alpha )$;
• Sign: For a specific User-Sensor with the secret key $\alpha$, the node first divides the collected medical data into m packets, where each packet can be regarded as a m-dimensional vector ${\mathit{v}}_j$=$(v_{j1},v_{j2},\dots ,v_{jN})\in {\mathbb{Z}}_p^N,j=1,2,\dots ,m$. Let $\mathit{V}$=$\{{\mathit{v}}_1,{\mathit{v}}_2,\dots ,{\mathit{v}}_m\}$$\subset {\mathbb{F}}_p^N$ ($0<m<N$) denote the subspace with the file identifier $name\in {\{0,1\}}^{*}$, where ${\mathit{v}}_1,{\mathit{v}}_2,\dots ,{\mathit{v}}_m$ is any basis of $\mathit{V}$. Then the node can compute the signature ${\sigma }_j$ as the following:

  $${\sigma }_j={\left({\Pi }_{i=1}^{N}H{(name,i)}^{v_{ji}}\right)}^{\alpha };$$
• Combine: Given a specific User-Sensor with the public key $PK$, a file identifier $name$ and $\{({\beta }_j,{\sigma }_j),{\beta }_j\in {\mathbb{Z}}_p,j=1,\dots ,m\}$, where ${\beta }_j$ is the coefficient and ${\sigma }_j$ is the signature on vector ${\mathbf{v}}_j$, then the Combine-Node computes:

  $$\sigma ={\Pi }_{j=1}^m{\sigma }_j^{{\beta }_j};$$
• Verify: Given a signature $\sigma$, vectors ${\mathit{v}}_j$=$(v_{j1},v_{j2},\dots ,v_{jN})\in {\mathbb{Z}}_p^N,$ coefficients ${\beta }_j,j=1,\dots ,m$ and a specific User-Sensor’s public key u, compute $\mathit{y}={\sum }_{j=1}^m{\beta }_j{\mathit{v}}_j$, and denote $\mathit{y}=(y_1,\dots ,y_N)$, then check if the equation,

  $$\widehat{e}(\sigma ,h)=\widehat{e}({\Pi }_{i=1}^{N}H{(name,i)}^{y_i},u),$$

  holds or not. If it holds, then accept; otherwise, reject.
• Agg: Let $U\in \mathfrak{U}$ be the aggregating subset of User-Sensors, and let $\left|U\right|=l$. Every User-Sensor with public key $u_z$ generates the signature ${\sigma }_z$ on the linear combination ${\mathit{y}}_z=\sum {\beta }_{zj}{\mathit{v}}_{zj}$ ($z=1,\dots ,l$), where vectors ${\mathit{v}}_{z1},{\mathit{v}}_{z2},\dots ,{\mathit{v}}_{z{m}_z}$ are a set of the basis of an $m_z$-dimensional subspace ${\mathit{V}}_z$ ($z=1,\dots ,l$). Moreover, denote X as the public key of a Medical-Server ($X=h^x$), the designated verifier. The Aggregator-Server computes:

  $$\begin{array}{ccc}\hfill t& =& H_0(\widehat{e}({\sigma }_1,X),\dots ,\widehat{e}({\sigma }_l,X)),\hfill \\ \hfill \sigma & =& {\left({\Pi }_{z=1}^l{\sigma }_z\right)}^t.\hfill \end{array}$$
  The aggregate signature is $\sigma$.
• AggVerify: Given an aggregating subset U of l aggregating User-Sensors, the signers, with public key $u_z,z=1,\dots ,l$, an aggregate signature on the vectors ${\mathit{y}}_z=\sum {\beta }_{zj}{\mathit{v}}_{zj}$ ($z=1,\dots ,l$) with file identifiers $nam{e}_1,nam{e}_2,\dots ,nam{e}_l$, where vectors ${\mathit{v}}_{z1},{\mathit{v}}_{z2},\dots ,{\mathit{v}}_{z{m}_z}$ is a set of basis of the $m_z$-dimensional subspace ${\mathit{V}}_z$ and ${\mathit{v}}_{zj}$ = $(v_{z{j}_1},v_{z{j}_2},\dots ,v_{z{j}_N})$. The Medical-Server with private key x accepts if the following equation holds:

  $$\widehat{e}(\sigma ,h)={\Pi }_{z=1}^l\widehat{e}({\Pi }_{i=1}^{N}H{(nam{e}_z,i)}^{y_{zi}},u_z^{t^{\prime }}),$$

  where

  $$\begin{array}{ccc}\hfill t^{\prime }& =& H_0(\widehat{e}({\Pi }_{i=1}^{N}H{(nam{e}_1,i)}^{y_{1i}},u_1^x),\dots ,\widehat{e}({\Pi }_{i=1}^{N}H{(nam{e}_l,i)}^{y_{li}},u_l^x)),\hfill \\ \hfill {\mathit{y}}_z& =& \sum _{j=1}^{m_z}{\beta }_{zj}{\mathit{v}}_{zj},{\mathit{y}}_z=(y_{z1},y_{z2},\dots ,y_{zN}),z=1,\dots ,l.\hfill \end{array}$$
  Correctness: If the combine signature ${\sigma }_z$ is generated on the specific User-Sensor with public key $u_z$, then the following equations hold for $z=1,\dots ,l$:

  $$\widehat{e}({\sigma }_z,X)=\widehat{e}({\Pi }_{i=1}^{N}H{(nam{e}_z,i)}^{y_{zi}},u_z^x).$$
  So,

  $$\begin{array}{ccc}\hfill t& =& H_0(\widehat{e}({\sigma }_1,X),\dots ,\widehat{e}({\sigma }_l,X))\hfill \\ & =& H_0(\widehat{e}({\Pi }_{i=1}^{N}H{(nam{e}_1,i)}^{y_{1i}},u_1^x),\dots ,\widehat{e}({\Pi }_{i=1}^{N}H{(nam{e}_l,i)}^{y_{li}},u_l^x))\hfill \\ & =& t^{\prime }.\hfill \end{array}$$
  Then,

  $$\begin{array}{ccc}\hfill \widehat{e}(\sigma ,h)& =& \widehat{e}({\left({\Pi }_{z=1}^l{\sigma }_z\right)}^t,h)\hfill \\ & =& {\Pi }_{z=1}^l\widehat{e}({\sigma }_z,h^t)\hfill \\ & =& {\Pi }_{z=1}^l\widehat{e}({\Pi }_{i=1}^{N}H{(nam{e}_z,i)}^{y_{zi}},u_z^{t^{\prime }}).\hfill \end{array}$$

5. Security Analysis

5.1. The Security of Basic Signature Scheme

Theorem 1.

Suppose an EUF-CMA adversary $\mathcal{A}$ can break the basic signature scheme with advantage ϵ, and suppose $\mathcal{A}$ can run in time t, make at most $q_H$ times H random oracle queries (on at most $q_{id}$ different identifiers, $q_{id}\le q_H$) and $q_{\sigma }$ times sign queries. Then, there exists a challenger $\mathcal{B}$ to solve the CDH problem with advantage ${ϵ}^{\prime }\ge \frac{1}{q_{id}}ϵ$ and in time $t^{\prime }\le t+(q_{id}·N+q_s·m)·Exp$, where $Exp$ marks the time cost of an exponentiation operation in $\mathbb{G}$.

Proof. 

Suppose $\mathcal{A}$ can break the basic scheme’s EUF-CMA security, then with inputting a random instance $(g,g^a,g^b)$, the challenger $\mathcal{B}$ can use $\mathcal{A}$ to compute $g^{ab}$, and solve the CDH problem.

At first, $\mathcal{B}$ generates $(\mathbb{G},{\mathbb{G}}_T,p,\widehat{e})$, and randomly chooses $\iota \in {\mathbb{Z}}_p^{*}$, computes $g_0=g^{\iota },g_1=g^{a\iota },g_2=g^{b\iota }$, then provides $\mathcal{A}$ with $\{\mathbb{G},{\mathbb{G}}_T,p,\widehat{e},g_0,PK=g_1\}$. Here, hash function H is considered a random oracle controlled by $\mathcal{B}$.

Then the adversary $\mathcal{A}$ generates an integer N; note that $\mathcal{B}$ generates all $H(name,i),i=1,\dots ,N$ when it receives an H query on a $name$. $\mathcal{B}$ chooses a random integer index $\lambda \in [1,q_{id}]$, assuming H’s $\lambda$-th query for a different name is on $nam{e}^{*}$.

$\mathcal{B}$ respectively responds to H queries and sign queries as follows:

H queries:$\mathcal{B}$ maintains a list $H^{list}$: $(name,i,{\zeta }_i,h_i)$. $\mathcal{A}$ requests the value of $H(name,i)$, $\mathcal{B}$ follows the steps below:

• if the corresponding tuple $(name,i,{\zeta }_i,h_i)$ already exists in the list, output $h_i$;
• otherwise,

  –

  if $name=nam{e}^{*}$, randomly choose ${\zeta }_i\in {\mathbb{Z}}_p^{*}$, and set $h_i=g_2^{{\zeta }_i}$, $i=1,\dots ,N$;

  –

  else, choose ${\zeta }_i\in {\mathbb{Z}}_p^{*}$ at random, and set $h_i=g_0^{{\zeta }_i}$, $i=1,\dots ,N$;

  –

  add $(name,i,{\zeta }_i,h_i)$ to the list, $i=1,\dots ,N$;

• output $h_i$.

We suppose $\mathcal{A}$ invariably makes the suitable H queries before others.

Sign queries:$\mathcal{A}$ requests such a query on a subspace $\mathit{V}\subset {\mathbb{F}}_p^N$, described by basis vectors ${\mathit{v}}_1,{\mathit{v}}_2,\dots ,{\mathit{v}}_m\in {\mathbb{F}}_p^N$, where vector ${\mathit{v}}_j$=$(v_{j1},$$v_{j2},$$\dots ,v_{jN})$, and $\mathcal{B}$ follows the steps bellow:

• Generate a file identifier $name\in {\{0,1\}}^{*}$ randomly. Seek $H^{list}$ or make H queries get $H(name,i)$ and ${\zeta }_i$, $i=1,\dots ,N$.

  –

  if $name=nam{e}^{*}$, then abort;

  –

  else, set $\mathbf{s}=({\zeta }_1,\dots ,{\zeta }_N)$, compute ${\sigma }_j=g_1^{\mathbf{s}·{\mathbf{v}}_j}$;

• output $name$ and $\sigma =({\sigma }_1,\dots ,{\sigma }_m)$.

Forge: Finally, $\mathcal{A}$ outputs a forgery ${\sigma }^{*}=({\sigma }_1,\dots ,{\sigma }_m)$ on a vector space ${\mathit{V}}^{*}\subset {\mathbb{F}}_p^N$ described by basis vectors ${\mathit{v}}_1,{\mathit{v}}_2,\dots ,{\mathit{v}}_m\in {\mathbb{F}}_p^N$, an identifier $name$ and coefficients ${\beta }_j\in {\mathbb{Z}}_p,j=1,\dots ,m$.

• if $name\ne nam{e}^{*}$, then abort;
• else set $\mathit{s}=({\zeta }_1,\dots ,{\zeta }_N)$, compute $\mathit{y}={\sum }_{j=1}^m{\beta }_j·{\mathit{v}}_j$, if $\mathit{s}·\mathit{y}=0$, then abort;
• else compute $\theta ={\left({\Pi }_{j=1}^m{\sigma }_j^{{\beta }_j}\right)}^{\frac{1}{\iota }·\frac{1}{\mathit{s}·\mathit{y}}}$, and output $\theta$.

We observe that if the forgery ${\sigma }^{*}=({\sigma }_1,\dots ,{\sigma }_m)$ described above is valid, then:

$$\begin{array}{ccc}\hfill \widehat{e}({\Pi }_{j=1}^m{\sigma }_j^{{\beta }_j},g_0)& =& \widehat{e}({\Pi }_{i=1}^{N}H{(name,i)}^{y_i},g_1)\hfill \\ & =& \widehat{e}({\Pi }_{i=1}^N{h}_i^{y_i},g_1)\hfill \\ & =& \widehat{e}(g_2^{\mathit{s}·\mathit{y}},g_1)\hfill \\ & =& \widehat{e}(g_2^{\mathit{s}·\mathit{y}},g_0^a);\hfill \end{array}$$

furthermore,

$${\Pi }_{j=1}^m{\sigma }_j^{{\beta }_j}=g_2^{a·\mathit{s}·\mathit{y}},$$

so,

$$\theta ={\left({\Pi }_{j=1}^m{\sigma }_j^{{\beta }_j}\right)}^{\frac{1}{\iota }·\frac{1}{\mathit{s}·\mathit{y}}}=g^{ab}.$$

Analysis. It is easy to get that $\mathcal{B}$ can solve the CDH problem with advantage ${ϵ}^{\prime }\ge \frac{1}{q_{id}}ϵ$ and in time $t^{\prime }\le t+(q_{id}·N+q_s·m)·Exp$. □

5.2. The Security of Aggregate Signature Algorithm

Theorem 2.

Suppose $H_0$ is a collision-resistant Hash function, then the aggregate signature in the above LHAS scheme is valid, if and only if every individual signature used in the Aggregate algorithm is valid.

Proof. 

Suppose each individual signature ${\sigma }_z$ involved in the aggregation is valid, where ${\sigma }_z$ is the combine signature on the linear combination ${\mathit{y}}_z=\sum {\beta }_{zj}{\mathit{v}}_{zj}$ ($z=1,\dots ,l$), where vectors ${\mathit{v}}_{z1},{\mathit{v}}_{z2},\dots ,{\mathit{v}}_{z{m}_z}$ is a set of basis of an $m_z$-dimensional subspace ${\mathit{V}}_z$ ($z=1,\dots ,l$). Recall that the verifier’s public key is X, and x is the corresponding secret key, i.e., $X=h^x$, then

$$\widehat{e}({\sigma }_z,X)=\widehat{e}({\Pi }_{i=1}^{N}H{(nam{e}_z,i)}^{y_{zi}},u_z^x),z=1,\dots ,l.$$

So we have:

$$\begin{array}{ccc}\hfill t& =& H_0(\widehat{e}({\sigma }_1,X),\dots ,\widehat{e}({\sigma }_l,X))\hfill \\ & =& H_0(\widehat{e}({\Pi }_{i=1}^{N}H{(nam{e}_1,i)}^{y_{1i}},u_1^x),\dots ,\widehat{e}({\Pi }_{i=1}^{N}H{(nam{e}_l,i)}^{y_{li}},u_l^x))\hfill \\ & =& t^{\prime },\hfill \end{array}$$

and

$$\begin{array}{ccc}\hfill \widehat{e}(\sigma ,h)& =& \widehat{e}({\left({\Pi }_{z=1}^l{\sigma }_z\right)}^t,h)\hfill \\ & =& {\Pi }_{z=1}^l\widehat{e}({\sigma }_z,h^t)\hfill \\ & =& {\Pi }_{z=1}^l\widehat{e}({\Pi }_{i=1}^{N}H{(nam{e}_z,i)}^{y_{zi}},u_z^{t^{\prime }}).\hfill \end{array}$$

This means that the aggregate signature is valid.

On the other hand, if the aggregate signature is valid, then:

$$\widehat{e}(\sigma ,h)={\Pi }_{z=1}^l\widehat{e}({\Pi }_{i=1}^{N}H{(nam{e}_z,i)}^{y_{zi}},u_z^{t^{\prime }}),$$

and

$$\begin{array}{ccc}\hfill \widehat{e}(\sigma ,h)& =& \widehat{e}({\left({\Pi }_{z=1}^l{\sigma }_z\right)}^t,h)\hfill \\ & =& {\Pi }_{z=1}^l\widehat{e}({\sigma }_z,h^t)\hfill \\ & =& {\Pi }_{z=1}^l\widehat{e}({\Pi }_{i=1}^{N}H{(nam{e}_z,i)}^{y_{zi}},u_z^t)\hfill \\ & =& {\Pi }_{z=1}^l\widehat{e}({\Pi }_{i=1}^{N}H{(nam{e}_z,i)}^{y_{zi}},u_z^{t^{\prime }}).\hfill \end{array}$$

This means that $t=t^{\prime }$, so we have

$$\begin{array}{ccc}& & H_0(\widehat{e}({\sigma }_1,X),\dots ,\widehat{e}({\sigma }_l,X))\hfill \\ & =& H_0(\widehat{e}({\Pi }_{i=1}^{N}H{(nam{e}_1,i)}^{y_{1i}},u_1^x),\dots ,\widehat{e}({\Pi }_{i=1}^{N}H{(nam{e}_l,i)}^{y_{li}},u_l^x)).\hfill \end{array}$$

The hash function’s collision resistance shows that:

$$\widehat{e}({\sigma }_z,X)=\widehat{e}({\Pi }_{i=1}^{N}H{(nam{e}_z,i)}^{y_{zi}},u_z^x),z=1,\dots ,l.$$

This guarantees the validity of each single signature ${\sigma }_z$ is valid.

The above analysis implies that the aggregate signature in our LHAS scheme is valid, if and only if every single signature used in the algorithm Agg is valid. That is to say, even if an adversary can get all signers’ $SK$ by accessing the relevant oracles, the adversary cannot forge a valid aggregate signature using a set of single signatures which are not all valid. □

6. Performance Analysis

In this section, we mainly conducted various performance analyses of our LHAS scheme with respect to aggregate and un-aggregate. We used the simulator built in Python, performed on the Virtual Machines (VM) with 64-bit Ubuntu 20.04. The hardware and software specifications are shown in

Table 1. The hardware and software specification.

CPU	Intel(R) Core(TM) it-4200H CPU @ 2.8 GHz
Operation System	64-bit Ubuntu 20.04
Library	PyCharm, PBC Library, Charm-Crypto Library

. In order to provide a numerical result, we choose the MNT curve in PBC library. Various notations used in this section are listed in

Table 2. Definition of notations.

Notation	Definition
Aggregate	aggregate scheme
Un-Aggregate	un-aggregate scheme
$\left|m\right|$	the overall length of { $m_1$,$m_2$,…,$m_l$ }
$T_M$	the computation cost of scalar multiplication calculation in $\mathbb{G}$ or ${\mathbb{G}}_T$
$T_E$	the computation cost of exponentiation calculation in $\mathbb{G}$ or ${\mathbb{G}}_T$
$T_P$	the computation cost of paring operation in ${\mathbb{G}}_T$
$T_H$	the computation cost of map-to-point

. We omit the ${\mathbb{Z}}_p$ hash operation because the cost of this operation is negligible.

We assume that l users participate in the communication of LHAS-EHS. The communication cost comparison of the un-aggregate scheme and aggregate scheme is shown in

Table 3. Performance comparison of communication cost.

	Un-Aggregate	Aggregate
Combine-Node → Aggregator-Server	$l\left|\mathbb{G}\right|+\left|m\right|$	$l\left|\mathbb{G}\right|+\left|m\right|$
Aggregator-Server→ Medical-Server	$l\left|\mathbb{G}\right|+\left|m\right|$	$\left|\mathbb{G}\right|+\left|m\right|$

. It is clear that our LHAS scheme reduces the $(l-1)\left|\mathbb{G}\right|$ communication cost of medical data in the process of data transmission from the Combine-Node to the Medical-Server. Concurrently, it can reduce the $(l-1)\left|\mathbb{G}\right|$ storage cost of the Medical-Server. This is because the Aggregator-Server is used to aggregate signatures generated by l users into a short one, so that the Medical-Server only needs to verify one aggregated signature. Therefore, our LHAS scheme can reduce communication cost compared with the un-aggregate signature. This means that our LHAS scheme is efficient for EHS.

For comparison, we assume that a medical data packet m can be divided into 100 vectors; the dimensional of the vector is 5 and the number of combined vectors is 100.

Table 4. Performance comparison of verification efficiency.

	Un-Aggregate	Aggregate
Medical-Server.Verify	2$l{T}_P$+$Nl(T_H+T_E$)+$l(N-1)T_M$	$(2l+1)T_P$+$((N+1)l+1)T_E$+$(Nl+1)T_H$+$l(N-1)T_M$

and Figure 4 from different directions give the verification efficiency comparison of the Medical-Server, i.e., the un-aggregate scheme and aggregate scheme. In Figure 4, the y-axis represents the time required to verify the signature, and the x-axis represents the number of signatures verified. In the aggregation experiment, we take one Medical-Server as an example. The number of signatures that the Aggregator-Server waits for before aggregation is set to 10, 20, 30, 40, 50, 60, 70, 80, 90, 100. In order to resist coalition attacks, more pairing operations are required in the process of aggregation verification, which leads to more verification overhead. As can be seen from Figure 4, the gap is negligible, and the computing power of the Medical-Server is very strong, which can complete this overhead.

In order to fit the practical application, we chose a larger number of users for the experiment. The number of users l ranges from 100 to 1000 with an interval of 100. We make the y-axis represent the time required to verify the signature, and the x-axis represent the number of users. For the security of the aggregate signature, we have to pay for a certain verification efficiency. As shown in Figure 5, the verification efficiency of un-aggregate scheme is higher than that of aggregate scheme. It can be seen that this overhead gap is not large. Moreover, it also saves storage cost. The experiment results indicate that our proposed LHAS scheme is practical for EHS.

If the coalition attack is not considered, the verification efficiency of the aggregate signature is greatly improved. For the security of the aggregate signature, many pairing operations are required in aggregate verification. This will increase the verification overhead. Since there is no guarantee that the Aggregator-Server is fully trusted in the IoT network, this problem is worth considering. Therefore, how to improve the efficiency of signature verification while resisting coalition attacks is the next problem we need to solve.

7. Conclusions

Firstly, this paper proposes an LHAS-EHS scheme for the electronic healthcare system deployed with IoT technology. This scheme has the characteristics of linear homomorphism and aggregation, and can realize double data compression. It is mainly used for the batch verification of data integrity and data security aggregation. Then, the security of the LHAS scheme is rigorously presented based on the CDH assumption in Theorem 1, and Theorem 2 indicates that our LHAS scheme can resist coalition attacks based on the collision resistance of hash functions, i.e., even if an adversary can get all signers’ secret keys, he (she) cannot forge a valid aggregate signature using single signatures that contain invalid ones. Finally, the transmission and verification efficiency of aggregate and un-aggregate schemes are evaluated through performance analysis. The results show that our LHAS-EHS scheme not only reduces the cost of transmission and storage, but also further improves the security. The results show that the proposed LHAS scheme is very suitable for EHS.