# Secure Outsourced Attribute-Based Signatures with Perfect Anonymity in the Standard Model

Authors: Zhenjie Huang; Runlong Duan; Qunshan Chen; Hui Huang; Yuping Zhou
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Outsourced attribute-based signatures (OABS) enable users to sign messages without revealing specific identity information and are suitable for scenarios with limited computing power. Recently, Mo et al. proposed an expressive outsourced attribute-based signature scheme (Peer-to-Peer Networking and Applications, 11, 2017). In this paper, we show that Mo et al.’s scheme does not achieve any of the three security properties. Their scheme is incorrect. The adversary can collude with the malicious signing-cloud service provider (S-CSP) to forge valid signatures on any message and any attribute set. And the S-CSP could trace the access structures used to generate the signatures. Then, we treat the S-CSP as an adversary and present more accurate unforgeability and anonymity models for OABS to remedy the drawbacks of the previous ones. Finally, we propose a simple but significant improvement to fix our attacks. The improved scheme achieves correctness, unforgeability, and perfect anonymity while keeping the efficiency almost unchanged. We also prove the security of the improved scheme under the standard model.


---

## Body

## 1. Introduction

Attribute-based cryptography is a powerful cryptographic primitive, enabling us to design various cryptosystems with fine-grained access control in a multiuser environment [1, 2]. Attribute-based signature (ABS) is one of the leading research contents of attribute-based cryptography. ABS can provide fine-grained privacy protection for signers and finds applications in many fields, such as private access control, trust negotiations, and anonymous credentials [2, 3]. ABS may also be applied to mobile authentication and two-factor/multifactor authentication in the future [4–6]. Since it was introduced, numerous ABS schemes for different access structures have been proposed one after another [7–15].However, with the continuous enhancement of the expressiveness of the access structure, the computational overhead of ABS is increasing, which makes it challenging to execute in devices with limited computing power. Using outsourcing technology of cloud computing, Chen et al. [16] introduced outsourced attribute-based signatures (OABS) to overcome this problem. In OABS, the signer can delegate most of his/her signing workload to a signing-cloud service provider (S-CSP). After receiving the semisignature from the S-CSP, the signer can generate the final signature by little computations. In this way, ABS can be used in resource-constrained devices.


### 1.1. Related Works

While introducing OABS, Chen et al. [16] proposed two concrete OABS schemes. Their schemes are signature-policy OABS schemes with threshold access structures. After, Mo et al. [17] proposed an OABS scheme and applied it to the medical cloud. Mo et al.’s scheme is a key-policy OABS scheme that supports a more expressive monotonic access structure. Sun et al. [18, 19] introduced decentralization into OABS and proposed an outsourcing decentralized multiauthority attribute-based signature scheme. Their scheme is a signature-policy scheme for threshold access structure. In 2021, Huang et al. [20] proposed a new key-policy OABS scheme for circuits. Their scheme is a short signature scheme, and its final signature has only one element of the group.Chen et al.’s OABS model assumes that the S-CSP is honest-but-curious, i.e., the S-CSP always runs the algorithm honestly and outputs the semisignatures correctly, but the S-CSP may forge signatures. As a remedy for the overly strong assumption of S-CSP’s honesty, Chen et al. [16] discussed the accountability of OABS, which provides an audit function for S-CSP’s honesty. Liu et al. [21] studied OABS under the concept of server-assisted anonymous attribute authentication, added the correctness verification of the semisignature to OABS, and defined the outsourcing verifiability. After that, Ren and Jiang [22] formally introduced the concept of Verifiable Outsourced Attribute-Based Signatures (VOABS) with a concrete scheme supporting threshold access structure. Unfortunately, Uzunkol [23] presented two attacks on the verifiability of Ren et al.’s scheme. Moreover, one of the attacks enables the untrusted S-CSP to forge signatures.In 2018, Cui et al. [24] introduced a new notion of Server-Aided Attribute-Based Signature (SA-ABS). SA-ABS outsources both signing tasks and verification tasks to cloud service providers, while OABS only outsources signing tasks. This is the main difference between the two. Cui et al. also proposed a signature-policy SA-ABS scheme for threshold access structure. But Hu et al. [25] pointed out that Cui et al.’s scheme [24] was forgeable and then proposed a new SA-ABS scheme for monotonic access structure.Wang et al. studied the other side of ABS outsourcing and introduced Attribute-Based Server-Aided Verification Signature (ABSAVS) [26]. In ABSAVS, the signer outsources the verification workload to the server but does not outsource the signing workload. Wang et al. also proposed a ABSAVS scheme for threshold access structure. Recently, Chen et al. proposed a new ABSAVS scheme for tree access structure [27].Previous schemes are summarized and compared in Table1.Table 1
Previous schemes.
SchemeChen et al. [16]Mo et al. [17]Sun et al. [19]Huang et al. [20]Liu et al. [21]Ren and Jiang [22]Cui et al. [24]Hu et al. [25]Access structureThresholdLSSSThresholdCircuitThresholdThresholdThresholdLSSSTypeSPKPSPKPSPSPSPKP∗LSSS = Linear Secret Sharing Scheme, SP = signature-policy, KP = key-policy.


### 1.2. Contributions

The main contributions of this paper are as follows:(i)
We analyze the security of Mo et al.’s EOABS scheme [17] and show that it does not achieve any of the three security properties. The scheme is incorrect. The adversary can collude with the malicious S-CSP to forge valid signatures on any message and any attribute set. The S-CSP could trace the access structures used to generate the signatures.(ii)
We present more accurate security models for OABS. The main drawback of the previous security models is that the S-CSP’s attacks are not considered, and our security models make up for it.(iii)
We propose a simple but significant improvement to fix our attacks. The improved scheme achieves correctness, unforgeability, and perfect anonymity while keeping the efficiency almost unchanged. We also prove its security under the standard model.


### 1.3. Organization

The rest of this paper is organized as follows. Section2 presents preliminaries. Section 3 reviews Mo et al.’s EOABS scheme and analyzes its security. Section 4 presents a new definition and new security models for OABS. Section 5 proposes an improvement to fix our attacks with security proofs and performance analysis. Section 6 concludes this paper.


## 1.1. Related Works

While introducing OABS, Chen et al. [16] proposed two concrete OABS schemes. Their schemes are signature-policy OABS schemes with threshold access structures. After, Mo et al. [17] proposed an OABS scheme and applied it to the medical cloud. Mo et al.’s scheme is a key-policy OABS scheme that supports a more expressive monotonic access structure. Sun et al. [18, 19] introduced decentralization into OABS and proposed an outsourcing decentralized multiauthority attribute-based signature scheme. Their scheme is a signature-policy scheme for threshold access structure. In 2021, Huang et al. [20] proposed a new key-policy OABS scheme for circuits. Their scheme is a short signature scheme, and its final signature has only one element of the group.Chen et al.’s OABS model assumes that the S-CSP is honest-but-curious, i.e., the S-CSP always runs the algorithm honestly and outputs the semisignatures correctly, but the S-CSP may forge signatures. As a remedy for the overly strong assumption of S-CSP’s honesty, Chen et al. [16] discussed the accountability of OABS, which provides an audit function for S-CSP’s honesty. Liu et al. [21] studied OABS under the concept of server-assisted anonymous attribute authentication, added the correctness verification of the semisignature to OABS, and defined the outsourcing verifiability. After that, Ren and Jiang [22] formally introduced the concept of Verifiable Outsourced Attribute-Based Signatures (VOABS) with a concrete scheme supporting threshold access structure. Unfortunately, Uzunkol [23] presented two attacks on the verifiability of Ren et al.’s scheme. Moreover, one of the attacks enables the untrusted S-CSP to forge signatures.In 2018, Cui et al. [24] introduced a new notion of Server-Aided Attribute-Based Signature (SA-ABS). SA-ABS outsources both signing tasks and verification tasks to cloud service providers, while OABS only outsources signing tasks. This is the main difference between the two. Cui et al. also proposed a signature-policy SA-ABS scheme for threshold access structure. But Hu et al. [25] pointed out that Cui et al.’s scheme [24] was forgeable and then proposed a new SA-ABS scheme for monotonic access structure.Wang et al. studied the other side of ABS outsourcing and introduced Attribute-Based Server-Aided Verification Signature (ABSAVS) [26]. In ABSAVS, the signer outsources the verification workload to the server but does not outsource the signing workload. Wang et al. also proposed a ABSAVS scheme for threshold access structure. Recently, Chen et al. proposed a new ABSAVS scheme for tree access structure [27].Previous schemes are summarized and compared in Table1.Table 1
Previous schemes.
SchemeChen et al. [16]Mo et al. [17]Sun et al. [19]Huang et al. [20]Liu et al. [21]Ren and Jiang [22]Cui et al. [24]Hu et al. [25]Access structureThresholdLSSSThresholdCircuitThresholdThresholdThresholdLSSSTypeSPKPSPKPSPSPSPKP∗LSSS = Linear Secret Sharing Scheme, SP = signature-policy, KP = key-policy.


## 1.2. Contributions

The main contributions of this paper are as follows:(i)
We analyze the security of Mo et al.’s EOABS scheme [17] and show that it does not achieve any of the three security properties. The scheme is incorrect. The adversary can collude with the malicious S-CSP to forge valid signatures on any message and any attribute set. The S-CSP could trace the access structures used to generate the signatures.(ii)
We present more accurate security models for OABS. The main drawback of the previous security models is that the S-CSP’s attacks are not considered, and our security models make up for it.(iii)
We propose a simple but significant improvement to fix our attacks. The improved scheme achieves correctness, unforgeability, and perfect anonymity while keeping the efficiency almost unchanged. We also prove its security under the standard model.


## 1.3. Organization

The rest of this paper is organized as follows. Section2 presents preliminaries. Section 3 reviews Mo et al.’s EOABS scheme and analyzes its security. Section 4 presents a new definition and new security models for OABS. Section 5 proposes an improvement to fix our attacks with security proofs and performance analysis. Section 6 concludes this paper.


## 2. Preliminaries

Leta∈RA denote sampling a randomly from A. Let n=1,2,…,n for n∈ℕ. For any vectors v=v1,v2,…,vk∈ℤpk and w=w1,w2,…,wk∈ℤpk, their inner product vw=∑i=1kviwi.


### 2.1. Bilinear Map

LetG and GT be prime order p multiplication cyclic groups. Let e:G×G⟶GT be a map satisfying the following properties:(i)
For alla,b∈Rℤp and g1,g2∈RG, eg1a,g2b=eg1,g2ab.(ii)
There existg1,g2∈G such that eg1,g2≠1GT.(iii)
For allg1,g2∈G, eg1,g2 can be computed efficiently.


#### 2.1.1. Computational Diffie-Hellman Exponent (CDHE) Problem

Giveng,ga,ga2,…,gan,gan+2,…,ga2n to compute gan+1, where g∈G, a∈Rℤp [28].


### 2.2. Linear Secret Sharing Scheme

LetP=p1,p2,…,pn be a party set; a collection A of nonempty subsets of P is defined as an access structure. A set in A is an authorized set, and a set not in A is an unauthorized set. An access structure A⊆2P is monotone, if B∈A and B⊆C implies C∈A for all B,C.A linear secret sharing scheme (LSSS) for a monotone access structureA over ℤp is a matrix Ml×k with a function πi indicating the i th row of M as an attribute, and it satisfies the following properties:(i)
For any authorized setA∈A, there are constants wi∈Zpi∈I such that ∑i∈IwiMi=1,0,…,0, where I=i:πi∈A, and Mi is the i th row of the matrix M.(ii)
For any unauthorized setB∉A, there are no constants wi∈ℤpi∈I such that ∑i∈IwiMi=1,0,…,0, where I=i:πi∈B.The distribution and reconstruction algorithms of an LSSS are as follows:(i)
Distribution: it takes as inputs a matrixMl×k with a function π. and a secret s∈ℤp to be shared. It chooses r2,r3,…,rk∈Rℤp, sets v=s,r2,r3,…,rk∈ℤpk, and computes share set λi:λi=Mivi.(ii)
Reconstruction: it takes as inputs a matrixMl×k with a function π. and an authorized set A∈A with its share set λii∈I. It finds constants wi∈ℤpi∈I such that ∑i∈IwiMi=1,0,…,0 and then reconstructs the secret s=∑i∈Iwiλi.Lemma 1 (see [29]).
Suppose thatAis a monotone access structure with matrixMl×k. For any unauthorized setB∉A, there is a vectorw=−1,w2,…,wk∈ℤpksuch thatMiw=0for alli:πi∈B.


## 2.1. Bilinear Map

LetG and GT be prime order p multiplication cyclic groups. Let e:G×G⟶GT be a map satisfying the following properties:(i)
For alla,b∈Rℤp and g1,g2∈RG, eg1a,g2b=eg1,g2ab.(ii)
There existg1,g2∈G such that eg1,g2≠1GT.(iii)
For allg1,g2∈G, eg1,g2 can be computed efficiently.


### 2.1.1. Computational Diffie-Hellman Exponent (CDHE) Problem

Giveng,ga,ga2,…,gan,gan+2,…,ga2n to compute gan+1, where g∈G, a∈Rℤp [28].


## 2.1.1. Computational Diffie-Hellman Exponent (CDHE) Problem

Giveng,ga,ga2,…,gan,gan+2,…,ga2n to compute gan+1, where g∈G, a∈Rℤp [28].


## 2.2. Linear Secret Sharing Scheme

LetP=p1,p2,…,pn be a party set; a collection A of nonempty subsets of P is defined as an access structure. A set in A is an authorized set, and a set not in A is an unauthorized set. An access structure A⊆2P is monotone, if B∈A and B⊆C implies C∈A for all B,C.A linear secret sharing scheme (LSSS) for a monotone access structureA over ℤp is a matrix Ml×k with a function πi indicating the i th row of M as an attribute, and it satisfies the following properties:(i)
For any authorized setA∈A, there are constants wi∈Zpi∈I such that ∑i∈IwiMi=1,0,…,0, where I=i:πi∈A, and Mi is the i th row of the matrix M.(ii)
For any unauthorized setB∉A, there are no constants wi∈ℤpi∈I such that ∑i∈IwiMi=1,0,…,0, where I=i:πi∈B.The distribution and reconstruction algorithms of an LSSS are as follows:(i)
Distribution: it takes as inputs a matrixMl×k with a function π. and a secret s∈ℤp to be shared. It chooses r2,r3,…,rk∈Rℤp, sets v=s,r2,r3,…,rk∈ℤpk, and computes share set λi:λi=Mivi.(ii)
Reconstruction: it takes as inputs a matrixMl×k with a function π. and an authorized set A∈A with its share set λii∈I. It finds constants wi∈ℤpi∈I such that ∑i∈IwiMi=1,0,…,0 and then reconstructs the secret s=∑i∈Iwiλi.Lemma 1 (see [29]).
Suppose thatAis a monotone access structure with matrixMl×k. For any unauthorized setB∉A, there is a vectorw=−1,w2,…,wk∈ℤpksuch thatMiw=0for alli:πi∈B.


## 3. Cryptanalysis of Mo et al.’s EOABS Scheme

### 3.1. Review of Mo et al.’s EOABS Scheme

In this section, we review the EOABS scheme proposed by Mo et al. [17]. It comprises five algorithms and involves four entities: attribute authority (AA), S-CSP, signer, and verifier.(i)
Setup: SupposeU is the attribute universe, δ is the default attribute, and m is the maximal length of the message.(i)
The AA chooses two prime orderp cyclic groups G and GT with a bilinear map e:G×G⟶GT.(ii)
It selects a generatorg of G.(iii)
It selectsa,b∈Rℤp and computes Y=eg,ga+b.(iv)
It samplesu0,u1,⋯,um∈RG.(v)
It choosesT0∈RG and Tu∈RG, u∈U∪​δ.The system public parameters:(1)PP=g,p,G,GT,Y,T0,Tuu∈U∪δ,u0,u1,⋯,um,the master secret key:(2)MSK=a,b.(ii)
KeyGen: it takes as inputs the master secret keyMSK and an access structure A with its matrix Ml×k.(i)
It choosesv2,⋯,vk∈Rℤp, sets v=a,v2,⋯,vk, and computes λi=Miv,i∈l.(ii)
For eachi∈l, it chooses ri∈Rℤp and computes(3)di=gλiT0Tπiri,di′=gri,diu″=Tur,u∈U\πi.(iii)
It choosesrδ∈Rℤp and then computes(4)dδ=gbT0Tδrδ,dδ′=grδ.The outsourced key:(5)OSKA=di,di′,diu″.The signer’s signing key:(6)PSKA=dδ,dδ′(iii)
OutSign: it takes as inputs an attribute set A and an outsourced key OSKA.(i)
IfA∈A, the S-CSP finds wi:i∈I=i∈l:πi∈A such that ∑i∈IwiMi=1,0,…,0.(ii)
It choosesr, s∈Rℤp, and computes(7)σ1′=T0∏u∈ATur∏i∈Idi∏u∈A,u≠πidiu″wi,σ2′=gr∏i∈Idi'wi,σ3′=gs.The outsourced signatureσout=σ1,σ2,σ3.(iv)
Sign: it takes as inputsPSKA, σout, and M=m1m2⋯mm∈0,1m, and the signer selects sδ∈Rℤp and computers(8)σ1=dδT0Tδsδσ1′u0∏i=1muimis,σ2=σ2′dδ′gsδ,σ3=σ3′.The final signatureσ=σ1,σ2,σ3.(v)
Verify: it takes as inputsPP,σ,M, and the verifier checks whether(9)eg,σ1=Yeσ2,T0∏uεA∪​δTueσ3,u0∏i=1muimi.outputs 1 if it holds; otherwise it outputs 0.


### 3.2. Attacks on Mo et al.’s EOABS Scheme

Mo et al.’s EOABS scheme [17] does not achieve any of the three security properties, although it was proven to be secure under their security models.


#### 3.2.1. On Correctness

Mo et al.’s EOABS scheme is incorrect.In Mo et al.’s scheme(10)σ1′=T0∏u∈ATur∏i∈Idi∏u∈A,u≠πidiu″wi,=T0∏u∈ATur∏i∈IgλiT0Tπiri∏u∈A,u≠πiTuriwi,=g∑i∈IλiwiT0∏u∈ATur+∑i∈Iriwi,=gaT0∏u∈ATur+∑i∈Iriwi,σ2′=gr∏i∈Idi′wi,=gr∏i∈Igriwi,=gr+∑i∈Iriwi,σ1=dδT0Tδsδσ1′u0∏i=1muimis,=gbT0TδrδT0TδsδgaT0∏u∈ATur+∑i∈Iriwiu0∏i=1muimis,=ga+bT0Tδrδ+sδT0∏u∈ATur+∑i∈Iriwiu0∏i=1muimis,σ2=σ2′dδ′gsδ,=gr+∑i∈Iriwigrδgsδ,=grδ+sδgr+∑i∈Iriwi,σ3=gs.So we have(11)eg,σ1Yeσ2,T0∏u∈A∪δTueσ3,u0∏i=1muimi,=eg,ga+bT0Tδrδ+sδT0∏u∈ATur+∑i∈lriwiu0∏i=1muimisYegrδ+sδgr+∑i∈lriwi,T0∏u∈A∪δTuegs,u0∏i=1muimi,=eg,ga+beg,T0Tδrδ+sδeg,T0∏u∈ATur+∑i∈lriwieg,u0∏i=1muimisYegrδ+sδ,T0∏u∈A∪δTuegr+∑i∈lriwi,T0∏u∈A∪δTuegs,u0∏i=1muimi,=1egrδ+sδ,T0∏u∈A∪δTuegr+∑i∈lriwi,T0,Tδ≠1GT.Thus, the verification equation does not hold.


#### 3.2.2. Forgery Attack

Mo et al.’s EOABS scheme is forgeable. Adversaries can collude with the malicious S-CSP to forge signatures.Suppose thatA is an attribute set, A is adversary ℬ’s access structure, and A∉A. Adversary ℬ can collude with the malicious S-CSP to forge signatures for M,A as follows:(i)
The malicious S-CSP finds an outsourced keyOSKA' with access structure A' satisfied by A. It runs the OutSign algorithm with OSKA'and generates and sends the outsourced signature σout=σ1′,σ2′,σ3′for A to adversary ℬ.(ii)
With the outsourced signatureσout and message M, adversary ℬ runs the Sign algorithm with his signing key PSKA and then outputs a signature σ=σ1,σ2,σ3 on M and A.The attack above is executable for the following reasons:(i)
The signing keyPSKA is only related to the master secret key b and the default attribute δ, but not to the access structure A.(ii)
A∈A', so the outsourced signature σout for A can be generated correctly using OSKA′.Obviously, the output of adversaryℬ above is a valid signature on the message M and the attribute set A. But the attribute set A does not satisfy ℬ’s access structure A.


#### 3.2.3. On Anonymity

Mo et al.’s EOABS scheme does not achieve anonymity. The S-CSP can identify the corresponding access structures of the signatures as follows:(i)
The S-CSP stores all outsourced signatureσout with its corresponding access structure A into a list L in the form of σ1′,σ2′,σ3′,A.(ii)
Receiving a final signatureσ=σ1,σ2,σ3, the S-CSP outputs the corresponding access structure A if there is σ3′=σ3 in L.The attack above is practicable for the following reasons:(i)
The S-CSP needs to know the access structureA when using OSKA to generate outsourced signatures. So it can maintain the list L correctly.(ii)
Sinceσ3=σ3′, the S-CSP can correctly establish the link between the final signature σ and the outsourced signature σout.


## 3.1. Review of Mo et al.’s EOABS Scheme

In this section, we review the EOABS scheme proposed by Mo et al. [17]. It comprises five algorithms and involves four entities: attribute authority (AA), S-CSP, signer, and verifier.(i)
Setup: SupposeU is the attribute universe, δ is the default attribute, and m is the maximal length of the message.(i)
The AA chooses two prime orderp cyclic groups G and GT with a bilinear map e:G×G⟶GT.(ii)
It selects a generatorg of G.(iii)
It selectsa,b∈Rℤp and computes Y=eg,ga+b.(iv)
It samplesu0,u1,⋯,um∈RG.(v)
It choosesT0∈RG and Tu∈RG, u∈U∪​δ.The system public parameters:(1)PP=g,p,G,GT,Y,T0,Tuu∈U∪δ,u0,u1,⋯,um,the master secret key:(2)MSK=a,b.(ii)
KeyGen: it takes as inputs the master secret keyMSK and an access structure A with its matrix Ml×k.(i)
It choosesv2,⋯,vk∈Rℤp, sets v=a,v2,⋯,vk, and computes λi=Miv,i∈l.(ii)
For eachi∈l, it chooses ri∈Rℤp and computes(3)di=gλiT0Tπiri,di′=gri,diu″=Tur,u∈U\πi.(iii)
It choosesrδ∈Rℤp and then computes(4)dδ=gbT0Tδrδ,dδ′=grδ.The outsourced key:(5)OSKA=di,di′,diu″.The signer’s signing key:(6)PSKA=dδ,dδ′(iii)
OutSign: it takes as inputs an attribute set A and an outsourced key OSKA.(i)
IfA∈A, the S-CSP finds wi:i∈I=i∈l:πi∈A such that ∑i∈IwiMi=1,0,…,0.(ii)
It choosesr, s∈Rℤp, and computes(7)σ1′=T0∏u∈ATur∏i∈Idi∏u∈A,u≠πidiu″wi,σ2′=gr∏i∈Idi'wi,σ3′=gs.The outsourced signatureσout=σ1,σ2,σ3.(iv)
Sign: it takes as inputsPSKA, σout, and M=m1m2⋯mm∈0,1m, and the signer selects sδ∈Rℤp and computers(8)σ1=dδT0Tδsδσ1′u0∏i=1muimis,σ2=σ2′dδ′gsδ,σ3=σ3′.The final signatureσ=σ1,σ2,σ3.(v)
Verify: it takes as inputsPP,σ,M, and the verifier checks whether(9)eg,σ1=Yeσ2,T0∏uεA∪​δTueσ3,u0∏i=1muimi.outputs 1 if it holds; otherwise it outputs 0.


## 3.2. Attacks on Mo et al.’s EOABS Scheme

Mo et al.’s EOABS scheme [17] does not achieve any of the three security properties, although it was proven to be secure under their security models.


### 3.2.1. On Correctness

Mo et al.’s EOABS scheme is incorrect.In Mo et al.’s scheme(10)σ1′=T0∏u∈ATur∏i∈Idi∏u∈A,u≠πidiu″wi,=T0∏u∈ATur∏i∈IgλiT0Tπiri∏u∈A,u≠πiTuriwi,=g∑i∈IλiwiT0∏u∈ATur+∑i∈Iriwi,=gaT0∏u∈ATur+∑i∈Iriwi,σ2′=gr∏i∈Idi′wi,=gr∏i∈Igriwi,=gr+∑i∈Iriwi,σ1=dδT0Tδsδσ1′u0∏i=1muimis,=gbT0TδrδT0TδsδgaT0∏u∈ATur+∑i∈Iriwiu0∏i=1muimis,=ga+bT0Tδrδ+sδT0∏u∈ATur+∑i∈Iriwiu0∏i=1muimis,σ2=σ2′dδ′gsδ,=gr+∑i∈Iriwigrδgsδ,=grδ+sδgr+∑i∈Iriwi,σ3=gs.So we have(11)eg,σ1Yeσ2,T0∏u∈A∪δTueσ3,u0∏i=1muimi,=eg,ga+bT0Tδrδ+sδT0∏u∈ATur+∑i∈lriwiu0∏i=1muimisYegrδ+sδgr+∑i∈lriwi,T0∏u∈A∪δTuegs,u0∏i=1muimi,=eg,ga+beg,T0Tδrδ+sδeg,T0∏u∈ATur+∑i∈lriwieg,u0∏i=1muimisYegrδ+sδ,T0∏u∈A∪δTuegr+∑i∈lriwi,T0∏u∈A∪δTuegs,u0∏i=1muimi,=1egrδ+sδ,T0∏u∈A∪δTuegr+∑i∈lriwi,T0,Tδ≠1GT.Thus, the verification equation does not hold.


### 3.2.2. Forgery Attack

Mo et al.’s EOABS scheme is forgeable. Adversaries can collude with the malicious S-CSP to forge signatures.Suppose thatA is an attribute set, A is adversary ℬ’s access structure, and A∉A. Adversary ℬ can collude with the malicious S-CSP to forge signatures for M,A as follows:(i)
The malicious S-CSP finds an outsourced keyOSKA' with access structure A' satisfied by A. It runs the OutSign algorithm with OSKA'and generates and sends the outsourced signature σout=σ1′,σ2′,σ3′for A to adversary ℬ.(ii)
With the outsourced signatureσout and message M, adversary ℬ runs the Sign algorithm with his signing key PSKA and then outputs a signature σ=σ1,σ2,σ3 on M and A.The attack above is executable for the following reasons:(i)
The signing keyPSKA is only related to the master secret key b and the default attribute δ, but not to the access structure A.(ii)
A∈A', so the outsourced signature σout for A can be generated correctly using OSKA′.Obviously, the output of adversaryℬ above is a valid signature on the message M and the attribute set A. But the attribute set A does not satisfy ℬ’s access structure A.


### 3.2.3. On Anonymity

Mo et al.’s EOABS scheme does not achieve anonymity. The S-CSP can identify the corresponding access structures of the signatures as follows:(i)
The S-CSP stores all outsourced signatureσout with its corresponding access structure A into a list L in the form of σ1′,σ2′,σ3′,A.(ii)
Receiving a final signatureσ=σ1,σ2,σ3, the S-CSP outputs the corresponding access structure A if there is σ3′=σ3 in L.The attack above is practicable for the following reasons:(i)
The S-CSP needs to know the access structureA when using OSKA to generate outsourced signatures. So it can maintain the list L correctly.(ii)
Sinceσ3=σ3′, the S-CSP can correctly establish the link between the final signature σ and the outsourced signature σout.


## 3.2.1. On Correctness

Mo et al.’s EOABS scheme is incorrect.In Mo et al.’s scheme(10)σ1′=T0∏u∈ATur∏i∈Idi∏u∈A,u≠πidiu″wi,=T0∏u∈ATur∏i∈IgλiT0Tπiri∏u∈A,u≠πiTuriwi,=g∑i∈IλiwiT0∏u∈ATur+∑i∈Iriwi,=gaT0∏u∈ATur+∑i∈Iriwi,σ2′=gr∏i∈Idi′wi,=gr∏i∈Igriwi,=gr+∑i∈Iriwi,σ1=dδT0Tδsδσ1′u0∏i=1muimis,=gbT0TδrδT0TδsδgaT0∏u∈ATur+∑i∈Iriwiu0∏i=1muimis,=ga+bT0Tδrδ+sδT0∏u∈ATur+∑i∈Iriwiu0∏i=1muimis,σ2=σ2′dδ′gsδ,=gr+∑i∈Iriwigrδgsδ,=grδ+sδgr+∑i∈Iriwi,σ3=gs.So we have(11)eg,σ1Yeσ2,T0∏u∈A∪δTueσ3,u0∏i=1muimi,=eg,ga+bT0Tδrδ+sδT0∏u∈ATur+∑i∈lriwiu0∏i=1muimisYegrδ+sδgr+∑i∈lriwi,T0∏u∈A∪δTuegs,u0∏i=1muimi,=eg,ga+beg,T0Tδrδ+sδeg,T0∏u∈ATur+∑i∈lriwieg,u0∏i=1muimisYegrδ+sδ,T0∏u∈A∪δTuegr+∑i∈lriwi,T0∏u∈A∪δTuegs,u0∏i=1muimi,=1egrδ+sδ,T0∏u∈A∪δTuegr+∑i∈lriwi,T0,Tδ≠1GT.Thus, the verification equation does not hold.


## 3.2.2. Forgery Attack

Mo et al.’s EOABS scheme is forgeable. Adversaries can collude with the malicious S-CSP to forge signatures.Suppose thatA is an attribute set, A is adversary ℬ’s access structure, and A∉A. Adversary ℬ can collude with the malicious S-CSP to forge signatures for M,A as follows:(i)
The malicious S-CSP finds an outsourced keyOSKA' with access structure A' satisfied by A. It runs the OutSign algorithm with OSKA'and generates and sends the outsourced signature σout=σ1′,σ2′,σ3′for A to adversary ℬ.(ii)
With the outsourced signatureσout and message M, adversary ℬ runs the Sign algorithm with his signing key PSKA and then outputs a signature σ=σ1,σ2,σ3 on M and A.The attack above is executable for the following reasons:(i)
The signing keyPSKA is only related to the master secret key b and the default attribute δ, but not to the access structure A.(ii)
A∈A', so the outsourced signature σout for A can be generated correctly using OSKA′.Obviously, the output of adversaryℬ above is a valid signature on the message M and the attribute set A. But the attribute set A does not satisfy ℬ’s access structure A.


## 3.2.3. On Anonymity

Mo et al.’s EOABS scheme does not achieve anonymity. The S-CSP can identify the corresponding access structures of the signatures as follows:(i)
The S-CSP stores all outsourced signatureσout with its corresponding access structure A into a list L in the form of σ1′,σ2′,σ3′,A.(ii)
Receiving a final signatureσ=σ1,σ2,σ3, the S-CSP outputs the corresponding access structure A if there is σ3′=σ3 in L.The attack above is practicable for the following reasons:(i)
The S-CSP needs to know the access structureA when using OSKA to generate outsourced signatures. So it can maintain the list L correctly.(ii)
Sinceσ3=σ3′, the S-CSP can correctly establish the link between the final signature σ and the outsourced signature σout.


## 4. Outsourced Attribute-Based Signature

The attacks above suggest that the security models in [17] are not conforming to the actual. Their models are similar to the nonoutsourced models [2, 30]. We present more accurate security models in this section.


### 4.1. Definition

An outsourced attribute-based signature (OABS) scheme is composed of the following algorithms.(i)
Setup1λ⟶pp,msk. It takes the security parameter λ as input and returns the public parameters pp and master key msk.(ii)
KeyGenpp,msk,A,fu⟶OSKAfu,PSKAfu. It takes the public parameters pp, master key msk, and an access structure A with a flag fu as inputs and returns the outsourced key OSKAfu and private signing key PSKAfu.(iii)
Signoutpp,OSKAfu,A⟶σout. The outsourced signing algorithm takes the public parameters pp, an outsourced key OSKAfu, and an attribute set A∈A as inputs and returns an outsourced signature σout.(iv)
Signpp,PSKAfu,M,A,σout⟶σ. The signing algorithm takes the public parameters pp, a private signing key PSKAfu, a message M, and an outsourced signature σout as inputs and returns a signature σ for M,A.(v)
Verifypp,σ,M,A⟶1/0. It takes the public parameters pp, a signature σ, a message M, and an attribute set A as inputs. If σ is valid, it returns 1; otherwise, it returns 0.Note: The flagfu we introduced above is just an identifier used to match the outsourced key and private signing key correctly. It does not take part in any operation and does not affect efficiency and security.


### 4.2. Security

In this subsection, we present enhanced formal security models for OABS.Definition 1 (correctness).
An OABS scheme is correct, if(12)PrVerifypp,σ,M,A=1pp,msk←Setup1λ,OSKAfu,PSKAfu←KeyGenpp,msk,A,fu,σout←Signoutpp,OSKAfu,A,A∈A,σ←Signpp,PSKAfu,M,A,σout=1,for any messageM, any access structureA, and any attribute setAsuch thatA∈A.


#### 4.2.1. Unforgeability

A trivial requirement for the unforgeability is that the adversary cannot possess the key required for signing because anyone who has the signing key can run the signing algorithm to generate a valid signature. In the scenario of outsourced signatures, all outsourced keys are sent to the S-CSP, and the S-CSP is not necessarily trusted. Therefore, it should be assumed that the adversary may have all the outsourced keys and only restrict him from possessing the required private signing key. To this end, we need to provide different oracles for the outsourced key and the private signing key. In addition, since the adversary is permitted to obtain all outsourced keys and can generate outsourced signatures by himself, he need not make any outsourced signing oracle query.The unforgeability model of Mo et al. [17] does not reflect the above requirements and is therefore inaccurate. We present a more accurate unforgeability model in the following. There are two main differences between our model and Mo et al.’s model: First, our model provides the adversary with two oracles, OSK-Oracle and SK-Oracle, while their model only provides one oracle, KeyGen-Oracle. Second, our model restricts the adversary from possessing any private signing key of the access structure satisfied by the challenge attribute. In contrast, their model does not prohibit the adversary from obtaining the private signing key. These two improvements reflect the ideas mentioned above.(1) GAME 1 (EUF-sA-CMA).(i)
Initialization. Adversary A selects and sends a challenge attribute set A∗ to challenger C.(ii)
Setup. C generates and sends the public parameters pp to A.(iii)
OSK-Oracle. A chooses and sends an access structure A with a flag fu to C. C returns an outsourced key OSKAfu to A.(iv)
SK-Oracle. A chooses and sends an access structure A with a flag fu to C. C returns a private signing key PSKAfu to A.(v)
Sign-Oracle:A chooses and sends a message M, an attribute set A, and an outsourced signature σout with a flag fu to C. C returns a signature σ to A.(vi)
Forgery. AdversaryA outputs a triple σ∗,M∗,A∗.AdversaryA wins the game, if(i)
M∗,A∗ was not queried to Sign-Oracle;(ii)
any access structureA queried to SK-Oracle is not satisfied by A∗;(iii)
Verifypp,σ∗,M∗,A∗=1.AdversaryA’s advantage is defined as its probability of winning the above game, denoted as AdvOABS,AEUF−sA−CMA1λ.Definition 2 (unforgeability).
An OABS scheme is existentially unforgeable under selective attribute set but adaptive chosen message attack, ifAdvOABS,AEUF−sA−CMA1λis negligible in the security parameterλfor any PPT adversaryA.


#### 4.2.2. Perfect Anonymity

In the outsourced attribute-based signature, the untrusted S-CSP generates the outsourced signature, and then the signer generates the final signature. This is the essential difference from the general attribute-based signature, which must be reflected in the security model. In the model of Mo et al., the outsourced signature is generated by the challenger, and the adversary has no way of knowing it. This makes it impossible for the adversary to determine the access structure through the outsourced signature. But in the outsourced attribute-based signature scheme, the outsourced signatures are calculated by the S-CSP, so that the S-CSP may track the access structures corresponding to the signatures through the outsourced signatures. This is why Mo et al.’s scheme is anonymous under their model, but the above attack exists. In our model, the outsourced signatures are generated by the adversary instead and then sent to the challenger. Under such a model, Mo et al.’s scheme does not achieve anonymity. Our model reflects the difference between outsourced attribute-based signatures and general attribute-based signatures.We formalize our definition by a game between challengerC and adversary A as follows.(1) GAME 2 (Perfect Anonymity).(i)
Setup. It is the same as that of GAME 1.(ii)
Phase 1. The adversary is allowed to request OSK-Oracle, SK-Oracle, and Sign-Oracle for any access structure or message he/she chooses. OSK-Oracle, SK-Oracle, and Sign-Oracle are the same as those of GAME 1.(iii)
Challenge.(i)
AdversaryA chooses a message M, an attribute set A, and two challenge access structures A0 and A1 such that A∈A0 and A∈A1 and generates two outsourced signatures σout0 and σout1 using outsourced keys OSKA0fu0 and OSKA1fu1, respectively. Then he sends M,A,A0,A1,σout0,σout1,fu0,fu1 to challenger C.(ii)
C flips a fair coin b∈0,1, generates a signature σb on message M and attribute set A using the signing key PSKAbfub, and then returns σb to A.(iv)
Phase 2. As in Phase 1, the adversary can continue to request OSK-Oracle, SK-Oracle, and Sign-Oracle for any access structure (including A0 and A1) or message he/she chooses.(v)
Guess. A outputs a bit b′∈0,1.The advantage ofA is defined as(13)AdvOABS,APerAnon1λ=Prb′=b−12.Definition 3 (perfect anonymity).
An OABS scheme is perfect anonymous, if for any adversaryAthe advantageAdvOABS,APerAnon1λis negligible for the security parameterλ.


## 4.1. Definition

An outsourced attribute-based signature (OABS) scheme is composed of the following algorithms.(i)
Setup1λ⟶pp,msk. It takes the security parameter λ as input and returns the public parameters pp and master key msk.(ii)
KeyGenpp,msk,A,fu⟶OSKAfu,PSKAfu. It takes the public parameters pp, master key msk, and an access structure A with a flag fu as inputs and returns the outsourced key OSKAfu and private signing key PSKAfu.(iii)
Signoutpp,OSKAfu,A⟶σout. The outsourced signing algorithm takes the public parameters pp, an outsourced key OSKAfu, and an attribute set A∈A as inputs and returns an outsourced signature σout.(iv)
Signpp,PSKAfu,M,A,σout⟶σ. The signing algorithm takes the public parameters pp, a private signing key PSKAfu, a message M, and an outsourced signature σout as inputs and returns a signature σ for M,A.(v)
Verifypp,σ,M,A⟶1/0. It takes the public parameters pp, a signature σ, a message M, and an attribute set A as inputs. If σ is valid, it returns 1; otherwise, it returns 0.Note: The flagfu we introduced above is just an identifier used to match the outsourced key and private signing key correctly. It does not take part in any operation and does not affect efficiency and security.


## 4.2. Security

In this subsection, we present enhanced formal security models for OABS.Definition 1 (correctness).
An OABS scheme is correct, if(12)PrVerifypp,σ,M,A=1pp,msk←Setup1λ,OSKAfu,PSKAfu←KeyGenpp,msk,A,fu,σout←Signoutpp,OSKAfu,A,A∈A,σ←Signpp,PSKAfu,M,A,σout=1,for any messageM, any access structureA, and any attribute setAsuch thatA∈A.


### 4.2.1. Unforgeability

A trivial requirement for the unforgeability is that the adversary cannot possess the key required for signing because anyone who has the signing key can run the signing algorithm to generate a valid signature. In the scenario of outsourced signatures, all outsourced keys are sent to the S-CSP, and the S-CSP is not necessarily trusted. Therefore, it should be assumed that the adversary may have all the outsourced keys and only restrict him from possessing the required private signing key. To this end, we need to provide different oracles for the outsourced key and the private signing key. In addition, since the adversary is permitted to obtain all outsourced keys and can generate outsourced signatures by himself, he need not make any outsourced signing oracle query.The unforgeability model of Mo et al. [17] does not reflect the above requirements and is therefore inaccurate. We present a more accurate unforgeability model in the following. There are two main differences between our model and Mo et al.’s model: First, our model provides the adversary with two oracles, OSK-Oracle and SK-Oracle, while their model only provides one oracle, KeyGen-Oracle. Second, our model restricts the adversary from possessing any private signing key of the access structure satisfied by the challenge attribute. In contrast, their model does not prohibit the adversary from obtaining the private signing key. These two improvements reflect the ideas mentioned above.(1) GAME 1 (EUF-sA-CMA).(i)
Initialization. Adversary A selects and sends a challenge attribute set A∗ to challenger C.(ii)
Setup. C generates and sends the public parameters pp to A.(iii)
OSK-Oracle. A chooses and sends an access structure A with a flag fu to C. C returns an outsourced key OSKAfu to A.(iv)
SK-Oracle. A chooses and sends an access structure A with a flag fu to C. C returns a private signing key PSKAfu to A.(v)
Sign-Oracle:A chooses and sends a message M, an attribute set A, and an outsourced signature σout with a flag fu to C. C returns a signature σ to A.(vi)
Forgery. AdversaryA outputs a triple σ∗,M∗,A∗.AdversaryA wins the game, if(i)
M∗,A∗ was not queried to Sign-Oracle;(ii)
any access structureA queried to SK-Oracle is not satisfied by A∗;(iii)
Verifypp,σ∗,M∗,A∗=1.AdversaryA’s advantage is defined as its probability of winning the above game, denoted as AdvOABS,AEUF−sA−CMA1λ.Definition 2 (unforgeability).
An OABS scheme is existentially unforgeable under selective attribute set but adaptive chosen message attack, ifAdvOABS,AEUF−sA−CMA1λis negligible in the security parameterλfor any PPT adversaryA.


### 4.2.2. Perfect Anonymity

In the outsourced attribute-based signature, the untrusted S-CSP generates the outsourced signature, and then the signer generates the final signature. This is the essential difference from the general attribute-based signature, which must be reflected in the security model. In the model of Mo et al., the outsourced signature is generated by the challenger, and the adversary has no way of knowing it. This makes it impossible for the adversary to determine the access structure through the outsourced signature. But in the outsourced attribute-based signature scheme, the outsourced signatures are calculated by the S-CSP, so that the S-CSP may track the access structures corresponding to the signatures through the outsourced signatures. This is why Mo et al.’s scheme is anonymous under their model, but the above attack exists. In our model, the outsourced signatures are generated by the adversary instead and then sent to the challenger. Under such a model, Mo et al.’s scheme does not achieve anonymity. Our model reflects the difference between outsourced attribute-based signatures and general attribute-based signatures.We formalize our definition by a game between challengerC and adversary A as follows.(1) GAME 2 (Perfect Anonymity).(i)
Setup. It is the same as that of GAME 1.(ii)
Phase 1. The adversary is allowed to request OSK-Oracle, SK-Oracle, and Sign-Oracle for any access structure or message he/she chooses. OSK-Oracle, SK-Oracle, and Sign-Oracle are the same as those of GAME 1.(iii)
Challenge.(i)
AdversaryA chooses a message M, an attribute set A, and two challenge access structures A0 and A1 such that A∈A0 and A∈A1 and generates two outsourced signatures σout0 and σout1 using outsourced keys OSKA0fu0 and OSKA1fu1, respectively. Then he sends M,A,A0,A1,σout0,σout1,fu0,fu1 to challenger C.(ii)
C flips a fair coin b∈0,1, generates a signature σb on message M and attribute set A using the signing key PSKAbfub, and then returns σb to A.(iv)
Phase 2. As in Phase 1, the adversary can continue to request OSK-Oracle, SK-Oracle, and Sign-Oracle for any access structure (including A0 and A1) or message he/she chooses.(v)
Guess. A outputs a bit b′∈0,1.The advantage ofA is defined as(13)AdvOABS,APerAnon1λ=Prb′=b−12.Definition 3 (perfect anonymity).
An OABS scheme is perfect anonymous, if for any adversaryAthe advantageAdvOABS,APerAnon1λis negligible for the security parameterλ.


## 4.2.1. Unforgeability

A trivial requirement for the unforgeability is that the adversary cannot possess the key required for signing because anyone who has the signing key can run the signing algorithm to generate a valid signature. In the scenario of outsourced signatures, all outsourced keys are sent to the S-CSP, and the S-CSP is not necessarily trusted. Therefore, it should be assumed that the adversary may have all the outsourced keys and only restrict him from possessing the required private signing key. To this end, we need to provide different oracles for the outsourced key and the private signing key. In addition, since the adversary is permitted to obtain all outsourced keys and can generate outsourced signatures by himself, he need not make any outsourced signing oracle query.The unforgeability model of Mo et al. [17] does not reflect the above requirements and is therefore inaccurate. We present a more accurate unforgeability model in the following. There are two main differences between our model and Mo et al.’s model: First, our model provides the adversary with two oracles, OSK-Oracle and SK-Oracle, while their model only provides one oracle, KeyGen-Oracle. Second, our model restricts the adversary from possessing any private signing key of the access structure satisfied by the challenge attribute. In contrast, their model does not prohibit the adversary from obtaining the private signing key. These two improvements reflect the ideas mentioned above.(1) GAME 1 (EUF-sA-CMA).(i)
Initialization. Adversary A selects and sends a challenge attribute set A∗ to challenger C.(ii)
Setup. C generates and sends the public parameters pp to A.(iii)
OSK-Oracle. A chooses and sends an access structure A with a flag fu to C. C returns an outsourced key OSKAfu to A.(iv)
SK-Oracle. A chooses and sends an access structure A with a flag fu to C. C returns a private signing key PSKAfu to A.(v)
Sign-Oracle:A chooses and sends a message M, an attribute set A, and an outsourced signature σout with a flag fu to C. C returns a signature σ to A.(vi)
Forgery. AdversaryA outputs a triple σ∗,M∗,A∗.AdversaryA wins the game, if(i)
M∗,A∗ was not queried to Sign-Oracle;(ii)
any access structureA queried to SK-Oracle is not satisfied by A∗;(iii)
Verifypp,σ∗,M∗,A∗=1.AdversaryA’s advantage is defined as its probability of winning the above game, denoted as AdvOABS,AEUF−sA−CMA1λ.Definition 2 (unforgeability).
An OABS scheme is existentially unforgeable under selective attribute set but adaptive chosen message attack, ifAdvOABS,AEUF−sA−CMA1λis negligible in the security parameterλfor any PPT adversaryA.


## 4.2.2. Perfect Anonymity

In the outsourced attribute-based signature, the untrusted S-CSP generates the outsourced signature, and then the signer generates the final signature. This is the essential difference from the general attribute-based signature, which must be reflected in the security model. In the model of Mo et al., the outsourced signature is generated by the challenger, and the adversary has no way of knowing it. This makes it impossible for the adversary to determine the access structure through the outsourced signature. But in the outsourced attribute-based signature scheme, the outsourced signatures are calculated by the S-CSP, so that the S-CSP may track the access structures corresponding to the signatures through the outsourced signatures. This is why Mo et al.’s scheme is anonymous under their model, but the above attack exists. In our model, the outsourced signatures are generated by the adversary instead and then sent to the challenger. Under such a model, Mo et al.’s scheme does not achieve anonymity. Our model reflects the difference between outsourced attribute-based signatures and general attribute-based signatures.We formalize our definition by a game between challengerC and adversary A as follows.(1) GAME 2 (Perfect Anonymity).(i)
Setup. It is the same as that of GAME 1.(ii)
Phase 1. The adversary is allowed to request OSK-Oracle, SK-Oracle, and Sign-Oracle for any access structure or message he/she chooses. OSK-Oracle, SK-Oracle, and Sign-Oracle are the same as those of GAME 1.(iii)
Challenge.(i)
AdversaryA chooses a message M, an attribute set A, and two challenge access structures A0 and A1 such that A∈A0 and A∈A1 and generates two outsourced signatures σout0 and σout1 using outsourced keys OSKA0fu0 and OSKA1fu1, respectively. Then he sends M,A,A0,A1,σout0,σout1,fu0,fu1 to challenger C.(ii)
C flips a fair coin b∈0,1, generates a signature σb on message M and attribute set A using the signing key PSKAbfub, and then returns σb to A.(iv)
Phase 2. As in Phase 1, the adversary can continue to request OSK-Oracle, SK-Oracle, and Sign-Oracle for any access structure (including A0 and A1) or message he/she chooses.(v)
Guess. A outputs a bit b′∈0,1.The advantage ofA is defined as(13)AdvOABS,APerAnon1λ=Prb′=b−12.Definition 3 (perfect anonymity).
An OABS scheme is perfect anonymous, if for any adversaryAthe advantageAdvOABS,APerAnon1λis negligible for the security parameterλ.


## 5. Improvement

In this section, we propose a simple but significant improvement to fix our attacks. The ideas behind our improvement are as follows.In Mo et al.’s scheme, the outsourced key and private signing key are independently generated with secret valuesa and b. Using such two keys to generate a signature, the public key Y=eg,ga+b will be canceled out in the verification equation. Since the outsourced key and the private signing key are independent of each other, using the outsourced key of Alice and the private signing key of Bob, one can also generate a correct signature, and the public key can also be canceled out in the verification equation. Our improvement fixes this shortcoming. We set α∈Rℤp as the master private key and Y=eg,gα as the public key and then use a∈Rℤp and b=α−a to generate the outsourced key and private signing key, respectively. In this way, everyone’s outsourced key and private signing key are associated. The outsourced key and the private signing key of different users cannot be combined to generate a correct signature. If Alice’s outsourced key and Bob’s private signing key are combined to generate a signature, then eg,gaA+α−aB will appear in the verification equation, which is not equal to the public key eg,gα. The signature will not be accepted as a valid signature.In Mo et al.’s scheme,σ3′ is not blinded but directly used as a component of the final signature. This allows the adversary to track the access structure used to generate the signature. To ensure anonymity, the outsourced signature must be blinded. But the computation cost of blinding σ3′ is the same as that of computing σ3′. Therefore, in our improved scheme, the user computes σ4 by himself, and the server no longer computes σ3′. σ4 in our improvement is equivalent to σ3 in Mo et al.’s scheme.We splitσ1′ into σ11′ and σ12′, and σ2 into σ2 and σ3, all for the signature to satisfy the verification equation.


### 5.1. Improved Scheme

(i)
Setup: it is the same as Mo et al.’s EOABS scheme, except thatY=eg,gα and MSK=α∈RZp.(ii)
KeyGen: it is the same as Mo et al.’s EOABS scheme but choosesa∈Rℤp and sets b=α−a.(iii)
OutSign: it takes as the inputs an attribute setA, an outsourced key OSKAfu with matrix MA, and a flag fu.(i)
IfA∈A, the S-CSP finds wi:i∈IA=i∈lA:πi∈A such that ∑i∈IAwiMAi=1,0,…,0.(ii)
computes(14)σ11′=T0∏u∈ATu,σ12′=∏i∈IAdi∏u∈A,u≠πidiu″wi,σ2′=∏i∈IAdi′wi.The outsourced signatureσout=σ11′,σ12′,σ2′.(iv)
Sign: with a private signing keyPSKAfu, a message M=m1m2…mm, and an outsourced signature σout, the signer selects r,s,sδ∈Rℤp and computes(15)σ1=dδT0Tδsδσ′11rσ12′u0∏i=1muimis,σ2=grσ2′,σ3=dδ′gsδ,σ4=gs.The final signature onM,A is σ=σ1,σ2,σ3,σ4.(v)
Verify: withPP,σ,M,A, the verifier checks whether(16)eg,σ1=Yeσ2,T0∏u∈ATueσ3,T0Tδeσ4,u0∏i=1muimi.If the equation holds, the verifier outputs 1. Otherwise, it outputs 0.


### 5.2. Proofs of Security

Theorem 1 (correctness).
The improved scheme is correct.Proof.
WhenA∈A, we can find wi:i∈IA such that(17)∑i∈IAwiMAi=1,0,…,0,and then(18)∑i∈IAwiλi=∑i∈IAwiMAiv=a.
So(19)eg,σ1=eg,gbT0TδrδT0TδsδT0∏u∈ATur∏i∈IAdi∏u∈A,u≠πidiu″wiu0∏i=1muimis,=eg,gα−aT0Tδrδ+sδT0∏u∈ATur∏i∈IAgλiT0Tπiri∏u∈A,u≠πiTuriwiu0∏i=1muimis,=eg,gα−ag∑i∈IAwiλiT0Tδrδ+sδT0∏u∈ATur+∑i∈IAriwiu0∏i=1muimis,=eg,gαeg,T0Tδrδ+sδeg,T0∏u∈ATur+∑i∈IAriwieg,u0∏i=1muimis,=Yeσ3,T0Tδegr+∑i∈IAriwi,T0∏u∈ATueσ4,u0∏i=1muimi,=Yeσ3,T0Tδegr∏i∈IAgriwi,T0∏u∈ATueσ4,u0∏i=1muimi,=Yeσ3,T0Tδeσ2,T0∏u∈ATueσ4,u0∏i=1muimi.
The verification equation holds, and the improved scheme is correct.Theorem 2 (unforgeability).
The improved scheme is existentially unforgeable. If an adversaryAcan win GAME 1 with advantageϵ, then there exists an algorithmℬthat solves the CDHE problem with probabilityϵ′≥ϵ/8qsm+1, whereqsis the maximum number of Sign-Oracle queries and m is the length of the message.Proof.
In the following,A is an adversary with advantage ϵ, and C is the challenger to the CDHE problem. We build ℬ as follows, which uses A to solve the CDHE problem.
Without loss of generality, we assume the attribute universeU=1,2,…,n. ℬ maintains an initially empty list Lkey.(i)
CDHE Problem Gen.(i)
C chooses two prime order p multiplicative cyclic groups G, GT and a bilinear map e:G×G⟶GT.(ii)
chooses a generatorg∈G and a∈Rℤp and computes g,ga,ga2,…,gan,gan+2,…,ga2n.(iii)
sendsp,G,GT,e,g,gi=gaii=1,i≠n+12n to ℬ.(ii)
Init Phase. A chooses and sends A∗ to ℬ.(iii)
Setup.(i)
ℬ chooses a′,t0∈Rℤp and tu∈Rℤp for all u∈U, and computes(20)Tu=gtugn+1−u:u∈U,T0=gt0∏u∈A∗Tu−1,Tδ=gt0T0−1.(ii)
computesY=eg,ga′eg1,gn (i.e., it sets the master secret key α=a′+an+1 implicitly).(iii)
LetlM=4qs, choosing kM∈Rm, picking x′∈RℤlM, y′∈Rℤp, x^i∈RℤlM:i∈m, y^i∈Rℤp:i∈m, and computing(21)u0=gnp−lMkM+x′gy′,ui=gnx^igy^i:i∈m.(iv)
sends the public parameterspp=p,g,G,GT,Y,e,T0,Tu:u∈U∪δ,u0,u1,…,um to A.(iv)
OSK-Oracle. Assume A queries an outsourced key on access structure A with the matrix MA of size lA×kA and flag fu. If A,fu in Lkey, it returns the corresponding outsourced key OSKAfu to A. Otherwise, we compute the keys as follows:(i)
IfA∗∈A:(i) setsPSKAfu=⊥ (A cannot query any private signing key for the access structure A satisfied by A∗).(ii) runs KeyGen to getOSKAfu.(iii) returnsOSKAfu to A.(iv) addsOSKAfu,⊥,A,fu into the key list Lkey.(ii)
IfA∗∉A:(i) finds a vectorw=−1,w2,…,wkA∈ℤpkA such that MAiw=0 for each i:πi∈A∗, where MAi is the i th row of MA (Lemma 1).(ii) choosesv1,v2,…,vkA∈Rℤp, and sets v′=0,v2,…,vkA.(iii) For alli∈lA,(i)
ifπi∈A∗, choose ri∈Rℤp and compute(22)di=gMAiv′T0Tπiri,di′=gri,diu″=Turi:u∈U/πi,(ii)
ifπi∉A∗, choose ri′∈Rℤp and compute(23)di=gMAiv′−v1wT0Tπiri′gπi−t0+tπi∏u∈A∗gπitugn+1−u+πi−MAiwdi′=gri′gπi−MAiwdiu″=Turi′gπitugn+1−u+πiMAiw,u∈U/πi.(iv)
selectsrδ∈Rℤp and computes dδ=ga′−v1T0Tδrδ, dδ′=grδ.(v)
returnsOSKAfu=di,di′,diu″i∈lA,u∈U\πi to A.(vi)
addsOSKAfu,PSKAfu=dδ,dδ′,A,fu into the key list Lkey.(iii)
SK-Oracle. It is the same as the OSK-Oracle above, except that it returns a private signing keyPSKAfu to A.Claim 1.
The keys simulated above are correct.Proof.
IfA∗∈A, and OSKAfu is generated by KeyGen, it is correct certainly.
IfA∗∉A, according to Lemma 1, we can find a vector w=−1,w2,…,wkA∈ℤpkA such that MAiw=0 for each i:πi∈A∗. We prove OSKAfu is a correct outsourced key with v=−v1+an+1w+v′ as follows:(i)
Whenπi∈A∗, MAiw=0, and λi=MAiv=−v1+an+1MAiw+MAiv′=MAiv′, we have(24)di=gMAiv′T0Tπiri=gλiT0Tπiri,di′=gri,diu″=Turi:u∈U/πi.(ii)
Whenπi∉A∗, we have λi=MAiv=MAiv′−v1w−an+1MAiw, and(25)di=gMAiv′−v1wT0Tπiri′gπi−t0+tπi∏u∈A∗gπitugn+1−u+πi−MAiw,=gMAiv′−v1wT0Tπiri′gaπit0MAiwgaπitπiMAiw,∏u∈A∗gaπitugn+1−uaπi−MAiwgan+1MAiwg−an+1MAiw,=gMAiv′−v1w−an+1MAiwT0Tπiri′gt0∏u∈A∗gtugn+1−u−1aπiMAiw,gaπitπiMAiwgan+1a−πiaπiMAiw,=gλiT0Tπiri′T0aπiMAiwgtπign+1−πiaπiMAiw,=gλiT0Tπiri′T0TπiaπiMAiw,=gλiT0Tπiri,di′=gri′gπiMAiw=gri,diu″=Turi′gπitugn+1−u+πiMAiw=Turi′gtugn+1−uaπiMAiw=Turi,whereri=ri′+aπiMAiw.
This concludes thatOSKAfu=di,di′,diu″i∈lA,u∈U/πi is a correct outsourced key.
Since the first component ofv is v1+an+1, then(26)α−v1+an+1=a′+an+1−v1+an+1=a′−v1.
ThusPSKAfu=dδ=ga′−v1T0Tδrδ,dδ′=grδ is a correct private signing key.(vi)
Sign-Oracle. It takes M,A,σout,fu as inputs.Define functions(27)FM=p−lMKM+x′+∑i=1mx^imi,JM=y′+∑i=1my^imi,KM=0,ifx′+∑i=1mx^i≡0modlM,1,otherwise.IfKM=0, it aborts. Otherwise, ℬ chooses μδ,s′,r′∈ℤp, and computes and returns(28)σ1=T0Tδrδ+μδga′T0∏u∈ATur′gnFMgJMs′g1−JM/FM,σ2=gr′,σ3=gμδ+rδ,σ4=gs′g1−1/FM.Claim 2.
The simulated signatures are correct.Proof.
By simple calculating, we haveu0∏i=1muimi=gnFMgJM. If KM≠0, then FM≠0modp, because we can assume lMm+1<p for any reasonable values of p,m, and lM. Then, we have(29)σ1=T0Tδrδ+μδga′T0∏u∈ATur′gnFMgJMs′g1−JM/FM,=T0Tδrδ+μδga′gan+1g−an+1T0∏u∈ATur′gnFMgJMs′g1−JM/FM,=T0Tδrδ+μδga′+an+1T0∏u∈ATur′gnFMgJMs′gn−aFM/FMg−aFM/FM,=T0Tδrδ+μδgαT0∏u∈ATur′gnFMgJMs′gnFMgJM−a/FM,=gαT0∏u∈ATur′T0Tδrδ+μδu0∏i=1muimis′−a/FM,σ2=gr′,σ3=gμδ+rδ,σ4=gs′g1−JM/FM=gs′−a/FM.
Then have(30)eg,σ1=eg,gαT0∏u∈ATur′T0Tδrδ+μδu0∏i=1muimis′−a/FM,=Yeσ2,T0∏u∈ATueσ3,T0Tδeσ4,u0∏i=1muimi.
The verification equation holds. Thus the simulated signature is correct.(vii)
Forgery. A outputs a signature σ∗=σ1∗,σ2∗,σ3∗,σ4∗ on M∗,A∗.(viii)
Output. If FM∗≠0modp, it aborts. Otherwise, ℬ computes and outputs(31)σ1∗ga′σ4∗JM∗σ2∗σ3∗t0.Claim 3.
The output ofℬ is gan+1.Proof.
BecauseFM∗=0modp, so u0∏i=0muimi∗=gnFM∗gJM∗=gJM∗.
σ∗ is a valid signature on message M∗ for A∗, so we have(32)eg,σ1∗=Yeσ2∗,T0∏u∈A∗Tueσ3∗,T0Tδeσ4∗,u0∏i=1muimi∗,=eg,gαeσ2∗,gt0eσ3∗,gt0eσ4∗,gJM∗,=eg,ga′+an+1σ2∗σ3∗t0σ4∗JM∗,and then(33)σ1∗ga′σ4∗JM∗σ2∗σ3∗t0=gan+1.Claim 4.
The probability that the simulation is not aborted is1/8qsm+1.Proof.
The same as Claim 2 of Waters [31].
Claims1 and 2 show that the simulation above is correct. Thus, by Claim 3 and Claim 4, ℬ can compute gan+1 with probability ϵ′≥ϵ/8qsm+1.Theorem 3 (perfect anonymity).
The improved scheme is perfect anonymous.Proof.
ChallengerC executes the Setup algorithm to set up the system and responds to the oracle requests by running the corresponding algorithm.
ReceivingM,A,A0,A1,σout0,σout1,fu0,fu1, C flips a fair coin b∈0,1, chooses rb,sb,sbδ∈RZp, and computes and returns a signature σb=σb1,σb2,σb3,σb4 from σoutb using OSKAbfub.
ChallengerC continues to respond to the oracle requests by running the corresponding algorithm.
Sinceσoutb=σ′11b,σ′12b,σ′2b is an outsourced signature on A using OSKAbfub, we have(34)σ11′b=T0∏u∈ATu,σ12′b=∏i∈IAbdbi∏u∈A,u∉πidbiu″wbi,σ2′b=∏i∈IAbdbi′wbi.
Andσb=σb1,σb2,σb3,σb4 is a signature calculated from σoutb, so we have(35)σb1=dbδT0Tδsbδσ11′brbσ12′bu0∏i=1muimisb=gaT0Tδrbδ+sbδT0∏u∈ATurb+∑i∈IAbrbiwbiu0∏i=1muimisb,σb2=grbσ2′b=grb+∑i∈IAbrbiwbi,σb3=dbδ′gsbδ=grbδ+sbδ,σb4=gsb.
We can rewriteσb as(36)σb1=gaT0Tδrb¯δ+rbδ−rb¯δ+sbδT0∏u∈ATurb+∑i∈IAbrbiwbi−∑i∈IAb¯rb¯iwb¯i+∑i∈IAb¯rb¯iwb¯iu0∏i=1muimisb=gaT0Tδrb¯δ+sb¯δT0∏u∈ATurb¯+∑i∈IAb¯rb¯iwb¯iu0∏i=1muimisb¯=db¯δT0Tδsb¯δσ′11b¯rb¯σ′12b¯u0∏i=1muimisb¯,σb2=grb+∑i∈IAbrbiwbi−∑i∈IAb¯rb¯iwb¯i+∑i∈IAb¯rb¯iwb¯i=grb¯+∑i∈IAb¯rb¯iwb¯i=grb¯σ2b¯,σb3=grbδ+sbδ=grb¯δ+sb¯δ=db¯δ′gsb¯δ,σb4=gsb=gsb¯,where rb¯=rb+∑i∈IAbrbiwbi−∑i∈IAb¯rb¯iwb¯i∈Zp, sb¯=sb, sb¯δ=rbδ−rb¯δ+sbδ, b¯=b⊕1.
This concludes thatσb is also a signature calculated from σoutb¯ out using rb¯,sb¯,sb¯δ and PSKAb¯fub¯. Because r,s,sδ are randomly selected from Zp, the probability of selecting rb,sb,sbδ is the same as that of rb¯,sb¯,sb¯δ, and both are p−3. Therefore, even if the adversary has an unlimited capability, it is impossible to distinguish which access structure was used to generate the signature.
On the other hand, the adversary may generate signatures by him/herself. Assuming that the random integer selected by the adversary isr,s,sδ, then the probabilities of r,s,sδ=rb,sb,sbδ and r,s,sδ=rb¯,sb¯,sb¯δ are the same p−3. So, even if the adversary possesses all the private signing keys and outsourced keys, it is impossible to determine which access structure was used to generate the signature.
In summary, adversaryA ’s advantage AdvOABS,APerAnon1λ is 0, and the improved scheme achieves perfect anonymity.


### 5.3. Performance Analysis

Denote byG an element of G, by Zp an element of Zp, by E an exponentiation in G, by M a multiplication in G, by P a computation of the pairing, and by I an inner product operation. Let n be the size of the attribute universe U, m be the length of the message, l be the number of rows of MA, lr be the number of rows whose attribute belongs to the attribute set, i.e., lr=IA, and la be the size of the attribute set, i.e., la=A. We compare our scheme to Mo et al.’s scheme in Table 2.Table 2
Comparison of performance.
SchemeEOABS [17]Improved schemeMPK.Sizen+m+4Gn+m+4GMSK.Size2Zp1ZpOut.Key.Sizen+1lGn+1lGSig.Key.Size2G2GOut.Sig.Size2G3GSig.Size3G4GKey.Genn+2l+3E+2l+1M+lIn+2l+3E+2l+1M+lIOut.Sig.Gen2lr+1E+n+1laM2lrE+n+1la−1MSig.Genm+4E+m+6Mm+6E+m+7MVerifymE+3P+la+m+1MmE+4P+la+m+1MUnforgeableNoYesPerfect anonymityNoYesCorrectnessNoYesIn terms of data size, our scheme has one less integer in the master private key and one more group element in the final signature. The other items are the same size. There is not much difference between the two schemes.In terms of computational overhead, our scheme has an extra2E+1M in signature generation. Estimated with the message length m=160, this is an increase of about 0.7%.Although our scheme is slightly inferior to Mo et al.’s schemes in terms of data length and computational overhead, our scheme has an overwhelming advantage in terms of security. Our scheme achieves correctness, unforgeability, and perfect anonymity, while their scheme does not achieve any of these three properties. It shows that our improvement is meaningful.


## 5.1. Improved Scheme

(i)
Setup: it is the same as Mo et al.’s EOABS scheme, except thatY=eg,gα and MSK=α∈RZp.(ii)
KeyGen: it is the same as Mo et al.’s EOABS scheme but choosesa∈Rℤp and sets b=α−a.(iii)
OutSign: it takes as the inputs an attribute setA, an outsourced key OSKAfu with matrix MA, and a flag fu.(i)
IfA∈A, the S-CSP finds wi:i∈IA=i∈lA:πi∈A such that ∑i∈IAwiMAi=1,0,…,0.(ii)
computes(14)σ11′=T0∏u∈ATu,σ12′=∏i∈IAdi∏u∈A,u≠πidiu″wi,σ2′=∏i∈IAdi′wi.The outsourced signatureσout=σ11′,σ12′,σ2′.(iv)
Sign: with a private signing keyPSKAfu, a message M=m1m2…mm, and an outsourced signature σout, the signer selects r,s,sδ∈Rℤp and computes(15)σ1=dδT0Tδsδσ′11rσ12′u0∏i=1muimis,σ2=grσ2′,σ3=dδ′gsδ,σ4=gs.The final signature onM,A is σ=σ1,σ2,σ3,σ4.(v)
Verify: withPP,σ,M,A, the verifier checks whether(16)eg,σ1=Yeσ2,T0∏u∈ATueσ3,T0Tδeσ4,u0∏i=1muimi.If the equation holds, the verifier outputs 1. Otherwise, it outputs 0.


## 5.2. Proofs of Security

Theorem 1 (correctness).
The improved scheme is correct.Proof.
WhenA∈A, we can find wi:i∈IA such that(17)∑i∈IAwiMAi=1,0,…,0,and then(18)∑i∈IAwiλi=∑i∈IAwiMAiv=a.
So(19)eg,σ1=eg,gbT0TδrδT0TδsδT0∏u∈ATur∏i∈IAdi∏u∈A,u≠πidiu″wiu0∏i=1muimis,=eg,gα−aT0Tδrδ+sδT0∏u∈ATur∏i∈IAgλiT0Tπiri∏u∈A,u≠πiTuriwiu0∏i=1muimis,=eg,gα−ag∑i∈IAwiλiT0Tδrδ+sδT0∏u∈ATur+∑i∈IAriwiu0∏i=1muimis,=eg,gαeg,T0Tδrδ+sδeg,T0∏u∈ATur+∑i∈IAriwieg,u0∏i=1muimis,=Yeσ3,T0Tδegr+∑i∈IAriwi,T0∏u∈ATueσ4,u0∏i=1muimi,=Yeσ3,T0Tδegr∏i∈IAgriwi,T0∏u∈ATueσ4,u0∏i=1muimi,=Yeσ3,T0Tδeσ2,T0∏u∈ATueσ4,u0∏i=1muimi.
The verification equation holds, and the improved scheme is correct.Theorem 2 (unforgeability).
The improved scheme is existentially unforgeable. If an adversaryAcan win GAME 1 with advantageϵ, then there exists an algorithmℬthat solves the CDHE problem with probabilityϵ′≥ϵ/8qsm+1, whereqsis the maximum number of Sign-Oracle queries and m is the length of the message.Proof.
In the following,A is an adversary with advantage ϵ, and C is the challenger to the CDHE problem. We build ℬ as follows, which uses A to solve the CDHE problem.
Without loss of generality, we assume the attribute universeU=1,2,…,n. ℬ maintains an initially empty list Lkey.(i)
CDHE Problem Gen.(i)
C chooses two prime order p multiplicative cyclic groups G, GT and a bilinear map e:G×G⟶GT.(ii)
chooses a generatorg∈G and a∈Rℤp and computes g,ga,ga2,…,gan,gan+2,…,ga2n.(iii)
sendsp,G,GT,e,g,gi=gaii=1,i≠n+12n to ℬ.(ii)
Init Phase. A chooses and sends A∗ to ℬ.(iii)
Setup.(i)
ℬ chooses a′,t0∈Rℤp and tu∈Rℤp for all u∈U, and computes(20)Tu=gtugn+1−u:u∈U,T0=gt0∏u∈A∗Tu−1,Tδ=gt0T0−1.(ii)
computesY=eg,ga′eg1,gn (i.e., it sets the master secret key α=a′+an+1 implicitly).(iii)
LetlM=4qs, choosing kM∈Rm, picking x′∈RℤlM, y′∈Rℤp, x^i∈RℤlM:i∈m, y^i∈Rℤp:i∈m, and computing(21)u0=gnp−lMkM+x′gy′,ui=gnx^igy^i:i∈m.(iv)
sends the public parameterspp=p,g,G,GT,Y,e,T0,Tu:u∈U∪δ,u0,u1,…,um to A.(iv)
OSK-Oracle. Assume A queries an outsourced key on access structure A with the matrix MA of size lA×kA and flag fu. If A,fu in Lkey, it returns the corresponding outsourced key OSKAfu to A. Otherwise, we compute the keys as follows:(i)
IfA∗∈A:(i) setsPSKAfu=⊥ (A cannot query any private signing key for the access structure A satisfied by A∗).(ii) runs KeyGen to getOSKAfu.(iii) returnsOSKAfu to A.(iv) addsOSKAfu,⊥,A,fu into the key list Lkey.(ii)
IfA∗∉A:(i) finds a vectorw=−1,w2,…,wkA∈ℤpkA such that MAiw=0 for each i:πi∈A∗, where MAi is the i th row of MA (Lemma 1).(ii) choosesv1,v2,…,vkA∈Rℤp, and sets v′=0,v2,…,vkA.(iii) For alli∈lA,(i)
ifπi∈A∗, choose ri∈Rℤp and compute(22)di=gMAiv′T0Tπiri,di′=gri,diu″=Turi:u∈U/πi,(ii)
ifπi∉A∗, choose ri′∈Rℤp and compute(23)di=gMAiv′−v1wT0Tπiri′gπi−t0+tπi∏u∈A∗gπitugn+1−u+πi−MAiwdi′=gri′gπi−MAiwdiu″=Turi′gπitugn+1−u+πiMAiw,u∈U/πi.(iv)
selectsrδ∈Rℤp and computes dδ=ga′−v1T0Tδrδ, dδ′=grδ.(v)
returnsOSKAfu=di,di′,diu″i∈lA,u∈U\πi to A.(vi)
addsOSKAfu,PSKAfu=dδ,dδ′,A,fu into the key list Lkey.(iii)
SK-Oracle. It is the same as the OSK-Oracle above, except that it returns a private signing keyPSKAfu to A.Claim 1.
The keys simulated above are correct.Proof.
IfA∗∈A, and OSKAfu is generated by KeyGen, it is correct certainly.
IfA∗∉A, according to Lemma 1, we can find a vector w=−1,w2,…,wkA∈ℤpkA such that MAiw=0 for each i:πi∈A∗. We prove OSKAfu is a correct outsourced key with v=−v1+an+1w+v′ as follows:(i)
Whenπi∈A∗, MAiw=0, and λi=MAiv=−v1+an+1MAiw+MAiv′=MAiv′, we have(24)di=gMAiv′T0Tπiri=gλiT0Tπiri,di′=gri,diu″=Turi:u∈U/πi.(ii)
Whenπi∉A∗, we have λi=MAiv=MAiv′−v1w−an+1MAiw, and(25)di=gMAiv′−v1wT0Tπiri′gπi−t0+tπi∏u∈A∗gπitugn+1−u+πi−MAiw,=gMAiv′−v1wT0Tπiri′gaπit0MAiwgaπitπiMAiw,∏u∈A∗gaπitugn+1−uaπi−MAiwgan+1MAiwg−an+1MAiw,=gMAiv′−v1w−an+1MAiwT0Tπiri′gt0∏u∈A∗gtugn+1−u−1aπiMAiw,gaπitπiMAiwgan+1a−πiaπiMAiw,=gλiT0Tπiri′T0aπiMAiwgtπign+1−πiaπiMAiw,=gλiT0Tπiri′T0TπiaπiMAiw,=gλiT0Tπiri,di′=gri′gπiMAiw=gri,diu″=Turi′gπitugn+1−u+πiMAiw=Turi′gtugn+1−uaπiMAiw=Turi,whereri=ri′+aπiMAiw.
This concludes thatOSKAfu=di,di′,diu″i∈lA,u∈U/πi is a correct outsourced key.
Since the first component ofv is v1+an+1, then(26)α−v1+an+1=a′+an+1−v1+an+1=a′−v1.
ThusPSKAfu=dδ=ga′−v1T0Tδrδ,dδ′=grδ is a correct private signing key.(vi)
Sign-Oracle. It takes M,A,σout,fu as inputs.Define functions(27)FM=p−lMKM+x′+∑i=1mx^imi,JM=y′+∑i=1my^imi,KM=0,ifx′+∑i=1mx^i≡0modlM,1,otherwise.IfKM=0, it aborts. Otherwise, ℬ chooses μδ,s′,r′∈ℤp, and computes and returns(28)σ1=T0Tδrδ+μδga′T0∏u∈ATur′gnFMgJMs′g1−JM/FM,σ2=gr′,σ3=gμδ+rδ,σ4=gs′g1−1/FM.Claim 2.
The simulated signatures are correct.Proof.
By simple calculating, we haveu0∏i=1muimi=gnFMgJM. If KM≠0, then FM≠0modp, because we can assume lMm+1<p for any reasonable values of p,m, and lM. Then, we have(29)σ1=T0Tδrδ+μδga′T0∏u∈ATur′gnFMgJMs′g1−JM/FM,=T0Tδrδ+μδga′gan+1g−an+1T0∏u∈ATur′gnFMgJMs′g1−JM/FM,=T0Tδrδ+μδga′+an+1T0∏u∈ATur′gnFMgJMs′gn−aFM/FMg−aFM/FM,=T0Tδrδ+μδgαT0∏u∈ATur′gnFMgJMs′gnFMgJM−a/FM,=gαT0∏u∈ATur′T0Tδrδ+μδu0∏i=1muimis′−a/FM,σ2=gr′,σ3=gμδ+rδ,σ4=gs′g1−JM/FM=gs′−a/FM.
Then have(30)eg,σ1=eg,gαT0∏u∈ATur′T0Tδrδ+μδu0∏i=1muimis′−a/FM,=Yeσ2,T0∏u∈ATueσ3,T0Tδeσ4,u0∏i=1muimi.
The verification equation holds. Thus the simulated signature is correct.(vii)
Forgery. A outputs a signature σ∗=σ1∗,σ2∗,σ3∗,σ4∗ on M∗,A∗.(viii)
Output. If FM∗≠0modp, it aborts. Otherwise, ℬ computes and outputs(31)σ1∗ga′σ4∗JM∗σ2∗σ3∗t0.Claim 3.
The output ofℬ is gan+1.Proof.
BecauseFM∗=0modp, so u0∏i=0muimi∗=gnFM∗gJM∗=gJM∗.
σ∗ is a valid signature on message M∗ for A∗, so we have(32)eg,σ1∗=Yeσ2∗,T0∏u∈A∗Tueσ3∗,T0Tδeσ4∗,u0∏i=1muimi∗,=eg,gαeσ2∗,gt0eσ3∗,gt0eσ4∗,gJM∗,=eg,ga′+an+1σ2∗σ3∗t0σ4∗JM∗,and then(33)σ1∗ga′σ4∗JM∗σ2∗σ3∗t0=gan+1.Claim 4.
The probability that the simulation is not aborted is1/8qsm+1.Proof.
The same as Claim 2 of Waters [31].
Claims1 and 2 show that the simulation above is correct. Thus, by Claim 3 and Claim 4, ℬ can compute gan+1 with probability ϵ′≥ϵ/8qsm+1.Theorem 3 (perfect anonymity).
The improved scheme is perfect anonymous.Proof.
ChallengerC executes the Setup algorithm to set up the system and responds to the oracle requests by running the corresponding algorithm.
ReceivingM,A,A0,A1,σout0,σout1,fu0,fu1, C flips a fair coin b∈0,1, chooses rb,sb,sbδ∈RZp, and computes and returns a signature σb=σb1,σb2,σb3,σb4 from σoutb using OSKAbfub.
ChallengerC continues to respond to the oracle requests by running the corresponding algorithm.
Sinceσoutb=σ′11b,σ′12b,σ′2b is an outsourced signature on A using OSKAbfub, we have(34)σ11′b=T0∏u∈ATu,σ12′b=∏i∈IAbdbi∏u∈A,u∉πidbiu″wbi,σ2′b=∏i∈IAbdbi′wbi.
Andσb=σb1,σb2,σb3,σb4 is a signature calculated from σoutb, so we have(35)σb1=dbδT0Tδsbδσ11′brbσ12′bu0∏i=1muimisb=gaT0Tδrbδ+sbδT0∏u∈ATurb+∑i∈IAbrbiwbiu0∏i=1muimisb,σb2=grbσ2′b=grb+∑i∈IAbrbiwbi,σb3=dbδ′gsbδ=grbδ+sbδ,σb4=gsb.
We can rewriteσb as(36)σb1=gaT0Tδrb¯δ+rbδ−rb¯δ+sbδT0∏u∈ATurb+∑i∈IAbrbiwbi−∑i∈IAb¯rb¯iwb¯i+∑i∈IAb¯rb¯iwb¯iu0∏i=1muimisb=gaT0Tδrb¯δ+sb¯δT0∏u∈ATurb¯+∑i∈IAb¯rb¯iwb¯iu0∏i=1muimisb¯=db¯δT0Tδsb¯δσ′11b¯rb¯σ′12b¯u0∏i=1muimisb¯,σb2=grb+∑i∈IAbrbiwbi−∑i∈IAb¯rb¯iwb¯i+∑i∈IAb¯rb¯iwb¯i=grb¯+∑i∈IAb¯rb¯iwb¯i=grb¯σ2b¯,σb3=grbδ+sbδ=grb¯δ+sb¯δ=db¯δ′gsb¯δ,σb4=gsb=gsb¯,where rb¯=rb+∑i∈IAbrbiwbi−∑i∈IAb¯rb¯iwb¯i∈Zp, sb¯=sb, sb¯δ=rbδ−rb¯δ+sbδ, b¯=b⊕1.
This concludes thatσb is also a signature calculated from σoutb¯ out using rb¯,sb¯,sb¯δ and PSKAb¯fub¯. Because r,s,sδ are randomly selected from Zp, the probability of selecting rb,sb,sbδ is the same as that of rb¯,sb¯,sb¯δ, and both are p−3. Therefore, even if the adversary has an unlimited capability, it is impossible to distinguish which access structure was used to generate the signature.
On the other hand, the adversary may generate signatures by him/herself. Assuming that the random integer selected by the adversary isr,s,sδ, then the probabilities of r,s,sδ=rb,sb,sbδ and r,s,sδ=rb¯,sb¯,sb¯δ are the same p−3. So, even if the adversary possesses all the private signing keys and outsourced keys, it is impossible to determine which access structure was used to generate the signature.
In summary, adversaryA ’s advantage AdvOABS,APerAnon1λ is 0, and the improved scheme achieves perfect anonymity.


## 5.3. Performance Analysis

Denote byG an element of G, by Zp an element of Zp, by E an exponentiation in G, by M a multiplication in G, by P a computation of the pairing, and by I an inner product operation. Let n be the size of the attribute universe U, m be the length of the message, l be the number of rows of MA, lr be the number of rows whose attribute belongs to the attribute set, i.e., lr=IA, and la be the size of the attribute set, i.e., la=A. We compare our scheme to Mo et al.’s scheme in Table 2.Table 2
Comparison of performance.
SchemeEOABS [17]Improved schemeMPK.Sizen+m+4Gn+m+4GMSK.Size2Zp1ZpOut.Key.Sizen+1lGn+1lGSig.Key.Size2G2GOut.Sig.Size2G3GSig.Size3G4GKey.Genn+2l+3E+2l+1M+lIn+2l+3E+2l+1M+lIOut.Sig.Gen2lr+1E+n+1laM2lrE+n+1la−1MSig.Genm+4E+m+6Mm+6E+m+7MVerifymE+3P+la+m+1MmE+4P+la+m+1MUnforgeableNoYesPerfect anonymityNoYesCorrectnessNoYesIn terms of data size, our scheme has one less integer in the master private key and one more group element in the final signature. The other items are the same size. There is not much difference between the two schemes.In terms of computational overhead, our scheme has an extra2E+1M in signature generation. Estimated with the message length m=160, this is an increase of about 0.7%.Although our scheme is slightly inferior to Mo et al.’s schemes in terms of data length and computational overhead, our scheme has an overwhelming advantage in terms of security. Our scheme achieves correctness, unforgeability, and perfect anonymity, while their scheme does not achieve any of these three properties. It shows that our improvement is meaningful.


## 6. Conclusion

OABS was introduced to solve the problem that ABS is not suitable for scenarios with limited computing power. Recently, Mo et al. proposed an expressive outsourced attribute-based signature scheme. In this paper, we analyze the security of Mo et al.’s EOABS scheme. We show that it does not achieve the correctness, unforgeability, and anonymity that they claimed. We present more accurate security models for OABS and propose an improved OABS scheme to fix our attacks. Our scheme is provably secure in the standard model.



---

*Source: 7884007-2021-10-16.xml*