A Linear Homomorphic Proxy Signature Scheme Based on Blockchain for Internet of Things

1  Introduction

In the past decade, the way of data collection and dissemination have inspired the rapid development of the Internet of Things (IoT) [1,2]. The IoT has opened up new avenues for technical support and business upgrades in the fields of industry, healthcare, transportation, military target tracking, smart homes and food traceability, among which mobile healthcare systems (MHSs) and the industrial Internet of Things (IIoT) are the most successful applications.

The IIoT continuously integrates all kinds of acquisition, sensors or controllers with sensing abilities, as well as mobile communication technology, into all aspects of industrial production, to improve production efficiency, reduce costs, and ultimately realize the conversion of traditional industry to smart industry [3]. MHSs provide services and applications [4,5], including mobile telemedicine and electronic monitoring systems based on wireless sensors. In this system, sensors (wearable or implanted) are connected to the bodies of remote patients to collect medical data, including body temperature, blood pressure, pH-value etc., and transmit these data through nodes to a medical server, which distributes the relevant data to professional medical personnel.

The rapid development of IIoT and MHSs, along with the generation of massive medical and industrial data, has led to increasing computing overhead and resource consumption, which makes traditional local computing model (most IoT devices have limited processing and computing power and are not economical to calculate) unable to meet the application requirements. Fortunately, due to the convenience and rapidity of cloud computing, many users migrate local data to cloud servers to meet the above challenge. Fig. 1 shows a typical cloud-based network architecture. Outsourcing data to cloud servers to obtain and accurate computation or analysis results have become preferential.

Figure 1: A typical architecture of cloud-based network

However, as an unsecure third party, cloud servers may return incomplete or wrong calculation results due to software and hardware errors and commercial interest inducement. Homomorphic signature (HS) provides a natural method for verifying outsourced computing, which can effectively solve the above problems. HS can enable untrusted servers to run calculations on outsourced data and generate a short signature to ensure the integrity and correctness of the calculation results. In recent years, HS has been extensively studied and developed [6–10].

Furthermore, consider such an application scenario: a hospital authorizes a sensor to sign data and communicate with the cloud server. The cloud server first confirms the authenticity of the sender (i.e., the sensor connected to the bodies of remote patients) and then sends the data calculation result and the derived signature to the hospital or research institution to verify its correctness. In an IIoT environment, an executive officer issues instructions to subordinates (such as the plant manager) to perform communication tasks. Thus, the data signature was often carried out by the subordinate on behalf of the superior organization. To realize this kind of authentication mechanism, it is necessary to authorize the signing right. In order to implement such kind of authentication mechanism, signature rights need to be authorized. Mambo et al. [11] realized this delegation authorization relationship with the concept of proxy signature (PS). In the PS scheme, the original signer (all represented by Alice) delegates its signing power to the proxy signer (all represented by Bob). Bob can generate valid proxy signatures in the name of Alice, and the verifier accepts the authorization protocol.

Naturally, to ensure the reliability of outsourced computing in the case of authorized signing rights, constructing a PS scheme with the homomorphism is interesting, which combines the delegation characteristics and homomorphism in the authentication method. In this type of scheme, Alice can authorize Bob, and Bob can create a proxy signature with homomorphic properties. However, as far as we know, constructions of linearly homomorphic proxy signature (LHPS) have been few and far between; in addition, the existing LHPS scheme [12] is only proven to be usually existential unforgeable (EUF) against adaptive chosen-message attacks (CMA). This security concept only guarantees that an adversary cannot forge a signature of any new message under the unqueried data identifier; it does not ensures that the adversary generates a valid signature for the data sets that have been queried for signatures (i.e., homomorphic existential forgery). In detail, for the security of a signature with homomorphic properties, there are two meanings of existential unforgeability, a verifiable forgery (f,y′,σ′) where f is an admissible function on messages x and y′≠y(y=f(x)) characterizes two facts: First, if f(x)=πi(x)=xi is a special projection function, then σ′ is a usual existential forgery (UEF), corresponding to the general concept of signature forgery. Another is that if f is a generally admissible function, then σ′ is a homomorphic existential forgery (HEF), that is, forgery σ′ authenticates y as f(x), which is not the case. Homomorphic unforgeability is an important property of the LHPS scheme, which can prevent untrusted cloud servers from authenticating the wrong computing or analysis results and returning them to the receiver. Unfortunately, for the two types of adversaries, the existing homomorphic proxy signature security model does not consider the situation in which adversaries output homomorphic existential forgeries; thus, the proposed scheme does not satisfy homomorphic unforgeability in the sense of provable security.

To overcome this security flaw, we improve the security definition for LHPS and construct a new LHPS scheme for IoT environments, and makes the following main contributions in this paper:

1.    The security model for LHPS is improved. For the two types of adversaries, considering the situation of an adversary’s output of a homomorphic existential forgery, the types of forgeries are more comprehensive, so the model security standard is higher.

2.    We construct a blockchain-based LHPS scheme and prove that this scheme is secure against existentially forgery (including the usual existential forgery and homomorphic existential forgery) on adaptive CMA based on the CDH assumption under two types of adversaries.

3.    The performance of the new LHPS is analyzed in detail. The discussion shows that our scheme has the same key size and comparable computational overhead as Lin et al.’s LHPS scheme [12], but it has higher security. Therefore, it is feasible to deploy and implement our LHPS scheme in cloud-based IoT environments.

2  Related Works

The concept of HS scheme was first proposed by Goldwasser et al. [13] in 2000. Johnson et al. [14] first introduced the formal definition and overall framework of HS. Until 2009, Boneh et al. [15] proposed the first secure and practical LHS scheme, which can be regarded as a milestone of LHS scheme. Utilizing the k-SIS hardness assumption, reference [9] proposed the first scheme that can against quantum attacks. In order to be independent of certificate management, scholars proposed identity-based LHS schemes [16–19]. Although certificate management is simplified, key escrow issues are introduced. In response to this problem, researchers have successively proposed certificateless LHS [20,21]. Recently, multi-key HS has attracted attention [22–29]. For datasets involving inputs authenticated by different clients, multiple-key support is required, Chen et al. [27,28] successively proposed two multi-key LHS schemes, supporting three-layer and multi-layer routing networks respectively. Lai et al. [29] proposed an unforgeable multi-key HS under internal corruption based on adaptive zero-knowledge non-interactive knowledge demonstration. The public verifiability of HS makes them studied in other application scenarios. For example, the verifiable encryption HS scheme proposed by Seo et al. [30] has been successfully applied to cumulative optimistic fair exchange, and the homomorphic signcryption scheme proposed by Fan et al. [31] has been successfully applied to electronic voting, for voters, the use of homomorphic signcryption can complete the encryption and signature of votes in one step. In 2021, Li et al. [32] proposed a homomorphic signcryption scheme with verifiable public plaintext results, allowing the evaluation of arbitrary functions on signcrypted data, and allowing anyone to publicly test whether a given ciphertext is a signcrypted file for a message under a key.

Since Mambo et al. [11] proposed the concept of PS in 1996, many variants of PS have been proposed by other researchers successively, including proxy multi-signatur, multi-PS, proxy blind signature, certificate-based proxy signature and designated verifier proxy signature [33–38]. In 2003, Lee et al. [39] believed that proxy signature does not necessarily require a secure channel. In terms of the security model, Cao et al. [40] and Wang et al. [41] presented the model of a multi-proxy signature scheme. However, as Schuldt et al. [42] pointed out, the structure of the model is complex and incomplete. In 2012, Boldyreva et al. [43] improved its early security model by clearly defining the security attributes of proxy signatures and formalizing the definition of adversary behavior.

Blockchain is a new type of decentralized protocol that can securely store Bitcoin transactions or other data. The information cannot be forged or tampered with, and smart contracts can be automatically executed without the audit of any centralized organization [44,45]. Transactions can be digital currencies such as Bitcoin or digital assets such as debt, equity, copyright, etc. Blockchain technology solves the Byzantine general problem, greatly reduces the cost of trust and accounting in the real economy, and redefines the property right system in the Internet era. The introduction of blockchain technology in the proxy signature mechanism can realize the delegation of digital signature rights under the premise of safety and reliability, and support traceability and tamper-proof modification [46]. Additionally, blockchain-based proxy signatures enable anonymity of authentication while ensuring traceability of misconduct [47].

3  Architecture of Sign Delegation and Authentication Computing in a Cloud-Based IoT Environment

In the architecture of a cloud-based IoT environment using delegation and authentication computing, five entities are involved: CA, data owner, cloud server, end user and blockchain, as shown in Fig. 2. The specific functions are as follows (In this paper, Alice/Bob always represents the original/proxy signer):

•   CA: It generates system parameters and generates certificates for users according to the identity and public key provided by each user.

•   Data owner: It is composed of industry officials (e.g., system administrators, executive officers, etc.) and intelligent devices (embedded sensors). In our LHPS scheme, the superior is the Alice, and the subordinate is the Bob. For smart machines, the deployment agency/supervisor acts as the Alice, and the sensor will act as the Bob. Therefore, the superior (or supervisor) delegates its signature right to the subordinate (or smart machine).

•   Cloud server: The cloud server can use the homomorphic signature to perform various calculations on the authentication data, and then sends the calculation results and the derived signatures to the end user, which can be done with minimal interaction and communication.

•   End user: The end user may be a hospital, a research institution, or an intelligent machine (depending on the scenario). It receives the calculation result and the corresponding signature and uses the public key of the two signers for verification.

•   Blockchain: The blockchain mainly stores the warrant from the original signer to the proxy signer so that other entities can download and verify the validity of the warrant.

Figure 2: Architecture for IoT environment based on LHPS, blockchain and cloud computing

4  Definitions and Security Model

4.1 Linearly Homomorphic Proxy Signature

A LHPS scheme proposed in this paper includes seven polynomial-time algorithms (Setup, UserKGen, Delegation, DeleVerify, LHP-Sign, LHP-Combine, LHP-Verify):

•   Setup: On input a security parameter λ and a integers l (the maximum data-size) as input, it outputs the system parameters params.

•   UserKGen: On input params, it output a public/private key pair (pku,sku) for a user.

•   Delegation: Given params, the private key skA of Alice, the warrant wB of Bob (it records the identity information of the Alice and Bob, the type of authorization message, and the validity period of the proxy signer), it output delegation information SwB.

•   DeleVerify: For the input params, public key of Alice, delegation and warrant, it outputs 0 or 1 according to reject or accept.

•   LHP-Sign: Bob greats a proxy signature σ on a message vector v, after using params, the private key skB of Bob, a warrant wB, delegation information SwB and a file identifier τ∈{0,1}λ.

•   LHP-Combine: Takes a file identifier τ, public keys of both signer, a warrant wB, and a set of tuples {(ci,σi)}i=1l, where ci∈Fq, σi← LHP-Sign (params,τ,skB,SwB,vi), and outputs a signature σ on v=∑i∈[l]civi.

•   LHP-Verify: Takes as input public keys of both signer, wB, a file identifier τ, and message/signature pair, outputs either 1 or 0.

Correctness. The requirement is that for any output (pkA,skA), (pkB,skB) of the algorithm UserKGen, the following conditions are true:

(1)   For any τ∈{0,1}λ and message vector v, if σ← LHP-Sign (skB,wB,SwB,τ,v), then LHP-Verify (τ,pkA,pkB,wB,v,σ) = 1.

(2)   For all τ and sets of tuples {(ci,σi,vi)}i=1l, if LHP-Verify (τ,pkA,pkB,wB,vi,σi) = 1, then LHP-Verify (τ,pkA,pkB,wB,∑i=1lcivi, LHP-Combine {τ,pkA,pkB,wB,(ci,σi)}i=1l) = 1.

4.2 Security Models

We consider two type of adversaries, and denoted by 𝒜ℐ, 𝒜ℐℐ, respectively.

Type-I adversary (𝒜ℐ): 𝒜ℐ consists of system parameters, Alice’s public-private key pair, and Bob’s public key. In fact, 𝒜ℐ is a malicious original signer.

Type II adversary (𝒜ℐℐ): 𝒜ℐℐ consists of system parameters, Bob’s public-private key pair, and Alice’s public key. In fact, 𝒜ℐℐ is a malicious proxy signer.

We use the following game between challenger 𝒞 and 𝒜ℐ, 𝒜ℐℐ to describe the security of the LHPS scheme.

Game 1. (Security against adversary 𝒜ℐ) 𝒜ℐ attempts to outputs a forged proxy signature while having no private key of the Bob. The following formalized security models are designed for 𝒜ℐ and 𝒞.

•   Setup: 𝒞 performs Setup and UserKGen oracles, and obtain the system parameters params, the key pair (pkA,skA) of Alice as well as key pair (pkB∗,skB∗) of the targeted proxy signer. 𝒞 then gives params and (pkA,skA,pkB∗) to 𝒜ℐ.

•   Queries: Adversary 𝒜ℐ can performs the following polynomial number of oracle queries.

    – Key Registration Queries: Given a key pair (pki,ski), 𝒞 first checks whether (pki,ski) is valid. If so, 𝒞 stores it in a list. Otherwise, 𝒞 rejects.

    – Signing Queries: Given a tuple (τ,pkA, pkB∗,wB∗,v), 𝒞 outputs a signature σ on v.

Output: 𝒜ℐ outputs a forgery tuple (pkA,pkB∗,wB∗,τ∗,v∗,σ∗). The adversary wins if LHP-Verify (τ∗, pkA,pkB∗,wB∗,v∗,σ∗) = 1, the message vector v∗ does not appear in signing queries, and one of the following conditions is satisfied:

(1)   For any τi appearing in the signing queries, τ∗≠τi holds (usual existential-forgery–Type 1 forgery).

(2)   For a τi appearing in the signing queries, there is τ∗=τi, but v∗∉Vi, where Vi represents the subspace spanned by the vectors {vi}i∈[l] that have been queried by the identifier τi (homomorphic existential-forgery–Type 2 forgery).

Game 2. (Security against adversary 𝒜ℐℐ) 𝒜ℐℐ attempts to output a forged proxy signature while having no private key of Alice. Now, the following formal model with respect to 𝒜ℐℐ and challenger 𝒞 is designed.

•   Setup: 𝒞 performs Setup and UserKGen oracles, and obtains the parameters params, the public/private key pair (pkA,skA) of Alice. 𝒞 then gives params and pkA to 𝒜ℐℐ.

•   Queries: Adversary 𝒜ℐℐ can performs the following polynomial number of oracle queries.

    – Key Registration Queries: Given a key pair (pki,ski), 𝒞 first checks whether (pki,ski) is valid. If so, 𝒞 stores it in a list. Otherwise, 𝒞 rejects.

    – Delegate Queries: Given public key pkA and registered pki, 𝒞 returns a warrant wi and a delegation Swi.

    – Signing Queries: Given public key pkA and registered public key pki, wi, τ, and a vector v, 𝒞 returns a signature σ on the message v.

•    Output: 𝒜ℐℐ outputs a forgery tuple (τ∗,pkA,pki∗,wBi∗,v∗,σ∗). 𝒜ℐℐ wins if LHP-Verify (τ∗,pkA,pki∗,wi∗,v∗,σ∗) = 1, and public key pki∗ and message vector v∗ do not appear in delegate queries and signing queries, respectively, and one of the following conditions is satisfied:

(1)   For any τi appearing in the signing queries, τ∗≠τi holds (usual existential-forgery–Type 1 forgery).

(2)   For a τi appearing in the signing queries, there is τ∗=τi, but v∗∉Vi, where Vi represents the subspace spanned by the vectors {vi}i∈[l] that have been queried by the identifier τi (homomorphic existential-forgery–Type 2 forgery).

The advantage of adversary 𝒜ℐ (𝒜ℐℐ) is the probability of winning Game 1 (Game 2), which is recorded as Adv𝒜ℐLHPS(λ) (Adv𝒜ℐℐLHPS(λ)).

Definition 4.1. Our proposed LHPS scheme is said to be unforgeable against the adversaries 𝒜I and 𝒜II in the above games, if Adv𝒜iLHPS(λ)(i=I,II) is negligible.

5  Proposed LHPS Scheme

Our proposed LHPS scheme is described in detail as follows:

•   Setup: Takes a security parameter λ and two positive integers l, n as inputs, CA generates params as follows:

(1) Choose two groups G1, G2 of the same prime order q, with g as the generator of G1, and select a bilinear pairing e:G1×G1→G2.

(2) Selects different hash functions H,H1,H2, each of which maps {0,1}∗ to G1.

•   UserKGen: Each user chooses xu∈Zq∗ at random as his private key and computes pku=gxu as public key. Then, the public/private key pair of original signer Alice and proxy signer Bob are (pkA=gxA,xA) and (pkB=gxB,xB), respectively. Subsequently, each user provides its identity and public key to the CA to obtain the corresponding certificate.

•   Delegation: Alice generates a warrant wB related to Bob, and computes delegation SwB=H(wB)xA, then returns SwB to Bob. After that, Alice uploads wB to the blockchain so that other users can query and verify the validity of wB.

•   DeleVerify: Bob checks e(SwB,g)=e(H(wB),pkA) and accepts delegation. Then, Bob sets proxy signing key as Sp=(SwB,xB).

•   LHP-Sign: Suppose that this algorithm has stored an initially empty list L containing information about all identifiers τ that have been used. Given a tuple (Sp,wB,τ∈{0,1}λ,v), here the message vector v=(v1,…,vn)∈Zqn, it performs the following steps:

   (1)   Retrieve the relevant (U,r) from L, if τ appears in the list L.

   (2)   Otherwise, it chooses a random number r∈Zq∗, lets U=gr, then stores (U,r) into L.

   (3)   Calculate hash values Qi=H1(pkA,wB,τ,U,i),i∈[n], Q=H2(pkB,wB).

   (4)   Choose a random number s∈Zq∗, and computes

W=(SwB)∑i∈[n]vi(H(wB)s⋅∏i∈[n]Qivi)r(Q∑i∈[n]vi)xB.

(5)   Output σ=(U,W,s) as signature.

LHP-Combine: On input pkA, pkB, τ, wB, and a set of tuple {(ci,σi)}i=1l with ci∈Zq, where σi=(U,Wi,si) (note that the data signatures under the same identifier have the same U), this algorithm computes W=∏i∈[l]Wici, s=∑i∈[l]cisi. Then, it outputs (U,W,s).

LHP-Verify: Given a tuple (τ,pkA,pkB,wB,v,σ), where vector v=(v1,…,vn)∈Zqn, σ=(U,W,s), the algorithm considers the proxy signature to be valid by verifying the following equation:

e(W,g)=e((H(wB)∑i∈[n]vi,pkA)⋅e(H(wB)s⋅∏i∈[n]Qivi,U)⋅e(Q∑i∈[n]vi,pkB).

Correctness

(1)   Given a tuple (τ,pkA,pkB,v=(v1,…,vn)∈Zqn,σ), if σ← LHP-Sign (Sp,wB,τ,v), then the correctness of proxy signature verification can be obtained by the following derivation:

e(W,g)=e((SwB)∑i∈[n]vi,g)⋅e(H(wB)s⋅∏i∈[n]Qivi)r,g)⋅e((Q∑i∈[n]vi)xB,g)=e((H(wB)∑i∈[n]vi,pkA)⋅e((H(wB)s∏i∈[n]Qivi,U)⋅e(Q∑i∈[n]vi,pkB).

(2)   Given a tuple (τ,wB,{(ci,σi,vi)}i=1l), where σi=(U,Wi,si) and vi=(vi1,…,vin), if σi← LHP-Sign (Sp,wB,τ,vi), we have to prove that σ=(U,W=∏i∈[l]Wici,s=∑i∈[l]cisi) is a signature on y=∑i∈[l]civi=(y1,…,yn). Since for each i∈[l], σi is the correct signature of vi, we have

e(Wi,g)=e(H(wB)∑j∈[n]vij,pkA)⋅e(H(wB)si∏j∈[n]Qjvij,U)⋅e(Q∑j∈[n]vij,pkB),

e(W,g)=∏i∈[l]e(Wi,g)ci=e(H(wB)∑i∈[l]∑j∈[n]civij,pkA)⋅e(H(wB)∑i∈[l]cisi∏j∈[n]Qj∑i∈[l]civij,U)⋅e(Q∑i∈[l]∑j∈[n]civij,pkB)=e(H(wB)∑j∈[n]yj,pkA)⋅e(H(wB)s⋅∏j∈[n]Qjyj,U)⋅e(Q∑j∈[n]yj,pkB).

Therefore, for the LHP-Combine algorithm, the LHP-Verify algorithm is correct.

6  Security Analysis

This section presents the security analysis of our LHPS scheme. In this section, (g,ga,gb) always represents a random instance of the CDH problem.

Theorem 6.1. If there is an adversary 𝒜ℐ that can forge a valid message/signature pair with an advantage ε within time t, then there is an algorithm 𝒞 that can solve the CDH problem with probability ε′ within time t′. Among them, qH refers to the number of querying H oracle, qHi(i=1,2) refers to the number of querying Hi oracles, qS refers to the number of querying signing oracle.

Proof. For any PPT adversary 𝒜ℐ, we construct a simulator 𝒞, which can call 𝒜ℐ to solve the CDH problem. Since 𝒜ℐ finally outputs one of the two forgery types, it is obvious that the probability of 𝒞 guessing the forgery type outputed eventually by 𝒜ℐ is 12.

Case 1 (usual existential-forgery.) 𝒞 guesses that adversary 𝒜ℐ will output a Type 1 forgery. 𝒞 is invoked on (g,ga,gb), and 𝒞’ goal is to compute gab. 𝒞 interacts with 𝒜ℐ in this way.

•   Setup: 𝒞 randomly selects xA∈Zq∗, computes Alice’s public key as pkA=gxA, and sets Bob’s public key as pkB∗=ga (note that in the proof of Theorem 1, Bob represents the target proxy signer). 𝒞 sets the system parameter params = (G1,G2,e,g,H,H1,H2,q). Then, 𝒞 sends params and (xA,pkA,pkB∗) to 𝒜ℐ.

•   Queries: 𝒜ℐ can issue queries to the following oracles simulated by 𝒞. 𝒞 maintains an initially empty list for each type of query, recording all responses to 𝒜ℐ.

    – Key Registration Queries: When 𝒜ℐ requests to register a new user i by outputting a key pair (pki,xi), 𝒞 verifies if it is valid, and then adds (pki,xi) to the list LK.

    – H Queries: On a requested wi, 𝒞 selects a random zi∈Zq∗ and sets H(wi)=gzi. Then, 𝒞 updates list LH←LH∪<wi,gzi,zi> and responds gzi to 𝒜ℐ.

–   H1 Queries: For a requested (PkA,wB,τ,U,i), 𝒞 first searches LH1 and if an required entry is found, 𝒞 returns it. Otherwise, 𝒞 selects a random ti∈Zq∗ and computes Qi=gti, then updates LH1←LH1∪<(pkA,wB,τ,U,i),Qi,ti> and sends Qi to 𝒜ℐ as response.

–   H2 Queries: On a requested (wB,pkB), 𝒞 checks the list LH2 to determine whether there is a corresponding hash value, and if so, 𝒞 returns it to 𝒜ℐ; otherwise, 𝒞 chooses a random number t∈Zq∗ and sets Q=(gb)t, then updates list LH2←LH2∪<(wB,pkB),Q,t> and sends Q to 𝒜ℐ as response.

– Signing Queries: Given τ, pkA,pkB∗, a warrant wB∗, and a vector v=(v1,…,vn)∈Zqn, 𝒞 generates the signature as follows:

(1)   Randomly choose numbers s,r,ui∈Zq∗(i∈[n]), and set U=pkB∗r=(ga)r.

(2)   Define the hash values of H1(pkA,wB∗,τ,U,i) as Qi=(guiQ)r−1∈G1, where Q=H2(wB∗,pkB∗)=(gb)t∗. If for some i∈[n], (pkA,wB∗,τ,U,i) has already been queried in the H1 queries phase, then 𝒞 terminates and gives up.

(3)   Recover H(wB∗)=gzB∗ from LH.

(4)   Finally, 𝒞 computes

W=(H(wB∗))xA∑i∈[n]vi⋅(pkB∗)∑i∈[n]uivi+srzB∗.

𝒞 returns the signature σ=(U,W,s) to 𝒜ℐ. From the following derivation process, it can be known that σ is a valid signature.

e(H(wB∗)∑i∈[n]vi,pkA)⋅e(H(wB∗)s⋅∏i∈[n]Qivi,U)⋅e(Q∑i∈[n]vi,pkB∗)=e(H(wB∗)xA∑i∈[n]vi,g)⋅e(H(wB∗)s⋅∏i∈[n](guiQ)r−1vi,pkB∗r)⋅e(Q∑i∈[n]vi,pkB∗)=e(H(wB∗)xA∑i∈[n]vi,g)⋅e(H(wB∗)s,pkB∗r)⋅e(g∑i∈[n]uivi,pkB∗)⋅e(Q−∑i∈[n]vi,pkB∗)⋅e(Q∑i∈[n]vi,pkB∗)=e(H(wB∗)xA∑i∈[n]vi,g)⋅e(H(wB∗)s,pkB∗r)⋅e(g∑i∈[n]uivi,pkB∗)=e(H(wB∗)xA∑i∈[n]vi⋅(pkB∗)∑i∈[n]uivi+srzB∗,g)=e(W,g).

•   Output: Finally, 𝒜ℐ outputs (pkA,pkB∗,wB∗,τ∗,v∗,σ∗), where v∗=(v1∗,…,vn∗), ∑i∈[n]vi∗≠0 and σ∗=(U∗,W∗,s∗). 𝒞 retrieves the items H(wB∗) from LH, the items Qi from LH1, and the item Q from LH2; Note that H(wB∗)=gzB∗,Qi=gti∗,Q=(gb)t∗. If the 𝒜ℐ successfully outputs a Type 1 forgery, then τ∗≠τi, i.e., none of the message vectors identified by τ∗ have been queried during the Signing Queries phase, and there is a verification equation.

e(W∗,g)=e(H(wB∗)∑i∈[n]vi∗,pkA)⋅e(H(wB∗)s∗∏i∈[n](Qi)vi∗,U∗)⋅e((Q)∑i∈[n]vi∗,pkB∗)=e(H(wB∗)xA∑i∈[n]vi∗⋅(U∗)s∗zB∗+∑i∈[n]ti∗vi∗⋅(gab)∑i∈[n]t∗vi∗,g).

Therefore, we have

W∗=H(wB∗)xA∑i∈[n]vi∗⋅(U∗)s∗zB∗+∑i∈[n]ti∗vi∗⋅(gab)∑i∈[n]t∗vi∗.

The CDH problem can be solved by calculating the following equation:

gab=(W∗H(wB∗)xA∑i∈[n]vi∗⋅(U∗)s∗zB∗+∑i∈[n]ti∗vi∗)1∑i∈[n]t∗vi∗.

Next we calculate the probability of 𝒞 success.

We only need to analyze the probability of 𝒞 aborting the simulation during the signing query phase. When the hash value conflicts on H1, that is, the same hash object appears in H1 hash query and signing query, 𝒞 aborts. Since the entry in LH1 is not more than qH1+qS, it is easy to know that the probability of 𝒞 aborting in signing query is at most qS(qH1+qS)2λ. Therefore, if the advantage of 𝒜ℐ forging a signature in Game 1 is ε, 𝒞 can solve the CDH problem with a probability of at least ε′=12ε−(qS)2+qH1qS2λ, within time t′=t+O(qH+qH1+qH2+qS)×texp+qS×Tmul, where Tmul and texp represent the multiplication and exponential operation time of group elements, respectively.

Case 2 (homomorphic existential-forgery): 𝒞 guesses that adversary 𝒜ℐ will output a Type 2 forgery. 𝒞 is invoked on a tuple (g,ga,gb), and is asked to compute value of gab by using 𝒜ℐ as a subroutine.

•   Setup: 𝒞 randomly selects xA∈Zq∗ and lets pkA=gxA, and runs 𝒜ℐ on input pkB∗=ga as the public key of Bob. 𝒞 sets the system parameter params = (G1,G2,e,g,H,H1,H2,q). Then, 𝒞 sends params and (xA,pkA,pkB∗) to 𝒜ℐ, and responds to 𝒜ℐ as follows.

•   Queries: 𝒞 maintains a corresponding list in both the key registration queries and the hash queries, recording all responses to the 𝒜ℐ.

–   Key Registration Queries: When 𝒜ℐ outputs the key pair (pki,xi) and requests to register a new user i, if 𝒞 verifies that it is a valid key pair, it will add (pki,xi) to the list LK; otherwise, (pki,xi) can be refused by 𝒜ℐ.

–   H Queries: On a requested wi=wB∗, 𝒞 sets H(wB∗)=gb; otherwise, wi≠wB∗. 𝒞 chooses a number zi∈Zq∗ randomly, and lets H(wi)=gzi. Then, 𝒞 updates list LH←LH∪<wi,gb,⊥> or LH←LH∪<wi,gzi,zi>, and responds H(wi) to 𝒜ℐ.

–   H1 Queries: For a requested (pkA,wB,τ,U,i), 𝒞 first searches LH1 and if an entry is found, 𝒞 returns it. Otherwise, 𝒞 chooses randomly αi,βi∈Zq∗ and sets Qi=(gb)αigβi, then updates list LH1←LH1∪<(pkA,wB,τ,U,i),Qi,αi,βi>, and returns Qi to 𝒜ℐ.

–   H2 Queries: 𝒜ℐ submits (wi,pki), if wi=wB∗, 𝒞 sets Q=(gb)t∗ with random t∗∈Zq∗. Otherwise, 𝒞 selects a number t∈Zq∗ randomly and lets Q=(gb)t, then updates list LH2←LH2∪<(wB∗,pkB∗),Q,t∗> or LH2←LH2∪<(wi,pki),Q,t>, and sends Q to 𝒜ℐ as response.

–   Signing Queries: Given τ, pkA,pkB∗, a warrant wB∗, and a vector v=(v1,…,vn)∈Zqn, 𝒞 generates the signature as follows:

(1)   If list L does not contain τ, 𝒞 choose numbers r∈Zq∗ randomly, set U=pkB∗r=(ga)r, and stores (wB∗,τ,U,r) in L. Otherwise, it recovers the required items from L.

(2)   𝒞 computes

W=(gb)xA∑i∈[n]vi⋅(ga)r∑i∈[n]βivi,s=−∑i∈[n](t∗r+αi)vi.

and returns the signature σ=(U,W,s) to 𝒜ℐ. The following analysis shows that σ is valid since s=−∑i∈[n](t∗r+αi)vi, so rs+r∑i∈[n]αivi+t∗∑i∈[n]vi=0. Hence,

(SwB∗)∑i∈[n]vi⋅(H(wB∗)s⋅∏i∈[n]Qivi)ra⋅(Q∑i∈[n]vi)xB∗=(gb)xA∑i∈[n]vi⋅(gbs⋅gb∑i∈[n]αivi⋅g∑i∈[n]βivi)ra⋅(gab)t∗∑i∈[n]vi=(gb)xA∑i∈[n]vi⋅gab(rs+r∑i∈[n]αivi+t∗∑i∈[n]vi)⋅gra∑i∈[n]βivi=(gb)xA∑i∈[n]vi⋅(ga)r∑i∈[n]βivi=W.

•   Output: Finally, 𝒜ℐ outputs (pkA,pkB∗,wB∗,τ∗,v∗,σ∗), where v∗=(v1∗,…,vn∗), ∑i∈[n]vi∗≠0 and σ∗=(U∗,W∗,s∗). 𝒞 retrieves the items H(wB∗), Ti and T from LH, LH1, and LH2, respectively. Note that H(wB∗)=gb,Qi=(gb)αigβi,Q=(gb)t∗. If 𝒜ℐ successfully outputs a Type 2 forgery, it is not hard to see that U∗=pkB∗r=(ga)r, and the following equation holds:

e(W∗,g)=e(H(wB∗)∑i∈[n]vi∗,pkA)⋅e(H(wB∗)s∗∏i∈[n](Qi∗)vi∗,U∗)⋅e((Q∗)∑i∈[n]vi∗,pkB∗)=e((gb)xA∑i∈[n]vi∗,g)⋅e(gbs∗+b∑i∈[n]αivi∗⋅g∑i∈[n]βivi∗,gar)⋅e(gbt∗∑i∈[n]vi∗,ga)=e(gbxA∑i∈[n]vi∗⋅gab(rs∗+r∑i∈[n]αivi∗+t∗∑i∈[n]vi∗)⋅gar∑i∈[n]βivi∗,g).