Flexible Attribute-Based Encryption
Seiko AritaGraduate School of Information Security,
Institute of Information Security, Japanarita@iisec.ac.jp

Abstract. In this paper, we propose a notion of flexible attribute-based
encryption. Flexible attribute-based encryption is a variant of ciphertextpolicy ABE, which allows one to loosen a decryption policy underlying agiven ciphertext, if one knows some system-wide trapdoor information,
without knowing its underlying plaintext message. We give a concrete
construction of the ﬂexible attribute-based encryption that satisﬁes indistinguishability under the loosening operation, based on the construction of ciphertext-policy ABE given by Bethencourt, Sahai and Waters.
Keywords: Attribute-based encryption, Ciphertext-policy, Loosening
operation.

1

Introduction

A notion of attribute-based encryption (ABE) was ﬁrst proposed by Sahai andWaters [13], in which, a message m is encrypted to a ciphertext c under somepredicate f , and a user with credential X can decrypt the ciphertext c if and only
if the predicate f is satisﬁed by the user’s credential X: f (X) = 1. The conceptof ABE was further clariﬁed by Goyal, Pandey, Sahai, and Waters [6]. They proposed two complementary forms of ABE: Key-Policy ABE and Ciphertext-Policy
ABE. In this paper, we focus on Ciphertext-Policy ABE, in which attributes areused to describe users’ credentials and formulas over these attributes are attached to the ciphertext by the encrypting party.
The ﬁrst construction of Ciphertext-Policy ABE was given by Bethencourt, Sahai, and Waters [4]. Its security is proved under the generic bilinear group withrandom oracle model. (We call the model which uses both the generic bilinear
group and random oracle the generic bilinear group with random oracle model.)Waters [15] gives a construction of ABE which can be proved under the standard
model in a selective manner. Lewko, Okamoto, Sahai, Takashima, and Waters [10]and Okamoto and Takashima [12] give fully secure constructions of ABE in thestandard model.
Supported by MEXT-Supported Program for the Strategic Research Foundation atPrivate Universities, 2011-2013.

T.W. Chim and T.H. Yuen (Eds.): ICICS 2012, LNCS 7618, pp. 471–478, 2012.
c Springer-Verlag Berlin Heidelberg 2012
472

S. Arita

On a while, ABE has been applied in building a variety of secure systems [14,5,2].
One of major problems in these applications is that ABE-based systems tend tolack ﬂexibility. A ciphertext once produced under decryption policy f never canbe decrypted under a more loosened policy or(f, Δf ) (if f is not satisﬁed) by thedeﬁnition of security of ABE (of course). However, in reality, the degree of privacyof information is never ﬁxed: yesterday’s secret is not necessary secret of today.
Even if some information is very restrictive (described as policy f ) to be accessedat this moment of time, the same information gradually can be made more andmore accessible (described as policy or(f, Δf )) as time goes by.
Our contribution. In this paper, we propose a notion of flexible attribute-based
encryption. Flexible attribute-based encryption is a variant of ciphertext-policy
ABE, which allows one to loosen a decryption policy underlying a given ciphertext, if one knows some system-wide trapdoor information, without knowing its
underlying plaintext message. More precisely, suppose a given ciphertext c wasgenerated by encrypting a plaintext m under a decryption policy f . The ﬂexible
attribute-based encryption enables a “loosening operation” that, given Δf andsome system-wide trapdoor information γ, converts the ciphertext c into a morenonrestrictive version of ciphertext c which encrypts the same plaintext m under the loosened policy or(f, Δf ), without knowing the message m itself. Users
having attributes that satisfy (only) the appended policy Δf now can decrypt the
ciphertext c to know the message m. Here we note that the trapdoor information
γ is independent of individual policies or ciphertexts.
As one of applications of such ﬂexible attribute-based encryption, we can consider an integration of cloud storage services. Suppose two storage services A and
B are going to integrate into one storage service. Suppose, by policy mapping, thatencrypted ﬁles CfA under policy fA in service A now should be decrypted also byentities satisfying policy fB in service B. The authenticated operator in service
A with trapdoor γ can use the loosening operation against those CfA to get new
encrypted ﬁles Cor(fA ,fB ) that can be decrypted also by entities satisfying policy
fB in service B.
We will see that there is a subtlety over security concerning such loosening operations and then we will deﬁne two notions of security of ﬂexible attribute-based
encryption, indistinguishability under loosening operation and indistinguishability
under loosening key.
We also give a concrete construction of the ﬂexible attribute-based encryptionthat satisﬁes the indistinguishability under loosening operation and the indistinguishability under loosening key, based on the construction of ciphertext-policy
attribute-based encryption given by [4]. Its security proof is given in the genericbilinear group with random oracle model.
Related works. The concept of our ﬂexible attribute-based encryption is similar
to the attribute-based proxy re-encryption [7,9,8].

Flexible Attribute-Based Encryption

473

In the attribute-base proxy re-encryption, one can generate re-encryption key
rkf1 →f2 , and by using the key rkf1 →f2 , a ciphertext cf1 for policy f1 can be reencrypted into a ciphertext cf2 for policy f2 . To generate such re-encryption key
rkf1 →f2 , the secret key skf1 for policy f1 is required. On a while, in our ﬂexible
ABE, all ciphertexts can be “loosened” using the single (system-wide) trapdoor
information γ (which is independent of individual policies).

2

A Notion of Flexible Attribute-Based Encryption

A flexible attribute-based encryption scheme is a tuple of ﬁve PPT algorithms Setup,
Enc, Ext, Dec and Loosen.
Algorithm Setup generates a public parameter par, a master secret mk
and a trapdoor information lk for loosening, given a security parameter 1k :(par, mk, lk) ← Setup(1k ). Algorithm Enc encrypts a given message m to a ciphertext c under a given decryption policy represented as a Boolean formula f :(f, c) ← Enc(par, f, m). Algorithm Ext generates a secret key d for a given attribute set as, using the master secret mk: (as, d) ← Ext(par, mk, as). Algorithm
Dec decrypts a ciphertext (f, c) by using a secret key d for an attribute set as toobtain a resulting plaintext m. The plaintext m may be a special symbol ⊥ indicating a decryption error if something is wrong: m/⊥ ← Dec(par, (f, c), (as, d)).
By using the dedicated trapdoor information lk, algorithm Loosen loosens a decryption policy of a given ciphertext (f, c) so that more entities, that satisfy some
added policy Δf , can also decrypt the ciphertext c, resulting a new ciphertext(or(f, Δf ), c ): (or(f, Δf ), c ) ← Loosen(par, lk, (f, c), Δf ).
Correctness requirement. Under any valid setup information (par, mk, lk)(← Setup(1k )), if one encrypts any message m ∈ Message(k) under any decryption policy f ∈ Policy(k) to a ciphertext (f, c), then it must be decrypted
to the original plaintext m as Dec(par, (f, c), (as, d)) = m, if the secret key(as, d) (← Ext(par, mk, as)) is generated for some attribute set as that satisﬁes
the decryption policy f .
If the ciphertext (f, c) is loosened by a policy Δf to a new ciphertext←
Loosen(par, lk, (f, c), Δf ), then the(or(f, Δf ), c ) as (or(f, Δf ), c )resulting ciphertext c must be decrypted to the original plaintext m as
Dec(par, (or(f, Δf ), c ), (as , d )) = m, even if the attribute set as satisﬁes theappended policy Δf (or f ).
Regarding security under loosening operations. Before deﬁning security in a formal way, here we consider some aspects regarding security of such attribute-based
encryption that gives loosening operations to users.
First of all, the loosening operation should be performed by some entity withpossession of the trapdoor information lk without knowing the underlying message. This will be captured in the security condition named ‘indistinguishability
under loosening key’.
Another point is a more subtle one. Suppose an adversary A obtains a ciphertext c∗ of a plaintext m under a policy f = A or B or C. It is plausible that A

474

S. Arita

manages to construct a ciphertext c of the same plaintext m (without knowing
m itself) under a more restricted policy f  = A or B, based on the ciphertext c∗ .
Then, A can use the loosening operation on c to get another ciphertext c alsoof the same plaintext m but under a loosened policy f  = A or B or D and thenA could know the underlying plaintext m of the original ciphertext c∗ by using acorrupt key dD of the added attribute D against the ciphertext c .
That scenario means that a victim’s ciphertext c∗ can be corrupted even if∗
c itself has never been processed under loosening operations. (Oﬀ course, if theattribute-based encryption has CCA-security, that type of attack based on malleability can be avoided. However, at the same time we lose the loosening operations, too.)
We will require that loosening operations for c diﬀerent from c∗ should neveraﬀect the security of c∗ , in the security condition named ‘indistinguishability under loosening operation’.

3

Security of Flexible Attribute-Based Encryption

To deﬁne security of a ﬂexible attribute encryption scheme, we describe two games
using the framework of code-based games [3]. In the framework, a game GameAis executed with an adversary A as follows. First, Initialize executes, and its outputs are the inputs to A. Then A executes, its oracle queries being answered by
the corresponding procedures of GameA . When A terminates, its output becomesthe input to the Finalize procedure. The output of the latter is called the outputof the game.
3.1

Indistinguishability under Loosening Operation

Let FABE = (Setup, Enc, Ext, Dec, Loosen) be a ﬂexible attribute encryption scheme. Let A be an arbitrary PPT adversary against FABE. Our game
Gameind−lso
A,FABE (k) uses the following Initialize and Finalize procedures:procedure Initialize:$procedure Finalize (b ):b ← {0, 1}?
(par, mk, lk) ← Setup(1k ) return b = b.
return par.
The game uses procedures Extract, LR and Loosen to answer oracle queries
from A:
procedure Extract (as): procedure Loosen ((f, c), Δf ):assert(f ∗ (as) = false)
assert((f, c)!= (f ∗ , c∗ ))(as, d) ← Ext(par, mk, as) (f  , c ) ← Loosen(par, lk, (f, c), Δf )return (f  , c ).
return (as, d).
∗procedure LR (f , m0 , m1 ):assert(f ∗ (as) = false) for as’s submitted to Extract(f ∗ , c∗ ) ← Enc(par, f ∗ , mb )return (f ∗ , c∗ ).

Flexible Attribute-Based Encryption

475

In the above, “assert(f ∗ (as) = false)” means that one must check whether thecondition f ∗ (as) = false holds or not if f ∗ already deﬁned, and abort if it does
not hold, or else continue. Similar for “assert((f, c)!= (f ∗ , c∗ ))”.
Definition 1. A flexible attribute encryption scheme FABE is said to be indistinguishable under loosening operation (IND-LSO) if for an arbitrary PPT adversary
ind−lsoA its advantage Advind−lso
A,FABE (k) := |Pr[GameA,FABE (k) = 1] − 1/2| is a negligible
function in k.
3.2

Indistinguishability under Loosening Key

Our game Gameind−lsk
A,FABE (k) uses the following Initialize and Finalize procedures:procedure Initialize:$procedure Finalize (b ):b ← {0, 1}?
k(par, mk, lk) ← Setup(1 ) return b = b.
return (par, lk).
Note that Initialize returns a trapdoor information lk for loosening operation
as well as parameter par (and adversaries A will know lk as well as par). The
game uses procedure LR to answer oracle queries from A:
procedure LR (f ∗ , m0 , m1 ):(f ∗ , c∗ ) ← Enc(par, f ∗ , mb )return (f ∗ , c∗ ).
Definition 2. A flexible attribute encryption scheme FABE is said to be indistinguishable under loosening key (IND-LSK) if for an arbitrary PPT adversary A
ind−lsk
its advantage Advind−lsk
A,FABE (k) := |Pr[GameA,FABE (k) = 1] − 1/2| is a negligible
function in k.
Note that since A has now loosening key lk, A can trivially decrypt the challenge
ciphertext if A had access to Extract-oracle.

4

Concrete FABE Scheme

Definition 3. A function F : {0, 1}∗ → {0, 1}2N is said to be N -lineardependency resistant if for any n ≤ N any PPT algorithm A is not able to generate any n distinct strings x1 , . . . , xn with function values F (x1 ), . . . , F (xn ) thatare linearly dependent (as vectors over Z2 ) except with a negligible probability.

476

S. Arita

A hash function F : {0, 1}∗ → {0, 1}2N is N -linear-dependency resistant in the
random oracle model with respect to F .
We construct a concrete ﬂexible attribute encryption scheme based on the attribute encryption scheme of [4]. In the followings, Leaf(f ) denotes a number ofleaf nodes of a given binary formula f . (ρ, M ) ← LSS(p, f ) denotes a transformation to convert a Boolean formula f into a linear secret sharing scheme deﬁned
by a share-generating matrix M over prime p (with corresponding secret-restoring
coeﬃcients (ωi )i ) with an assignment function ρ from the rows of matrix M to theuniverse of attributes. For its details we refer to [11]. Predicate IsDH(g, g1 , g2 , g3 )means the tuple (g, g1 , g2 , g3 ) is a Diﬃe-Hellman tuple, i.e., g3 = g2a for a satisfying g1 = g a . For vectors
 a = (a1 , . . . , an ) and b = (b1 , . . . , bn ), their inner productis written as a · b = i=1,...,n ai bi .
Setup (1k , N (k)):(g, p, e) ← GenGrp(1k )Select F (= F1 · · · F2N ) : {0, 1}∗ → {0, 1}2N$α, β, γ1 , . . . , γ2N ← Zp
h = g β , w = e(g, g)α , u1 = g γ1 , . . . , u2N = g γ2NReturn par = (g, h, w, F, u1 , . . . , u2N ), mk = (β, g α ) and lk = γ := (γ1 , . . . , γ2N ).
F (S)F2N (S)/* (u1 , . . . , u2N ) defines a hash function H(S) = u1 1 · · · u2N*/
Enc (par, f, m):Assert n := Leaf(f ) < N(ρ, M ) ← LSS(p, f ) /* Let dimension of M be n × l */$s, r2 , . . . , rl ← Zp , si = Mi · (s, r2 , . . . , rl ) (i ∈ [1..n])c0 = mws , c1 = g s , c2 = hs , c3 = (g si )i∈[1..n] , c4 = (H(ρ(i))si )i∈[1..n] , c5 = H(f, c0 , . . . , c4 )sReturn (f, c = (c0 , . . . , c5 )).
Ext (f, mk, as):$$r ← Zp , ra ← Zp (a ∈ as)
d1 = g (α+r)/βd2 = (g r H(a)ra )a∈as , d3 = (g ra )a∈as
Return d = (as, d1 , d2 , d3 ).

Dec (par, (f, c), (as, d)):(ρ, M ) ← LSS(p, f )−1(as) and compute the constants {ωi }i∈I
I = ρ
κ = i∈I {e(c3,i , d2,ρ(i) )/e(c4,i , d3,ρ(i) )}ωi
Return κc0 /e(d1 , c2 ).

Loosen (par, lk, (f, c), Δf ):Loosen the policy f to f  = or(f, Δf )Assert n := Leaf(f  ) < N and IsDH(g, H(f, c0 , · · · , c4 ), c1 , c5 )(ρ, M ) ← LSS(p, f  ) /* Let dimension of M be n × l */$Let g s = c1 and r2 , . . . , rl ← Zp /* We don’t know the value of s */Compute g si = g Mi ·(s,r2 ,...,rl ) for i ∈ [1..n] and set c3 = (g si )i∈[1..n]/* The knowledge g s is enough to compute g si */ 
c4 = (g si (γ·F (ρ(i))) )i∈[1..n] , c5 = (c1 )γ·F (f ,c0 ,c1 ,c2 ,c3 ,c4 )Return c = (f  , c0 , c1 , c2 , c3 , c4 , c5 ).

We can prove the following theorems regarding security of the FABE scheme (theproofs are in the full version [1]).

Flexible Attribute-Based Encryption

477

Theorem 1. The FABE scheme with parameter N = N (k) is indistinguishable
under loosening operation in the generic bilinear group model, under the assumption that the function F is (N + 1)-linear-dependency resistant.
Theorem 2. The FABE scheme is indistinguishable under loosening key in thegeneric bilinear group model.

5Conclusion

We proposed a notion of ﬂexible attribute-based encryption, that allows one toloosen a decryption policy underlying a given ciphertext. We gave a concrete construction of such ﬂexible attribute-based encryption that is provably secure in thegeneric bilinear group model.

References
1. Arita, S.: Flexible Attribute-Based Encryption (2012),
http://lab.iisec.ac.jp/~ arita/pdf/fabe.pdf
2. Badenand, R., Benderand, A., Springand, N., Bhattacharjee, B., Starin, D.: Persona: An online social network with user deﬁned privacy. In: ACM SIGCOMM(2009)
3. Bellare, M., Rogaway, P.: The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs. In: Vaudenay, S. (ed.) EUROCRYPT
2006. LNCS, vol. 4004, pp. 409–426. Springer, Heidelberg (2006)
4. Bethencourt, J., Sahai, A., Waters, B.: Ciphertext-Policy Attribute-Based Encryption. In: SP 2007, pp. 321–334. IEEE Computer Society (2007)
5. Bobba, R., Fatemieh, O., Khan, F., Gunter, A.K.C.A., Khurana, H., Prabhakaran,
M.: Attribute-based messaging: Access control and conﬁdentiality. ACM Transactions on Information and System Security (TISSEC) 13(4)6. Goyal, V., Pandey, O., Sahai, A., Waters, B.: Attribute-based encryption for ﬁnegrained access control of encrypted data. In: ACM Conference on Computer andCommunications Security, pp. 89–98 (2006)
7. Guo, S., Zeng, Y., Wei, J., Xu, Q.: Attribute-based re-encryption scheme in the standard model. Wuhan University Journal of Natural Sciences 13(5), 621–625 (2008)
8. Ibraimi, L., Asim, M., Petkovic, M.: An Encryption Scheme for a Secure Policy Updating. In: SECRYPT 2010, pp. 399–408 (2010)
9. Liang, X., Cao, Z., Lin, H., Shao, J.: Attribute Based Proxy Re-encryption with
Delegating Capabilities. In: ASIACCS 2009, pp. 276–286 (2009)
10. Lewko, A., Okamoto, T., Sahai, A., Takashima, K., Waters, B.: Fully Secure Functional Encryption: Attribute-Based Encryption and (Hierarchical) Inner ProductEncryption. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 62–91.
Springer, Heidelberg (2010)
11. Lewko, A., Waters, B.: Decentralizing Attribute-Based Encryption. In: Paterson,
K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 568–588. Springer, Heidelberg(2011)

478

S. Arita

12. Okamoto, T., Takashima, K.: Fully Secure Functional Encryption with General Relations from the Decisional Linear Assumption. In: Rabin, T. (ed.) CRYPTO 2010.
LNCS, vol. 6223, pp. 191–208. Springer, Heidelberg (2010)
13. Sahai, A., Waters, B.: Fuzzy Identity-Based Encryption. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 457–473. Springer, Heidelberg (2005)
14. Traynor, P., Butler, K.R.B., Enck, W., McDaniel, P.: Realizing massive-scale conditional access systems through attribute-based cryptosystems. In: NDSS (2008)
15. Waters, B.: Ciphertext-Policy Attribute-Based Encryption: An Expressive, Eﬃcient, and Provably Secure Realization. In: Catalano, D., Fazio, N., Gennaro, R.,
Nicolosi, A. (eds.) PKC 2011. LNCS, vol. 6571, pp. 53–70. Springer, Heidelberg(2011)