Advanced
Attribute Set Based Signature Secure in the Standard Model
Attribute Set Based Signature Secure in the Standard Model
KSII Transactions on Internet and Information Systems (TIIS). 2015. Apr, 9(4): 1516-1528
Copyright © 2015, Korean Society For Internet Information
  • Received : August 19, 2014
  • Accepted : March 02, 2015
  • Published : April 30, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Baohong Li
School of Electronics and Information Engineering, Xi’an Jiaotong University Xi’an, 710049 - China
Yinliang Zhao
School of Electronics and Information Engineering, Xi’an Jiaotong University Xi’an, 710049 - China
Hongping Zhao
518th Hosp. of PLA Xi’an, 710049 - China

Abstract
We introduce attribute set based signature (ASBS), a new cryptographic primitive which organizes user attributes into a recursive set based structure such that dynamic constraints can be imposed on how those attributes may be combined to satisfy a signing policy. Compared with attribute based signature (ABS), ASBS is more flexible and efficient in managing user attributes and specifying signing policies. We present a practical construction of ASBS and prove its security in the standard model under three subgroup decision related assumptions. Its efficiency is comparable to that of the most efficient ABS scheme.
Keywords
1. Introduction
- 1.1 Motivation
F lexible and privacy-preserving authentication scheme is a fundamental concern in modern cryptography, and attribute based signature (ABS) [1] is proposed as a potential solution. However, as observed by Bobba, Khurana and Prabhakaran [2] , attribute based systems are far from being flexible in managing user attributes and specifying signing policies, mainly due to the fact that they organizes user attributes into a single set, and a user can use all possible combinations of attributes issued in her attribute keys to satisfy a policy. For example, consider a graduate student who has enrolled in course 525 and she is also the TA for course 101. Here, both ‘ CourseID: 101’ and ‘Role: TA ’ are valid attributes but their combination is not allowed. To prevent such undesirable combination, these attributes have to be appended into two strings of ‘ Role:TA_CourseID:101 ’ and ‘ Role:Grad_CourseID:525 ’. However, this approach leads to another undesirable consequence where a singleton attribute, say, ‘ Role:TA ’ , can’t be used alone to satisfy a policy, since attribute based systems only checks the equality of strings and can’t extract a single attribute from a string.
To addresses these limitations, Bobba, Khurana and Prabhakaran present ciphertext policy attribute set based encryption (CP-ASBE) [2] as an enhancement to attribute-based encryption (ABE). By organizing user attributes into a recursive set based structure, CP-ASBE allows users to impose dynamic constraints on how those attributes may be combined to satisfy a policy, that is, policies can be specified to restrict decrypting users to use attributes from a single set or allow them to combine attributes from multiple sets. Moreover, CP-ASBE can efficiently support multiple value assignments and attribute revocation. Due to these powerful features, CP-ASBE provides an attractive primitive to realize a flexible and fine-grained access control in distributed systems.
Since ABS suffers from almost same problems as ABE, a natural question is whether there exists a practical signature analog of CP-ASBE, to realize a flexible and privacy-preserving authentication mechanism.
- 1.2 Contribution
In this paper, we introduce attribute set based signature (ASBS) as an enhancement to ABS. Since ASBS also organizes user attributes into a recursive set based structure, it shares same flexibility and other desirable features with CP-ASBE; that is, ASBS allows dynamic constraints to be imposed on how those attributes may be combined to satisfy a signing policy, and it also can efficiently support compound attributes, multiple value assignments and attribute revocation. We also construct a practical ASBS and prove its security in the standard model under three subgroup decision related assumptions. The efficiency of our construction is comparable to that of the most efficient ABS scheme.
Although our ASBS may be thought as the signature analog of CP-ASBE, it can’t be straightforwardly converted from Bobba, Khurana and Prabhakaran’s construction, since it can only be proved secure under both generic group model and random oracle model. In addition, perfect privacy is a specific requirement in our ASBS.
Roughly speaking, a signature in our construction is generated by re-randomizing a secret key, and it is verified by first distributing shares of a secret exponent across some verification components and then checking whether the secret can be recovered by the signature. To do so, we need to extend the re-randomization technique from the ABS scheme due to Okamoto and Takashima [3] , in order to accommodate our more complicated key structure. We also adapt the dual system encryption of Lewko and Waters to prove the security of our ASBS. Their technique is originally developed to prove the full security of IBE and ABE [4 , 5] .
The primary challenge in our construction is how to manage the recursive set based attribute structure. Specifically, our construction should allow a signing policy to specify whether and how a signer can combine attributes from multiple sets within her attribute structure. To tackle the issue, we introduce the translating keys and translating verification components . Given a signer’s attribute structure, we randomize attribute keys in each attribute set with a unique exponent. Then a translating key is issued for each attribute set, used to translate the exponent into a constant such that attribute keys in this attribute set can be combined with other attribute keys to satisfy a signing policy. However, this combination can only be performed with the help of the corresponding translating verification component, which is generated by the verifier when the signing policy does specify to do so.
- 1.3 Related Work
Because ABS is the most related concept to ours ASBS, we briefly review it as follows.
Maji, Prabhakaran and Rosulek [1] presented the first ABS in 2008. This primitive allows a signer to convince a verifer that she holds a set of attributes satisfying the signing policy and has endorsed the message. Their scheme supports very expressive signing policies and is almost optimally efficient, but its security is only proven in generic group model, an artificial model which is not solid enough to guarantee the security.
Motivated by the limitation of [1] , several ABS schemes [6 - 8 , 15 - 17] were presented to be secure in the standard model , but they can only achieve selective security , a weaker notion of unforgeability than adaptive security . In this security model, an adversary is required to announce the target signing policy she intends to attack before seeing the public parameters. In addition, signing policies in most of these ABS schemes are limited to threshold predicate, which is less expressive than necessary.
Maji, Prabhakaran and Rosulek [9] presented the first ABS which is adaptively secure in the standard model, but it is much less efficient (in terms of signature size) since it employed the Groth-Sahai NIZK system as building blocks, in order to prove relations between the bits of elements in the group. By using the technology of dual pairing vector spaces, Okamoto and Takashima [3] also presented an ABS scheme which is adaptively secure in the standard model, and their scheme is more expressive, i.e., it allows non-monotone predicates to express signing policies. They further improved it to accommodate the setting of multi-authority [10] . However, the efficiencies of their two schemes are several times worse than that of Maji, Prabhakaran and Rosulek’s ABS scheme [1] .
As we mentioned earlier, all of these ABS schemes are not flexible enough in managing user attributes and specifying signing policies. So our goal is to present a construction of ASBS that satisfies at the same time the following properties: (1) it is proved adaptively secure in the standard model, (2) it admits general signing policies, and (3) it is efficient in terms of signature size.
The remainder of the paper is organized as follows. In Section 2, we review some definitions and complexity assumptions. Section 3 defines ASBS and formulizes its security. In Section 4, we present our construction of ASBS and prove its security. Finally, Section 5 concludes the whole paper.
2. Preliminaries
- 2.1 Bilinear Groups of Composite Order and Complexity Assumptions
Definition 1 (Bilinear group of composite order) : A (symmetric) bilinear group of composite order is a tuple ( N , G , GT , ê ) where N = p 1 p 2 p 3 for distinct primes p 1 , p 2 , p 3 , G , GT are cyclic groups of composite order N , and ê : G × G GT is an efficiently computable function with the following properties:
(1) ∀ g , h G , ∀ a , b Z N , ê ( ga , hb ) = ê ( g , h ) ab
(2) The element ê ( g , g ) is a generator of GT .
The security of our construction relies on three subgroup decision related assumptions on bilinear groups of composite order. They have been used by Lewko and Waters to prove the security of their IBE [4] and ABE [5] . To be concise, in the sequel we use Gpi or Gpipj to denote the subgroup of order pi or pi pj in G .
Assumption 1 : Given a bilinear group of composite order ( N , G , GT , ê ) and random g Gp 1 , X 3 Gp 3 , it is hard to distinguish a random element T 1 Gp 1 p 2 from a random element T 2 Gp 1
Assumption 2 : Given a bilinear group of composite order ( N , G , GT , ê ) and random g,X 1 Gp 1 , X 2 Y 2 Gp 2 , X 3 Y 3 Gp 3 , it is hard to distinguish a random element T 1 G from a random element T 2 Gp 1 p 3 .
Assumption 3 : Given a bilinear group of composite order ( N , G , GT , ê ) and random α , s Z N , g Gp 1 , X 2 , Y 2 , Z 2 Gp 2 , X 3 Gp 3 , it is hard to distinguish the element T 1 = ê ( g , g ) αs from a random element T 2 GT .
- 2.2 Linear Secret Sharing Scheme and Attribute Structure
Definition 2 (Monotone access structure [11]) : Let P= { P 1 , P 2 ,…, Pl } be a set of parties (attributes in our setting). A collection Λ⊆2 P is monotone if ∀ B,C : if B ∈Λ and B C then C ∈Λ. A monotone access structure is a collection Λ of non-empty subsets of P, and elements in Λ are called as authorized sets.
Definition 3 (Linear secret sharing scheme (LSSS) [11]) : A secret sharing scheme over a set of parties P= { P 1 , P 2 ,…, Pl } is called linear (over Z N ) if,
(1) The shares of each party form a vector over Z N , and
(2) There exists a matrix A with l rows and n columns, and a function ρ which maps Ax , the x -th row of A , to the party ρ ( x ) for x = 1, …, l . Given a random vector v = ( s , v 2 ,…, vn )∈ Z nN , A⋅v is the vector of l shares of the secret s , and Ax⋅v belongs to party ρ ( x ).
Using standard techniques [12] , any monotonic boolean formulas can be converted into an LSSS matrix A to represent its access structure Λ. For each authorized set B ∈Λ, there exists a reconstruction vector ω = ( ω 1 , ω 2 ,…, ωl )∈ Z lN , where ωx = 0 if ρ ( x )∉ B , such that ω A = (1, 0, …, 0) and Σ ρ(x)∉ B ωxAx⋅v=s . On the contrary, no reconstruction vector exists if B ∉Λ.
Definition 4 (Attribute structure): An attribute structure in ASBS is a recursive set where each element of the set is either a set itself (i.e. an attribute structure) or an attribute.
The depth of an attribute structure is defined as the number of its recursive levels. Like the CP-ASBE [2] , our construction mainly focuses on the attribute structure with depth 2, where elements at depth 1 can either be attributes or sets but elements at depth 2 can only be attributes, belonging to some sets at depth 1. For each set at depth 1, an index , numbered from 1, is assigned to identify it. For the sake of consistency, attributes at depth 1 can be thought to form a set with index of 0. We also abuse the notion of index to an individual attribute, which is defined as the combination of the index of the set it belongs to and its sequence number in the set.
In our construction, a signing policy is expressed by a monotonic boolean formula and a signer’s attributes are described by an attribute structure. If a signer’s attribute structure satisfies the signing policy, the signing policy is realized by the corresponding LSSS matrix and the reconstruction vector is used to generate a signature.
3. Definitions
- 3.1 Attribute Set based Signature
Definition 5 (Attribute Set based Signature) : An attribute set based signature ASBS = {Setup, KGen, Sign, Verify} is a tuple of polynomial time algorithms.
–Setup (1 λ ) → ( PK , MSK ) . On input security parameter 1 λ , the setup algorithm outputs the public parameters PK and a master secret key MSK for the attribute authority.
–KGen ( PK , MSK , AS ) → SK . Given ( PK , MSK ) and an user’s attribute structure AS , the key generation algorithm outputs a secret key SK for the user.
–Sign ( PK , SK , M , ( A , ρ )) → σ . The signing algorithm takes in PK , a secret key SK , a message M and a LSSS access structure ( A , ρ ) over the universe of attributes. If the attribute structure in SK satisfies the LSSS access structure, it outputs a signature σ .
–Verify ( PK , M , ( A , ρ ), σ ) → 1/0. Given PK , a message M , a LSSS access structure ( A , ρ ) and a signature σ , the verification algorithm outputs 1 if σ is a valid signature on M or 0 otherwise.
- 3.2 Security model for ASBS
Perfect privacy and unforgeability are two security properties that ASBS should satisfy. We give their formal definitions as follows.
Definition 6 (Perfect Privacy) : An ASBS scheme is perfect privacy, if, for all ( PK , MSK ) ← Setup(1 λ ), all messages M , all attribute structures AS (1) and AS (2) , all secret keys SK (1) ← KGen( PK , MSK , AS (1) ) and SK (2) ← KGen( PK , MSK , AS (2) ), all access structures ( A , ρ ) such that both AS (1) and AS (2) satisfy ( A , ρ ), the distributions of σ (1) = Sign( PK , SK (1) , M , ( A , ρ )) and σ (2) = Sign( PK , SK (2) , M , ( A , ρ )) are equal.
Definition 7 (Existential Unforgeability) : For an adversary A , we define GameAdv A to be its success probability in the following game. An ASBS scheme is existentially unforgeable if GameAdv A is negligible for any polynomial-time adversary A .
Setup Run ( PK , MSK ) ← Setup(1 λ ) and give PK to A .
Queries A can adaptively makes a polynomial number of q queries of the following two types:
(1) Key Queries A can request a secret key for any attribute structure AS .
(2) Signing Queries A can request a signature for any message, attribute structure AS and access structure ( A , ρ ), with the restriction that the attribute structure AS should satisfy the access structure ( A , ρ ).
–Forgery A outputs a signature σ * on a message M * and an access structure ( A *, ρ *). A succeeds in the game if
(1) Verify( PK , M *, ( A *, ρ *), σ *) = 1.
(2) A has never queried a secret key for an attribute structure AS * satisfying ( A *, ρ *).
(3) A has never queried a signature on message M * and ( A *, ρ *).
4. OUR ASBS
- 4.1 Construction
We construct our ASBS in a bilinear group of composite order ( N , G , GT , ê ), where keys and signatures occur in the subgroups G p1p3 , while the subgroup G p2 is used as the semi-functional space to prove the security of our construction.
–Setup (1 λ ) The setup algorithm performs the following steps:
(1) Generate a bilinear group ( N , G , GT , ê ) of composite order N = p 1 p 2 p 3 .
(2) Pick random value α , a Z N , g G p1 , X 3 G p3 , and choose u 0 , u 1 ,…, uη G p1 as Water’s hash function [13] , where η is the length of a message. To be concise, we define
PPT Slide
Lager Image
for a message M = ( μ 1 , μ 2 ,…, μη ).
(3) Let the universe attribute structure be AS = { AS 0 , AS 1 , …, ASm }. For each attribute set ASi = { ati ,1 , …, , ati,ni }, 1≤ i m , pick a unique random exponent bi Z N . For the j -th attribute appearing in set ASi , 0≤ i m , 1≤ j ni , pick a unique random exponent hij Z N .
The algorithm outputs public parameters and the master secret key as:
  • PK= (N,G,GT,ê,g,ga,ê(g,g)α,u0,u1,…,uη,gbi∀i,ga/bi∀i,Hij=∀i∀j)
  • MSK= (α,bi∀i,X3)
–KGen ( PK , MSK , AS ) The key generation algorithm chooses a unique random ti Z N for each set ASi AS , 0≤ i m . It also chooses random elements R 0 ,Ri,R'i,Rij Gp 3 and outputs the secret key as:
  • K=gαgat0R0,
  • Ki=gtiRi,Kij=(Hij)tiRij, 0≤i≤m, 1≤j≤ni
  • Li=ga(t0+ti)/biR'i, 1≤i≤m
–Sign ( PK , SK , M , ( A , ρ )) Let A be an l × n matrix and Ax be the x -th row of A . The function ρ maps each row number x to an attribute’s index ρ ( x ), while the function φ maps x to the index of the set the attribute ρ ( x ) belongs to. The algorithm proceeds as follows:
(1) Choose random t' 0 t'ϕ (x) Z N for 1≤ x l , and blind the secret key SK as:
  • K' =K(ga)t'0= (gαga(t0+‘t0)R0,
  • K'ϕ(x)=Kϕ(x)gt'ϕ(x)=gtϕ(x)+t'ϕ(x)Rϕ(x),
  • K'ρ(x)=Kρ(x)(Hρ(x))t'ϕ(x)= (Hρ(x))tϕ(x)+t'ϕ(x)Rρ(x)
  • L'ϕ(x)=Lϕ(x)(ga/bϕ(x))t'0t'ϕ(x)=ga(t0+t'0+tϕ(x)+t'ϕ(x))/bϕ(x)R'ϕ(x)
(2) Find a reconstruction vector ω = ( ω 1 , ω 2 ,…, ωl )∈ Z lN and two random vectors β 1 = ( β 11 , β 12 ,…, β 1l ), β 2 = ( β 21 , β 22 ,…, β 2l ), such that β 1 A = β 2 A = (0, 0, …, 0). We discuss the existence of β 1 , β 2 in the proof of Theorem 1. Then compute:
  • σa=K'∏lx=1((K'ρ(x))ωx, (Hρ(x))β1x)F(M)r,σb=gr
  • σ1,x= (K'ϕ(x))ωxgβ1x,σ2,x= (L'ϕ(x))ωx(ga/bϕ(x))β2x, 1≤x≤l
The algorithm outputs the signature as σ = ( σa , σb , ( σ 1,x , σ 2,x ) x =1,...,l ).
–Verify ( PK , M , ( A , ρ ), σ ) Given a signature σ on a message M , the algorithm first chooses a random vector v = ( s , v 2 , ..., vn )∈ Z nN and generates a group of verification components as follow:
  • C=gs,Cx=gaAxv(Hρ(x))−s,Ex=gbϕ(x)Axv, 1 ≤x≤l
Then the algorithm outputs 1 if the following verification equation holds
PPT Slide
Lager Image
We name the component Li in a secret key and Ex in the verification components as the translating key and the translating verification component , respectively. During verification, only simultaneous use of both a translating key and the corresponding translating verification component can translate the exponents ti in Ki and Kij into the constant t 0 , and the verification succeeds only when all ti are translated into t 0 .
- 4.2 Efficiency
To show the efficiency and security of our ASBS, we compare it with existing ABS schemes which support general signing policies in Table 1 , where l and n are the size of the underlying LSSS matrix, and λ is the security parameter (e.g., 128). The signature size and complexity are measured in terms of the number of group elements and the number of paring operations to verify a signature, respectively. In addition, since there are two constructions are presented in [9] , the more efficient construction based on Waters signature is used to measure the signature size, and the underlying Groth-Sahai NIZK system is instantiated under DLIN Assumption.
Comparison with ABS schemes supporting general signing policies
PPT Slide
Lager Image
Comparison with ABS schemes supporting general signing policies
Although some ABS schemes, such as [6 - 8 , 15 - 17] , have short or even constant signature size, we need not compare with them in Table 1 , since they only admit threshold signing policies, which can’t provide enough flexibility than necessary. Although some of them, such as [17] , can be extended to admit general signing policies, the signature size, as the authors of [17] denoted, will drastically increase.
Since the ABS scheme due to Maji, Prabhakaran and Rosulek [1] has the best efficiency among all ABS schemes, we consider it as a benchmark. Compared with this ABS scheme, our ASBS has almost same signature size but less complexity.
- 4.3 Perfect Privacy
Theorem 1. Our construction of ASBS can achieve perfect privacy.
Proof. Given a LSSS access structure ( A , ρ ), if rank( A ) < l , there obviously exist polynomial numbers of vectors β such that β A = (0, 0, …, 0). If rank( A ) = l , there exists only one β = (0, 0, …, 0) such that β A = (0, 0, …, 0), but the signing policy is limited to a ( n , n )-threshold predicate, which means there is no attribute privacy at all. So we only need to consider the case of rank( A ) < l .
To show that two signatures of σ (1) = Sign ( PK , SK (1) , M , ( A , ρ )) and σ (2) = Sign ( PK , SK (2) , M , ( A , ρ )) have equal distributions, it suffices to prove that, by choosing proper random t'i , r and β 1 , β 2 , same signatures can be generated from different keys SK (1) and SK (2) . To do so, we choose r (1) = r (2) , t 0 (1) + t ' 0 (1) = t 0 = t 0 (2) + t ' 0 (2) and
PPT Slide
Lager Image
for 1 ≤ x l . Given
PPT Slide
Lager Image
we also choose β 1 (2) and β 2 (2) by setting
PPT Slide
Lager Image
It is easy to check that β 1 (2) A = β 2 (2) A = (0, 0, …, 0) and σ (1) = σ (2) .
- 4.4 Existential Unforgeability
We adapt the dual system encryption technique [4 , 5] to prove the unforgeability of our construction. Specifically, we define two types of semi-functional signatures and an additional semi-functional verification algorithm VerifySF . We also define a sequence of games where the first game is the real unforgeable game and in the last game the success probability of any polynomial-time adversary is negligible. Then, by standard hybrid arguments, we prove several lemmas to show that the adversary's success probabilities are indistinguishable among these games. The unforgeability of our construction follows from these lemmas.
–Semi-functional signatures of type 1 Given a normal signature
PPT Slide
Lager Image
a semi-functional signature of type 1 is generated by choosing a generator g 2 G p2 , random exponents d , e Z N and fx Z N , and outputting
PPT Slide
Lager Image
–Semi-functional signatures of type 2 Given a normal signature
PPT Slide
Lager Image
a semi-functional signature of type 2 is generated as
PPT Slide
Lager Image
–VerifySF This algorithm is same as Verify except that it chooses a random exponent c Z N , two random vectors u,w Z nN , random values γx Z N , for each x , and random values zρ (x) Z N for each attribute ρ ( x ), and generates semi-functional verification components as:
PPT Slide
Lager Image
–Gamereal : The real security game defined in Section 3.
–Game0 : The real security game with the exception that the algorithm VerifySF is used to verify a forged signature.
–Gamek,1 , 1 ≤ k q : Same as Game 0 except that the first k − 1 signatures are semi-functional signatures of type 2 and the k -th key is a semi-functional signature of type 1.
–Gamek,2 , 1 ≤ k q : Same as Game k ,1 except that the k -th signature is also a semi-functional signature of type 2.
–Gamefinal : In this game, all signatures are semi-functional signatures of type 2, and the forged signature is verified by VerifySF .
Lemma 1. Suppose there exists an adversary A such that Game real Adv A − Game 0 Adv A = ε , then we can build a simulator S that has advantage ε in breaking the Assumption 1.
Proof. The simulator S begins by taking in an instance ( g , X 3 , T ) of Assumption 1, where T = gsgc 2 or gs for unknown s,c Z N . It simulates Game real or Game 0 as follows:
–Setup S generates PK and MSK by running the algorithm Setup .
–Queries Since S knows the MSK , it can run algorithms KGen and Sign to outputs any secret keys and signatures.
–Forgery Upon receiving a forged signature, S chooses a random vector v ' = (1, v ' 2 , ..., v'n )∈ Z nN , and generates verification components as follows:
  • C=T,Cx=TaAxv'T−sρ(x),Ex=Tbφ(x)Axv'
If T = gs , we have C = gs ,
PPT Slide
Lager Image
Ex = g bφ(x)Axsv' . They are properly distributed normal verification components with the implicit setting of v = sv '.
If T = gsgc 2 , we have C = gsgc 2 ,
PPT Slide
Lager Image
They are well-formed semi-functional verification components if we further set u = cav ', zρ (x) = csρ (x) , cbϕ (x) = γx and w = v '. Although some values in G p1 parts of the verification components, such as a , v ', sρ (x) , bφ (x) , are reused in G p2 parts, it is still properly distributed, since these values modulo p 2 are uncorrelated from their values modulo p 1 due to the Chinese Remainder Theorem. Hence S can use the output of A to break the Assumption 1 with advantage ε .
Lemma 2. Suppose there exists an adversary A such that Game k−1,2 Adv A − Game k,1 Adv A = ε , then we can build a simulator S □ that has advantage ε in breaking the Assumption 2.
Proof. Given an instance ( X 1 X 2 , X 3 , Y 2 Y 3 , T ) of Assumption 2, where T = gtge 2 R or gtR , for some unknown t , e eZ N and R Gp 3 , S simulates Game k−1,2 or Game k,1 as follows.
–Setup S generates PK and MSK by running the algorithm Setup .
–Queries Since S knows the MSK , it can generate any secret keys by running the algorithm KGen . S can also generate normal signtures for requests > k by running the algorithm Sign .
To generate the first k − 1 semi-functional signatures, S first generates a normal signature σ' = ( σ'a , σ'b , ( σ' 1,x , σ' 2,x ) x=1 ,..., l ). Then it choose random d' eZ N and outputs the signature as σ = ( σ'a ( Y 2 Y 3 ) d' σ'b , ( σ' 1,x , σ' 2,x ) x=1 ,..., l ). It is a properly distributed semi-functional signature of type 2 if we implicitly set
PPT Slide
Lager Image
To generate the k -th signature, S chooses random ξϕ (x) Z N , R' 0 , R'ϕ (x) , R"ϕ (x) , R'ρ (x) G p3 and r Z N . It also chooses a reconstruction vector ω and two random vectors β 1 , β 2 such that β 1 A = β 2 A = (0, 0, …, 0), and outputs:
PPT Slide
Lager Image
If T = gtge 2 R , we have a properly distributed semi-functional signature of type 1 as follows, where we implicitly set t 0 = t , tϕ (x) = t + ξϕ (x) , fx = 2 ae / bϕ (x) , R 0 = R' 0 Ra , Rρ (x) = Rsρ (x) R'ρ (x) ,
PPT Slide
Lager Image
Rϕ (x) = RR'ρ (x) , R'ϕ (x) = R 2 R''ϕ (x) .
PPT Slide
Lager Image
If T = gtR , we have a properly distributed normal signature with the implicit setting of t 0 = t , tϕ (x) = t + ξϕ (x) .
It can be checked that the k -th signature, in both cases of T = gtge 2 R or T = gtR , can be successfully verified by the algorithm VerifySF , so neither A □nor S can distinguish two games by verifying the k -th signature.
–Forgery To simulate the algorithm VerifySF , S implicitly sets gs = X 1 , gc 2 = X 2 and obtains ê ( g , g ) αs by computing ê ( g , X 1 X 2 ) α . It also chooses a random vector u' = ( a , u' 2 ,..., u'n ) and generates verification components as follows:
PPT Slide
Lager Image
We can check that
PPT Slide
Lager Image
thus it is a properly distributed verification components with the implicit setting of v = sa −1 u ', u = cu ', zρ (x) = csρ (x) , γx = cbρ (x) and w = a −1 u '.
To sum up, depend on whether T G or T G p1p3 , S can properly simulate Game k−1,2 or Game k,1 , thus can use the output of A to break the Assumption 2 with advantage ε .
Lemma 3. Suppose there exists an adversary A such that Game k,1 Advk A − Game k,2 Advk A = ε , then we can build a simulator S that has advantage ε in breaking the Assumption 2.
Proof. S simulates the games in almost the same way as it does in the lemma 2, except that it chooses a random exponent h Z N and generates the k -th signature as:
PPT Slide
Lager Image
Depend on T G or T G p1p3 , it is a properly distributed semi-functional signature of type 2 or normal signature, and in both cases it can’t be verified by the algorithm VerifySF due to the extra term ( Y 2 Y 3 ) h . Thus S can also use the output of A to break the Assumption 2 with advantage ε .
Lemma 4. Suppose there exists an adversary A such that Game q,2 Advk A − Game final Advk A = ε , then we can build a simulator S that has advantage ε in breaking the Assumption 3.
Proof. Given an instance ( gαX 2 , X 2 , gsY 3 , Z 2 , T ) of Assumption 3, where T = ê ( g , g ) αs or ê ( g , g ) r for unknown α , s , r Z N , S simulates Game q,2 or Game final as follows.
–Setup S chooses random exponents a , bi , sij , u 0 , u 1 ,…, uη Z N , and sets PK as:
  • PK= (N,G,GT,ê,g,ga,ê(g,gαX2),u0,u1,…,uη,gbi∀i,ga/bi∀i,Hij=∀i∀j)
–Queries S generates a secret key as follows:
  • K=gαX2gat0(Z2)t0R0
  • Ki=gtiRi,Kij= (Hij)tiRij, 0 ≤i≤m, 1≤j≤ni
  • Li=ga(t0+ti)/biR'i, 1≤j≤m
Given such a secret key, S generates a signature by running the algorithm Sign . The resulting signature is a properly distributed semi-functional signature of type 2 with the implicit setting of gd 2 = X 2 ( Z 2 ) t0 .
–Forgery To simulate the algorithm VerifySF , S chooses a random vector u ' = ( a , u ' 2 ,..., u'n ), and outputs verification components as follows:
PPT Slide
Lager Image
It is a properly distributed semi-functional verification components, with the implicitly setting of gc 2 = Y 2 , v = sa −1 u ', u = cu ', zρ (x) = csρ (x) , γx = cbρ (x) and w = a −1 u '. Then S verifies the signature by the verification equation of ê ( σa , C ) = ( F ( M ) s , σb )∏ lx =1 ê ( Ex , σ 2x )/ ê ( Cx , σ 1x ).
If T = ê ( g , g ) αs , it is the original verification equation (1) used in VerifySF . Otherwise, due to the random T in the verification equation, S rejects the forged signature with overwhelming probability. Thus S can use the output of A to break the Assumption 3 with advantage ε .
Theorem 2 (Unforgeability). Our construction of ASBS is existential unforgeable under Assumptions 1, 2 and 3.
Proof. It follows from lemma 1 to 4, and the fact that the success probability of any polynomial-time adversary in Game final is negligible.
5. Conclusion
In this paper, we introduce attribute set based signature as an enhancement to attribute based signature. ASBS organizes user attributes into a recursive set based structure such that dynamic constraints can be imposed on how those attributes may be combined to satisfy a signing policy. Thus it is more flexible and efficient in managing user attributes and specifying signing policies. We present a practical construction of ASBS and prove its security in the standard model under three subgroup decision related assumptions. Its efficiency is comparable to that of the most efficient ABS scheme.
Our construction relies on a bilinear group of composite order. This requires large group orders to guarantee security. So an interesting direction for future research is to convert it to prime order groups, probably using the technique from [14] .
BIO
Baohong Li, Lecturer in School of Electronics and Information Engineering, Xi’an Jiaotong University (XJTU), China. He received his M.S. degree and Ph.D. degree in computer science from XJTU in 2002 and 2006. His current research interests include Network Security and Cryptography.
Yinliang Zhao, Professor in School of Electronics and Information Engineering, Xi’an Jiaotong University (XJTU), China. He received his M.S. degree and Ph.D. degree in computer science from XJTU in 1988 and 1995. His research interests include Network Security, Parallel Computing thread-level parallelism and Compiler Optimization.
Hongping Zhao, She received her M.S. degree and Ph.D. degree from the Fourth Military Medical University in 2003 and 2006. She is currently a chief engineer in 518th Hosp. of PLA. Her research interests include network security and Management Information System.
References
Maji H. K. , Prabhakaran M. , Rosulek M. 2008 “Attribute-based signatures: achieving attribute-privacy and collusion-resistance,” IACR Cryptology ePrint Archive 328 -
Bobba R. , Khurana H. , Prabhakaran M. “Attribute-sets: a practically motivated enhancement to attribute-based encryption,” in Proc. of 14th European Symposium on Research in Computer Security 2009 587 - 604
Okamoto T. , Takashima K. “Efficient attribute-based signatures for non-monotone predicates in the standard model,” in Proc. of the 14th Int. Conf. on Public Key Cryptography 2011 35 - 52
Lewko A. , Waters B. “New techniques for dual system encryption and fully secure HIBE with short ciphertexts,” in Proc. of 7th Theory of Cryptography Conference 2010 455 - 479
Lewko A. , Okamoto T. , Sahai A. “Fully secure functional encryption: attribute-based encryption and (hierarchical) inner product encryption,” in Proc. of Advances in Cryptology - EUROCRYPT 2010 2010 62 - 91
Li J. , Au M. H. , Susilo W. “Attribute-based signature and its application,” in Proc. of 5th ACM Symposium on Information, Computer and Communications Security 2010 60 - 69
Shahandashti S. F. , Safavi-Naini R. “Threshold attribute-based signatures and their application to anonymous credential systems,” in Proc. of Progress in Cryptology – AFRICACRYPT 2009 2009 198 - 216
Guo S. , Zeng Y. “Attribute-based signature scheme,” in Proc. of International Conference on Information Security and Assurancec 2008 509 - 511
Maji H. K. , Prabhakaran M. , Rosulek M. “Attribute-based signatures,” in Proc. of Cryptographers’Track at the RSA Conference 2011 376 - 392
Okamoto T. , Takashima K. “Decentralized attribute-based signatures,” in Proc. of Public-Key Cryptography 2013 125 - 142
Beimel A. , PhD thesis 1996 “Secure schemes for secret sharing and key distribution,” Isral institute of technology PhD thesis
Karchmer M. , Karchmer A. W. “On span programs,” in Proc. of the 8th IEEE Structure in Complexity Theory Conference 1993 102 - 111
Waters B. “Efficient identity-based encryption without random oracle,” in Proc. of Advances in Cryptology - EUROCRYPT 2005 2005 114 - 127
Lewko A. “Tools for simulating features of composite order bilinear groups in the prime order setting,” in Proc. of Advances in Cryptology - EUROCRYPT 2012 2012 318 - 335
Herranz J. , Laguillaumie F. , Libert B. , Ràfols C. “Short attribute-based signature for threshold predicates,” in Proc. of Int. Conf. of the cryptographers’ Track at the RSA 2012 51 - 67
Chen C. , Chen J. , Lim H. W. “Fully secure attribute-based systems with short ciphertexts/signatures and threshold access structures,” in Proc. of Int. Conf. of the cryptographers’ Track at the RSA 2013 50 - 67
Escala A. , Herranz J. , Morillo P. “Revocable attribute-based signatures with adaptive security in the standard model,” in Proc. of Progress in Cryptology - AFRICACRYPT 2011 2011 224 - 241