Attribute-Based Signature with Policy-and-Endorsement Mechanism

Wang HX, Zhu Y, Feng RQ et al. Attribute-based signature with policy-and-endorsement mechanism. JOURNAL OF

COMPUTER SCIENCE AND TECHNOLOGY 25(6): 1293–1304 Nov. 2010. DOI 10.1007/s11390-010-1102-7

Attribute-Based Signature with Policy-and-Endorsement Mechanism

Huai-Xi Wang1,5 (��), Yan Zhu2,3,∗ (� �), Rong-Quan Feng1 (��), and Stephen S. Yau4, Fellow, IEEE

1LMAM, School of Mathematical Sciences, Peking University, Beijing 100871, China2Institute of Computer Science and Technology, Peking University, Beijing 100871, China3Key Laboratory of Network and Software Security Assurance (Peking University), Ministry of Education

Beijing 100871, China4Information Assurance Center and School of Computing, Informatics and Decision Systems Engineering

Arizona State University, Tempe, AZ 85287, U.S.A.5Electronic Engineering Institute, Hefei 230037, China

E-mail: {wanghuaixi,yan.zhu}@pku.edu.cn; [email protected]; [email protected]

Received February 3, 2010; revised August 30, 2010.

Abstract In this paper a new signature scheme, called Policy-Endorsing Attribute-Based Signature, is developed to cor-respond with the existing Ciphertext-Policy Attribute-Based Encryption. This signature provides a policy-and-endorsementmechanism. In this mechanism a single user, whose attributes satisfy the predicate, endorses the message. This signature

allows the signer to announce his endorsement using an access policy without having to reveal the identity of the signer. Thesecurity of this signature, selfless anonymity and existential unforgeability, is based on the Strong Diffie-Hellman assumptionand the Decision Linear assumption in bilinear map groups.

Keywords cryptography, fine-grained access control, attribute-based signature, policy-and-endorsement, selfless anonymity,

existential unforgeability

1 Introduction

In this paper a general framework for constructingattribute-based cryptosystems (ABC) with encryption,signature, and authentication is developed. Attribute-based systems are a natural fit for settings where theroles of the users depend on the combination of at-tributes they possess. In such systems, the users obtainmultiple attributes from one or more attribute authori-ties, and a user’s capability in the system (e.g., sendingmessages, accessing to resources) depends on his at-tributes. We start with an informal description of theframework as follows.• Let A be a finite set of attributes, and everyone

can know this set;• Let R be a finite set of roles, where each role is

a subset of attributes, i.e., ρ ∈ R and ρ ⊆ A. Eachmember has a role in R and can obtain a private keyK(ρ) corresponding to its role;• Let P be a finite set of policies, where each policy

can be expressed as a logical function on attributes,

fπ(X) for any π ∈ P and X ⊆ A. Roughly speaking, amessage can be encrypted or signed to any policy π inP ; and•We allow for an arbitrary predicate called open on

the set P ×R that specifies which roles in R can openwhat policies in P .

In encryption case, a key K(ρ) can decrypt cipher-texts encrypted for policy π if and only if the role ρopens the policy π, i.e., open(π, ρ) = fπ(ρ) is true.This kind of encryption is also called ciphertext-policyattribute-based encryption (CP-ABE), which can beconsidered as a kind of spatial encryption[1].

In a signature case, everyone can also use policy πto verify signature for key K(ρ) if and only if the roleρ opens the policy π, i.e., open(π, ρ) is true. This kindof message authentication differs from that offered bytraditional digital signatures due to the fact that it is apolicy-and-endorsement mechanism that supports theclaims of the form: “a single user, whose attributes sa-tisfy the predicate, endorsed this message.” As a simpleexample, suppose Alice wishes to fill out a form with

Regular PaperThis paper is supported by the National Nature Science Foundation of China under Grant No. 10990011, the National Science

Foundation of US under Grant No. CCF-0725340, the National Development and Reform Commission under the project of “AMonitoring Platform for Web Safe Browsing”, and China Next Generation Internet CNGI Project under Grant No. CNGI-09-01-12.

∗Corresponding Author�2010 Springer Science +Business Media, LLC & Science Press, China

1294 J. Comput. Sci. & Technol., Nov. 2010, Vol.25, No.6

the following claim to endorse her finance application:(Warrantor is a Professor AND in school of (ComputerScience OR Electronic Engineering)). To give credibi-lity to this form, she needs to find the proper warrantorto sign her form. It is a reasonable requirement that anyreferendary must be adaptable to validate Alice’s formin a secure way even if she does not know her warran-tor. That is, this kind of signature needs to provideanonymity for signers.

In this simple example, the set of attributes is de-fined as A = {Professor, Computer Science, Elec-tronic Engineering}, and they are divided into twocategories, {Faculty,Dept .}, respectively. The policyabout Warrantor can be defined as Warrantor := ((Fac-ulty == Professor) AND ((Dept. == Computer Sci-ence) OR (Dept. == Electronic Engineering))). Givenan assignment of roles Louis := {Professor, Com-puter Science}, the open function returns true, that is,open(Warrantor ,Louis) = true.

This signature can also be efficiently converted intoan entity authentication protocol: given a public policyπ, the verifier can interactively check the availabilityof guarantees generated by the key K(ρ) of the proverif and only if open(π, ρ) is true. This means that thiskind of identification can utilize contextual attributesto achieve anonymous authentication. Thus, it has themarked difference from the traditional approaches thatrequire principals to present personal identity informa-tion in order to obtain access to various services.

1.1 Our Contribution

In this paper we focus on a much richer type of cryp-tosystem, called adaptive-policy attribute-based cryp-tosystem (AP-ABC), that is motivated by real-life chal-lenges in access control management. At a high level,one can consider a natural access control system (calledfine-grained access control, FGAC): each user is associ-ated with a subset of attributes that specify which typeof resources the user can access; each resource is also as-sociated with an access policy that specifies which typeof users can access the resource. The AP-ABC is sucha cryptographic system to implement FGAC due to thefact that this cryptosystem can adaptively change theprotected resources according to access policy. In Sec-tion 2 we formalize the model of AP-ABC and the pre-cise definition of the security using the framework ofBoneh and Hamburg[1]. We also briefly discuss the me-chanics of the work with AP-ABC and the features thatthey can provide.

The new tool we develop in Section 3, called policy-endorsing attribute-based signature (PE-ABS), is apolicy-and-endorsement mechanism by improving theoriginal CP-ABE scheme proposed by Bethencourt et

al.[2] This signature allows the signer to announce hisendorsement using his claim without having to revealthe identity of signer. In this case, we consider it asa special role signature with anonymity, which is amethod for allowing a member of a group to anony-mously sign a message on behalf of the specified role(known as a set of attributes), e.g., title, position, ortime-bound in social organization. This functionalitybecomes more attractive in the case where it is practi-cally infeasible for the signature holder and the verifierto know all possible signers in large-size systems.

Another challenge, also an important part ofthe security requirement, is the provable security ofthe proposed PE-ABS scheme. In Section 4 wepresent the proof of two security requirements: self-less anonymity and existential unforgeability. The se-curity of scheme is based on the Strong Diffie-Hellman(SDH) assumption[3] in the random oracle model[4]. Wealso need the Decision Linear assumption that has beenproved useful for constructing short group signature.Further, we analyze the performance of our scheme byconstructing a practical AP-ABC in Section 5. Finally,the conclusion is presented in Section 6.

1.2 Related Work

Attribute-based cryptosystem provides a fine-grained access control mechanism by means of en-cryption, signature, authentication, and identification,which depends on the match between access policiesembedded into the resources and identity attributesascribed into user’s private key. Since the first ABEscheme was introduced by Sahai and Waters in 2005[5],ABC has received much attention and many schemeshave been proposed in recent years[2,6-10]. Accordingto the structure of access policy, these schemes can beroughly divided into two categories: single thresholdstructure and hierarchical threshold structure.

ABC schemes with single threshold structure gene-rally use techniques from secret-sharing schemes as acore component of these schemes. For example, thescheme of Sahai and Waters[5], called fuzzy identity-based encryption, allows for a threshold attribute-baseddecryption of encrypted data. Messages can be en-crypted by specifying a set of decryptor attributes ρ′

during encryption. Such a ciphertext can then be de-crypted by any user with the attribute set ρ such that|ρ ∩ ρ′| � t. It is well known that secret-sharing tech-nique can be used to express monotonic access struc-tures, that is, ∀ρ′, ρ′′ ∈ R, if open(π, ρ′) = true andρ′ ⊆ ρ′′, then open(π, ρ′′) = true. So Goyal et al.[6]

subsequently increased the expressibility of ABE sys-tems by allowing the private key to express any mono-tonic access structure over attributes. This scheme is

Huai-Xi Wang et al.: Attribute-Based Signature with Policy-and-Endorsement Mechanism 1295

also called key-policy ABE (KP-ABE), where attributesare used to annotate the ciphertexts and formulas overthese attributes are ascribed to users’ secret keys. Sin-gle threshold structure is also fit for attribute-based sig-nature scheme, in which a signer has a set of attributesρ and the verifier specifies a verification attribute setρ′. A signature is verified as valid if |ρ ∩ ρ′| � t, wheret is fixed during the setup time. For example, Shahan-dashti and Safavi-Naini[7] proposed threshold attribute-based signatures (t-ABS), in which, signers are associ-ated with a set of attributes and verification of a signeddocument against a verification attribute set succeedsif the signer has a threshold number t of attributes incommon with the verification attribute set.

Another kind of ABC has hierarchical thresholdstructure, in which the policy is transformed into ac-cess tree with threshold gates: AND gates can beconstructed as n-of-n threshold gates and OR gatesas 1-of-n threshold gates. This structure has greaterflexibility than single threshold structure since the lat-ter can be obtained as a special case of the former.Bethencourt, Sahai and Waters first gave a construc-tion for this structure in the form of ciphertext-policyABE (CP-ABE)[2]. In their construction, the roles ofthe ciphertexts and keys are reversed in the sense thatattributes are used to describe the features of a keyholder, and an encrypter will associate an access policywith the ciphertext. Since then, some cryptographicallystronger CP-ABE constructions[8-9] that allowed reduc-tions to the decisional bilinear Diffie Hellman Prob-lem have been proposed in recent years. For exam-ple, Goyal et al.[8] presented bounded CP-ABE in thestandard model. Waters[9] proposed the first fully ex-pressive CP-ABE in the standard model. Hierarchicalthreshold structure can also be used to construct moreflexible signature schemes. For example, Khader[10]

proposed a signature scheme, called attribute-basedgroup signatures, based on Boneh’s group signature[3].This scheme, however, lacks a corresponding encryptionscheme to construct a complete attribute-based cryp-tosystem.

Techniques similar to ABC were proposed formany applications like Attribute-Based Access Con-trol (ABAC, used in service-oriented architecture(SOA))[11], Property-Based Broadcast Encryption(used in DRM)[12-13], Hidden Credentials[14], aswell as dynamic communication in vehicular ad hocnetworks[15].

2 Preliminaries

In this section we propose the formal definitionof adaptive-policy attribute-based cryptosystem (AP-ABC) for fine-grained access control. Based on

an attribute-based cryptographic infrastructure, thiscryptosystem specifies two fundamental cryptographictools: ciphertext-policy attribute-based encryption(CP-ABE) and policy-endorsing attribute-based signa-ture (PE-ABS). In addition, we describe two adver-sary’s attack models for PE-ABS.

2.1 Attribute-Based Cryptosystem

Let A be the universe of possible attributes inFGAC. Given an access policy π over A, we assume thatthere exists a function open(π, x), where x is associatedwith attributes of A. An attribute set ρ ⊆ A is saidto satisfy a claim-predicate π if open(π, ρ) = true. Interms of these notations, we define an adaptive-policyattribute-based cryptosystem as follows.

Definition 1 (Adaptive-Policy Attribute-BasedCryptosystem). An attribute-based cryptosystem con-sists of the following three procedures, which are pa-rameterized by a universe of attributes A:

Infrastructure : generates the parameters and user’skeys of the cryptosystem:

Setup(κ,A): takes as input the security parame-ter κ and the set A. It outputs a manager-key gmkand a public-key gpk;

Join(gmk , i, ρi): takes as input the manager keygmk, a user counter i, and the user’s role ρi ⊆ A. Itoutputs a user’s private-key gsk [i], where ρi ∈ gsk [i].Encryption: realizes the ciphertext-policy attribute-

based encryption:Encrypt(gpk , π,M): takes as input the public key

gpk, the access policy π, and the plaintext M ∈{0, 1}∗. It outputs a ciphertext C.

Decrypt(gsk [i], C): takes as input a ciphertext Cand a private key gsk [i]. If open(π, ρi) = true, thisalgorithm outputs the plaintext M .Signature: realizes the policy-endorsing attribute-

based signature:Sign(gsk [i], π,M): takes as input a private key

gsk [i], a policy π, and a message M ∈ {0, 1}∗. Itreturns a signature σ and π ∈ σ.

Verify(gpk , σ,M): takes as input the public keygpk, a message M , and a purported signature σ onM . It returns a Boolean value, valid or invalid.In this definition, CP-ABE and PE-ABS are inti-

mately integrated into a complete system by a cryp-tographic key management infrastructure, which sup-ports dynamically joining new users. As there alreadyexist schemes on CP-ABE, we will design the AP-ABCsystem based on these existing schemes in this work.Hence, we will not consider CP-ABE scheme but directour attention to the construction of PE-ABS in thispaper. Note that, the existing CP-ABEs still need to


make the necessary changes to construct AP-ABC. Forexample, such a CP-ABE scheme, derived from [2], isdescribed in Appendix.

2.2 Access Policy and Attribute Tree

We now discuss how to construct the cryptographicfunction open(π, ρ) with secrecy and correctness forany π, ρ ⊆ A. Without loss of generality, we assumethat any access policy π over A can be expressed asa Boolean function fπ(·), whose inputs are associatedwith attributes of A. With the help of gpk or gsk , it ispossible to use fπ(·) to hide a secret value, such thatthere merely exist some appointed values that the ve-rifier can later accept as legal “opening”.

Given an arbitrary access policy π with Booleanfunction fπ(·), we use hierarchical threshold structureto implement the above-mentioned approach, as fol-lows: firstly transform fπ(·) into an attribute tree T ,which consists of AND and OR threshold gates, thenuse threshold cryptographic techniques to generate arandom function, e.g., secret sharing schemes, and fi-nally realize Boolean function under the decisional bi-linear Diffie-Hellman (DBDH) assumption.

An attribute tree is a tree in which each interiornode is a threshold gate and the leaves are linked withattributes. An m-of-n threshold gate means that thesecret of the parent node can be recovered if and onlyif at least m of n children is available. We note thatAND gates can be constructed as n-of-n threshold gatesand OR gates as 1-of-n threshold gates. Attribute treealso implements some power logic function, e.g., integercomparisons[2], and satisfaction of a leaf is achieved byowning an attribute.

2.3 Correctness and Security Definitions

Now we define the security requirements of anattribute-based cryptosystem. Since the security of CP-ABE has already been widely studied in previous work,we will only formulate the security of PE-ABS and payattention to the construction of PE-ABS scheme basedon the existing CP-ABE scheme in this work.

Firstly, we must ensure that our scheme is correct.The correctness property of PE-ABS scheme is thathonestly-generated signatures should pass the verifica-tion check:

Definition 2 (Correctness). A PE-ABS schemeis correct if for all attribute sets A, ∀(gpk , gmk) =Setup(κ,A), ∀i ∈ N, ∀gsk [i] ← Join(gmk , i, ρi), ∀M ∈{0, 1}∗, all claim-predicates π with open(π, ρi) = true,

Verify(gpk ,Sign(π, gsk [i],M),M) = valid ,

with probability 1 over the randomness of all the algo-

rithms.Secondly, we present two formal definitions, selfless

anonymity and existential unforgeability, that togethercapture the desired notions of the security of PE-ABS,as follows.

Definition 3 (Selfless Anonymity). An n-user PE-ABS scheme is (t, n, qh, qs, ε)-selfless anonymity if thesuccess probability of any polynomial-time adversary inthe following experiment is at most ε in time at most t:

1) run (gpk , gmk)← Setup(κ,A) and give gpk to theadversary;

2) the adversary is given access at most qh times tooracle Hash(·) and qs times to oracle Sign(π, gsk [i], ·),as well as at most n− 1 times to oracle Join(gmk , ·, ·)to request the private key of the user i ∈ [1, n];

3) the adversary outputs (M, i0, i1) and the systemreturns a challenge σ∗ = Sign(gpk , gsk [ib],M), whereb←R {0, 1};

4) the adversary outputs a bit b′ as the guess of b.We say the adversary succeeds if b′ = b, and i0, i1

were never queried to the corruption oracle Join at ei-ther index.

In the selfless-anonymity game, the adversary’s goalis to determine which of the two keys generated the sig-nature. The adversary is not given access to either keybut he is allowed to corrupt the private keys of otherusers.

Definition 4 (Existential Unforgeability). A PE-ABS scheme is (t, qh, qs, ε)-existentially unforgeable un-der a chosen message attack if the success probability ofany polynomial-time adversary in the following experi-ment is at most ε in time at most t:

1) run (gpk , gmk)← Setup(κ,A) and give gpk to theadversary;

2) the adversary is given access at most qh times tooracle Hash(·) and qs times to oracle Sign(π, gsk [i], ·),respectively;

3) at the end the adversary outputs (M ′, π′, σ′).We say the adversary succeeds if (M ′, π′) was never

queried to the Sign oracle, and Verify(gpk , σ′,M ′) =valid .

The security proof for our scheme is in the randomoracle model and the extra parameter qh in the secu-rity definitions denotes the number of random oraclequeries that the adversary issues.

3 Our Construction for PE-ABS

Now we construct a fully secure attribute-based sig-nature scheme with selfless anonymity and existen-tial unforgeability in the random oracle model. Thisscheme is constructed on ciphertext-policy attribute-based encryption (in short BSW scheme) in [2]. The


scheme is presented in Appendix.

3.1 Bilinear Group System

Let G1,G2, and GT be three cyclic groups of primeorder p. G1 and G2 are two additive groups and GT

is a multiplicative group. There exists an efficientlycomputable homomorphism ψ from G2 to G1 but thereexists no efficiently computable homomorphism fromG1 to G2.

Definition 5 (Bilinear Map). Let e be an efficientlycomputable bilinear map e : G1 × G2 → GT with thefollowing properties: for all G ∈ G1, H ∈ G2 and alla, b ∈ Zp,

1) Bilinearity: e([a]G, [b]H) = e(G,H)ab;2) Non-degeneracy: e(G,H) �= 1 unless G or H is

the identity of G1 or G2;3) Computability: e(G,H) is efficiently computable.In addition, for all S, T ∈ G2 and an efficient ho-

momorphism ψ : G2 ← G1, we have e(ψ(S), T ) =e(ψ(T ), S). On this basis, we will use the followingbilinear group system to construct PE-ABS scheme.

Definition 6 (Bilinear Group System). We callS = (p,G1,G2,GT , e(·, ·)) a bilinear group system, ifthere exists an efficiently computable bilinear map e :G1 × G2 → GT and the operations in G1,G2,GT areefficient.

3.2 Hashing Functions

Our scheme makes use of two hash functions:• H0 : {0, 1}∗ → G2, mapping an arbitrary string to

an element of G2;• H1 : {0, 1}∗ → Zp, mapping an arbitrary string to

an element of Zp.

3.3 Policy-Endorsing Attribute-BasedSignature

Consider a security parameter κ, a bilinear groupsystem S = (p,G1,G2,GT , e(·, ·)) with homomorphismψ : G2 → G1 and log p = O(κ). The scheme em-ploys hash functions H0 and H1 with ranges G2 andZp respectively, treated as random oracles. We proposePE-ABS scheme as follows.

Setup(κ,A). Takes as inputs the security parame-ter κ, the bilinear group system S and the set of allattributes A = {attr1, . . . , attrm}, where each attr i de-notes an attribute and m is the total number of at-tributes. It proceeds as follows:

1) selects two generators G and h of G1 and G2 uni-formly at random such that e(G, h) �= 1;

2) selects two random integers α, β ∈R Zp;3) sets g = [β]G ∈ G1 and ζ = e(G, h)α ∈ GT ;4) outputs the management key and public key:

gmk = (α, β,G), gpk = (S,A, g, h, ζ).

The manager publishes gpk and keeps gmk secret.Join(gmk , i, ρi). Takes as inputs the management

key gmk, a member counter i ∈ Z, and a set of at-tributes ρi = {attr i1 , . . . , attr il

} ⊆ A. It proceeds asfollows:

Algorithm. Disperse(s,T )

Require: a policy tree T and a secret s;Ensure: a set of secrets of attributes in T ;1: Each node ti is assigned a secret value si = 0, an index

value indi ∈ Zp, and a polynomial qi(x) = 0; and setss1 = s for the root node t1.

2: while T is not empty do3: Finds an unprocessed node ti from top to bottom;4: Computes the secret si = qparent(i)(indi);5: if ti is an internal node then6: Finds its children {ti1 , . . . , til

};7: if {ti1 , . . . , til

} has OR relation then8: Generates qi(x) = si;9: end if

10: if {ti1 , . . . , til} has AND relation then

11: Generates qi(x) = si +∑l−1

j=0 ai,jxj (mod p),where any ai,j ∈R Z∗

p;12: end if13: end if14: if ti is a leaf node then15: Outputs si = qparent(i)(ind i) as the secret of corre-

sponding attribute ΔT (attrj), which is also denotedΔs(attr j);

16: end if17: end while

Algorithm. Aggregate(T , {Si1 , . . . , Sil})

Require: a policy tree T and a set of commitments of secrets{Sij

= e(G, h)ri·ΔT (attrj)}attrj∈σ in σ;Ensure: e(G, h)ri·s or failure;1: for ∀attrj ∈ σ, lets tk = Node(attrj) and sets Sk =

e(G, h)ri·ΔT (attr(j)) as the value of leaf node tk and its statusstk = 2 (available), otherwise stk = 0 (undecided).

2: while the set {tk}stk=0 is not empty do3: Find an undecided node tk from down to up;4: if its children Wk = {tk1 , . . . , tkl

} has OR relation and∃tkj

∈Wk, stkj= 2 then

5: Sets the secret value Sk = Skjand stk = 2;

6: Sets stj = 0 for ∀stj = 1 (processed but unavailable);7: else if its children Wk = {tk1 , . . . , tkl

} has AND relationand ∀tkj

, stkj= 2 then

8: Computes Sk =∏

tkj∈Wk

SλWk

(tkj)

kjand stk = 2;

9: Sets stj = 0 for ∀stj = 1;10: else11: Sets stk = 1 (processed but unavailable);12: end if13: if tk is the root node and stk = 2 then14: Outputs Sk and halts;15: end if16: end while17: Halts and outputs “the attributes are unsatisfied”.

Fig.1. Disperse algorithm and aggregate algorithm.


1) selects a fresh ri ∈R Zp and computes Di =[α+ri

β ]h ∈ G2;2) picks a random integer rj ∈R Zp for each attr j ∈

ρi, and computes{Ai,j = [ri]G+ [rj ]ψ(H0(attr j)) ∈ G1,

A′i,j = [rj ]ψ(h) ∈ G1;

3) outputs the private key:

gsk [i] = (Di, (Ai,j , A′i,j)attrj∈ρi).

The system manager sends gsk [i] to this member. Ob-viously, nobody should be allowed to possess ri exceptthe system manager.

Sign(gsk [i], π,M). Takes as inputs a private keygsk [i], the policy π, and a message M ∈ {0, 1}∗, andreturns a signature σ. It proceeds as follows:

1) picks a random integer t ∈R Zp and two randomgenerators u ∈R G1, v ∈R G2, and computes

Ei = [t]u ∈ G1, Ti = Di + [t]v ∈ G2;

2) selects a random integer s ∈ Zp, set Qi = [s]g ∈G1, and then creates access policy tree T and invokesthe Disperse algorithm with which the signer can com-pute

{ΔT (attr j)}attrj∈T = Disperse(s, T ).

As a result, the following values can be computedfor each attrj ∈ ρi ∩ T ,

{Bi,j = [ΔT (attrj)]Ai,j ∈ G1,

B′i,j = [ΔT (attrj)]A′

i,j ∈ G1;

3) picks two blinding values rs, rt ∈R Zp and com-putes

V1 = [rt]u ∈ G1, V2 = ζrs · e(Qi, v)rt ∈ GT ;

4) computes a challenge c ∈ Zp by using c ←H1(gpk ,M, u, v, Ti, Ei, Qi, V1, V2), and then computesthe following parameters:

ss = rs + c · s, st = rt + c · t.

The final signature is

σ = (T , u, v, Ti, Ei, Qi, c, ss, st, {(Bi,j , B′i,j)}attrj∈ρi∩T ).

Verify(gpk , σ,M). Takes as inputs the group publickey gpk and a purported signature σ on a message M .It returns either valid or invalid. It can check whetherσ is a valid signature as follows:

1) for each attribute attrj ∈ σ, computes Cj = h,C′

j = H0(attr j), and

Sij =e(Bi,j , Cj)e(B′

i,j , C′j)

= e(G, h)ri·ΔT (attrj),

to obtain the set {Si1 , . . . , Sil};

2) invokes the Aggregate algorithm to get

S = e(G, h)ri·s = Aggregate(T , {Si1 , . . . , Sil}),

which may be regarded as the inverse process of theDisperse algorithm, and then computes

V ′1 = [st]u− [c]Ei, V ′

2 =ζss · Sc · e(Qi, v)st

e(Qi, Ti)c;

3) checks that whether the challenge c is correct:

c?=H1(gpk ,M, u, v, Ti, Ei, Qi, V

′1 , V

′2).

If so, outputs valid; otherwise, outputs invalid.

3.4 Disperse and Aggregate Algorithms

We propose a pairwise algorithm, called the disperseand aggregate algorithms, to fix and open the accesspolicy π ∈ P , as follows.

3.4.1 Disperse Algorithm

Given an integer s and a policy tree T generatedfrom a logical function fπ(X) for π ∈ P and X ={attr i} ⊆ A, the disperse algorithm shares the secrets in X and returns a set of values {ΔT (attr i)} for∀attr i ∈ X . In Fig.2, a simple example is providedto explain the attribute tree, in which the variant Timeis denoted as Time3‖Time2‖Time1 in a binary format.In the attribute tree, the nodes are divided into twocategories: leaf nodes and internal nodes (or non-leafnodes). The attributes are assigned into the leaf nodes

Fig.2. Example for policy tree.


and each internal node denotes a logical relation(AND/OR).

We adopt the secret sharing method with hierar-chical polynomials to realize the disperse algorithm:firstly, assign a random index ind i for each node ti inT ; secondly, choose a polynomial qi(x) for each inter-nal node ti, where qi(x) =

∑k−1j=0 ajx

j is a polynomialwith k − 1 degree for each AND node with k branches,or a constant polynomial for each OR node; third, setqi(0) = qparent(i)(ind i) and set q1(0) = s for the rootnode t1; and then, execute the algorithm in Fig.1; fi-nally, assign a value qT (attr i) = qparent(k)(indk) andk = Node(attr i) for the corresponding attr i.

3.4.2 Aggregate Algorithm

The aggregate algorithm can be considered as the in-verse operation of disperse algorithm, but our schememerely needs the “commitment” of secret s ratherthan the original secret s. The aggregate algo-rithm takes as input the set of secret of attributes{e(G, h)ri·ΔT (attrj)}attrj∈σ and T , output e(G, h)ri·s orfailure. The algorithm is described in Fig.1. In thisalgorithm, the nodes in policy tree are reduced frombottom to top, but a successful match requires onlyone efficient path to resume e(G, h)ri·s. So, in orderto find this efficient path, we need to mark the state ofeach node and check each path repeatedly. Here, we di-vide the state of nodes into three categories: undecided,processed but unavailable, and available. Otherwise, inthe 8th step of aggregate algorithm, the equation holdssince

Sk =∏

tkj∈Wk

SλWk

(tkj)

kj

=∏

tkj∈Wk

e(G, h)ri·ΔT (attrj)·λWk(tkj

)

= e(G, h)ri·

∑tkj

∈WkΔT (attrkj

)·λWk(tkj

)

= e(G, h)ri·ΔT (attrk), (1)

where λWk(tkj ) =

∏tki

∈Wk,tki�=tkj

indki

indki−indkj

is La-grange interpolation coefficient.

4 Security Proof of PE-ABS Scheme

In this section, we shall analyze the security of ourscheme in three aspects: correctness, selfless anonymity,and existential unforgeability. Firstly, we prove the cor-rectness of the scheme as follows.

Theorem 1. The PE-ABS scheme constructed inSection 3 is correct.

Proof. In order to validate the policy in signature σ,the proposed scheme involves the verification of three

aspects: the match of attributes, the consistency of po-licy, and the correctness of signature.

1) Match Attributes : it can hold since

Sij =e(Bi,j , Cj)e(B′

i,j , C′j)

=e([Δs(attr j)]Ai,j , Cj

)e([Δs(attr j)]A′

i,j , C′j

)= e

([ri ·Δs(attr j)]G, h

)= e

(G, h

)ri·Δs(attrj).

2) Consist with Policy : it can hold by invoking theaggregate algorithm to compute S = e(G, h)ris. Fromthe algorithm, we know that the user will obtain thevalue S if and only if his attributes satisfy the accesspolicy.

3) Verify Signature : it can hold since for each

V ′1 = [st]u− [c]Ei = [rt]u = V1,

V ′2 =

ζss · Sc · e(Qi, v)st

e(Qi, Ti)c

=e(G, h)αss · e(G, h)ri·c·s · e(g, v)st·s

e([s]g,Di + [t]v)c

=e(G, h)αss · e(G, h)ri·c·s · e(g, v)st·s

e([s]g,Di)c · e([s]g, [t]v)c

=e(G, h)α(rs+cs) · e(G, h)ri·c·s · e(g, v)(rt+ct)·s

e([sβ]G,

[α+ riβ

]h)c

· e(g, v)t·s·c

=e(G, h)α(rs+cs) · e(G, h)ri·c·s · e(g, v)(rt+ct)·s

e(G, h)(α+ri)s·c · e(g, v)t·s·c

= e(G, h)αrs · e(g, v)rts = ζrs · e(Qi, v)rt = V2.

Since V ′1 = V1 and V ′

2 = V2, then we have c′ = c.Hence, the attribute-based signature scheme is cor-

rect. �

4.1 Selfless Anonymity Security

For arbitrary generators P , Q and R of G2, con-sider the following Decision Linear problem: for alla, b, c ∈ Zp, given (P,Q,R, [a]P, [b]Q, [c]R) ∈ G6

2, decidewhether c = a+ b (mod p). One can easily show thatan algorithm for solving Decision Linear in G2 gives analgorithm for solving DDH in G2. The converse is be-lieved to be false. That is, it is believed that DecisionLinear is a hard problem even in bilinear groups wheredecisional Diffie-Hellman problem is easy.

Definition 7 (Decision Linear Assumption). The(t, ε)-decision linear assumption is said to hold in G2

if no t-time algorithm A has advantage at least ε insolving the Decision Linear problem in G2, i.e.,

∣∣∣∣Pr[A(P,Q,R, [a]P, [b]Q, [a+ b]R) = 1]−Pr[A(P,Q,R, [a]P, [b]Q,Z) = 1]

∣∣∣∣ � ε,


where a, b ∈ Zp, P,Q,R,Z ∈ G2, and the probability isover the random choices of the parameters and of thecoin tosses of A.

Boneh, Boyen, and Shacham[3] show that the Deci-sion Linear assumption holds in generic bilinear groups.

Theorem 2. The n-user PE-ABS scheme in(G1,G2) has (t, qh, qs, n, ε) selfless anonymity in therandom oracle model, assuming the (t, ε′) Decision Lin-ear assumption holds in the group G2 for ε′ = ε

2

(1

n2 −qsqh

p

)≈ ε

2n2 .Proof. Suppose Algorithm A breaks the selfless

anonymity of the n-user PE-ABS signature scheme. Webuild an algorithm B that breaks the Decision Linearassumption in G2. Algorithm B is given as input of a 6-tuple (u0, u1, w, h0 = [a]u0, h1 = [b]u1, Z) ∈ G6

2, whereu0, u1, w ∈ G2, a, b ∈R Zp, and either Z = [a+b]w ∈ G2

or Z is random in G2. The Algorithm B decides whichZ was given by interacting with A as follows.

Setup. B simulates Setup as follows:1) B selects a random G = ψ(u0) ∈ G1, h = [a]w ∈

G2 (unknown) as generators of G1 and G2, respectively;2) B picks a random integer α ∈R Zp, β = a (un-

known) and computes,

g = [β]G = [a]ψ(u0) = ψ(h0) ∈ G1,

ζ = e(G, h)α = e(ψ(u0), [a]w)α

= e(ψ(h0), w)α ∈ GT ;

3) B picks a random e ∈R Z∗p and defines G′ =

[1/e]ψ(h0) = [a/e]ψ(u0) ∈ G1 and h′ = [e]w ∈ G2,which replace G and h in attributes recovery, sincee(G, h) = e(ψ(u0), [a]w) = e(G′, h′);

4) B picks two random users i0, i1 ∈R [1, n]. Forall i ∈ [1, n] except i0, i1, B selects ri, rj ∈R Z∗

p andcomputes

Di =[α+ ri

β

]h = [α+ ri]w ∈ G2,

Ai,j = [ri]G′ + [rj ]ψ(H0(attrj))= [ri/e]ψ(h0) + [rj ]ψ(H0(attr j)) ∈ G1,

A′i,j = [rj ]ψ(h′) = [rje]ψ(w) ∈ G1,

as the private key (Di, Ai,j , A′i,j) due to

e(Ai,j , h′)

e(A′i,j , H0(attrj))

= e([ri]G′, h′) = e([ri]G, h).

5) for i0 and i1, B picks a random r ∈R Zp anddefines Di0 =

[α+ar

β

]h = [α + ar]w ∈ G2 and Di1 =

[r]Z+[α− br]w ∈ G2, which is unknown since it knows

neither a nor b. Observe that if Z = [a+ b]w, then

Di0 = [α+ ar]w = [ar + br]w + [α]w − [br]w= [r]Z + [α]w − [br]w = Di1 .

Hence, users i0 and i1 have the same private key in thiscase.

Hash Queries. At any time, A can query the hashfunctions H0, H1. B responds with random values withconsistency.

Phase 1. A can request signing queries and corrup-tion queries. If i �= i0, i1, then B uses the secret keyof i to respond to the query as usual. If i = i0, i1, Bresponds as follows.

Signing Query. B generates a signature for Musing Di0 or Di1 :• for user i = i0, B picks random x, k, l ∈R Zp,

sets t = (ar + x)/k and computes:

u = [k]ψ(u0) ∈ G1,

v = [kl]u0 − [k]w ∈ G2,

Ei = [t]u = [ar + x]ψ(u0)

= [r]ψ(h0) + [x]ψ(u0) ∈ G1,

Ti =Di0 + [t]v

= [α− x]w + [rl]h0 + [xl]u0 ∈ G2;

• for user i = i1, B picks random x, k, l ∈R Zp,sets t = (br + x)/k and computes:

u = [k]ψ(u1) ∈ G1,

v = [kl]u1 + [k]w ∈ G2,

Ei = [t]u = [br + x]ψ(u1)= [r]ψ(h1) + [x]ψ(u1) ∈ G1,

Ti =Di1 + [t]v= [r]Z + [α+ x]w + [lr]h1 + [xl]u1 ∈ G2.

Any way, Ei = [t]u ∈ G1 and Ti = Di +[t]v ∈ G2 for some random t ∈ Zp and in-dependent u ∈ G1, v ∈ G2. Since ri = arand β = a, algorithm B selects a random inte-ger y ∈ Zp, sets s = y/a ∈ Zp and computes[ris]G = [ary/a]u0 = [yr]u0 and Qi = [sβ]G =[ay/a]u0 = [y]u0. In terms of e(G, h) = e(G′, h′),B sets [ris]G′ = [yr/e]ψ(h0) ∈ G1. Moreover,since [Δs(j)]([ri]G′) = [Δris(j)]G′,� B sets ris =ary/a = yr, rj ∈R Zp, and computes the followingequation in terms of policy tree T ,

Bi,j = [Δyr(attrj)]G′+

[Δs(attr j)rj ]ψ(H0(attr j))

�Let Δs(x) = s+∑t

i=1 aixi. Then [Δs(x)]g = [s]g +

∑ti=1[aix

i]g. When [s]g = [ris]G′ = [yr/e]ψ(h0), g = [1/e]ψ(h0), we have

[Δyr(x)]G′ = [yr/e]ψ(h0) +∑t

i=1[aixi/e]ψ(h0).


= [Δyr(attr j)][1/e]ψ(h0)+[Δs(attr j)rj ]ψ(H0(attr j)),

B′i,j = [Δs(attr j)rj ]ψ(h′)

= [Δs(attr j)erj ]ψ(w).

B assures that the equation

e(Bi,j , h′)

e(B′i,j , H0(attrj))

= e([Δris(attrj)]G′, h′)·

e([Δs(attr j)rj ]ψ(H0(attrj)), h′)e(Δs(attr j)[rj ]ψ(h′), H0(attr j))

= e([Δs(attrj)]([ri]G′), h′)= e([Δris(attr j)]G, h).

So, e([ris]G, h) can be recovered.� Next, B picks st,ss ∈R Zp and computes the corresponding V1, V2:

V1 = [st]u− [c]Ei,

V2 =ζss · e([ris]G, h)c · e(Qi, v)st

e(Qi, Ti)c.

In the unlikely event A has already issued a hashquery for c = H1(gpk , M,Ti, Ei, Qi, V1, V2). B re-ports failure and terminates. This happens withprobability at most qh/p. Otherwise, B definesc = H1(gpk ,M, Ti, Ei, Qi, V1, V2). Algorithm B thencomputes the signature σ = (T , u, v, Ti, Ei, Qi, c, ss,st, {Bi,j , B

′i,j}attrj∈ρi∩T ), and gives σ to A.

Corruption Query. If A issues a corruption queryfor user i0 or i1, then B reports failure and aborts.

Challenge. A outputs a message M and two usersi∗0 and i∗1 where it wishes to be challenged. If {i∗0, i∗1} �={i0, i1}, then B reports failure and aborts. Otherwise,B picks a random b ∈R {0, 1} and generates a signatureσ∗ under user ib’s key for M using the same methodresponding to signing queries in Phase 1. It gives σ∗ asthe challenge to A.

Phase 2. A issues restricted queries. B responds asin Phase 1.

Output. Eventually, A outputs its guess b′ ∈ {0, 1}for b. If b = b′, then B outputs 0 (meaning that Z israndom in G2); otherwise, B outputs 1 (meaning thatZ = [a+ b]w).

Suppose B does not terminate in the simulation.When Z is random in G2, B emulates the selfless-anonymity game perfectly. Hence, Pr[b = b′] > 1

2 + ε.Then, when Z = [a + b]w, the private keys for useri0 and i1 are identical and hence the challenge signa-ture σ∗ is independent of b. It follows that Pr[b =b′] = 1

2 . Therefore, assuming B does not abort, it hasadvantage at least ε/2 in solving the given linear chal-lenge (u0, u1, w, h0, h1, Z) ∈ G6

2.

B does not abort if it correctly guesses the valuesi∗0 and i∗1 during the setup phase and none of the sign-ing queries causes it to abort. The probability thata given signature query causes B to abort is at mostqs/p and therefore the probability that B aborts as aresult of A’s signature is at most qhqs/p. As long as Bdoes not abort in Phase 1, A gets no information abouti0, i1. So the probability that the query during Phase1 and the choice of challenge do not cause B to abortis 1/

(n2

), greater than 1/n2. It now follows that B can

solve the given linear challenge with advantage at leastε2 ( 1

n2 − qsqh

p ), as required. This completes the proof ofTheorem 2. �

4.2 Existential Unforgeability Under ChosenMessage Attacks

In the bilinear group pair (G1,G2), q-strong Diffie-Hellman (SDH) problem is stated as follows: given a(q+2)-tuple of elements (P,Q, [γ]Q, [γ2]Q, . . . , [γq]Q) ∈G1 × G

q+12 , output a pair (x, [ 1

γ+x ]Q) for a freely cho-sen value x ∈ Zp\{−γ}, where P,Q are generators inG1 and G2 respectively. We give a definition of theSDH assumption as follows.

Definition 8 (Strong Diffie-Hellman Assumption).(q, t, ε)-SDH assumption holds in (G1,G2) if no t-timealgorithm A has advantage at least ε in solving q-strongDiffie-Hellman on (G1,G2), i.e.,

Pr[A

(P,Q, [γ]Q, . . . , [γq]Q

)=

(x,

[ 1γ + x

]Q

)]� ε,

where the probability is over the random choices of gene-rators (P,Q) in G1×G2, of γ in Zp and of the randombits of A, P = ψ(Q) for an efficient homomorphism ψ.

SDH assumption was proposed by Boneh and Boyento construct a short signature scheme without randomoracle. To gain confidence in the assumption theyproved that it holds in generic groups and it has similarproperties to the strong-RSA assumption.

Theorem 3. Suppose (q, t′, ε)-SDH assumptionholds in (G1,G2). Then PE-ABS scheme above is(t, qs, ε)-secure against existential forgery under a weakchosen message attack provided that qs � q and t �t′ − Θ(q2T ), where T is the maximum time for an ex-ponentiation in G1,G2, and Zp.

Proof. Suppose that there is a (t, qs, ε)-forger al-gorithm A that breaks the signature scheme. Weconstruct an algorithm B, by interacting with theforger A, which can solve the q-SDH problem intime t′ with advantage ε. B is given a randominstance (P,Q, [γ]Q, . . . , [γq]Q) of the q-SDH problemin (G1,G2), where P = ψ(Q).

�e([ris]G,h) = e([yr]ψ(u0), [a]w) = e([ayr/e]ψ(u0), [e]w) = e([yr/e]ψ(h0), [e]w) = e([yr]G′, h′).


Setup. Let f be the univariate polynomial definedby f(X) =

∏qi=1(X + xi) and fi(X) = f(X)

X+xi. Expand

f and write f(X) =∑q

i=0 aiXi where a0, . . . , aq ∈ Zp

are the coefficients of the polynomial f . Let α = f(γ),β = γ, G = P , then the simulator B chooses a randominteger ξ ∈ Z∗

p and sets

gpk =

⎧⎪⎪⎪⎨⎪⎪⎪⎩

g = [β]G = [γ]P = ψ([γ]Q),h = [ξ]Q,

ζ = e(G, h)α = e(P, [ξ]Q)f(γ)

= e(P, [f(γ)]Q)ξ = e(P,Q)ξf(γ).

Note that, gmk = (α, β,G) = (f(γ), γ, P ) is unknown.For each ri = −xi(fi(γ) + γ), compute

ski =

⎧⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎩

Di =[α+ ri

β

]h

=[f(γ)− xi(fi(γ) + γ)

γ

]h

= [ξ(fi(γ)− xi)]Q,

Ai,j = [ri]G+ [rj ]ψ(H0(attr j))= [−xi(fi(γ) + γ)]P + [rj ]ψ

(H0(attr j)

),

A′i,j = [rj ]ψ(h).

Queries. The simulator B must respond with atmost q signatures on the respective messages from A.B chooses t = xi and sets

Ei = [t]u = [xi]P,Ti =Di + [t]v = [fi(γ)− xi]h+ [xi]h = [ξfi(γ)]Q,

Qi = [s]g = [γs]G = [γs]P,Bi,j = [−xi(fi(γ) + γ)Δs(attr j)]P+

[rjΔs(attr j)]ψ(H0(attr j)),B′

i,j = [rjΔs(attr j)]ψ(h),

then selects c, ss, st ∈ Zp, and computes

V1 = [st]u− [c]Ei,

V2 =ζsse([ri]G, h)se(Qi, v)st

e(Qi, Ti)c,

c = H1(gpk ,M, Ti, Ei, Qi, V1, V2).

Output. After receiving the signature (M, σ =(T , u, v, Ti, Ei, Qi, c, ss, st, {(Bi,j , B′

i,j)}attrj∈T )), Battempts to extract t, the discrete logarithm of Ei.Using this value, B can compute xi. To achieve thisvalue, B checks

e([γ]G+ Ei, Ti) = e([γ + xi]G,

[ f(γ)γ + xi

]h)

= e(P,Q)ξf(γ) = ζ.

If the equality holds, B runs the above process againwith the same state as before but a different hashchallenge c ∈ Zp, and then obtains response (M, σ =(T , u, v, Ti, Ei, Qi, c, ss, st, {(Bi,j , B

′i,j)}attrj∈T )).

• If Ei = Ei, Ti = Ti, and V1 = V1, B computesxi = xi = st−st

c−c mod p due to that st = rt + c · xi,st = rt + c · xi, and rt = rt.• If Ei �= Ei, Ti �= Ti, or V1 �= V1, (Ei, V1, c, st) is a

zero-knowledge scheme, then there exists a knowledgeextractor that extracts t = xi from Ei.

Now, B gets a pair (xi, Ti) = (xi, [fi(γ)]h) =(xi, [

f(γ)γ+xi

]h). Write f(x) = (∑q−1

l=0 a′lx

l)(x + xi) + r.Thus B knows a′0, . . . , a

′q−1 and r. According to

[ f(γ)γ + xi

]h =

[ q−1∑l=0

a′lγl +

r

γ + xi

]h,

B computes

[ 1γ + xi

]Q =

[ 1rξ

]([ f(γ)γ + xi

]h−

[ q−1∑l=0

a′lγl]h)

=[ 1rξ

](Ti −

q−1∑l=0

a′l · [γl]h).

Finally, B outputs (xi, [ 1γ+xi

]Q) as the solution to thesubmitted instance of the SDH problem, which contra-dicts with SDH assumption.

The claimed bound t ≤ t′−Θ(q2T ) is obvious by theconstruction of the Algorithm B. �

5 Performance Analysis

In this section, we analyze the efficiency of the above-mentioned scheme. Firstly, we analyze the computationcost of disperse algorithm, aggregate algorithm, and allphases in the signature scheme. The basic operationof our scheme is the computation of a multiple ellip-tic point in elliptic curve (Mul), namely, [k]P , wherek is a positive integer and P is an elliptic curve point.We neglect the computation costs of an addition of el-liptic points and simple modular arithmetic operationsbecause they run fast enough[16]. The important ope-rations are the computation of a bilinear map e(·, ·) be-tween two elliptic points (BM), Hash functions (Hashs),and exponential operation in GT (EXP). For clearance,we give Table 1 to present them. In this table, weassume that the aggregate algorithm executes n timesEquation (1) and that each internal node has logn chil-dren, where n is the number of attributes.

Here we assume the pairing takes the form e :E(Fpm) × E(Fpkm) → F∗

pkm (we give here the defini-tion from [17-18]), where p is a prime, m is a positiveinteger, and k is the embedding degree (or security


Table 1. Performance Analysis for PE-ABS

Phase�Item Mul Hash BM EXP

Setup 2 0 1 1

Join 1 + 3n n 0 0

Sign 3 + 2n 1 1 2

Verify 3 n+ 1 2n+ 2 4

Disperse 0 0 0 0

Aggregate 0 0 0 n logn

multiplier). Without loss of generality, let the securityparameter κ be 80 bits, we need the elliptic curve do-main parameters over Fp with |p| = 160bits and m = 1in our experiments. This means that the length of in-teger is l0 = 2κ in Zp. Similarly, we have l1 = 4κin G1, l2 = 24κ in G2, and lT = 24κ in GT forthe embedding degree k = 6. Hence, for PE-ABSscheme, the communication overhead of sign/interactis 3l0 +(3+2n)l1 +2l2 + |T | = 66κ+9nκ bits, where nis the number of attributes and |T | denotes the lengthof policy tree (assume |T | = nκ). This means that 1 KBcan store a signature with more than 100 attributes.

6 Conclusion

The endorsement of claim is an important signatureform, widely used for accounting, banking, legal, busi-ness, insurance and other services. In order to imple-ment a cryptographic signature for the endorsement ofclaim, we propose an attribute-based signature schemewith policy-and-endorsement mechanism. Dependingon the match between access policies of signature andidentity attributes of private key, this scheme can meetvarious requirements to authenticate identity of sign-ers. Without doubt, the security proof of signaturescheme is a challenging task for random oracle model incomparison to standard model. Based on strong Diffie-Hellman assumption and Decision Linear assumption,we describe the security of our scheme from two aspects:selfless anonymity and existential unforgeability. In ad-dition, the performance analysis shows that our schemehas lower computational overheads and shorter signa-ture length for a highly complex policy. Future studiesin this area are two folds: first, to make access policymore refined, we will try to produce Boolean valuesusing relational comparisons; second, based on policy-and-endorsement mechanism, a group-oriented authen-tication scheme will be investigated to implement off-line identification in information sharing system.

Acknowledgement We thank the anonymousreferees for their valuable comments that have helpedto improve the manuscript.

References

[1] Boneh D, Hamburg M. Generalized identity based and

broadcast encryption schemes. In Proc. the 14th Int. Conf.the Theory and Application of Cryptology and InformationSecurity, Melbourne, Australia, Dec. 7-11, 2008, pp.455-470.

[2] Bethencourt J, Sahai A, Waters B. Ciphertext-policy attri-bute-based encryption. In Proc. the IEEE Symposium on Se-curity and Privacy, Oakland, USA, May 20-23, 2007, pp.321-334.

[3] Boneh D, Boyen X, Shacham H. Short group signatures. InProc. the 24th Annual International Cryptology Conference,Santa Barbara, USA, Aug. 15-19, 2004, pp.41-55.

[4] Wei P, Wang X, Zheng Y. Public key encryption without ran-dom oracle made truly practical. In Proc. the 11th Int. Conf.Information and Communications Security (ICICS), Beijing,China, Dec. 14-17, 2009, pp.107-120.

[5] Sahai A, Waters B. Fuzzy identity-based encryption. In Proc.the 24th Annual Int. Conf. the Theory and Applicationsof Cryptographic Techniques, Aarhus, Denmark, May 22-26,2005, pp.457-473.

[6] Goyal V, Pandey O, Sahai A, Waters B. Attribute-based en-cryption for fine-grained access control of encrypted data. InProc. the 13th ACM Conf. Computer and CommunicationsSecurity, Virginia, USA, Oct. 30-Nov. 3, 2006, pp.89-98.

[7] Shahandashti S-F, Safavi-Naini R. Threshold attribute-basedsignatures and their application to anonymous credential sys-tems. In Proc. the 2nd Int. Conf. Cryptology in Africa,Gammarth, Tunisia, Jun. 21-25, 2009, pp.198-216.

[8] Goyal V, Jain A, Pandey O, Sahai A. Bounded ciphertextpolicy attribute based encryption. In Proc. the 35th In-ternational Colloquium, Reykjavik, Iceland, Jul. 7-11, 2008,pp.579-591.

[9] Waters B. Ciphertext-policy attribute-based encryption: Anexpressive, efficient, and provably secure realization. Tech-nical Report, Cryptology ePrint archive: Report 2008/290,2008, http://eprint.iacr.org/2008/290.

[10] Khader D. Attribute based group signatures. Technical Re-port, Cryptology ePrint Archive, Report 2007/159, 2007,http://eprint.iacr.org/2007/159.

[11] Yuan E, Tong J. Attributed based access control (abac) forWeb services. In Proc. the 2005 IEEE Int. Conf. Web Ser-vices, Orlando, USA, July 11-15, 2005, pp.561-569.

[12] Adelsbach A, Huber U, Sadeghi A-R. Property-based broad-cast encryption for multi-level security policies. In Proc. the8th International Conference on Information Security andCryptology (ICISC), Seoul, Korea, Dec. 1-2, 2005, pp.15-31.

[13] Adelsbach A, Greveler U. A broadcast encryption scheme withfree-riders but unconditional security. In Proc. the First In-ternational Conference on Digital Rights Management: Tech-nologies, Issues, Challenges and Systems (DRMTICS), Syd-ney, Australia, Oct. 31-Nov. 2, 2005, pp.246-257.

[14] Kapadia A, Tsang P P, Smith S W. Attribute-based publish-ing with hidden credentials and hidden policies. In Proc. the2007 Network and Distributed System Security Symposium,California, USA, Feb. 28-Mar. 2, 2007, The Internet Society.

[15] Huang D, Verma M. Aspe: Attribute-based secure policy en-forcement in vehicular ad hoc networks. Ad Hoc Networks,2009, 7(8): 1526-1535.

[16] Barreto P S L M, Galbraith S D, O’Eigeartaigh C, Scott MEfficient pairing computation on supersingular abelian vari-eties. Des. Codes Cryptography, 2007, 42(3): 239-271.

[17] Beuchat J-L, Brisebarre N, Detrey J, Okamoto E. Arithmeticoperators for pairing-based cryptography. In Proc. the 9thInternational Workshop on Cryptographic Hardware and Em-bedded Systems (CHES), Vienna, Austria, Sept. 10-13, 2007,pp.239-255.

[18] Hu H, Hu L, Feng D. On a class of pseudo-random sequencesfrom elliptic curves over finite fields. IEEE Transactions onInformation Theory, 2007, 53(7): 2598-2605.


Huai-Xi Wang received his B.S.degree from the School of Mathemat-ical Sciences, Peking University in2006. He is a Ph.D. candidate at

Peking University. His research in-terests include attribute based sys-tem and paring based cryptography.

Yan Zhu is an associate professorof computer science in the Instituteof Computer Science and Technologyat Peking University since 2007. Heworked at the Department of Com-

puter Science and Engineering, Ari-zona State University as a visiting as-sociate professor from 2008 to 2009.His research interests include cryp-tography and network security.

Rong-Quan Feng received hisPh.D. degree from Academy ofMathematics and Systems Science,Chinese Academy of Sciences at1994. He is currently a professor

and Ph.D. supervisor at the School ofMathematical Sciences, Peking Uni-versity. His research interests in-clude cryptology and algebraic com-bination theory.

Stephen S. Yau received theB.S. degree from National TaiwanUniversity, and the M.S. and Ph.D.degrees from the University of Illi-nois, Urbana, all in electrical engi-

neering. He is a professor of Com-puter Science and Engineering andthe Director of Information Assur-ance Center at Arizona State Uni-versity, Tempe. He was previously

with the University of Florida, Gainesville and Northwest-

ern University, Evanston, Illinois. He has served as thepresident of the IEEE Computer Society and the Editor-in-Chief of Computer. His current research is in cyber se-curity, distributed computing systems, software engineer-ing, service-based computing and cloud computing sys-tems. Contact him at [email protected] or visit his Website:http://dpse.asu.edu/yau/.

Appendix BSW’s Attribute-BasedEncryption: Revised Version

The following scheme is the revised version of BSW’sCP-ABE in [2] with the result that we extend the el-liptic curve systems into G1 × G2 → GT to design thenew PE-ABS scheme.

Setup(κ,A). Let S = (p,G1,G2,GT , e(·, ·)) be a

bilinear map group system. It proceeds as follows:1) selects two generators G and h in G1 and G2 at

random;2) selects two random integers α, β ∈R Z∗

p;3) computes g = [β]G ∈ G1 and ζ = e(G, h)α ∈ GT ;4) publishes gpk = (S,A, g, h, ζ), and keeps gmk =

(α, β,G) secret.Join(gmk , i, ρi). Given gmk and a user counter i, let

ρi denote the set of attributes of user i. It proceeds asfollows:

1) selects a fresh ri ∈R Zp and computes⎧⎪⎪⎨⎪⎪⎩Di =

[α+ riβ

]h ∈ G2,

Ai,j = [ri]G+ [rj ]ψ(H(attrj)) ∈ G1,

A′i,j = [rj ]ψ(h) ∈ G1;

2) defines gsk [i] = (Di, (Ai,j , A′i,j)attrj∈ρi) and sends

it to member i.Encrypt(gpk , π,M). Given a plaintext M , the user

encrypts M as follows:1) selects s ∈R Zp and creates an access tree T start-

ing from root s according to Disperse algorithm;2) computes the ciphertext

⎧⎪⎪⎪⎨⎪⎪⎪⎩

C1 = [s]g ∈ G1,

C2 = M · ζs ∈ GT ,

Ej = [Δs(attrj)]h ∈ G2,

E′j = [Δs(attrj)]H(attrj) ∈ G2;

3) defines C = (T , C1, C2, (Ej , E′j)attrj∈T ).

Decrypt(gsk [i], C). Given C = (T , C1, C2, C3), theuser with gsk [i] will run as follows:

3.1) Computes

Tj =e(Ai,j , Ej)e(A′

i,j , E′j)

= e([ri]G, [Δs(attr j)]h),

where

e([rj ]ψ(H(attr j)), [Δs(attrj)]h)

= e([rj ]ψ(h), [Δs(attr j)]H(attr j)).

3.2) Uses a similar procedure to Aggregate algo-rithm, from the leaf-node of the tree upto the root nodelevel by level to recover S = e(G, h)ri·s, and then com-putes

M ′ =C2 · S

e(C1, Di)=

M · ζs · e(G, h)ri·s

e([sβ]G,

[α+ riβ

]h) .

If the user’s attributes satisfy the policy tree, then hecan obtain the message M ; otherwise, he cannot getany information about M .

Date post:	28-Nov-2023
Category:	Documents
Upload:	independent
View:	0 times
Download:	0 times

Attribute-Based Signature with Policy-and-Endorsement Mechanism

Documents