# SPCABS: Signature-Policy Comparable Attribute-Based Signatures

Authors: Hongying Chen; Zhenjie Huang; Hui Huang; Yafeng Guo
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Attribute-based signature is an attractive cryptographic primitive and finds broad applications in many fields. Existing attribute-based signature schemes deal with attributes in the way of “with” or “without,” and there is no attribute-based signature scheme that supports comparing attributes. Using the 0-encoding and 1-encoding, we propose an access structure algorithm and an attribute expansion algorithm, enabling the attribute-based signature scheme to effectively deal with the comparative attributes. Then, we propose a signature-policy comparable attribute-based signature scheme using the proposed expansion algorithms. The proposed scheme is existentially unforgeable under the computational Diffie–Hellman exponent (CDHE) assumption and achieves privacy in the sense of information theory. Theoretical analysis and simulation experiments show that our method is practical and has significant advantages in storage and computation overhead compared with the trivial way. Comparable attribute-based signature dramatically expands the application scenarios of attribute-based signature.


---

## Body

## 1. Introduction

Attribute-based signature is a very attractive cryptographic primitive [1]. ABS is divided into key-policy ABS (KP-ABS) and signature-policy ABS (SP-ABS). The former KP-ABS uses the access policy (structure) to generate the signing key, and the message can be signed only when its attribute set satisfies the access policy. The latter SP-ABS is the opposite. The signer possesses the signing key corresponding to his attributes and the message with an access policy. In the signature generation stage, a valid signature can be generated if and only if the attributes of the signer satisfy the access policy. In the signature verification phase, the verifier can only ensure that the signer’s attributes satisfy the message’s access policy but cannot distinguish the signer’s identity. These are the unforgeability and privacy (anonymity) of ABS. Since ABS has fine-grained access control, anonymous authentication, privacy protection, and other good properties, it finds broad applications in many fields, such as private access control and anonymous credential.The concept of ABS was introduced by Maji et al. [1]. They presented the definition and security model and proposed concrete schemes with security proof under the general group model. Later, Li et al. [2, 3], Shahandashti et al. [4], and Gagné et al. [5] constructed the ABS schemes under the selection model. These schemes only support threshold predicates. Maji et al. [6] and Gu et al. [7] proposed ABS schemes for monotone predicates. In 2011, Okamoto et al. [8, 9] proposed ABS schemes supporting nonmonotone predicates, improving access control flexibility, and satisfying adaptive security. In 2012, Herranz et al. [10] constructed a threshold ABS scheme with constant signature length, and its security is improved from the original selective unforgeability to adaptive unforgeability. In the same year, Chen et al. [11] combined ABS with attribute-based encryption (ABE) to construct a hybrid ABS/ABE scheme. The advantage is that ABS and ABE share the same user private key, which reduces the cost of key generation. Su et al. [12] proposed an attribute signature scheme that supports the threshold tree access structure. While the expression and security of ABS continue to improve, its functions are also constantly evolving. Wang and Chen [13] constructed a lattice-based ABS scheme to resist quantum computing attacks. Escala et al. [14] introduced the concept of traceability, allowing a trusted authority to control the signer’s identity and hold the signer accountable when the signer breaks the law. Tang et al. [15] proposed an ABS scheme for circuits from multilinear, and Sakai et al. [16] proposed an ABS scheme for circuits from bilinear maps. Based on lattices, Kaafarani et al. [17] proposed an ABS scheme for unbounded circuits. Datta et al. [18] proposed an ABS scheme for unbounded arithmetic branching programs.All ABS schemes mentioned above have a single attribute authority. This attribute authority knows the signing keys of all users, so it must be trustworthy. Moreover, this attribute authority may become the bottleneck of the system. To overcome this shortcoming, the concepts of multiauthority attribute-based signature [19–21] and decentralized attribute-based signature [22–24] were introduced.The existing works are summarized in Table1.Table 1
Summary of existing works.
SchemeAccess structureTypeAssumptionModelMaji et al. [1]LSSSKPCDHGGMJin and Kim [2]ThresholdKPCDHROMJin et al. [3]ThresholdSPCDHROM&SMShahandashti and Safavi-Naini [4]ThresholdKPCDHSMGagné et al. [5]ThresholdKPCDHROMMaji et al. [6]ThresholdSPCDH&DLINGGMGu et al. [7]LSSSSPCDHSMOkamoto and Takashima [8]ThresholdKPDLINGGMOkamoto and Takashima [9]LSSSSPDLINGGMHerranz et al. [10]ThresholdSPDLINGGMChen et al. [11]LSSSSPCDHEROMSu et al. [12]ThresholdSPCDHROMWang and Chen [13]ThresholdSPSISROMEscala et al. [14]LSSSSPSISSMTang et al. [15]CircuitKPMCDHROMSakai et al. [16]CircuitKPCDHROMKaafarani and Ghadafi [17]CircuitSPDDHGGMDatta et al. [18]LSSSSPDLINSMCao et al. [19]ThresholdSPCDHSMCao et al. [20]ThresholdKPCDHROMEl Kaafarani et al. [21]LSSSSPDDHROMOkamoto and Takashima [22]LSSSSPDLINROMEl Kaafarani et al. [23]LSSSSPDLIN&CDHROM&SMGhadafi [24]LSSSSPDDH&DLINSMLSSS = linear secret sharing scheme, SP=signature-policy, KP=key-policy, DLIN = decisional linear assumption, SIS=short integer solution, CDH=computational Diffie–Hellman assumption, MCDH = multilinear CDH, DDH = decisional DH, CDHE=computational Diffie–Hellman exponent assumption, GGM = generic group model, ROM = random oracle model, and SM=standard model.


### 1.1. Related Works

Generally, the computational overhead of ABS is too large, making it unsuitable for resource-constrained equipment. To this end, using cloud computing outsourcing technology, Chen et al. [25] introduced the concept of outsourced attribute-based signature. After that, several outsourced attribute-based signature schemes were proposed [26, 27]. In addition, several ABS schemes with various additional properties have also been proposed, such as group signature [28], signcryption [29], proxy signature [30], traceability [23], revocation [14], hierarchical [31], linkability [21], message recovery [32], and self-revealability [33].So far, attribute-based signatures are still receiving widespread attention. In 2021, Perera et al. [34] constructed an attribute-based group signature (ABGS) scheme with verifier-local revocation (VLR). In the same year, Chen et al. [35] presented a novel ABS scheme using the attribute tree as an access policy that expresses flexible access control. They utilized the server-aid technique to verify signatures and reduce the computation burden. Luo et al. [36] introduced attribute-based proxy resignatures (ABPRS), which allows a semitrusted proxy to transform a signature of one entity into a signature of another, without revealing any signing key and information about the signer. Zhao et al. [37] constructed a novel attribute-based signcryption (ABSC) scheme realizing multiauthority access control and constant-size ciphertext that does not depend on the number of attributes or authorities.In recent years, attribute-based signature has found new applications in many fields. Yang et al. [38] and Guo et al. [39] construct medical record management systems based on attribute-based signature and blockchain, respectively. Liu et al. [40] proposed a secure vehicular crowdsensing scheme based on multiauthority attribute-based signature (TRAMS), which allows the publisher to flexibly customize a fine-grained policy that the potential participants must satisfy and uses the attribute-based signature to authenticate sensed messages while protecting the privacy of the sensing vehicle. Also, they proposed a multiauthority key management scheme, which can improve vehicle-based sensing efficiency on the Internet of vehicles.


### 1.2. Motivation and Contributions

So far, the existing attribute-based signature schemes have dealt with attributes in a way that is “with” or “without”. No attribute-based signature scheme supports comparative attributes or more complex relationship attributes. Consider such a simple illustrative example. On the forum of a game community, it is required that only players who meet the following conditions can postexperience and guide novices:Member of the community AND((Register before 2018 AND More than 10 million game points) OR Top 32 in first-class competitions).Suppose member Alice was registered in 2017 and has 20 million game points. We can easily determine that her attributes meet the above access structure, but none of the existing attribute-based signature schemes can handle it directly. The previous processing method is to expand the access structure or attributes. For example, expand “Register before 2018” and “More than 10 million game points” to“Registered in 2000 OR Registered in 2002 OR⋯ OR Registered in 2017” and“11 million game points OR 12 million game points OR⋯ OR 127 million game points”.Although this trivial method can solve the problem, it bringsON level attribute amount expansion, where N is the size of the value space of the attribute. This will make the storage overhead and computation overhead increase linearly with N. The trivial method is not practical, so it is urgent to propose a practical comparative attribute management method.The main contributions of this paper are as follows:(i)
Using the 0-encoding and 1-encoding of Lin and Tzeng [41], we propose an access structure algorithm and an attribute expansion algorithm, which reduce the data expansion from ON to Olog2N. These two algorithms enable the attribute-based signature scheme to deal with the comparative attributes effectively.(ii)
Using the proposed expansion algorithms, we propose an efficient attribute-based signature scheme that supports comparative attributes. Assuming that the computational Diffie–Hellman exponent (CDHE) problem is hard, the proposed scheme is existentially unforgeable under adaptive chosen message but selective access structure attack. The proposed scheme achieves privacy in the sense of information theory, and the adversary cannot break the privacy even if he has infinite capabilities.(iii)
Theoretical analysis and simulation experiments show that our method is practical and has significant advantages in storage and computation overhead compared with the trivial way.(iv)
Comparable attribute-based signature dramatically expands the application scenarios of attribute-based signature.


### 1.3. Organization

The rest of the paper is organized as follows. The necessary background and notations are presented and reviewed in Section2. Section 3 reviewed the attribute-based signature with its security model. Section 4 describes comparative attribute management. Our CABS constructions are proposed in Section 5. The security proof and performance analysis of the proposed scheme are given in Sections 6 and 7, respectively. Finally, the paper is concluded in Section 8.


## 1.1. Related Works

Generally, the computational overhead of ABS is too large, making it unsuitable for resource-constrained equipment. To this end, using cloud computing outsourcing technology, Chen et al. [25] introduced the concept of outsourced attribute-based signature. After that, several outsourced attribute-based signature schemes were proposed [26, 27]. In addition, several ABS schemes with various additional properties have also been proposed, such as group signature [28], signcryption [29], proxy signature [30], traceability [23], revocation [14], hierarchical [31], linkability [21], message recovery [32], and self-revealability [33].So far, attribute-based signatures are still receiving widespread attention. In 2021, Perera et al. [34] constructed an attribute-based group signature (ABGS) scheme with verifier-local revocation (VLR). In the same year, Chen et al. [35] presented a novel ABS scheme using the attribute tree as an access policy that expresses flexible access control. They utilized the server-aid technique to verify signatures and reduce the computation burden. Luo et al. [36] introduced attribute-based proxy resignatures (ABPRS), which allows a semitrusted proxy to transform a signature of one entity into a signature of another, without revealing any signing key and information about the signer. Zhao et al. [37] constructed a novel attribute-based signcryption (ABSC) scheme realizing multiauthority access control and constant-size ciphertext that does not depend on the number of attributes or authorities.In recent years, attribute-based signature has found new applications in many fields. Yang et al. [38] and Guo et al. [39] construct medical record management systems based on attribute-based signature and blockchain, respectively. Liu et al. [40] proposed a secure vehicular crowdsensing scheme based on multiauthority attribute-based signature (TRAMS), which allows the publisher to flexibly customize a fine-grained policy that the potential participants must satisfy and uses the attribute-based signature to authenticate sensed messages while protecting the privacy of the sensing vehicle. Also, they proposed a multiauthority key management scheme, which can improve vehicle-based sensing efficiency on the Internet of vehicles.


## 1.2. Motivation and Contributions

So far, the existing attribute-based signature schemes have dealt with attributes in a way that is “with” or “without”. No attribute-based signature scheme supports comparative attributes or more complex relationship attributes. Consider such a simple illustrative example. On the forum of a game community, it is required that only players who meet the following conditions can postexperience and guide novices:Member of the community AND((Register before 2018 AND More than 10 million game points) OR Top 32 in first-class competitions).Suppose member Alice was registered in 2017 and has 20 million game points. We can easily determine that her attributes meet the above access structure, but none of the existing attribute-based signature schemes can handle it directly. The previous processing method is to expand the access structure or attributes. For example, expand “Register before 2018” and “More than 10 million game points” to“Registered in 2000 OR Registered in 2002 OR⋯ OR Registered in 2017” and“11 million game points OR 12 million game points OR⋯ OR 127 million game points”.Although this trivial method can solve the problem, it bringsON level attribute amount expansion, where N is the size of the value space of the attribute. This will make the storage overhead and computation overhead increase linearly with N. The trivial method is not practical, so it is urgent to propose a practical comparative attribute management method.The main contributions of this paper are as follows:(i)
Using the 0-encoding and 1-encoding of Lin and Tzeng [41], we propose an access structure algorithm and an attribute expansion algorithm, which reduce the data expansion from ON to Olog2N. These two algorithms enable the attribute-based signature scheme to deal with the comparative attributes effectively.(ii)
Using the proposed expansion algorithms, we propose an efficient attribute-based signature scheme that supports comparative attributes. Assuming that the computational Diffie–Hellman exponent (CDHE) problem is hard, the proposed scheme is existentially unforgeable under adaptive chosen message but selective access structure attack. The proposed scheme achieves privacy in the sense of information theory, and the adversary cannot break the privacy even if he has infinite capabilities.(iii)
Theoretical analysis and simulation experiments show that our method is practical and has significant advantages in storage and computation overhead compared with the trivial way.(iv)
Comparable attribute-based signature dramatically expands the application scenarios of attribute-based signature.


## 1.3. Organization

The rest of the paper is organized as follows. The necessary background and notations are presented and reviewed in Section2. Section 3 reviewed the attribute-based signature with its security model. Section 4 describes comparative attribute management. Our CABS constructions are proposed in Section 5. The security proof and performance analysis of the proposed scheme are given in Sections 6 and 7, respectively. Finally, the paper is concluded in Section 8.


## 2. Preliminaries

### 2.1. Notations

The notations are summarized in Table2.Table 2
Notations.
NotationDescriptionx∈RXPicking an elementx uniformly at random from the set XnPositive integer set {1, 2, …,n} for any positive integer naA vectora=a1,…,aj∈ℤpjabInner product of vectorsa and b, ab  =  a1b1+⋯+ajbjAThe number of elements in the setAuiUsual attributeu˜iComparative attributeu¨iComparative attribute namea¨iComparative attribute thresholdb¨iUser attribute value


### 2.2. Bilinear Mapping and the Complexity Assumptions

In this section, we introduce the notions of bilinear maps, complexity assumption, access structure, and linear secret sharing scheme.Definition 1 (bilinear maps).
Letpbe a prime number. LetGandGTbe multiplicative cyclic groups of orderp. A mape:G×G⟶GTis called a bilinear map or (bilinear) pairing if the following hold:(i)
Bilinearity.eg1a,g2b=eg1,g2ab,∀g1,g2∈G,a,b∈ℤp.(ii)
Nondegeneracy.eg1,g2≠1T, wheneverg1,g2≠1,1, where 1 (or1T) is the identity element inGorGT.(iii)
Computability.eg1,g2is efficiently computable,∀g1,g2∈G.Definition 2 (computational Diffie–Hellman exponent (CDHE) assumption).
The challenger choosesg∈G,α∈ℤpat random and outputsg,gα,gα2,…,gαn,gαn+2,…,gα2n. The CDHE problem is to computegαn+1according tog,gα,gα2,…,gαn,gαn+2,…,gα2n. Thet,ε-CDHE assumption holds if not-time adversary has at leastεadvantage to solve the CDHE problem.


### 2.3. 0-Encoding and 1-Encoding

The 0-encoding and the 1-encoding are used by Lin et al. to solve the millionaire problem [41]. Let s=snsn−1…s1∈0,1n be an n-length binary string of a value:(i)
The0-encoding of s is defined as a set(1)Ss0=snsn−1⋯si+11|si=0,1≤i≤n.(ii)
The1-encoding of s is the set(2)Ss1=snsn−1⋯si|si=1,1≤i≤n.Intuitively, the 1-encoding ofs is the set of all its odd prefix substrings, and the 0-encoding is the set of all of its modified even prefix substrings, where the least significant bit is flipped from “0” to “1”. For example, 20=101002, its 0-encoding S200=11,1011,10101, and 1-encoding S201=1,101.Lemma 1 (see [41]).
x>yif and only ifSx1∩Sy0≠∅.


### 2.4. Access Structure and Linear Secret Sharing Scheme

LetU=u1,u2,…,un be an attribute universe; an access structure is a Boolean function f over U. An attribute set A⊆U is an authorized set, if fA=1. An access structure is monotone if fA=1 and A⊆B implies fB=1 for all A,B⊆U.A Linear Secret Sharing Scheme (LSSS) for monotone access structuref over ℤp is a matrix Ml×k along with a function ρi to indicate the i-th row of M as an attribute in f, which consists of the following polynomial time operations:(i)
Distribution of Shares. The distribution of a secret a∈ℤp is performed by the dealer. The dealer first samples a2,a3,…,ak∈ℤp and sets v=a,a2,a3,…,ak∈ℤpk. Then, the dealer outputs a set λi:λi=Mivi∈l, where Mi is the ith row of the matrix M.(ii)
Reconstruction of the Secret. Suppose that A is an authorized set. The secret reconstruction constants wii∈I⊂ℤp, where I=i:ρi∈A, satisfying ∑i∈IwiMi=1. Hence, ∑i∈Iwiλi=a.


## 2.1. Notations

The notations are summarized in Table2.Table 2
Notations.
NotationDescriptionx∈RXPicking an elementx uniformly at random from the set XnPositive integer set {1, 2, …,n} for any positive integer naA vectora=a1,…,aj∈ℤpjabInner product of vectorsa and b, ab  =  a1b1+⋯+ajbjAThe number of elements in the setAuiUsual attributeu˜iComparative attributeu¨iComparative attribute namea¨iComparative attribute thresholdb¨iUser attribute value


## 2.2. Bilinear Mapping and the Complexity Assumptions

In this section, we introduce the notions of bilinear maps, complexity assumption, access structure, and linear secret sharing scheme.Definition 1 (bilinear maps).
Letpbe a prime number. LetGandGTbe multiplicative cyclic groups of orderp. A mape:G×G⟶GTis called a bilinear map or (bilinear) pairing if the following hold:(i)
Bilinearity.eg1a,g2b=eg1,g2ab,∀g1,g2∈G,a,b∈ℤp.(ii)
Nondegeneracy.eg1,g2≠1T, wheneverg1,g2≠1,1, where 1 (or1T) is the identity element inGorGT.(iii)
Computability.eg1,g2is efficiently computable,∀g1,g2∈G.Definition 2 (computational Diffie–Hellman exponent (CDHE) assumption).
The challenger choosesg∈G,α∈ℤpat random and outputsg,gα,gα2,…,gαn,gαn+2,…,gα2n. The CDHE problem is to computegαn+1according tog,gα,gα2,…,gαn,gαn+2,…,gα2n. Thet,ε-CDHE assumption holds if not-time adversary has at leastεadvantage to solve the CDHE problem.


## 2.3. 0-Encoding and 1-Encoding

The 0-encoding and the 1-encoding are used by Lin et al. to solve the millionaire problem [41]. Let s=snsn−1…s1∈0,1n be an n-length binary string of a value:(i)
The0-encoding of s is defined as a set(1)Ss0=snsn−1⋯si+11|si=0,1≤i≤n.(ii)
The1-encoding of s is the set(2)Ss1=snsn−1⋯si|si=1,1≤i≤n.Intuitively, the 1-encoding ofs is the set of all its odd prefix substrings, and the 0-encoding is the set of all of its modified even prefix substrings, where the least significant bit is flipped from “0” to “1”. For example, 20=101002, its 0-encoding S200=11,1011,10101, and 1-encoding S201=1,101.Lemma 1 (see [41]).
x>yif and only ifSx1∩Sy0≠∅.


## 2.4. Access Structure and Linear Secret Sharing Scheme

LetU=u1,u2,…,un be an attribute universe; an access structure is a Boolean function f over U. An attribute set A⊆U is an authorized set, if fA=1. An access structure is monotone if fA=1 and A⊆B implies fB=1 for all A,B⊆U.A Linear Secret Sharing Scheme (LSSS) for monotone access structuref over ℤp is a matrix Ml×k along with a function ρi to indicate the i-th row of M as an attribute in f, which consists of the following polynomial time operations:(i)
Distribution of Shares. The distribution of a secret a∈ℤp is performed by the dealer. The dealer first samples a2,a3,…,ak∈ℤp and sets v=a,a2,a3,…,ak∈ℤpk. Then, the dealer outputs a set λi:λi=Mivi∈l, where Mi is the ith row of the matrix M.(ii)
Reconstruction of the Secret. Suppose that A is an authorized set. The secret reconstruction constants wii∈I⊂ℤp, where I=i:ρi∈A, satisfying ∑i∈IwiMi=1. Hence, ∑i∈Iwiλi=a.


## 3. Attribute-Based Signature

### 3.1. Algorithms

An attribute-based signature (ABS) scheme consists of the following algorithms:(i)
Setup: it takes as input the security parameter λ and returns the system public parameters PP and master secret key msk.(ii)
KeyGen: it takes the master secret key msk and an attribute set A as inputs and returns the signing key skA.(iii)
Sign: it takes a signing key skA, a message M, and an access structure f as inputs and returns a signature σ if fA=1.(iv)
Verify: it takes a signature σ, a message M, and an access structure f as inputs and returns 1 or 0.


### 3.2. Security

A secure ABS scheme should have the properties of correctness, unforgeability, and privacy. We present formal definitions of them in the following.Definition 3 (correctness).
An ABS scheme is correct, if(3)PrVerifyσ,M,f→1PP,msk←Setup1λskA←KeyGenmsk,Aσ←SignskA,M,f=1,for anyM,f, andAsuch thatfA=1.
The popular notion of unforgeability for ABS is unforgeable under adaptive chosen message and selective access structure (EUF-sA-CMA). We describe the EUF-sA-CMA attack by the following game between challengerC and adversary A.GAME 1.(EUF-sA-CMA):(i)
Init. A sends a challenge access structure f∗ to C.(ii)
Setup. C generates and sends the system public parameters to A.(iii)
Queries Phase. A can access the following oracles.(a)
KeyGen-Oracle. A sends an attribute set A to C, C returns a signing key skA.(b)
Sign-Oracle. A sends a message M and an access structure A to C, C returns a signature.(iv)
Forgery. A outputs a triple σ∗,M∗,f∗A wins the GAME 1, if(i)
Verifyσ∗,M∗,f∗⟶1.(ii)
M∗,f∗ has never been queried to Sign-Oracle.(iii)
Any attribute setA queried to KeyGen-Oracle does not satisfy the challenge access structure f∗.The advantageAdvAEUF1λ is defined as the probability of A winning the game above.Definition 4.
(unforgeability).An ABS scheme is existentially unforgeable under adaptive chosen message but selective attribute attack if the advantageAdvAEUF1λis negligible for any PPT adversaryA.
For a secure ABS scheme, an adversary cannot find the attribute set used to generate the signature. We describe privacy by the following game between challengerC and adversary A.GAME 2.(privacy):(i)
Setup and Queries Phase 1 are the same as Setup and Queries Phase in GAME 1, respectively(ii)
Challenge. A chooses and sends M,f,A0,A1 such that fA0=fA1=1 to C. C chooses b∈R0,1, runs Sign with inputs SKAb,M,f to generate σb, and returns σb to A.(iii)
Queries Phase 2. The same as the Queries Phase 1 above.(iv)
Guess. A outputs his guess b′∈0,1.The advantage ofA is AdvAPri1λ=Prb′=b−1/2.Definition 5 (privacy).
An ABS scheme achieves privacy if the advantageAdvAPri1λis negligible for any adversaryA.


## 3.1. Algorithms

An attribute-based signature (ABS) scheme consists of the following algorithms:(i)
Setup: it takes as input the security parameter λ and returns the system public parameters PP and master secret key msk.(ii)
KeyGen: it takes the master secret key msk and an attribute set A as inputs and returns the signing key skA.(iii)
Sign: it takes a signing key skA, a message M, and an access structure f as inputs and returns a signature σ if fA=1.(iv)
Verify: it takes a signature σ, a message M, and an access structure f as inputs and returns 1 or 0.


## 3.2. Security

A secure ABS scheme should have the properties of correctness, unforgeability, and privacy. We present formal definitions of them in the following.Definition 3 (correctness).
An ABS scheme is correct, if(3)PrVerifyσ,M,f→1PP,msk←Setup1λskA←KeyGenmsk,Aσ←SignskA,M,f=1,for anyM,f, andAsuch thatfA=1.
The popular notion of unforgeability for ABS is unforgeable under adaptive chosen message and selective access structure (EUF-sA-CMA). We describe the EUF-sA-CMA attack by the following game between challengerC and adversary A.GAME 1.(EUF-sA-CMA):(i)
Init. A sends a challenge access structure f∗ to C.(ii)
Setup. C generates and sends the system public parameters to A.(iii)
Queries Phase. A can access the following oracles.(a)
KeyGen-Oracle. A sends an attribute set A to C, C returns a signing key skA.(b)
Sign-Oracle. A sends a message M and an access structure A to C, C returns a signature.(iv)
Forgery. A outputs a triple σ∗,M∗,f∗A wins the GAME 1, if(i)
Verifyσ∗,M∗,f∗⟶1.(ii)
M∗,f∗ has never been queried to Sign-Oracle.(iii)
Any attribute setA queried to KeyGen-Oracle does not satisfy the challenge access structure f∗.The advantageAdvAEUF1λ is defined as the probability of A winning the game above.Definition 4.
(unforgeability).An ABS scheme is existentially unforgeable under adaptive chosen message but selective attribute attack if the advantageAdvAEUF1λis negligible for any PPT adversaryA.
For a secure ABS scheme, an adversary cannot find the attribute set used to generate the signature. We describe privacy by the following game between challengerC and adversary A.GAME 2.(privacy):(i)
Setup and Queries Phase 1 are the same as Setup and Queries Phase in GAME 1, respectively(ii)
Challenge. A chooses and sends M,f,A0,A1 such that fA0=fA1=1 to C. C chooses b∈R0,1, runs Sign with inputs SKAb,M,f to generate σb, and returns σb to A.(iii)
Queries Phase 2. The same as the Queries Phase 1 above.(iv)
Guess. A outputs his guess b′∈0,1.The advantage ofA is AdvAPri1λ=Prb′=b−1/2.Definition 5 (privacy).
An ABS scheme achieves privacy if the advantageAdvAPri1λis negligible for any adversaryA.


## 4. Comparative Attribute Management

### 4.1. Expansion Algorithms

Denote the usual attribute asui and the comparative attribute as u˜i. The comparative attribute is further expressed as u¨i>a¨i or u¨i<a¨i, where u¨i is its attribute name and a¨i is its threshold. Denote the user attribute corresponding to the comparative attribute u˜i as u¨i‖b¨i.In the above example, “Member of the community” is a usual attribute, “Register before 2018,” “More than 10 million game points”, and “Top 32 in the first-class competition” are comparative attributes; they can be denoted asu1, u˜2=u¨2<18, u˜3=u¨3>10, and u˜4=u¨4≤32=u¨4<33. Then, the access structure is f=u1∧u˜2∧u˜3∨u˜4. Alice’s attributes can be denoted as A=u1,u¨217,u¨320.We can easily see that Alice’s attributesA satisfy the access structure f, but the algorithm cannot. It is necessary to extend the comparative attributes and access structure so that the algorithm can use Lemma 1 to determine whether it is satisfied. We propose the following algorithms to extend the access structure and user attributes.


#### 4.1.1. AccStruExpan

The access structure expansion algorithm inputs an access structuref with its matrix M and outputs a new access structure f′ with its matrix M′.For all comparative attributesu˜i,Ifu˜i=u¨i>a¨i, encode it to 0-coding Uu˜i=Ua¨i0=u˜i,1,u˜i,2,…,u˜i,nu˜i.Ifu˜i=u¨i<a¨i, encode it to 1-coding Uu˜i=Ua¨i1=u˜i,1,u˜i,2,…,u˜i,nu˜i.Sets(4)ρ′j=ρj,j<k,u˜i,l,j=k+l−1,l∈1,2,…,nu˜i,ρj−nu˜i+1,j≥k+nu˜i,wherek:ρk=u˜i.Repeat thek-th row of the matrix nu˜i times as rows k,k+1,…,k+nu˜i−1 to obtain a new matrix.Replace each comparative attributeu˜i in f with ∨j=1nu˜iu˜i,j to get the new access structure f′.


#### 4.1.2. UserAttExpan

The user attribute expansion algorithm inputs a user attribute setA and outputs a new attribute set A′.(i)
Encode each attributeu¨i‖b¨i to 0-coding Au¨i‖b¨i0 and 1-coding Au¨i‖b¨i1(ii)
Replace each attributeu¨i‖b¨i in A with Au¨i‖b¨i0∪Au¨i‖b¨i1 to get the new attribute set A′


### 4.2. Example

To facilitate understanding the above algorithms, we use the above example to execute the algorithms as follows.AccStruExpan: Take as input f,M,ρ, where f=u1∧u˜2∧u˜3∨u˜4,(5)M=110011001010,ρ1=u1,ρ2=u˜2,ρ3=u˜3,ρ4=u˜4,(i)
Foru˜2,Encode u˜2=u¨2<18 to 1-coding:(6)Uu˜2=Uu¨2<18=U181=1,u¨2<,1001,u¨2<=u˜2,1,u˜2,2. Set ρ′1=ρ1=u1, ρ′2=u˜2,1,ρ′3=u˜2,2, ρ′4=ρ3=u˜3,ρ′5=ρ4=u˜4. Repeat the 2-th row 2 times as rows 2,3 to obtain a new matrix(7)M′=110011011001010,ρ′1=u1,ρ′2=u˜2,1,ρ′3=u˜2,2,ρ′4=u˜3,ρ′5=u˜4,(ii)
Foru˜3, Encode u˜3=u¨3>10 to 0-coding:(8)Uu˜3=Uu¨3>10=U100=1,u¨3>,01,u¨3>,001,u¨3>,00011,u¨3>,0001011,u¨3>=u˜3,1,u˜3,2,u˜3,3,u˜3,4,u˜3,5. Set ρ″1=ρ′1=u1, ρ″2=ρ′2=u˜2,1,ρ″3=ρ′3=u˜2,2, ρ″4=u˜3,1,ρ″5=u˜3,2,ρ″6=u˜3,3,ρ″7=u˜3,4,ρ″8=u˜3,5,ρ″9=ρ′9=u˜4. Repeat the 4-th row 5 times as rows 4,5,6,7,8 to obtain a new matrix:(9)M′′=110011011001001001001001010,ρ″1=u1,ρ″2=u˜2,1,ρ″3=u˜2,2,ρ″4=u˜3,1,ρ″5=u˜3,2,ρ″6=u˜3,3,ρ″7=u˜3,4,ρ″8=u˜3,5,ρ″9=u˜4.(iii)
Foru˜4,Encode u˜4=u¨4<33 to 1-coding:(10)Uu˜4=Uu¨4<33=U331=1,u¨4<,100001,u¨4<=u˜4,1,u˜4,2.Set ρ‴1=ρ″1=u1, ρ‴2=ρ″2=u˜2,1,ρ‴3=ρ″3=u˜2,2, ρ‴4=ρ″4=u˜3,1,ρ‴5=ρ″5=u˜3,2,ρ‴6=ρ″6=u˜3,3,ρ‴7=ρ″7=u˜3,4,ρ‴8=ρ″8=u˜3,5,ρ‴9=u˜4,1,ρ‴10=u˜4,2. Repeat the 9-th row 2 times as rows 9,10 to obtain the final matrix which is(11)M′″=110011011001001001001001010010,ρ‴1=u1,ρ‴2=u˜2,1,ρ‴3=u˜2,2,ρ‴4=u˜3,1,ρ‴5=u˜3,2,ρ‴6=u˜3,3,ρ‴7=u˜3,4,ρ‴8=u˜3,5,ρ‴9=u˜4,1,ρ‴10=u˜4,2. Replace u˜2,u˜3, and u˜4 with u˜2,1∨u˜2,2,u˜3,1∨u˜3,2∨u˜3,3∨u˜3,4∨u˜3,5, and u˜4,1∨u˜4,2 respectively; the final access structure is(12)f′=u1∧u˜2,1∨u˜2,2∧u˜3,1∨u˜3,2∨u˜3,3∨u˜3,4∨u˜3,5∨u˜4,1∨u˜4,2.UserAttExpan: take as input A=u1,u¨217,u¨320.(i)
Encode attributeu¨2‖17 to 0-coding:(13)Au¨2‖170=11,u¨2<,101,u¨2<,1001,u¨2<=u2,1,u2,2,u2,3.and 1-coding(14)Au¨2‖171=1,u¨2>,10001,u¨2>=u2,4,u2,5.(ii)
Encode attributeu¨3‖20 to 0-coding:(15)Au¨3200=1,u¨3<,01,u¨3<,0011,u¨3<,001011,u¨3<,0010101,u¨3<=u3,1,u3,2,u3,3,u3,4,u3,5,and 1-coding(16)Au¨3‖201=001,u¨3>,00101,u¨3>=u3,6,u3,7.(iii)
The new user attribute setA′=u1,u2,1,u2,2,u2,3,u2,4,u2,5,u3,1,u3,2,u3,3,u3,4,u3,5,u3,6,u3,7.When running the algorithms above, we assume that the value spaces of the comparative attributesu˜2,u˜3, and u˜4 are 0,31,0,127, and 0,63, respectively. If the trivial expansion method is used, the matrix of the access structure will increase from 4 rows to 168 rows, while using our expansion method, the matrix only grows to 10 rows. There is a 15.8 times gap between the two, which shows that our expansion method is effective.


## 4.1. Expansion Algorithms

Denote the usual attribute asui and the comparative attribute as u˜i. The comparative attribute is further expressed as u¨i>a¨i or u¨i<a¨i, where u¨i is its attribute name and a¨i is its threshold. Denote the user attribute corresponding to the comparative attribute u˜i as u¨i‖b¨i.In the above example, “Member of the community” is a usual attribute, “Register before 2018,” “More than 10 million game points”, and “Top 32 in the first-class competition” are comparative attributes; they can be denoted asu1, u˜2=u¨2<18, u˜3=u¨3>10, and u˜4=u¨4≤32=u¨4<33. Then, the access structure is f=u1∧u˜2∧u˜3∨u˜4. Alice’s attributes can be denoted as A=u1,u¨217,u¨320.We can easily see that Alice’s attributesA satisfy the access structure f, but the algorithm cannot. It is necessary to extend the comparative attributes and access structure so that the algorithm can use Lemma 1 to determine whether it is satisfied. We propose the following algorithms to extend the access structure and user attributes.


### 4.1.1. AccStruExpan

The access structure expansion algorithm inputs an access structuref with its matrix M and outputs a new access structure f′ with its matrix M′.For all comparative attributesu˜i,Ifu˜i=u¨i>a¨i, encode it to 0-coding Uu˜i=Ua¨i0=u˜i,1,u˜i,2,…,u˜i,nu˜i.Ifu˜i=u¨i<a¨i, encode it to 1-coding Uu˜i=Ua¨i1=u˜i,1,u˜i,2,…,u˜i,nu˜i.Sets(4)ρ′j=ρj,j<k,u˜i,l,j=k+l−1,l∈1,2,…,nu˜i,ρj−nu˜i+1,j≥k+nu˜i,wherek:ρk=u˜i.Repeat thek-th row of the matrix nu˜i times as rows k,k+1,…,k+nu˜i−1 to obtain a new matrix.Replace each comparative attributeu˜i in f with ∨j=1nu˜iu˜i,j to get the new access structure f′.


### 4.1.2. UserAttExpan

The user attribute expansion algorithm inputs a user attribute setA and outputs a new attribute set A′.(i)
Encode each attributeu¨i‖b¨i to 0-coding Au¨i‖b¨i0 and 1-coding Au¨i‖b¨i1(ii)
Replace each attributeu¨i‖b¨i in A with Au¨i‖b¨i0∪Au¨i‖b¨i1 to get the new attribute set A′


## 4.1.1. AccStruExpan

The access structure expansion algorithm inputs an access structuref with its matrix M and outputs a new access structure f′ with its matrix M′.For all comparative attributesu˜i,Ifu˜i=u¨i>a¨i, encode it to 0-coding Uu˜i=Ua¨i0=u˜i,1,u˜i,2,…,u˜i,nu˜i.Ifu˜i=u¨i<a¨i, encode it to 1-coding Uu˜i=Ua¨i1=u˜i,1,u˜i,2,…,u˜i,nu˜i.Sets(4)ρ′j=ρj,j<k,u˜i,l,j=k+l−1,l∈1,2,…,nu˜i,ρj−nu˜i+1,j≥k+nu˜i,wherek:ρk=u˜i.Repeat thek-th row of the matrix nu˜i times as rows k,k+1,…,k+nu˜i−1 to obtain a new matrix.Replace each comparative attributeu˜i in f with ∨j=1nu˜iu˜i,j to get the new access structure f′.


## 4.1.2. UserAttExpan

The user attribute expansion algorithm inputs a user attribute setA and outputs a new attribute set A′.(i)
Encode each attributeu¨i‖b¨i to 0-coding Au¨i‖b¨i0 and 1-coding Au¨i‖b¨i1(ii)
Replace each attributeu¨i‖b¨i in A with Au¨i‖b¨i0∪Au¨i‖b¨i1 to get the new attribute set A′


## 4.2. Example

To facilitate understanding the above algorithms, we use the above example to execute the algorithms as follows.AccStruExpan: Take as input f,M,ρ, where f=u1∧u˜2∧u˜3∨u˜4,(5)M=110011001010,ρ1=u1,ρ2=u˜2,ρ3=u˜3,ρ4=u˜4,(i)
Foru˜2,Encode u˜2=u¨2<18 to 1-coding:(6)Uu˜2=Uu¨2<18=U181=1,u¨2<,1001,u¨2<=u˜2,1,u˜2,2. Set ρ′1=ρ1=u1, ρ′2=u˜2,1,ρ′3=u˜2,2, ρ′4=ρ3=u˜3,ρ′5=ρ4=u˜4. Repeat the 2-th row 2 times as rows 2,3 to obtain a new matrix(7)M′=110011011001010,ρ′1=u1,ρ′2=u˜2,1,ρ′3=u˜2,2,ρ′4=u˜3,ρ′5=u˜4,(ii)
Foru˜3, Encode u˜3=u¨3>10 to 0-coding:(8)Uu˜3=Uu¨3>10=U100=1,u¨3>,01,u¨3>,001,u¨3>,00011,u¨3>,0001011,u¨3>=u˜3,1,u˜3,2,u˜3,3,u˜3,4,u˜3,5. Set ρ″1=ρ′1=u1, ρ″2=ρ′2=u˜2,1,ρ″3=ρ′3=u˜2,2, ρ″4=u˜3,1,ρ″5=u˜3,2,ρ″6=u˜3,3,ρ″7=u˜3,4,ρ″8=u˜3,5,ρ″9=ρ′9=u˜4. Repeat the 4-th row 5 times as rows 4,5,6,7,8 to obtain a new matrix:(9)M′′=110011011001001001001001010,ρ″1=u1,ρ″2=u˜2,1,ρ″3=u˜2,2,ρ″4=u˜3,1,ρ″5=u˜3,2,ρ″6=u˜3,3,ρ″7=u˜3,4,ρ″8=u˜3,5,ρ″9=u˜4.(iii)
Foru˜4,Encode u˜4=u¨4<33 to 1-coding:(10)Uu˜4=Uu¨4<33=U331=1,u¨4<,100001,u¨4<=u˜4,1,u˜4,2.Set ρ‴1=ρ″1=u1, ρ‴2=ρ″2=u˜2,1,ρ‴3=ρ″3=u˜2,2, ρ‴4=ρ″4=u˜3,1,ρ‴5=ρ″5=u˜3,2,ρ‴6=ρ″6=u˜3,3,ρ‴7=ρ″7=u˜3,4,ρ‴8=ρ″8=u˜3,5,ρ‴9=u˜4,1,ρ‴10=u˜4,2. Repeat the 9-th row 2 times as rows 9,10 to obtain the final matrix which is(11)M′″=110011011001001001001001010010,ρ‴1=u1,ρ‴2=u˜2,1,ρ‴3=u˜2,2,ρ‴4=u˜3,1,ρ‴5=u˜3,2,ρ‴6=u˜3,3,ρ‴7=u˜3,4,ρ‴8=u˜3,5,ρ‴9=u˜4,1,ρ‴10=u˜4,2. Replace u˜2,u˜3, and u˜4 with u˜2,1∨u˜2,2,u˜3,1∨u˜3,2∨u˜3,3∨u˜3,4∨u˜3,5, and u˜4,1∨u˜4,2 respectively; the final access structure is(12)f′=u1∧u˜2,1∨u˜2,2∧u˜3,1∨u˜3,2∨u˜3,3∨u˜3,4∨u˜3,5∨u˜4,1∨u˜4,2.UserAttExpan: take as input A=u1,u¨217,u¨320.(i)
Encode attributeu¨2‖17 to 0-coding:(13)Au¨2‖170=11,u¨2<,101,u¨2<,1001,u¨2<=u2,1,u2,2,u2,3.and 1-coding(14)Au¨2‖171=1,u¨2>,10001,u¨2>=u2,4,u2,5.(ii)
Encode attributeu¨3‖20 to 0-coding:(15)Au¨3200=1,u¨3<,01,u¨3<,0011,u¨3<,001011,u¨3<,0010101,u¨3<=u3,1,u3,2,u3,3,u3,4,u3,5,and 1-coding(16)Au¨3‖201=001,u¨3>,00101,u¨3>=u3,6,u3,7.(iii)
The new user attribute setA′=u1,u2,1,u2,2,u2,3,u2,4,u2,5,u3,1,u3,2,u3,3,u3,4,u3,5,u3,6,u3,7.When running the algorithms above, we assume that the value spaces of the comparative attributesu˜2,u˜3, and u˜4 are 0,31,0,127, and 0,63, respectively. If the trivial expansion method is used, the matrix of the access structure will increase from 4 rows to 168 rows, while using our expansion method, the matrix only grows to 10 rows. There is a 15.8 times gap between the two, which shows that our expansion method is effective.


## 5. Comparable Attribute-Based Signature Scheme

Based on the above comparative attribute management method and Chen et al.’s attribute-based signature scheme [11], we propose a practical attribute-based signature scheme that supports comparative attributes.


### 5.1. The Overall Framework

The overall framework of our scheme is shown in Figure1. The Setup algorithm generates the public parameters and master private key for the system. The KeyGen algorithm calls the UserAttExpan algorithm to generate the private key. The Sign algorithm and the Verify algorithm call the AccStruExpan algorithm to generate a signature and verify the signature, respectively.Figure 1
The framework of SPCABS.


### 5.2. The Proposed Scheme

Chen et al.’s scheme inputs the attribute universe in theSetup phase and its public key is related to the attribute universe, so it is challenging to support attribute expansion. We use the hash value H1u of attribute u instead of the public key hu in Chen et al.’s scheme. So the scheme can support the dynamic attribute universe and solve the problem of not supporting attribute expansion. Another advantage is that the size of the public key is significantly reduced.(i)
Setup1λ,1k: Choose two prime order p>2λ multiplicative cyclic groups G, GT with a generator g and a bilinear map e:G×G⟶GT. Choose two collision-resistant hash functions H1:0,1∗⟶G, H2:0,1∗⟶0,1kChoose a,α∈Rℤp, then compute y=ga,Z=eg,gα. Choose u0,ui∈RG,i=1,2,…,k. The public parameters PP=p,g,G,GT,e,y,Z,H1,H2,u0,uii=1k and the master secret key MSK=α.(ii)
KeyGenPP,MSK,A: Run the user attribute expansion algorithm UserAttExpan, and extend A to A′. Pick a random value t∈Rℤp, and compute(17)D=gα⋅yt,L=gt,Du=H1tuu∈A′.The private key SKA=D,L,Duu∈A′.(iii)
SignPP,f,M,SKA: Run the access structure expansion algorithm AccStruExpan, extend Mf,ρ to Mf′,ρ′.Let I=i∈lf′:ρ′i∈A′, and find wi:i∈I such that ∑i∈IwiMf′i=1, where 1=1,0,…,0. Set wi=0 for i∈lf′\I. Pick random vii=1lf′ satisfying ∑i=1lf′viMf′i=0, where 0=0,0,…,0. Choose t′∈Rℤp, randomize part of the private key(18)D′=D⋅yt′,L′=L⋅gt′,Du′=Du⋅H1t′uu∈ρ′i:i∈I.Compute h=H2f‖M=h1h2…hk, and HM=u0⋅∑i=1kuihi.Choose r,s∈Rℤp, and compute(19)σ0=D′⋅HMr,σ0′=gr,σ0,i=L′wi⋅gsvi,i∈lf′,σ1,i=Dρ′i′wi⋅H1sviρ′i,i∈lf′.The final signature σ=σ0,σ0′,σ0,i,σ1,ii=1lf′.(iv)
VerifyPP,σ,M,f: Run the access structure expansion algorithm AccStruExpan, and extend Mf,ρ to Mf′,ρ′. Pick a random vector x=x,x2,…,xn∈ℤpn, and compute the shares λi=x,Mf′i for i=1,…,lf′. Compute h=H2f‖M=h1h2…hk, and HM=u0⋅∑i=1kuihi. The verifier checks the equation(20)egx,σ0eHMx,σ0′⋅∏i=1lf′eyλiH1−xρ′i,σ0,i⋅egx,σ1,i=?Zx.


## 5.1. The Overall Framework

The overall framework of our scheme is shown in Figure1. The Setup algorithm generates the public parameters and master private key for the system. The KeyGen algorithm calls the UserAttExpan algorithm to generate the private key. The Sign algorithm and the Verify algorithm call the AccStruExpan algorithm to generate a signature and verify the signature, respectively.Figure 1
The framework of SPCABS.


## 5.2. The Proposed Scheme

Chen et al.’s scheme inputs the attribute universe in theSetup phase and its public key is related to the attribute universe, so it is challenging to support attribute expansion. We use the hash value H1u of attribute u instead of the public key hu in Chen et al.’s scheme. So the scheme can support the dynamic attribute universe and solve the problem of not supporting attribute expansion. Another advantage is that the size of the public key is significantly reduced.(i)
Setup1λ,1k: Choose two prime order p>2λ multiplicative cyclic groups G, GT with a generator g and a bilinear map e:G×G⟶GT. Choose two collision-resistant hash functions H1:0,1∗⟶G, H2:0,1∗⟶0,1kChoose a,α∈Rℤp, then compute y=ga,Z=eg,gα. Choose u0,ui∈RG,i=1,2,…,k. The public parameters PP=p,g,G,GT,e,y,Z,H1,H2,u0,uii=1k and the master secret key MSK=α.(ii)
KeyGenPP,MSK,A: Run the user attribute expansion algorithm UserAttExpan, and extend A to A′. Pick a random value t∈Rℤp, and compute(17)D=gα⋅yt,L=gt,Du=H1tuu∈A′.The private key SKA=D,L,Duu∈A′.(iii)
SignPP,f,M,SKA: Run the access structure expansion algorithm AccStruExpan, extend Mf,ρ to Mf′,ρ′.Let I=i∈lf′:ρ′i∈A′, and find wi:i∈I such that ∑i∈IwiMf′i=1, where 1=1,0,…,0. Set wi=0 for i∈lf′\I. Pick random vii=1lf′ satisfying ∑i=1lf′viMf′i=0, where 0=0,0,…,0. Choose t′∈Rℤp, randomize part of the private key(18)D′=D⋅yt′,L′=L⋅gt′,Du′=Du⋅H1t′uu∈ρ′i:i∈I.Compute h=H2f‖M=h1h2…hk, and HM=u0⋅∑i=1kuihi.Choose r,s∈Rℤp, and compute(19)σ0=D′⋅HMr,σ0′=gr,σ0,i=L′wi⋅gsvi,i∈lf′,σ1,i=Dρ′i′wi⋅H1sviρ′i,i∈lf′.The final signature σ=σ0,σ0′,σ0,i,σ1,ii=1lf′.(iv)
VerifyPP,σ,M,f: Run the access structure expansion algorithm AccStruExpan, and extend Mf,ρ to Mf′,ρ′. Pick a random vector x=x,x2,…,xn∈ℤpn, and compute the shares λi=x,Mf′i for i=1,…,lf′. Compute h=H2f‖M=h1h2…hk, and HM=u0⋅∑i=1kuihi. The verifier checks the equation(20)egx,σ0eHMx,σ0′⋅∏i=1lf′eyλiH1−xρ′i,σ0,i⋅egx,σ1,i=?Zx.


## 6. Proofs of Security

Theorem 1 (correctness).
The proposed scheme is correct.Proof.
Because(21)σ0=D′⋅HMr,σ0′=gr,σ0,i=L′wi⋅gsvi,i∈lf′,σ1,i=Dρ′i′wi⋅H1sviρ′i,i∈lf′,we have(22)egx,σ0=egx,D′⋅HMr=egx,gα⋅yt⋅yt′⋅HMr=egx,gα⋅gat+t′⋅HMr=eg,gxα⋅eg,gxat+t′⋅eg,HMxr,eHMx,σ0′=eHMx,gr=eg,HMxr,eyλiH1−xρ′i,σ0,i⋅egx,σ1,i=egaλiH1−xρ′i,L′wigsvi⋅egx,Dρ′i′wiH1sviρ′i=egaλiH1−xρ′i,L⋅gt′wigsvi⋅egx,Dρ′iwi⋅H1t′wiρ′iH1sviρ′i=egaλiH1−xρ′i,gt+t′wi⋅gsvi⋅egx,H1t+t′wiρ′iH1sviρ′i=eg,gaλit+t′wi+svi.Then,(23)∏i=1lf′eyλiH1−xρ′i,σ0,i⋅egx,σ1,i=∏i=1lf′eg,gaλit+t′wi+svi=eg,gat+t′∑i∈Iλiwi⋅eg,gas∑i=1lf′λivi=eg,gxat+t′.
Therefore,(24)egx,σ0eHMx,σ0′⋅∏i=1lf′eyλiH1−xρ′i,σ0,i⋅egx,σ1,i=eg,gxα⋅eg,gxat+t′⋅eg,HMxreg,HMxr⋅eg,gxat+t′=Zx.
The verification equation is established, so the proposed scheme is correct. □Theorem 2 (unforgeability).
If the CDHE problem is difficult, then the proposed scheme above is existentially unforgeable under adaptive chosen message but selective access structure attack.Proof.
LetA be an adversary against our scheme, and let C be a challenger who generates a random instance of the CDHE problem. We construct an adversary ℬ, which uses A as a subroutine, to solve the CDHE problem as follows. Here, ℬ acts as a challenger of our scheme for A as well. Let k^ be the maximum number of columns of the access structure matrixes and let qs be the maximum number of Sign-Oracle queries.(i)
CDHE Problem Gen. C generates a random instance of the CDHE problem p,G,GT,e,g,gi=gaii=1,i≠k^+12k^ and sends it to ℬ.(ii)
Init. A sends a challenge access structure f∗=Ml∗×k∗∗,ρ∗ to ℬ. ℬ extends f∗ to f∗′=M′l′∗×k′∗∗,ρ′∗ by running AccStruExpan.(iii)
Setup. Choose α′∈Rℤp and set y=ga,Z=ega,gak^eg,gα′=eg,gak^+1+α′=eg,gα, where α=ak^+1+α′. Let lM=4qs,kM∈Rk, choose ϕ0,ϕ1,…,ϕk∈ℤlM and π0,π1,…,πk∈ℤp, and set u0=gap−lMkM+π0⋅gϕ0 and ui=gaπi⋅gϕi, i=1,…,k. Forward PP=p,g,G,GT,e,y,Z,u0,uii=1k to A.(iv)
H1-Oracle. A sends an attribute u to ℬ.ℬ chooses zu∈Rℤp. If there exists i such that ρ′∗i=u, then let(25)hu=gzugaMi,1∗ga2Mi,2∗…gak′∗Mi,k′∗∗.Otherwise, let hu=gzu.Return hu to A.(v)
H2-Oracle. A sends access structure f and a message M to ℬ. ℬ chooses h∈R0,1k and returns it to A.(vi)
KeyGen-Oracle. A sends an attribute set A to ℬ. ℬ extends A to A′ by running UserAttExpan. Finds v=v1=−1,v2,…,vk′∗ such that vM′i∗=0 for all i∈1,l′∗:ρ′∗i∈A′.Choose r∈ℤp and set(26)L=gr∏i=1k′∗gak^−i+1vi=gt,D=gα′gar⋅∏i=2k′∗gak^−i+2vi=gα⋅yt,where t=r+∑i=1k′viak^−i+1. For all u∈A′, request H1-Oracle on u. If there exists i such that ρ′∗i=u, then let(27)Du=Lzu⋅∏j=1k′∗gaj⋅r∏d≠jgak^+1+j−dvdMi,j∗=H1ut.Otherwise, let(28)Du=Lzu=gtzu=H1ut.Return skA′=D,L,Duu∈A′.(v)
Sign-Oracle. A sends a message M and an access structure f to ℬ.ℬ extends f to f′ by running AccStruExpan. Finds wi:i∈I such that ∑i∈IwiMf′i=1, where I=i∈lf′:ρ′i∈A′, 1=1,0,…,0. Set wi=0 for i∈lf′\I.Request H2Oracle on f‖M and get h=H2f‖M=h1h2…hk. Compute(29)FM=p−lMkM+π0+∑j=1kπj⋅hj,JM=ϕ0+∑j=1kϕj⋅hj,KM=0,ifπ0+∑j=1kπj⋅hj≡0modlM1,otherwise.If KM=0, the simulation stops. If KM≠0, then FM≠0modp, because we can assume lMk+1<p for any reasonable values of p,k and lM. Choose t,s∈Rℤp, and vii=1,…,lf′ such that ∑i=1lf′vi⋅Mi=0, and then compute(30)σ0=gat+α′⋅gα′⋅gak^−JM/FM=gα⋅yt⋅u0∏i=1kuihi−ak^/FM=gα⋅yt⋅HMr′,σ0′=gak^−1/FM=g−ak^/FM=gr′,σ0,i=gwit+vis,i∈lf′,σ1,i=H1ρiwit+vis,i∈lf′,where r′=−ak^/FM.Return the signature σ=σ0,σ0′,σ0,i,σ1,ii=1,…,lf′.(vi)
Output: A outputs a triple σ∗,M∗,f∗. If FM∗≠0, then the simulation stops. Otherwise, ℬ computes and outputs(31)σ0∗⋅∏i=1l′∗σ0,i∗zρ′∗i∏i=1l′∗σ1,i∗⋅σ0′∗JM∗⋅gα′=gak^+1.The calculation of the above equation is as follows:(32)σ0∗⋅∏i=1l′∗σ0,i∗zρ′∗i∏i=1l′∗σ1,i∗⋅σ0'∗JM∗⋅gα′=gα⋅yt∗⋅HMr∗⋅∏i=1l′∗gwi∗t∗+vi∗s∗zρ′∗i∏i=1l′∗H1ρ′∗iwi∗t∗+vi∗s∗⋅gr∗JM∗⋅gα′,=gak^+1+α′⋅gat∗⋅gr∗aFM∗+JM∗⋅∏i=1l′∗gwi∗t∗+vi∗s∗zρ′∗igat∗⋅∏i=1l′∗gwi∗t∗+vi∗s∗zρ′∗i⋅gr∗JM∗⋅gα′,=gak^+1.Note thatFM∗=0..According to Claim 2 of Waters [42], the probability that the simulation is not aborted is 1/8qsk+1. Therefore, if A can successfully forge a valid signature with probability ε, then ℬ can solve the CDHE problem with probability ε′≥ε/8qsk+1.Theorem 3 (privacy).
The proposed scheme achieves privacy.Proof.
The adversaryA and the challenger C perform the following interactive game:(i)
C executes the Setup algorithm to set up the system and responds to the oracle requests by running the corresponding algorithm.(ii)
A chooses and sends M,f,A0,A1 such that fA0=fA1=1 to C.(iii)
C chooses b∈R0,1, runs Sign with inputs SKAb,M,f to generate σb, and returns it to A.(iv)
C continues to respond to the oracle requests by running the corresponding algorithm.
Sinceσb=σ0b,σ0b′,σ0b,i,σ1b,ii=1lf′ is a signature on M,f using SKAb, we have(33)σ0b=Db′⋅HMrb=gα⋅gatb+tb′⋅HMrb,σ0b′=grb,σ0b,i=Lb′wbi⋅gsbvbi=gtb+tb′wbi+sbvbi,i∈lf′,σ1b,i=Dbρ′i′wbi⋅H1ρ′isbvbi=H1ρ′itb+tb′wbi+sbvbi,i∈lf′,where wb=wb1,wb2,…,wblf′ and vb=vb1,vb2,…,vblf′ such that(34)wbMf′=∑i=1lf′wbiMf′i=1,vbMf′=∑i=1lf′vbiMf′i=0.
LetIb¯=i∈lf′:ρ′i∈Ab¯′, and find wb¯i:i∈Ib¯ such that ∑i∈Ib¯wb¯iMf′i=1, where 1=1,0,…,0. Set wbi¯=0 for i∈lf′∖Ib¯.
Letwb¯=wb¯1,wb¯2,…,wb¯lf′ and vb¯=sb−1tb+tb′wb−wb¯+vb; then,(35)vb¯Mf′=sb−1tb+tb′wbMf′−wb¯Mf′+vbMf′=0.Now, we rewrite σb=σ0b,σ0b′,σ0b,i,σ1b,ii=1lf′ as(36)σ0b=gα⋅gatb+tb′⋅HMrb=gα⋅gatb¯+tb′−tb¯⋅HMrb=gα⋅gatb¯+tb¯′⋅HMrb=Db¯′⋅HMrb,σ0b′=grb,σ0b,i=gtb+tb′wbi+sbvbi=gtb¯+tb¯′wb¯i+sbvb¯i=Lb¯′wb¯i⋅gsbvb¯i,i∈lf′σ1b,i=H1ρ′itb+tb′wbi+sbvbi=H1ρ′itb¯+tb¯′wb¯i+sbvb¯i=Db¯ρ′i′wb¯i⋅H1ρ′isbvb¯i,i∈lf′,where tb¯′=tb′−tb¯.
This concludes thatσb is also a signature using SKAb¯. Therefore, even if the adversary has an unlimited capability, it is impossible to distinguish which attribute set was used to generate the signature, and the advantage of A of winning GAME 2 is 0. The proposed scheme achieves privacy.


## 7. Performance Analysis and Experimental Simulation

### 7.1. Performance Analysis

We compare our method with the trivial method in terms of data size and computational overhead. Without loss of generality, we assume that the attribute universeU=u˜1,…,u˜n1,un1+1,…,un1+n2, where u˜i is a comparative attribute and its value space is Ni; a¨i takes the number near the median of the value space; the access structure f contains attributes u˜1,…,u˜l1,un1+1,…,un1+l2 and each attribute only appears once; the user’s attribute set A=u¨1b¨1,…,u¨t1b¨t1,un1+1,…,un1+t2. Let k be the length of the output of the Hash function, and let G and ℤp be an element of G and ℤp, respectively. Denote by P a pairing operation and by E an exponentiation operation, respectively.The comparison is carried out on five schemes, and the results are shown in Tables3–10. In these tables, the left column shows the theoretical calculation results, and the right column shows the results in the case of the above example.Table 3
Comparison of master public key sizes.
SchemesTrivial methodOur methodPercentageTheoreticalExampleTheoreticalExampleMaji et al. [6]2n1′+2n2+1G289G2n1′′+2n2+1|G|11G3.81%Gu et al. [7]n1′+n2+6G150Gn1′′+n2+6|G|11G7.33%Chen et al. [11]n1′+n2+k+3G307Gk+3|G|163G53.09%Okamoto and Takashima [9]17n1′+17n2+29G2477G17n1′′+17n2+29|G|114G4.60%Okamoto and Takashima [22]39n1′+39n2G5616G39n1′′+39n2|G|195G3.47%•n1′=∑i=1n1Ni/2,n1′′=∑i=1n1log2Ni/2.Table 4
Comparison of master secret key sizes.
SchemesTrivial methodOur methodPercentageTheoreticalExampleTheoreticalExampleMaji et al. [6]3ℤp3ℤp3ℤp3ℤp100%Gu et al. [7]1ℤp1ℤp1ℤp1ℤp100%Chen et al. [11]1ℤp1ℤp1ℤp1ℤp100%Okamoto and Takashima [9]1G1G1G1|G|100%Okamoto and Takashima [22]13n1′+13n2ℤp1872ℤp13n1′′+13n2ℤp65ℤp3.47%•n1′=∑i=1n1Ni/2,n1′′=∑i=1n1log2Ni/2.Table 5
Comparison of signing key sizes.
SchemesTrivial methodOur methodPercentageTheoreticalExampleTheoreticalExampleMaji et al. [6]t1+t2+1G4Gt1′′+t2+1G14G350%Gu et al. [7]t1+t2+2G5Gt1′′+t2+2G15G300%Chen et al. [11]t1+t2+2G5Gt1′′+t2+2G15G300%Okamoto and Takashima [9]t1+t2+3G6Gt1′′+t2+3G16G267%Okamoto and Takashima [22]13t1+13t2G39G13t1′′+13t2G169G433%•t1′′=∑i=1n1log2Ni/2.Table 6
Comparison of signature sizes.
SchemesTrivial methodOur methodPercentageTheoreticalExampleTheoreticalExampleMaji et al. [6]2l1′+l2+2G230G2l1′′+l2+2G24G10.43%Gu et al. [7]2l1′+l2+2G227G2l1′′+l2+2G21G9.25%Chen et al. [11]2l1′+l2+1G228G2l1′′+l2+1G22G9.65%Okamoto and Takashima [9]l1′+l2+2G115Gl1′′+l2+2G12G10.43%Okamoto and Takashima [22]l1′+l2G113Gl1′′+l2G10G8.85%•l1′=∑i=1l1Ni/2,l1′′=∑i=1l1log2Ni/2.Table 7
Comparison of master public key generation overhead.
SchemesTrivial methodOur methodPercentageTheoreticalExampleTheoreticalExampleMaji et al. [6]2n′+1E73E2n″+1E11E15.07%Gu et al. [7]1E1E1E1E100%Chen et al. [11]2E+1P2E+1P2E+1P2E+1P100%Okamoto and Takashima [9]144n′+162E144E144n″+162E5E3.47%Okamoto and Takashima [22]8n′E1152E8n′′E40E3.47%•n′=∑i=1n1Ni/2+n2,n″=∑i=1n1log2Ni/2+n2.Table 8
Comparison of signing key generation overhead.
SchemesTrivial methodOur methodPercentageTheoreticalExampleTheoreticalExampleMaji et al. [6]t′+1E4Et″+1E14E350.00%Gu et al. [7]t′+2E5Et″+2E15E300.00%Chen et al. [11]t′+3E6Et″+3E16E266.67%Okamoto and Takashima [9]4t′+8E20E4t″+8E60E300.00%Okamoto and Takashima [22]8t′E24E8t′′E192E800.00%•t′=∑i=1t1Ni/2+t2,t″=∑i=1t1log2Ni/2+t2.Table 9
Comparison of signature generation overhead.
SchemesTrivial methodOur methodPercentageTheoreticalExampleTheoreticalExampleMaji et al. [6]4lf+2E678E4lf′+2E42E6.19%Gu et al. [7]2lf+5E343E2lf′+5E25E7.29%Chen et al. [11]2lf+2I+3E347E2lf′+2I+3E29E8.36%Okamoto and Takashima [9]3lf+3E510E3lf′+333E6.47%Okamoto and Takashima [22]9lfE1521E9lf′E90E5.92%Table 10
Comparison of signature verification overhead.
SchemesTrivial methodOur methodPercentageTheoreticalExampleTheoreticalExampleMaji et al. [6]3lfE+2lf+2P507E+340P3lf′E+2lf′+2P30E+22P6.44%Gu et al. [7]lf+2E+2lf+4P171E+342Plf′+2E+2lf′+4P12E+24P7.01%Chen et al. [11]2lf+3E+2lf+2P341E+340P2lf′+3E+2lf′+2P23E+22P6.69%Okamoto and Takashima [9]4lf+6E+lf+3P682E+172P4lf′+6E+lf′+3P46E+13P7.45%Okamoto and Takashima [22]10lf+1E+lfP1691E+169P10lf′+1E+lf′P101E+10P5.93%The analysis shows the following:(1)
Our method has significant advantages in signature size, signature generation overhead, and signature verification overhead, which is less than 10% of the trivial method.(2)
There is also a significant advantage in master public key size. Except for [11] which is about half, the others are less than 10%.(3)
There are also advantages in the overhead of master public key generation, especially when applied to the schemes of [6, 9] and [22].(4)
The sizes of the master secret keys are the same except for [22]. For [22], our method can reduce the size of the master private key to 3.47%.(5)
In terms of signing key size and signing key generation overhead, our method is not as good as the trivial method, which is about three times theirs.Generally, the system only needs to generate a signing key once for each user, and the user only needs one signing key. However, one user may sign multiple messages to generate multiple signatures, and a signature may be verified multiple times by different users. Our method has advantages in the case of “multiple,” while the disadvantages are “one-time.” Therefore, our method has significant advantages.


### 7.2. Experimental Simulation

Two main factors are affecting the system data size and computing overhead. One is the number of attributes, especially comparative attributes. The second is the size of the value space of the comparative attribute. We simulate and analyze these two cases, respectively. The simulation experiment is carried out on the windows 10 subsystem Debian-10.9, 11th Gen Intel(R) Core(TM) i7-11370H @3.30 GHz, CPU× 4, RAM 16 GB, and the PBC-0.5.14 library. We use “a.param” as the incoming parameter file of the PBC library.The first scenario we simulated assumes that the access structure hasl1 comparative attributes and l2 usual attributes, and the user has t1 comparative attributes and t2 usual attributes. l1,l2,t1,t2 take five groups of data, which are 3,1,2,1,6,2,4,2,9,3,6,3,12,4,8,4, and 16,6,10,6. The results are shown in Figures 2–5.Figure 2
Comparison of master public key sizes on the attribute number.Figure 3
Comparison of signature sizes on the attribute number.Figure 4
Comparison of signing overhead on the attribute number.Figure 5
Comparison of verification overhead on the attribute number.The simulation results show that our scheme has significant advantages in data size and computational overhead. The details are as follows:(1)
In terms of master public key size, using our method, the average sizes of the five schemes are 91, 51, 163, 794, and 1755 Kb, respectively. Using the trivial method, the average size of the five schemes increases to 2260, 1135, 1292, 19232, and 44054 Kb. In other words, our method reduces the master public key sizes to 4.03%, 4.49%, 12.61%, 4.13%, and 3.98%. See Figure2.(2)
In terms of master secret key size, using our method, the average sizes of the five schemes are 72.4, 71.4, 70.4, 36.2, and 34.2 Kb, respectively. Using the trivial method, the average size of the five schemes increases to 1130, 1129 1128, 565, and 563 Kb. That is, our method reduces the master public key sizes to 6.41%, 6.32%, 6.24%, 6.41%, and 6.07%. See Figure3. Because the data of the [6, 7] and [11] schemes are very close, and the data of the [9, 22] schemes are also very close, it seems that there are only 2 schemes and 4 polylines in Figure 3. In fact, there are 5 schemes and 10 polylines.(3)
The cost of signature generation for the 5 schemes grows linearly with the number of attributes, whether using our method or the trivial method. But the increase is much faster with the trivial method, and the 5 dashed lines representing the trivial method are all above the 5 solid lines representing our method. The signing overhead using our method is 0.10, 0.05, 0.08, 0.07, and 0.22 seconds on average, which are about 6% of the trivial method. See Figure4.(4)
Similarly, the overhead of signature verification can be reduced to about 6% of the trivial method with our method. Here, the advantage of the scheme [11] is obvious. The minimum overhead is 0.03 seconds, and the maximum overhead is only 0.09 seconds, which is only 1.28% of the trivial method. See Figure 5.The second scenario we simulated uses the example above. The value space of comparative attributesu˜2,u˜3, and u˜4 takes five groups of data such as 25,27,26,26,28,27,27,29,28,28,210,29, and 29,211,210. The results are shown in Figures 6–9. They show that the advantages of our method are more significant in the second case.(1)
When using our method, the signature size, signing overhead, and verification overhead all remain largely unchanged. Instead, they both grow exponentially faster using the trivial method. In all three aspects, our method reduces them to within 2%.(2)
Our method also grows slower than the trivial method in terms of master public key size. It can be reduced to about 15% in all five schemes.(3)
Using our method, the average size of the master public key for the 5 schemes is 241, 126, 163, 2072, and 4687 Kb; the average size of the signature for the 5 schemes is 30, 27, 28, 15, and 13 Kb, respectively.(4)
Using our method, the average signature generation overhead for the 5 schemes is 0.04, 0.02, 0.03, 0.03, and 0.08 seconds; the average verification overhead for the 5 schemes is 0.56, 0.58, 0.04, 0.34, and 0.34 seconds, respectively.Figure 6
Comparison of master public key sizes on the value space.Figure 7
Comparison of signature sizes on the value space.Figure 8
Comparison of signing overhead on the value space.Figure 9
Comparison of verification overhead on the value space.Overall, the simulation results show that our method has significant advantages over the trivial method and is then practicable and meaningful.


## 7.1. Performance Analysis

We compare our method with the trivial method in terms of data size and computational overhead. Without loss of generality, we assume that the attribute universeU=u˜1,…,u˜n1,un1+1,…,un1+n2, where u˜i is a comparative attribute and its value space is Ni; a¨i takes the number near the median of the value space; the access structure f contains attributes u˜1,…,u˜l1,un1+1,…,un1+l2 and each attribute only appears once; the user’s attribute set A=u¨1b¨1,…,u¨t1b¨t1,un1+1,…,un1+t2. Let k be the length of the output of the Hash function, and let G and ℤp be an element of G and ℤp, respectively. Denote by P a pairing operation and by E an exponentiation operation, respectively.The comparison is carried out on five schemes, and the results are shown in Tables3–10. In these tables, the left column shows the theoretical calculation results, and the right column shows the results in the case of the above example.Table 3
Comparison of master public key sizes.
SchemesTrivial methodOur methodPercentageTheoreticalExampleTheoreticalExampleMaji et al. [6]2n1′+2n2+1G289G2n1′′+2n2+1|G|11G3.81%Gu et al. [7]n1′+n2+6G150Gn1′′+n2+6|G|11G7.33%Chen et al. [11]n1′+n2+k+3G307Gk+3|G|163G53.09%Okamoto and Takashima [9]17n1′+17n2+29G2477G17n1′′+17n2+29|G|114G4.60%Okamoto and Takashima [22]39n1′+39n2G5616G39n1′′+39n2|G|195G3.47%•n1′=∑i=1n1Ni/2,n1′′=∑i=1n1log2Ni/2.Table 4
Comparison of master secret key sizes.
SchemesTrivial methodOur methodPercentageTheoreticalExampleTheoreticalExampleMaji et al. [6]3ℤp3ℤp3ℤp3ℤp100%Gu et al. [7]1ℤp1ℤp1ℤp1ℤp100%Chen et al. [11]1ℤp1ℤp1ℤp1ℤp100%Okamoto and Takashima [9]1G1G1G1|G|100%Okamoto and Takashima [22]13n1′+13n2ℤp1872ℤp13n1′′+13n2ℤp65ℤp3.47%•n1′=∑i=1n1Ni/2,n1′′=∑i=1n1log2Ni/2.Table 5
Comparison of signing key sizes.
SchemesTrivial methodOur methodPercentageTheoreticalExampleTheoreticalExampleMaji et al. [6]t1+t2+1G4Gt1′′+t2+1G14G350%Gu et al. [7]t1+t2+2G5Gt1′′+t2+2G15G300%Chen et al. [11]t1+t2+2G5Gt1′′+t2+2G15G300%Okamoto and Takashima [9]t1+t2+3G6Gt1′′+t2+3G16G267%Okamoto and Takashima [22]13t1+13t2G39G13t1′′+13t2G169G433%•t1′′=∑i=1n1log2Ni/2.Table 6
Comparison of signature sizes.
SchemesTrivial methodOur methodPercentageTheoreticalExampleTheoreticalExampleMaji et al. [6]2l1′+l2+2G230G2l1′′+l2+2G24G10.43%Gu et al. [7]2l1′+l2+2G227G2l1′′+l2+2G21G9.25%Chen et al. [11]2l1′+l2+1G228G2l1′′+l2+1G22G9.65%Okamoto and Takashima [9]l1′+l2+2G115Gl1′′+l2+2G12G10.43%Okamoto and Takashima [22]l1′+l2G113Gl1′′+l2G10G8.85%•l1′=∑i=1l1Ni/2,l1′′=∑i=1l1log2Ni/2.Table 7
Comparison of master public key generation overhead.
SchemesTrivial methodOur methodPercentageTheoreticalExampleTheoreticalExampleMaji et al. [6]2n′+1E73E2n″+1E11E15.07%Gu et al. [7]1E1E1E1E100%Chen et al. [11]2E+1P2E+1P2E+1P2E+1P100%Okamoto and Takashima [9]144n′+162E144E144n″+162E5E3.47%Okamoto and Takashima [22]8n′E1152E8n′′E40E3.47%•n′=∑i=1n1Ni/2+n2,n″=∑i=1n1log2Ni/2+n2.Table 8
Comparison of signing key generation overhead.
SchemesTrivial methodOur methodPercentageTheoreticalExampleTheoreticalExampleMaji et al. [6]t′+1E4Et″+1E14E350.00%Gu et al. [7]t′+2E5Et″+2E15E300.00%Chen et al. [11]t′+3E6Et″+3E16E266.67%Okamoto and Takashima [9]4t′+8E20E4t″+8E60E300.00%Okamoto and Takashima [22]8t′E24E8t′′E192E800.00%•t′=∑i=1t1Ni/2+t2,t″=∑i=1t1log2Ni/2+t2.Table 9
Comparison of signature generation overhead.
SchemesTrivial methodOur methodPercentageTheoreticalExampleTheoreticalExampleMaji et al. [6]4lf+2E678E4lf′+2E42E6.19%Gu et al. [7]2lf+5E343E2lf′+5E25E7.29%Chen et al. [11]2lf+2I+3E347E2lf′+2I+3E29E8.36%Okamoto and Takashima [9]3lf+3E510E3lf′+333E6.47%Okamoto and Takashima [22]9lfE1521E9lf′E90E5.92%Table 10
Comparison of signature verification overhead.
SchemesTrivial methodOur methodPercentageTheoreticalExampleTheoreticalExampleMaji et al. [6]3lfE+2lf+2P507E+340P3lf′E+2lf′+2P30E+22P6.44%Gu et al. [7]lf+2E+2lf+4P171E+342Plf′+2E+2lf′+4P12E+24P7.01%Chen et al. [11]2lf+3E+2lf+2P341E+340P2lf′+3E+2lf′+2P23E+22P6.69%Okamoto and Takashima [9]4lf+6E+lf+3P682E+172P4lf′+6E+lf′+3P46E+13P7.45%Okamoto and Takashima [22]10lf+1E+lfP1691E+169P10lf′+1E+lf′P101E+10P5.93%The analysis shows the following:(1)
Our method has significant advantages in signature size, signature generation overhead, and signature verification overhead, which is less than 10% of the trivial method.(2)
There is also a significant advantage in master public key size. Except for [11] which is about half, the others are less than 10%.(3)
There are also advantages in the overhead of master public key generation, especially when applied to the schemes of [6, 9] and [22].(4)
The sizes of the master secret keys are the same except for [22]. For [22], our method can reduce the size of the master private key to 3.47%.(5)
In terms of signing key size and signing key generation overhead, our method is not as good as the trivial method, which is about three times theirs.Generally, the system only needs to generate a signing key once for each user, and the user only needs one signing key. However, one user may sign multiple messages to generate multiple signatures, and a signature may be verified multiple times by different users. Our method has advantages in the case of “multiple,” while the disadvantages are “one-time.” Therefore, our method has significant advantages.


## 7.2. Experimental Simulation

Two main factors are affecting the system data size and computing overhead. One is the number of attributes, especially comparative attributes. The second is the size of the value space of the comparative attribute. We simulate and analyze these two cases, respectively. The simulation experiment is carried out on the windows 10 subsystem Debian-10.9, 11th Gen Intel(R) Core(TM) i7-11370H @3.30 GHz, CPU× 4, RAM 16 GB, and the PBC-0.5.14 library. We use “a.param” as the incoming parameter file of the PBC library.The first scenario we simulated assumes that the access structure hasl1 comparative attributes and l2 usual attributes, and the user has t1 comparative attributes and t2 usual attributes. l1,l2,t1,t2 take five groups of data, which are 3,1,2,1,6,2,4,2,9,3,6,3,12,4,8,4, and 16,6,10,6. The results are shown in Figures 2–5.Figure 2
Comparison of master public key sizes on the attribute number.Figure 3
Comparison of signature sizes on the attribute number.Figure 4
Comparison of signing overhead on the attribute number.Figure 5
Comparison of verification overhead on the attribute number.The simulation results show that our scheme has significant advantages in data size and computational overhead. The details are as follows:(1)
In terms of master public key size, using our method, the average sizes of the five schemes are 91, 51, 163, 794, and 1755 Kb, respectively. Using the trivial method, the average size of the five schemes increases to 2260, 1135, 1292, 19232, and 44054 Kb. In other words, our method reduces the master public key sizes to 4.03%, 4.49%, 12.61%, 4.13%, and 3.98%. See Figure2.(2)
In terms of master secret key size, using our method, the average sizes of the five schemes are 72.4, 71.4, 70.4, 36.2, and 34.2 Kb, respectively. Using the trivial method, the average size of the five schemes increases to 1130, 1129 1128, 565, and 563 Kb. That is, our method reduces the master public key sizes to 6.41%, 6.32%, 6.24%, 6.41%, and 6.07%. See Figure3. Because the data of the [6, 7] and [11] schemes are very close, and the data of the [9, 22] schemes are also very close, it seems that there are only 2 schemes and 4 polylines in Figure 3. In fact, there are 5 schemes and 10 polylines.(3)
The cost of signature generation for the 5 schemes grows linearly with the number of attributes, whether using our method or the trivial method. But the increase is much faster with the trivial method, and the 5 dashed lines representing the trivial method are all above the 5 solid lines representing our method. The signing overhead using our method is 0.10, 0.05, 0.08, 0.07, and 0.22 seconds on average, which are about 6% of the trivial method. See Figure4.(4)
Similarly, the overhead of signature verification can be reduced to about 6% of the trivial method with our method. Here, the advantage of the scheme [11] is obvious. The minimum overhead is 0.03 seconds, and the maximum overhead is only 0.09 seconds, which is only 1.28% of the trivial method. See Figure 5.The second scenario we simulated uses the example above. The value space of comparative attributesu˜2,u˜3, and u˜4 takes five groups of data such as 25,27,26,26,28,27,27,29,28,28,210,29, and 29,211,210. The results are shown in Figures 6–9. They show that the advantages of our method are more significant in the second case.(1)
When using our method, the signature size, signing overhead, and verification overhead all remain largely unchanged. Instead, they both grow exponentially faster using the trivial method. In all three aspects, our method reduces them to within 2%.(2)
Our method also grows slower than the trivial method in terms of master public key size. It can be reduced to about 15% in all five schemes.(3)
Using our method, the average size of the master public key for the 5 schemes is 241, 126, 163, 2072, and 4687 Kb; the average size of the signature for the 5 schemes is 30, 27, 28, 15, and 13 Kb, respectively.(4)
Using our method, the average signature generation overhead for the 5 schemes is 0.04, 0.02, 0.03, 0.03, and 0.08 seconds; the average verification overhead for the 5 schemes is 0.56, 0.58, 0.04, 0.34, and 0.34 seconds, respectively.Figure 6
Comparison of master public key sizes on the value space.Figure 7
Comparison of signature sizes on the value space.Figure 8
Comparison of signing overhead on the value space.Figure 9
Comparison of verification overhead on the value space.Overall, the simulation results show that our method has significant advantages over the trivial method and is then practicable and meaningful.


## 8. Conclusion

Attribute-based signature is a widely used cryptographic primitive and has been studied by many scholars. However, none of the existing attribute-based signature schemes supports comparing attributes. Using the 0-encoding and 1-encoding, we propose a signature-policy comparable attribute-based signature scheme, which effectively deals with the comparative attributes. Theoretical analysis and simulation experiments show that our method is practical and has significant advantages in storage and computation overhead compared with the trivial method. CABS may be combined with other technologies for wider application in the future [43–46].The method proposed in this paper does not seem to be suitable for the case of key-policy, and it is one of the future research directions to propose a key-policy comparable attribute-based signature scheme.



---

*Source: 9287026-2022-06-18.xml*