A Bunch of Broken Schemes: A Simple yet

Powerful Linear Approach to Analyzing Security

of Attribute-Based Encryption

Marloes Venema1 and Greg Alpár1,2

1
Radboud University, Nijmegen, the Netherlands
2
Open University of the Netherlands
{[Link],[Link]}@[Link]

Abstract. We present a linear approach to analyzing security of attri-

bute-based encryption (ABE). We use this approach to algebraically
break eleven schemes: two single-authority and nine multi-authority attri-
bute-based encryption (MA-ABE) schemes. These latter attacks illus-
trate that mistakes are made in transforming single-authority schemes
into multi-authority ones. Our linear approach is not only useful in the
analysis of existing schemes, but can also be applied during the design
and verification of new schemes. As such, it can prevent the design of
insecure MA-ABE schemes in the future.

Keywords: attribute-based encryption · cryptanalysis · multi-authority

attribute-based encryption · attacks.

1 Introduction

Attribute-based encryption (ABE) [34] is important in the cryptographic en-

forcement of access control. Ciphertext-policy (CP) ABE [5] naturally imple-
ments a fine-grained access control mechanism that puts the data owner in
control, and is therefore often considered in applications involving e.g. cloud
environments [30,42,44,43,25,27] or medical settings [33,29,31]. These applica-
tions of ABE allow the storage of data to be outsourced to potentially untrusted
providers whilst ensuring that data owners can securely manage access to their
data. Many such works use the multi-authority (MA) variant [6], which employs
multiple authorities to generate and issue secret keys. These authorities can be
associated with different organizations, e.g. hospitals, insurance companies or
universities. This allows data owners, e.g. patients, to securely share their data
with other users from various domains, e.g. doctors, actuaries or medical re-
searchers. Because existing schemes may not sufficiently address the problems
that arise in these real-world applications, new schemes are needed. Unfortu-
nately, proving and verifying security of such schemes are difficult, and, perhaps
unsurprisingly, several schemes turn out to be vulnerable to attacks.
In this work, we focus on algebraic attacks. In particular, we establish a
framework for effectively analyzing schemes by exploiting their similar alge-
2 M. Venema, G. Alpár

braic structure. These schemes use symmetric pairings that map two prime-
order source groups to a target group. The secret keys and ciphertext elements
exist in the source groups, and decryption involves the pairing of the key and
ciphertext elements such that the blinding value—which exists in the target
group and masks the message—can be recovered. To simplify the analysis, one
can also consider the exponent spaces of the secret keys and ciphertexts. Then,
decryption can be described as a linear combination of products of key and ci-
phertext entries such that the exponent of the blinding value can be recovered.
This implies a more concise, intuitive and structured notation that also simpli-
fies the (manual) security analysis of multi-authority schemes, which should be
secure against corruption of authorities. To analyze the insecurity of schemes,
we examine whether the blinding value can be recovered for some ciphertext and
unauthorized secret keys. Concretely, we define different types of attacks involv-
ing the recovery of a master- or attribute-key, or the unauthorized decryption
of a ciphertext, all impacting the overall security of a scheme. Furthermore, we
describe a heuristic approach to finding such attacks. Using this, we have found
vulnerabilities in several existing schemes that aim to solve real-world problems,
rendering these at least partially insecure.
More generally, our goal is not necessarily to attack existing schemes, but
to propose a framework that simplifies the design of secure (multi-authority)
schemes. While the described approach is manual and non-exhaustive, it does
help ruling out algebraic insecurities at an early stage in the design. In the fu-
ture, our approach may be extended to be exhaustive and automated, such that
the security of every new scheme can be verified efficiently. To some extent, such
frameworks already exist for single-authority schemes [1,2], though our frame-
work also contributes by providing concrete attacks and a general approach.
Because of its importance in solving real-world problems, (MA-)ABE should
be simple to securely design. Our framework provides a powerful tool in this
endeavor.

1.1 Our contribution

Our contribution is twofold. First, we describe a linear approach to algebraic

security analysis of ABE based on the common structure of many schemes. We
describe three types of attacks, which model the implicit security requirements on
the keys and ciphertexts. They model whether the master-key can be recovered,
or whether users can collude and decrypt ciphertexts that they cannot individu-
ally decrypt. In the multi-authority setting, we also model the notion of corrup-
tion. Generally, the ability to perform any of the attacks proves the insecurity
of a scheme. Second, we use our approach to show that fifteen works describing
eleven different schemes are vulnerable to our attacks, consequently rendering
them (partially) insecure. Five of these are insecure in the single-authority secu-
rity model. The other six are insecure in the multi-authority security model, but
are possibly secure if all authorities are assumed to be trusted. Essentially, these
schemes provide a comparable level of security as single-authority schemes.
 A Simple yet Powerful Linear Approach to Analyzing Security of ABE 3

1.2 Technical details – a brief overview of the attacks

In CP-ABE, ciphertexts are associated with access policies, and secret keys are
associated with sets of attributes. A secret key is authorized to decrypt a cipher-
text if its access structure is satisfied by the associated set. These secret keys
are generated by a KGA from a master-key, which can be used to decrypt any
ciphertext. Users with keys for different sets of attributes should not be able to
collude in collectively decrypting a ciphertext that they are individually not able
to decrypt. Implicitly, the keys need to be secure in two ways. First, the master-
key needs to be sufficiently hidden in the secret keys. Second, combining the
secret keys of different users should not result in more decryption capabilities.
We propose three types of attacks, which all imply attacks on the security
model for ABE. This model considers chosen-plaintext attacks (CPA) and col-
lusion of users. Two of our attacks only consider the secret keys issued in the
first key query phase of the CPA-security model, while the third also considers
the challenge ciphertext. The attacks are informally defined as follows.

– Master-key attack (MK): The attacker can extract the KGA’s master-
key, which can be used to decrypt any ciphertext.
– Attribute-key attack (AK): The attacker can generate a secret key for a
set S 0 that is strictly larger than each set Si associated with a key.
– Decryption attack (D): The attacker can decrypt a ciphertext for which
no authorized key was generated.

In addition, we formulate the notions of complete and conditional decryption

attacks. These model the distinction between attacks that can be performed un-
conditionally, or only under conditions on the access structure and the collective
set of attributes possessed by the colluding users. Specifically, complete attacks
allow all ciphertexts to be decrypted by all unauthorized keys, while conditional
attacks only allow a ciphertext to be decrypted if the associated access structure
is satisfied by the collective set. Figure 1 illustrates the relationship between
the attacks, and how the attacks relate to the security model. We consider the
first key query phase and the challenge phase, which output the secret keys for
a polynomial number of sets of attributes, and a ciphertext associated with an
access structure such that all keys are unauthorized, respectively.
The security models in the multi-authority setting are similar, but include the
notion of corruption. The attacker is allowed to corrupt one or more authorities
in an attack, which should not yield sufficient power to enable an attack against
the honest authorities. Sometimes, schemes employ a central authority (CA)
in addition to employing multiple attribute authorities. This CA is assumed to
perform the algorithms as expected, though it can be assumed to be honest or
semi-honest. An honest CA is not allowed to collaborate with any other entities,
while a semi-honest CA can passively collaborate with other entities in an attack.
In this work, we show how to model the corruption of attribute authorities and
semi-honest CAs, and how the additional knowledge (e.g. the master secret keys)
gained from corrupting an authority can be included in the attacks.
4 M. Venema, G. Alpár

Fig. 1. The general attacks and how they relate to one another.
.. Challenger Attacker
.
SKS1 , ..., SKSn
Key query phase I

Master-key Attribute-key
attack attack

MK SKSS 0 :
S0 ⊇ n i=1 Si
CTA : ∀i ∈ {1, ..., n}
A 6|= Si
Challenge phase

Sn
A 6|= i=1 Si ?

Yes No

Complete Conditional
decryption attack decryption attack
..
.
m m

We make some observations about the security models for multi-authority

ABE. First, multi-authority ABE was initially designed [6,7,22] to provide se-
curity against corruption. This does not only protect honest authorities from
corrupt authorities, but it also increases security from the perspective of the en-
crypting users. Second, not allowing corruption in the security model provides a
comparable level of security to that of single-authority ABE. Third, some mod-
els are impractical. For instance, they might protect against corruption, but in
turn only protect against a bounded number of colluding users [26]. Fourth, in
some cases, the informal description of a scheme is ambiguous on whether it
provides security against corruption. For instance, schemes are compared with
other multi-authority schemes that provide security against corruption, while
the proposed scheme does not, though is not explicitly mentioned [31,27].
Table 1 summarizes the schemes we analyzed. We indicate on which scheme
it is based, which type of attack we found and whether it is complete, whether it
uses collusion or corruption, whether the attack explicitly contradicts the model
that the scheme is claimed to be secure in. We also list the conference or journal
in which the scheme was published and how many times the paper is cited3 .

3
According to Google Scholar. These measures were taken at 9 April 2020.
 A Simple yet Powerful Linear Approach to Analyzing Security of ABE 5

Table 1. Schemes for which we provide attacks.

Scheme Based on CD Att. Col. Cor. Con. Venue Cit.

ZH10 [47] CCS 101
- 7 AK 2 - X
ZHW13 [48] NC 106
NDCW15 [30] Wat11 [38] X D - - X ESORICS 38
YJ12 [42] - X MK - A X NC 141
YJR+13 [44] TIFS 452
- X D - - X
Multi-authority ABE

WJB17 [40] NC 24
JLWW13 [18] NC 169
BSW07 [5] 7 AK 2 - X
JLWW15 [19] TIFS 146
QLZ13 [32] - X MK - - X ICICS 37
YJ14 [43] - X D - A X NC 227
CM14 [9] - X D - A U NC 42
QLZH15 [33] Cha07 [6] - C - - X IJIS 105
LXXH16 [25] X NC 95
Wat11 [38] X MK - CA
MST17 [29] U AsiaCCS 17
PO17 [31] - X D - A U SACMAT 11
MGZ19 I [27] LW11 [22] X MK - CA U Inscrypt 1
CD = complete decryption attack, Att = attack, MK = master-key attack, AK =
attribute-key attack, D = decryption attack, C = correctness attack; Col = collusion,
Cor = corruption, Con = contradicts proposed security model, U = unclear,
NC = non-crypto venue/journal
For convenience, we refer to the key schemes by concatenating the first letter of each
author’s surname with the last two digits of the year of publication.

1.3 Related work

Prior to this work, several ABE schemes were shown to be insecure. Some
schemes were broken with respect to the same types of attacks as we introduce
in this work. Others were only broken with respect to additional functionality.
Table 2 summarizes each scheme, in which work it was broken, the proposed
attack on the scheme, and whether it was later fixed. Also, we provide the venue
and number of citations for these schemes. Notably, the schemes broken with
respect to additional functionality have been fixed, while the others have not.

2 Preliminaries

We provide the necessary preliminaries and notations. If an element is chosen

uniformly at random from some finite set S, we write x ∈R S. If an element
x is generated by running algorithm Alg, we write x ← Alg. We use boldfaced
variables for vectors x and matrices M, where x denotes a row vector and y|
denotes a column vector. Furthermore, xi denotes the i-th entry of x. If the
vector size is unknown, v ∈R S indicates that for each entry: vi ∈R S. Finally,
x(y1 , y2 , ...) denotes a vector, where the entries are polynomials over variables
6 M. Venema, G. Alpár

Table 2. The first three schemes were previously broken with respect to their additional
functionality, and the second three were broken with respect to our attacks.

Scheme Broken in Attacked functionality Fixed? Venue Cit.

LRZW09 [23] ISC 188
LHC+11 [24]
ZCL+13 [46] Private access policies [24] AsiaCCS 92
CDM15 [8]
XFZ+14 [41] NC 40
HXL15 [16]
YJR+13 [44] Revocation [40] TIFS 452
WJB17 [40]
JLWW15 [19] MZY16 [28] Distributed key generation [20] TIFS 146
Scheme Broken in CD Att. Col. Cor. Con. Fixed? Venue Cit.
HSMY12 [13] GZZ+13 [11] 7 D 2 - X 7 NC 172
HSM+14 [14] ESORICS 26
WZC15 [37] 7 D 2 - X 7
HSM+15 [15] TIFS 108
YCT15 [45] TYH19 [35] 7 AK 2 - X 7 NC 158
CD = complete decryption attack, Att = attack, AK = attribute-key attack, D =
decryption attack; Col = collusion, Cor = corruption, Con = contradicts proposed
security model, NC = non-crypto venue/journal

y1 , y2 , ..., with coefficients in some specified field. We refer to a polynomial with

only one term, or alternatively one term of the polynomial, as a monomial.

2.1 Access structures

In this work, we only consider monotone access structures4 . If a set S satisfies
access structure A, then we denote this as A |= S. We denote the i-th attribute
in the access structure as atti ∼ A.

2.2 Pairings
We define a pairing to be an efficiently computable map e on two groups G and
GT of prime order p, such that e : G × G → GT , with generator g ∈ G such
that for all a, b ∈ Zp , it holds that e(g a , g b ) = e(g, g)ab (bilinearity), and for
g a , g b 6= 1G , it holds that e(g a , g b ) 6= 1GT , where 1G0 denotes the unique identity
element of the associated group G0 (non-degeneracy).

2.3 Formal definition of (multi-authority) ciphertext-policy ABE

In this work, we focus primarily on ciphertext-policy attribute-based encryption.
Definition 1 (Ciphertext-policy ABE). A ciphertext-policy attribute-based
encryption (CP-ABE) scheme with some authorities A1 , ..., An (where n ∈ N)
Sn that each Ai manages universe Ui , users and a universe of attributes U =
such
i=1 Ui may consist of the following algorithms.
4
A formal definition of (monotone) access structures can be found in Appendix A.
 A Simple yet Powerful Linear Approach to Analyzing Security of ABE 7

– GlobalSetup(λ) → GP: This randomized algorithm takes as input the secu-

rity parameter λ, and outputs the public global system parameters GP (in-
dependent of any attributes).
– MKSetup(GP) → (GP, MK): This randomized algorithm takes as input the
global parameters GP, and outputs the (secret) master-key MK (independent
of any attributes) and updates the global parameters by adding the public key
associated with MK.
– AttSetup(att, MK, GP) → (MSKatt , MPKatt ): This randomized algorithm
takes as input an attribute, possibly the master-key and the global parameters,
and outputs a master secret MSKatt and public key MPKatt associated with
attribute att.
– UKeyGen(id, MK, GP) → SKid : This randomized algorithm takes as input
the identifier id, the master-key MK and the global parameters GP, and
outputs the secret key SKid associated with id.
– AttKeyGen(S, GP, MK, SKid , {MSKatt }att∈S ) → SKid,att : This randomized
algorithm takes as input an attribute att possessed by some user with iden-
tifier id, and the global parameters, the master-key MK, the secret key SKid
and master secret key MSKatt , and outputs a user-specific secret key SKid,att .
– Encrypt(m, A, GP, {MPKatt }att∼A ) → CTA : This randomized algorithm is
run by any encrypting user and takes as input a message m, access structure
A and the relevant public keys. It outputs the ciphertext CTA .
– Decrypt(SKid,S , CTA ) → m: This deterministic algorithm takes as input
a ciphertext CTA and secret key SKid,S = {SKid , SKid,att }att∈S associated
with an authorized set of attributes, i.e. A |= S, and outputs plaintext m.
Otherwise, it aborts.
– MKDecrypt(MK, CT) → m: This deterministic algorithm takes as input a
ciphertext CT and the master-key MK, and outputs plaintext m.
The scheme is called correct if decryption outputs the correct message for a secret
key associated with a set of attributes that satisfies the access structure.
In the single-authority setting (i.e. n = 1), the GlobalSetup, MKSetup and
AttSetup are described in one Setup, and the UKeyGen and AttKeyGen have to
be run in one KeyGen. In the multi-authority setting (i.e. n > 1), the GlobalSetup
is run either jointly or by some additional central authority (CA). MKSetup can
either be run distributively or independently by each Ai . AttSetup can be run
distributively or individually by Ai for the managed attributes Ui . UKeyGen is
run either distributively, individually for each Ai , or implicitly (e.g. by using a
hash). AttKeyGen is run by the Ai managing the set of attributes. MKDecrypt
is typically run jointly by an authorized set of authorities.

2.4 The security model and our attacks

We consider the notion of chosen-plaintext attack (CPA) security for ABE [5].
Definition 2 (Full CPA-security for CP-ABE [5]). Let C = (GlobalSetup,
..., MKDecrypt) be a CP-ABE scheme for authorities A1 , ..., An (n ∈ N) conform
Definition 1. We define the game between challenger and attacker as follows.
8 M. Venema, G. Alpár

– Initialization phase: The attacker corrupts a set I ( {1, ..., n} of au-

thorities, and sends I to the challenger. In the selective security game, the
attacker also commits to an access structure A.
– Setup phase: The challenger runs the GlobalSetup, MKSetup for all au-
thorities, and AttSetup for all attributes. It sends the global parameters
GP, master public keys {MPKatt }att∈U , andScorrupted master secret keys
{MSKatt }att∈UI to the attacker, where UI = i∈I Ui .
– Key query phase I: The attacker queries secret keys for sets of attributes
(id1 , S1 ), ..., (idn1 , Sn1 ). The challenger runs UKeyGen and AttKeyGen for
each (idj , Sj ) and sends SKid1 ,S1 ,...,SKidn1 ,Sn1 to the attacker.
– Challenge phase: The attacker generates two messages m0 and m1 of equal
length, together with an access structure A such that Sj ∪ UI does not satisfy
A for all j. The challenger flips a coin b ∈R {0, 1} and encrypts mb under
A. It sends the resulting challenge ciphertext CTA to the attacker.
– Key query phase II: The same as the first key query phase, with the
restriction that the queried sets Sn1 +1 , ..., Sn2 are such that A 6|= Sj ∪ UI .
– Decision phase: The attacker outputs a guess b0 for b.
The advantage of the attacker is defined as | Pr[b0 = b] − 21 |. A ciphertext-
policy attribute-based encryption scheme is fully secure if all polynomial-time
attackers have at most a negligible advantage in this security game.

We formally define our attacks in line with the chosen-plaintext attacks above
and Figure 1, such that CPA-security also implies security against these attacks.
Conversely, the ability to find such attacks implies insecurity in this model. While
this follows intuitively, we prove this in Appendix B.

Definition 3 (Master-key attacks (MKA)). We define the game between

challenger and attacker as follows. First, the initialization, setup and first key
query phases are run as in Definition 2. Then:
– Decision phase: The attacker outputs MK0 .
The attacker wins the game if for all messages m, decryption of ciphertext CT ←
Encrypt(m, ...) yields m0 ← MKDecrypt(MK0 , CT) such that m = m0 .

Definition 4 (Attribute-key attacks (AKA)). We define the game between

challenger and attacker as follows. First, the initialization, setup and first key
query phases are run as in Definition 2. Then:
0
– Decision phase: The Sn1attacker outputs SKS , where S ) Sj for all j ∈
0
0
{1, ..., n1 }, and S ⊇ j=1 Sj .
The attacker wins the game if SKid0 ,S 0 is a valid secret key for some arbitrary
identifier id0 and set S 0 .

Definition 5 (Decryption attacks (DA)). We define the game between chal-

lenger and attacker as follows. First, the initialization, setup, first key query and
challenge phases are run as in Definition 2. Then:
 A Simple yet Powerful Linear Approach to Analyzing Security of ABE 9

– Decision phase: The attacker outputs plaintext m0 .

The attacker
Sn1 wins the game if m0 = m. A decryption attack is conditional if
A |= j=1 Sj . Otherwise, it is complete.

3 Our methodology
Our methodology consists of a systemized approach to finding attacks on a
scheme. First, we review a common structure of many ABE schemes, which
implies a more concise notation for schemes to simplify cryptanalysis (Section
3.1). Then, we consider the effect of learning one or more values ‘in the exponent’,
e.g. by corrupting an authority, and how such knowledge can be modeled in any
attacks (Section 3.2). Using this, we formally define our attacks (Sections 3.3 and
3.4). Finally, we describe a heuristic approach that should simplify the effort of
finding attacks (Section 3.5).

3.1 The standard form implies a more concise notation

Many pairing-based ABE schemes have a similar form. This form is explicitly
defined and used in generic frameworks that simplify the design and analysis of
ABE [39,3]. Our goal is to simplify the cryptanalysis of ABE. We have adapted
the definition to match our own extended definition of CP-ABE (Definition 1).
Definition 6 (Standard form of CP-ABE). The standard form of a CP-
ABE scheme is defined as follows. Let A1 , ..., An be someSauthorities (where
n
n ∈ N) such that each Ai manages universe Ui , and U = i=1 Ui denotes the
collective universe of attributes.
– GlobalSetup(λ): This algorithm generates three groups G, H, GT of prime
order p with generators g ∈ G, h ∈ H, and chooses a pairing e : G × H → GT .
It may also select attribute-independent common variables b ∈R Zp .
It publishes the global parameters
GP = (p, G, H, GT , g, h, U, g gp(b) ),
where we refer to gp as the global parameter encoding.
– MKSetup(GP): This algorithm selects α ∈R Zp , updates GP ← GP∪{e(g, h)α },
publishes GP and keeps master-key MK = α secret.
– AttSetup(att, MK, GP): This algorithm selects integers batt ∈R Zp as secret
MSKatt = batt , and publishes
MPKatt = g mpka (batt ,b) ,
where we refer to mpka as the master attribute-key encoding.
– UKeyGen(id, MK, GP): This algorithm selects user-specific random integers
ru ∈R Zp and computes partial user-key

SKid = hku (id,α,ru ,b) ,

where we refer to ku 6= 0 as the user-key encoding.
10 M. Venema, G. Alpár

– AttKeyGen(S, GP, MK, SKid , {MSKatt }att∈S ): Parse SKid = (hid,1 , hid,2 , ...).
This algorithm selects user-specific random integers ra ∈R Zp and computes
a key SKid,S = {SKid,att }att∈S , such that for all att ∈ S
k
a,1 (att,ra ,b,batt ) k a,2 (att,ra ,b,batt )
SKid,att = (hid,1 , hid,2 , ...),
where we refer to ka,i as the user-specific attribute-key encodings.
– Encrypt(m, A, GP, {MPKatt }att∼A ): This algorithm selects ciphertext-specific
randoms s = (s, s1 , s2 , ...) ∈R Zp and outputs the ciphertext
CTA = (A, m · e(g, h)αs , g c(A,s,b) , g ca (A,s,b,{batt }att∼A ) ),
where we refer to c as the attribute-independent ciphertext encoding,
and ca the attribute-dependent ciphertext encoding. In particular, we
assume that each entry of ca uses a variable in batt for some att.
– Decrypt((SKid , SKid,S ), CTA ): Let SKid = hku (id,α,ru ,b) = (hid,1 , ...), SKid,S =
ka,1 (att,ra,i ,b,batt ) ka,2 (att,ra,i ,b,batt )
{(hid,1 , hid,2 ,...)}i∈{1,...,n},att∈S∩Ui , and CTA =
(A, C = m · e(g, h) , C = g αs c(A,s,b)
, Ca = g ca (A,s,b,{batt }att∼A ) ). Denote
SA = {att ∼ A | att ∈ S}. Define matrices E, Eatt,S,A for each att ∈ S
such that X
cEk|u + (c | ca )Eatt,S,A (ku | ka )| = αs.
att∈SA
In particular, we assume that Eatt,S,A only has non-zero entries if the asso-
ciated key or ciphertext encoding depends on att. Then the plaintext m can
be retrieved by recovering e(g, h)αs from C, Ca and SKid , SKid,S , and
m = C/e(g, h)αs .
– MKDecrypt(MK, CT): Let MK = α, MK0 = hmk(α,b) and CT = (C =
m · e(g, h)αs , C = g c(A,s,b) , Ca = g ca (A,s,b,{batt }att∼A ) ). Define vector e such
that cemk = αs. Then m can be retrieved by computing
Y
C/ e(C` , MK0 )e` ,
`

where C` and e` denote the `-th entry of C and e, respectively.

The scheme is correct if it holds that αs can be retrieved if the secret key asso-
ciated with S and ciphertext associated with A are such that A |= S.
Each encoding enc(var) denotes a vector of polynomials over variables var.
Depending on the scheme, MKSetup may be run distributively or by a CA (in
which case there is only one public key e(g, h)α associated with the master-keys),
or independently and individually (in which case there are multiple
P public keys
e(g, h)αi , and we replace the blinding value e(g, h)αs by e(g, h) i∈I αi s ).
Remark 1. Generators constructed by hash functions [5] are also included in this
definition, i.e. by assuming that H(att) = g batt for some implicit batt .
This standard form implies a concise notation. Only the encodings are dis-
tinct and therefore sufficient to consider for cryptanalysis. As such, we provide
our attacks in terms of encodings rather than group elements.
 A Simple yet Powerful Linear Approach to Analyzing Security of ABE 11

3.2 Modeling knowledge of exponents – extending Zp

The previously defined notation describes the relationship between the various
variables ‘in the exponent’ of the keys and ciphertexts. The values of most vari-
ables are unknown to the attacker. In multi-authority ABE, authorities provide
the inputs to some encodings, and therefore know some values, and most impor-
tantly, their (part of the) master-key. Hence, corruption of authorities results in
the knowledge of some values ‘in the exponent’. If the values provided by honest
authorities are not well-hidden, it might enable an attack on them.
We model the ‘knowledge of exponents’ in attacks by extending the space
from which the entries of E and Eatt,S,A are chosen: Zp (or some extension with
variables associated with S and A). In fact, the entries of these matrices may be
any fraction of polynomials over Zp and the known exponents. Let K be the set
of known exponents, then the extended field of rational fractions is defined as

Zp (K) = {ab−1 (mod p) | a, b ∈ Zp [K]},

where Zp [K] denotes the polynomial ring of variables K.

3.3 Formal definitions of the attacks in the concise notations

We formally define our attacks (Definitions 7–9) in the concise notation. For each
attack, K denotes the set of known variables. We use the following shorthand for
a key encoding for a user id with set S and for a ciphertext encoding for access
structure A:
kid,S := (gp(b), mpka (batt , b), ku (id, α, ru , b) | ka,1 (att, ra , b, batt ) | ...),
cA := (gp(b), mpka (batt , b), c(A, s, b) | ca (A, s, b, {batt }att∼A )).

We first define the master-key attacks. In a master-key attack, the attacker

has to retrieve the master-key m(α, b) such that any ciphertext can be decrypted
with MKDecrypt.

Definition 7 (Master-key attacks). A scheme is vulnerable to a master-

key attack if there exist (id1 , S1 ), ..., (idn1 , Sn1 ) and the associated keyP
encodings
kidi ,Si , then there exist ei ∈ Zp (K)`i , where `i = |kidi ,Si |, such that i ki e|i =
mk(α, b) ∈ Zp (α, b). Then, it holds that for all attribute-independent ciphertext
0
encodings c there exists e0 ∈ Z`p (with |c| = `0 ) such that mke0 c| = αs.

We formally define attribute-key attacks. In an attribute-key attack, the

attacker has to generate a secret key associated with a set S 0 that is strictly
larger than any of the sets Si associated with the issued keys.

Definition 8 (Attribute-key attacks). A scheme is vulnerable to an attribute-

key attack if there exist (id1 , S1 ), ..., (idn1 , Sn1 ) such that for the key encod-
ings kidi ,Si , it holds that kid0 ,S 0 (with user-specific randoms ru and ra con-
structed
Sn1 linearly 0from the other user-specific randoms) can be generated such
that i=1 Si ⊆ S and Si ( S 0 for all i ∈ {1, ..., n1 }.
12 M. Venema, G. Alpár

We formally define the complete and conditional decryption attacks. A de-

cryption attack takes as input a ciphertext and a polynomial number of unautho-
rized keys and outputs the plaintext. The attack is conditional if the collective set
of attributes satisfies the access structure associated with the ciphertext. Oth-
erwise it is complete, because it implies that any set of keys can be generated,
which can then decrypt any ciphertext.
Definition 9 (Complete/conditional decryption attacks). A scheme is
vulnerable to a decryption attack if there exist (id1 , S1 ), ..., (idn1 , Sn1 ) and A
such that A 6|= Si , associated ciphertext encoding cA and key encodings kidi ,Si ,
0
for which
P there exist Ei ∈ Zp (K)`i ×` , where `i = |kidi ,Si | and `0 = |cA |,Ssuch
that i kidi ,Si Ei c|A = αs. The attack is conditional if it holds that A |= i Si .
Otherwise, it is complete.
It readily follows that master-key and attribute-key attacks imply decryp-
tion
Sn attacks.0 Specifically, master-key attacks and attribute-key attacks for which
i=1 Si ( S holds imply complete decryption attacks.
Finally, we formally define attacks on the correctness of a scheme. That is, for
some schemes it holds that there exist a ciphertext and an authorized key such
that the ciphertext cannot be decrypted. In a sense, such attacks are orthogonal
to decryption attacks.
Definition 10 (Correctness attacks). A scheme is incorrect if there exist
id, S and A such that A |= S for which there exists no E ∈ Zp (K)`1 ×`2 , where
`1 = |kid,S | and `2 = |cA | such that kid,S Ec|A = αs.

3.4 Definitions of multi-authority-specific attacks

The multi-authority setting yields two additional difficulties in the design of
secure schemes. First, the corruption of authorities yields extra knowledge about
the exponent space. Second, the distributed structure of the master-key may
enable new attacks. Formally, we define attacks under corruption as follows.
Definition 11 (Attacks under corruption). A scheme is vulnerable to at-
tacks under corruption if an attacker can corrupt a subset I ( {1, ..., n} of au-
thorities A1 , ..., An (where n = poly(n)) and thus obtain knowledge of variables
K consisting of all variables and (partial) encodings generated by the corrupt
authorities, enabling an attack conform Definitions 7, 8 or 9.
Oftentimes, the master-key is generated distributively by the P KGAs, hence
the blinding value is of a distributed form, e.g. e(g, h)αs = e(g, h) i αi s . If each
partial blinding value e.g. e(g, h)αi s can be recovered independently of the user’s
randomness, then the scheme is vulnerable to a multi-authority-specific decryp-
tion attack. For instance, suppose the blinding value is defined as (α1 + α2 )s. If
one user can recover α1 s (but not α2 s) and another user can recover α2 s (but
not α1 s), then the scheme is vulnerable to a multi-authority-specific decryption
attack. They can collectively recover (α1 + α2 )s, while clearly, they cannot do
this individually.
 A Simple yet Powerful Linear Approach to Analyzing Security of ABE 13

Definition 12 (Multi-authority-specific (MAS) decryption attacks). A

scheme is vulnerable to a multi-authority-specific
P decryption attack if the blind-
ing value of the message is of the form i bvi (αi , s, b), where αi denotes the
master-key of authority Ai , and bvi are elements in GT . If there exist ciphertext
encoding cA and sets Si ⊆ Ui with key encodings kidi ,Si for which there exist
0
Ei ∈ Zp (K)`i ×` , where `i = |kidi ,Si | and `0 = |cA |, such that kidi ,Si Ei c|A = bvi .
Remark 2. A multi-authority-specific decryption attack is also a decryption at-
tack conform Definition 9. That is, the blinding value can be retrieved, even
though the individual sets are not authorized to decrypt the ciphertext. Con-
versely, such attacks do not exist in the single-authority setting, meaning that
they are strictly weaker than regular (single-authority) decryption attacks.
Remark 3. The attacks of Wang et al. [37] on the HSM+14 [14] scheme—and
by extension the HSM+15 [15] scheme—are examples of multi-authority specific
decryption attacks.

3.5 Our heuristic approach

We devise a targeted approach to finding attacks, which can be applied manually.
As the definitions in the previous section imply, finding an attack is equivalent
to finding a suitable linear combination—where the linear coefficients are the
entries of e or E—of all products of the key and ciphertext entries. While find-
ing such coefficients is relatively simple, we note that the inputs of the attacks
are variable. The number of colluding users and the number of attributes as-
sociated with the keys and ciphertexts are effectively unbounded. However, we
observe that it often suffices to consider a limited number of inputs, and that
for some attacks, only the user-key and attribute-independent ciphertext entries
need to be considered. Specifically, Table 3 describes these inputs in terms of
encodings, the sets of attributes, and the access policy. Depending on the max-
imum number of monomials consisting of common variables in any key entry,
the attacker might need multiple secret keys for the same set of attributes to
recover certain coefficients. For instance, suppose the attacker wants to retrieve
α from α + r1 batt1 + r10 b0att1 , where r1 and r10 are known, user-specific random
variables, and batt1 and b0att1 denote the common variables associated with at-
tribute att1 . Because of the three unknown, linearly independent monomials,
this can only be done if the attacker has three distinct keys for attribute att1 .
In general, the maximum number of keys with the same set of attributes can
be determined in this way, i.e. by counting the maximum number of linearly
independent monomials for each entry.
Similarly, the inputs to multi-authority specific attacks can be limited. First,
we consider the attacks under corruption. Corruption of any number of authori-
ties results in the additional knowledge of some otherwise hidden exponents, i.e.
the master keys and any random variables generated by these authorities. We
assume that it is sufficient to consider one corrupted and one honest authority
in the attacks. Further, we use the same descriptions of the inputs to the at-
tacks as in the single-authority setting, with the additional requirement that the
14 M. Venema, G. Alpár

Table 3. The inputs of the attacks, and which encodings are needed.

Secret keys Ciphertexts

Attack
UK AK S AI AD A
Master-key X 7 - 7 7 -
Attribute-key X X S1 = {att1 }, S2 = {att2 } 7 7 -
Complete decryption X 7 - X 7 -
Conditional decryption X X S1 = {att1 }, S2 = {att2 } X X A = att1 ∧ att2
UK, AK = user-, attribute-key; AI, AD = attribute-independent, -dependent

Table 4. The number of required honest authorities n and the attribute universes U1
and U2 managed by authorities A1 and A2 in the multi-authority setting.

Attack n U1 U2
Master-key 1 7 7
Attribute-key 1 {att1 , att2 } 7
Complete decryption 1 7 7
Conditional decryption 1 {att1 , att2 } 7
MAS-decryption 2 {att1 } {att2 }

input attributes are managed by the honest authority. Second, we consider multi-
authority specific decryption attacks. Corruption is not necessary in this setting,
so we assume that the authorities are honest. Additionally, we require at least
two honest authorities as input to finding any attack, so we let each authority
manage one attribute. Table 4 summarizes the additional inputs to the attacks
in Table 3. Finally, it may be possible that a semi-honest central authority (CA)
is part of the scheme, in which case we also consider whether corruption of this
CA enables an attack. A semi-honest CA is assumed to perform all algorithms
as required, but it is allowed to be corrupted/collude passively.
We describe a more targeted approach to finding an attack, i.e. the linear
coefficients e and E, given the input encodings. The approach to finding an attack
is linear, as we attempt to retrieve the desired output (conform Definitions 7, 8
and 9) by making linear combinations of products of encodings. For the master-
key and decryption P attacks, the goal is to retrieve master-key α, or blinding
value αs (or e.g. ( i αi )s in some multi-authority schemes). Typically, α occurs
only in one entry of the keys, while s occurs only in one entry of the ciphertext.
Instead of blindly trying all combinations of the key entries with the ciphertext,
we formulate a more targeted approach. First, consider the monomials to be
canceled, and then which combinations of the key and ciphertext entries can
make these monomials. In canceling the previous monomials, it might be the
case that new monomials are added, meaning that these in turn also need to
be canceled. This process repeats until all monomials are canceled, and α or αs
remains—unless such attack cannot be found. For conciseness, we only provide
the non-zero coefficients in an attack.
 A Simple yet Powerful Linear Approach to Analyzing Security of ABE 15

4 Detailed examples using the approach

Using examples, we illustrate the way in which our heuristic approach can be
applied. In particular, we give several examples of attacks with or without cor-
ruption, correctness attacks and a multi-authority specific decryption attack.

4.1 Example without corruption: the YJR+13 [44] scheme

The YJR+13 [44] scheme, also known as DAC-MACS, is a multi-authority
scheme that supports the revocation of keys. This revocation functionality was
already broken in [16,40], but a fix for its revocation functionality was proposed
in the latter [40]. We show that the basic scheme—which is also the basic scheme
in the ‘fixed version’ [40]—is vulnerable to a complete decryption attack. The
scheme consists of the following encodings, which are sufficient for an attack.
– Type of attack: Complete decryption attack;
– Global parameters: gp = (gp1 , gp2 , ...) = (b, 1/b0 , ...);
– User-key: ku (α, r, b) = (α/x1 + x2 b + rb/b0 , rb0 /x1 , rb);
– Attribute-independent ciphertext: c(s, b) = (s, s/b0 );
– Known exponents: K = {x1 , x2 } (by definition);
The exponents x1 , x2 are known to any decrypting user to enable decryp-
tion. We show that knowing these exponents also enables an attack. That is,
any decrypting user is trivially able to decrypt any ciphertext, without even
considering the attribute-keys. First, we show that it is not possible to retrieve
the master-key. We sample a user-key (k1 , k2 , k3 ) ← ku (α, r, b), and observe that
master-key α only occurs in k1 = α/x1 + x2 b + rb/b0 . We can cancel x2 b, because
x2 is known and gp1 = b is a global parameter. Unfortunately, we cannot cancel
rb/b0 , it can only be retrieved by combining k1 and gp2 . Second, using these
observations, we show that it is possible to perform a decryption attack. We also
sample (c1 , c2 ) ← c(s, b). To retrieve αs, we start by pairing k1 with c1 :
Blinding value
to cancel
z }| {
x1 k1 c1 = αs + x1 x2 sb + x1 rsb/b0

x1 x2 gp1 c1
x 1 k 3 c2

Hence, we use these observations to formulate the attack as follows:

 
x1 0 00  
 0 c1
0 0 0 

  c2 
 
αs = (k1 , k2 , k3 , gp1 , gp2 )  0 −x 1 0 0 
 gp 1

−x1 x2 0 0 0
| {z }
ku gp2
0 0 0 0 | {z }
| {z } c
E
= x1 k1 c1 − x1 k3 c2 − x1 x2 gp1 c1 .
16 M. Venema, G. Alpár

Note that most of the entries of E are zero, so for brevity, we only write down
the non-zero entries of E below. t
u

4.2 Example without corruption: the JLWW13 [18] scheme

The JLWW13 [18] and JLWW15 [19] schemes, also known as AnonyControl,
have the same key generation. Note that the JLWW15 [19] scheme is different
from JLWW13 in the encryption algorithm. It is incorrect, because a value of a
single user-specific secret key is used in the encryption algorithm. We also show
that both schemes are vulnerable to a conditional attribute-key attack under
collusion of two users. The encodings of the global parameters, secret keys (both
the user-key and attribute-key parts) are defined as follows.

– Type of attack: Conditional attribute-key attack, collusion of two users;

– Global parameters: gp = (b, b0 ), mpka (atti ) = batti ;
– Secret keys: ku (α, r, b) = (α + r), ka (atti , r, ri , b) = (ri batti + r, ri );

We show that the recurrence of r as a monomial in the user-key and attribute-

key encoding enables an attack. While it is relatively simple to show that this
cannot be exploited in a single-user setting, we show that sampling two keys
for two different sets of attributes S1 = {att1 } and S2 = {att2 } (as in Table 3)
enables the generation of a third key for both attributes, i.e. S3 = {att1 , att2 }.
For S1 = {att1 }, we sample k ← ku (α, r, b), and (k1 , k2 ) ← ka (att1 , r, r1 , b).
For S2 = {att2 }, we sample k 0 ← ku (α, r0 , b), and (k10 , k20 ) ← ka (att2 , r0 , r2 , b).
The goal is to generate a key for set S3 = {att1 , att2 }. We aim to generate
attribute-keys for the user-key associated with S1 , i.e. k, which links the keys
together with r. Of course, the attribute-key for attribute att1 can also be readily
used for S3 . We generate the attribute-key for att2 from the other key parts:
ka (att2 , r, r2 , b) = (k10 + k − k 0 , k20 ). t
u

4.3 Example with corruption: the YJ14 [43] scheme

The YJ14 [43] scheme is somewhat similar to the YJR+13 [44] scheme in the
secret keys. However, the decrypting user knows fewer exponents: instead of
sharing x2 (in the YJR+13 scheme) with the user, it is shared with the attribute
authorities. Hence, corruption of one authority leads to the knowledge of x2 , and
thus enables an attack. We define the encodings and attack as follows.

– Type of attack: Complete decryption attack, under corruption of one A;

– Global parameters: gp = (b, b0 );
– Master secret key Ai : mski = (αi , x);
– User-key: ku (αi , r, b) = (αi + xb + rb0 , r);
– Attribute-independent
P ciphertext: c(s, b) = (s, sb0 , ...);
– Blinding value: ( i αi )s;
– Known variables: K = {x} (by corrupting A0 );
– The goal: Recover αi s from (k1,i , k2,i ) ← ku (αi , r, b), (c1 , c2 ) ← c(s, b);
– The attack: αi s = k1,i c1 − k2,i c2 − xmpk1 c1 . t
u
 A Simple yet Powerful Linear Approach to Analyzing Security of ABE 17

4.4 Example of correctness attack: the QLZH15 [33] scheme

The QLZH15 [33] scheme is essentially the CP-ABE variant of the CC09 [7]
scheme (or the multi-authority variant of [17]). We show that it is incorrect,
and that it cannot be fixed without making it vulnerable to another attack. To
ensure ‘correctness’, we assume that each authority has a dummy attribute for
which every user receives a secret key.

Remark 4. For this scheme, it is important to know how we implement the access
structures A, e.g. A = att1 ∧ att2 . In particular, we mathematically implement a
conjunction by computing two randoms s1 , s2 ∈R Zp associated with attributes
att1 and att2 and set s ← s1 + s2 (mod p) as the shared secret.

– Type of attack: Incorrect;

– Global parameters: gp = (b);
– Master key pair of Ai : mski (att)
P = (batt ), mpki (att) = (batt );
– Secret key: ku (α, r, b) = (α + ( ri )b), ka (atti , ri , b) = (ri b/batti );
– Ciphertext: A = att1 ∧ att2 , c(A, s1 , s2 , b) = (s1 + s2 , s1 batt1 , s2 batt2 );
– Input (keys): For S = {att1 , att2 } such that att1 ∈ U1 , att2 ∈ U2 , authority
A1 and A2 securely and jointly generate k ← ku (α, r1 , r2 , b), where r1 , r2 ∈R
Zp are generated by A1 and A2 , respectively, and ki ← ka (atti , ri , b);
– Input (ciphertext): A = att1 ∧ att2 , (c1 , c2 , c3 ) ← c(A, s1 , s2 , b);
– Blinding value: α(s1 + s2 );
– The goal: Showing that, even though A |= S, α(s1 +s2 ) cannot be recovered;
– The attack: A |= S, so k should be able to decrypt c, yet:

kc1 − k1 c2 − k2 c3 = α(s1 + s2 ) + (r1 + r2 )(s1 + s2 )b − r1 s1 b − r2 s2 b

= α(s1 + s2 ) + r1 s2 b + r2 s1 b 6= α(s1 + s2 ).

We observe that the issue is that both the secret key and the ciphertext
provide a different random for each attribute. To allow cancellation of (r1 +
r2 )(s1 + s2 )b, either we require that the same random s = s1 + s2 on each
attribute-dependent ciphertext element is used, or the same random r = r1 + r2
on each attribute-dependent secret key element is used. The next two subsections
will discuss these modifications.

4.5 Example of a MAS-decryption attack: modified QLZH15 I

We modify the QLZH15 scheme such that it uses the same V random s for all
ciphertext parts. That is, we define each access policy as A = Ai Ai such that
Ai consists only of attributes managed by Ai . We show that this scheme is
vulnerable to a multi-authority specific decryption attack.

– Type of attack: Multi-authority specific decryption attack;

– Global parameters: gp = (b);
– Master key pair of Ai : mski =P (batt ), mpki = (batt );
– Secret key: ku (α, r, b) = (α + ( ri )b), ka (atti , ri , b) = (ri b/batti );
18 M. Venema, G. Alpár

– Ciphertext: A = att1 ∧ att2 , c(A, s, b) = (s, sbatt1 , sbatt2 );

– Input (keys): For S1 = {att1 }, and S2 = {att2 } such that att1 ∈ U1 ,
att2 ∈ U2 . For S1 , authority A1 and A2 securely and jointly generate k ←
ku (α, r, b), where r ∈R Zp is jointly generated by A1 and A2 , and k1 ←
ka (att1 , r, b). They also generate k 0 ← ku (α, r0 , b) and k20 ← ka (att2 , r0 , b);
– Input (ciphertext): A = att1 ∧ att2 , (c1 , c2 , c3 ) ← c(A, s, b);
– Blinding value: αs;
– The goal: Recover αs even though neither A 6|= S1 and A 6|= S2 ;
– The attack:
αs = 21 (kc1 − k1 c2 ) + 12 (k 0 c1 − k20 c3 )
= 1
+ rsb − rsb) + 12 (αs + r0 sb − r0 sb).
2 (αs

t
u

4.6 Example of other issues: modified QLZH15 II and III

We present two modifications of the QLZH15 scheme such that it uses the same
random r for all keys (like in [17] and [38], respectively). We show that the first
modification has vulnerabilities under corruption. For the second modification,
we use Chow’s [10] multi-authority version of Wat11 [38], which uses his gen-
eralization of the Chase-Chow [7] approach. However, we point out that there
might be some other vulnerabilities that may be exploitable.

Modification II: Naively, we modify QLZH15 such that it uses the same random
r for all key elements. We show that this proposed modification cannot be secure
against corruption, regardless of how the key generation is implemented.

– Type of attack: Complete master-key attack under corruption;

– Global parameters: gp = (b);
– Master key pair of Ai : mski = (batt )att∈Ui , mpki = (batt )att∈Ui ;
– Secret key: ku (α, r, b) = (α + rb), ka (att, r, b) = (rb/batt );
– Known variables: K = {batt1 } (by corrupting A1 );
– The goal: Recover α from k ← ku (α, r, b), k1 ← ka (att1 , r, b);
– The attack: α = k − batt1 k1 . t
u

Modification III: This is the multi-authority version of the Wat11 [38] scheme as
presented by Chow [10]. In particular, the key generation is run in two rounds:
the first round involves the user-key and the second round the attribute-keys.
– Type of attack: Exploit of two-phase key generation;
– Global parameters: gp = (b);
– Master key pair of Ai : mski = (batt )att∈Ui , mpki = (batt )att∈Ui ;
– Secret key round I: ku (α, r, b) = (α + rb, r);
– Secret key round II: ka (att, r, b) = (rbatt ) (generated from r);
– Ciphertext: A = att1 ∧ att2 , c(s1 , s2 , b) = (s1 + s2 ), ca (atti , si , s0i , b) =
(si b + s0i batti , s0i );
 A Simple yet Powerful Linear Approach to Analyzing Security of ABE 19

– Blinding value: αs;

– Input: For S1 = {att1 }, we run the key generation as defined: (k1 , k2 ) ←
ku (α, r, b), k3 ← ka (att1 , r, b). Define A = att1 ∧ att2 ;
– The goal: Recover α(s1 + s2 ) from (k1 , k2 , k3 ), c ← c(A, s1 , s2 , b), (ci , c0i ) ←
ca (atti , si , s0i , b) and S2 = {att2 };
– The attack: For S2 , we initiate the first round of the key generation:
(k10 , k20 ) ← ku (α, r0 , b). However, for the second round, we give as input
c02 instead of k20 . So k30 ← ka (att2 , s02 , b) = s02 batt2 . Then

α(s1 + s2 ) = k1 c − k2 c1 + k3 c01 − c2 + k30

= α(s1 + s2 ) + r(s1 + s2 )b − rs1 b − rs01 batt1 + rs01 batt1
−s2 b − s02 batt2 + s02 batt2 .
t
u
This attack can be averted by ensuring that the second round of the key
generation only allows actual outputs of the first round as input. For instance,
these outputs can be signed by all authorities, such that the second round can
only be instantiated if the given input verifies correctly. Furthermore, r needs
to be generated such that none of the authorities can actively cheat (e.g. by
ensuring that r is s0i like in the attack). Hence, this scheme is considerably more
difficult to secure than schemes with a one-round key generation such as [22].

5 Attacks on several schemes

We present attacks on several existing schemes (some of which were already
shown in Section 4). For each scheme, we describe the secret keys, and possibly
the global parameters and master keys, the ciphertext, and the form of the
blinding value in the concise notation introduced in Section 3.1. Furthermore, we
show whether collusion between users and corruption of any entities are required
for the attack. Such corruption results in extra knowledge of exponents, so Zp
is extended with the known variables conform Section 3.2.

5.1 Single-authority ABE

The ZH10 [47] and ZHW13 [48] schemes: In these schemes, three generators are
defined for each attribute att, indicating the presence (att), or absence (¬att)
of an attribute, and a dummy value of the attribute ∗att. For each user, the
secret key consists of a part associated with the positive or negative attribute
(depending on whether att is in the user’s possession) and the dummy value.

– Type of attack: Conditional attribute-key attack, collusion of two users;

– Global parameters: gp = (b), mpka (atti ) = (batti , b¬atti , b∗atti );
– Secret
P keys: Define
P att = att if att ∈ S and otherwise att = ¬att,
ku ( ri , b) = (( atti ∈U ri )b), and ka (atti , ri , b) = (ri b + bbatti , ri b + bb∗atti );
– Input: S1 = {att1 , ¬att2 }, ku ← ku (r1 +r2 , b), (k1,i , k2,i ) ← ka,1 (atti , ri , b),
S2 = {¬att1 , att2 }, with ku0 ← ku (r10 + r20 , b), (k1,i
0 0
, k2,i ) ← ka (atti , ri0 , b);
20 M. Venema, G. Alpár

– The goal: Generate a key for S3 = {att1 , att2 };

– The attack: ku (r10 + r20 , b) = ku0 , ka (att1 , r10 , b) = (k1,1 + k2,1
0 0
− k2,1 , k2,1 ),
0 0 0
and ka (att2 , r2 , b) = (k1,2 , k2,2 ). t
u

The NDCW15 [30] scheme: This scheme implements a white-box tracing scheme
such that the KGA can trace the secret keys of misbehaving users to the identity.
To this end, some of the exponents (i.e. x1 , x2 , x3 below) are known to the user.
Note that this scheme is given in a composite-order setting, despite the fact that
our framework is defined in the prime-order setting. However, the attack also
readily extends to the composite-order setting. Furthermore, it should be noted
that the keys as considered below correspond with those given in the second
step of the key generation in [30]. We have also removed all unnecessary global
parameters and ciphertext elements.

– Type of attack: Complete decryption attack;

– Global parameters: gp = (b1 , b2 );
– α
User-key: ku (α, b) = ( b1 +x 3
+ x2 b1 b+x
2
3
, x1 , x1 b1 );
– Attribute-independent ciphertext: c(s, b) = (s, sb1 , sb2 );
– Known variables: K = {x1 , x2 , x3 } (by definition);
– The goal: Recover αs from (k1 , k2 , k3 ) ← ku (α, b), (c1 , c2 , c3 ) ← c(s, b);
– The attack: αs = x3 k1 c1 + k1 c2 − x2 c3 . t
u

5.2 Multi-authority ABE

The YJ12 [42] scheme: This scheme employs a certificate authority (CA), which
is assumed to be fully trusted, and (corruptable) attribute authorities (Ai ),
which are responsible for the generation of the secret keys. The CA generates
user-specific random r, meaning that each authority Ai needs to know the master
secret key b/b0 in order to compute its user-key element. For the definition of the
key encodings, it is important to know that we assume that the master public
0
keys are generated as H(att)αi rather than g αi H (att) , as proposed in [42]. The
latter trivially enables complete attribute-key attacks if H0 is public, while the
former ensures that H(att)αi = g αi batt such that batt is unknown to everyone
and therefore protects against these attacks.

– Type of attack: Complete master-key attack, corruption of one A;

– Global parameters: gp = (b0 , 1/b0 );
– Master secret key Ai : mski = (αi , b/b0 );
– User-key: k(αi , r, b) = (r, rb/b0 + αi /b0 );
– Attribute-independent ciphertext: c(s, b) = (sb0 );
Blinding value: ( i αi )s, so mk(αi , b) = αi /b0 ;
P
–
– Known exponents: K = {α0 , b/b0 } (by corrupting A0 );
– The goal: Recover mk(αi , b) from (k1,i , k2,i ) ← k(αi , r, b);
– The attack: mk(αi , b) = k2,i − b/b0 k1,i . t
u
 A Simple yet Powerful Linear Approach to Analyzing Security of ABE 21

Note that this scheme cannot easily be fixed. Even if it is assumed that r
and b/b0 cannot be retrieved via corruption of one authority A0 , the fact that
each user-key encoding uses the same r and b/b0 ensures that any A0 can use its
knowledge of αi to recover rb/b0 . Therefore, collusion with a user leads to the
recovery of αj /b0 of each other authority that issued a key to this user.

The YJR+13 [44] and WJB17 [40] schemes: A more detailed description of this
scheme and our attack can be found in Section 4.1.

– Type of attack: Complete decryption attack;

– Global parameters: gp = (gp1 , gp2 , ...) = (b, 1/b0 , ...);
– User-key: ku (α, r, b) = (α/x1 + x2 b + rb/b0 , rb0 /x1 , rb);
– Attribute-independent ciphertext: c(s, b) = (s, s/b0 );
– Known exponents: K = {x1 , x2 } (by definition);
– The goal: Recover αs from (k1 , k2 , k3 ) ← ku (α, r, b), (c1 , c2 ) ← c(s, b);
– The attack: αs = x1 k1 c1 − x1 x2 gp1 c1 − x1 k3 c2 . t
u

The YJ14 [43] scheme (which we discuss later) was proposed as a ‘more
secure’ version of this scheme. In this scheme, x2 is removed from the secret key
of the user, and instead shared with each attribute authority Ai .

The JLWW13 [18] and JLWW15 [19] schemes: JLWW15 [19] is different from
JLWW13 in the encryption algorithm. It is incorrect, because a value of a single
user-specific secret key is used in the encryption algorithm. More details on this
attack can be found in Section 4.2.

– Type of attack: Conditional attribute-key attack, collusion of two users;

– Master attribute-key: mpka (atti ) = batti ;
– Secret keys: ku (α, r, b) = (α + r), ka (atti , r, ri , b) = (ri batti + r, ri );
– Input: S1 = {att1 }, k ← ku (α, r, b), (k1 , k2 ) ← ka (att1 , r, r1 , b),
S2 = {att2 }, k 0 ← ku (α, r0 , b), (k10 , k20 ) ← ka (att2 , r0 , r2 , b);
– The goal: Generate a key for S3 = {att1 , att2 };
– The attack: ku (α, r, b) = k, ka (att1 , r, r1 , b) = (k1 , k2 ), ka (att2 , r, r2 , b) =
(k10 + k − k 0 , k20 ). t
u

This scheme was derived from the BSW07 [5] scheme, however, the user-key
part of the secret key is defined as (α + r)/b, and the ciphertext also includes
sb. While the JLWW15 [19] seems to address this issue, it does this by including
a user-specific b, meaning that a ciphertext can only be decrypted by one user.
Moreover, encryption can only be performed by a user that knows this specific
value. Because the generation of α and r are distributed, the generation of any
‘fixed’ version that replaces α + r by (α + r)/b needs to be distributed as well. It
is unclear if this can be done (in any way that preserves the rest of the scheme).
22 M. Venema, G. Alpár

The QLZ13 [32] scheme: This scheme addresses real-world privacy concerns
involving the authorities and other users. In particular, it implements hidden
access structures, and supports a blind key generation. However, we show that
the secret keys trivially leak the master-key of all authorities. Note that we only
list those parts of the user-key that are relevant to the attack.

– Type of attack: Complete master-key attack;

– Global parameters: gp = (b, b1 , b0 , ...);
b1 0 0 1
– User-key: ku (α, r, b) = (α + rb + x+b 0 , rb − r b1 , (r + x+b0 )b1 );
– Known variables: K = {x} (by definition);
– The goal: Recover α from (k1 , k2 , k3 ) ← ku (α, r, b);
– The attack: α = k1 − k2 + k3 . t
u

The YJ14 [43] scheme: Details about this attack can be found in Section 4.3.

– Type of attack: Complete decryption attack, under corruption of one A;

– Global parameters: gp = (b, b0 );
– Master secret key Ai : mski = (αi , x);
– User-key: ku (αi , r, b) = (αi + xb + rb0 , r);
– Attribute-independent
P ciphertext: c(s, b) = (s, sb0 , ...);
– Blinding value: ( i αi )s;
– Known variables: K = {x} (by corrupting A0 );
– The goal: Recover αi s from (k1,i , k2,i ) ← ku (αi , r, b), (c1 , c2 ) ← c(s, b);
– The attack: αi s = k1,i c1 − k2,i c2 − xmpk1 c1 . t
u

The CM14 [9] scheme: This scheme is a multi-authority version of the Wat11
[38] scheme.

– Type of attack: Complete decryption attack, under corruption of one A;

– Master key pair of Ai : mpki = (bi ), mski = (bi );
– User-key: ku (αi , r, b) = ( αib+r
i
, r);
– Attribute-independent
P ciphertext: c(s, b) = (sbi );
– Blinding value: ( i αi )s;
– Known variables: K = {b1 } (by corrupting A1 );
– The goal: Recover αi s from (k1,i , k2,i ) ← ku (αi , r, b), c1 ← c(s, b);
– The attack: αi s = k1,i c1 − 1/b1 k2,i c1 such that i 6= 1. t
u

The issue in this scheme is that s (which is part of the blinding value of the
message) can be recovered by every authority associated with the access policy.
It is unclear if the scheme can be fixed without creating other issues e.g. with
security or the revocation functionality.

The QLZH15 [33] scheme: Details of this attack can be found in Section 4.4.

– Type of attack: Incorrect;

item Global parameters: gp = (b);
– Master key pair of Ai : mski (att) = (batt ), mpki (att) = (batt );
 A Simple yet Powerful Linear Approach to Analyzing Security of ABE 23

P
– Secret key: ku (α, r, b) = (α + ( ri )b), ka (atti , ri , b) = (ri b/batti );
– Input: For S = {att1 , att2 } such that att1 ∈ U1 , att2 ∈ U2 , authority A1
and A2 securely and jointly generate k ← ku (α, r1 , r2 , b), where r1 , r2 ∈R Zp
are generated by A1 and A2 , respectively, and ki ← ka (atti , ri , b);
– Ciphertext: A = att1 ∧ att2 , cA (s1 , s2 , b) = (s1 + s2 , s1 batt1 , s2 batt2 );
– Blinding value: α(s1 + s2 );
– The goal: Showing that, even though A |= S, α(s1 +s2 ) cannot be recovered;
– Incorrectness:
kc1 − k1 c2 − k2 c3 = α(s1 + s2 ) + (r1 + r2 )(s1 + s2 )b − r1 s1 b − r2 s2 b
= α(s1 + s2 ) + r1 s2 b + r2 s1 b 6= α(s1 + s2 ).

t
u

The LXXH16 [25] and MST17 [29] schemes: These schemes are similar. The
LXXH16 scheme employs a semi-honest (i.e. corruptable) certificate authority
CA to run the global setup. In the MST17 scheme, it is unclear which entity
runs it and therefore generates the b below.

– Type of attack: Complete master-key attack, under corruption of CA;

– Global parameters: gp = (b);
– User-key: ku (α, r, b) = (α + rb, r);
– Known variables: K = {b} (by corrupting CA, and thus the global setup);
– The goal: Recover α from (k1 , k2 ) ← ku (α, r, b);
– The attack: α = k1 − bk2 . t
u
– Note: This scheme can be fixed by distributing the generation of b.

The PO17 [31] scheme: This scheme was proposed to address some issues of the
Cha07 [6] scheme. In particular, the Cha07 scheme requires that a user receives
a key from each authority. However, unlike Cha07, the PO17 scheme does not
protect against corruption, so in terms of security, it is closer to any single-
authority scheme. It is unclear to us why this scheme uses different master secret
keys for each authority if they are assumed to behave correctly and honestly.
That is, employing a single-authority scheme, and sharing the master secret
keys with all authorities, seems more straightforward, and provides even more
redundancy than the proposed solution. In addition, the single-authority variant
(e.g. [17]) is generally more efficient.

– Type of attack: Complete decryption attack under corruption of one A;

– Master key pair of Ai : mpki = (bi ), mski = (bi );
– User-key: ku (αi , r, b) = ( αib−r
i
, r);
– Attribute-independent
P ciphertext: c(s, b) = (sbi );
– Blinding value: ( i αi )s;
– Known variables: b1 (by corrupting A1 );
– The goal: Recover αi s from (k1,i , k2,i ) ← ku (αi , r, b), c1 ← c(s, b);
– The attack: αi s = k1,i c1 + 1/b1 k2,i c1 . t
u
24 M. Venema, G. Alpár

Table 5. Table of the analyzed schemes, and the consequences of our attacks.

Scheme Problem CPA-security

ZH10 [47], ZHW13 [48] Recurring monomials 7
NDCW15 [30] Known-exponent exploits 7
YJ12 [42] Known-exponent exploits 7A
YJR+13 [44], WJB17 [40] Known-exponent exploits 7
JLWW13 [18], JLWW15 [19] Recurring monomials 7
MA-ABE

QLZ13 [32] Recurring monomials 7

YJ14 [43] Known-exponent exploits 7A
CM14 [9] Known-exponent exploits 7A
QLZH15 [33] Incorrect U
LXXH16 [25], MST17 [29] Known-exponent exploits 7CA
PO17 [31] Known-exponent exploits 7A
MGZ19 I [27] Known-exponent exploits 7CA
7A , 7CA = none under corruption of A, CA; U = unknown

The first MGZ19 [27] scheme: This scheme addresses the issue of using a random
oracle in the LW11 [22] scheme. It employs multiple ‘central authorities’ and
attribute authorities. The security model considers corruption of the attribute
authorities, however, it does not consider the corruption of one of the CAs.
These CAs provide the user-specific randoms in the key generation to avoid
random oracles. We show that trusting the CA is necessary to ensure security.
In particular, we show that the scheme is vulnerable to an attack, provided that
the attribute authorities trust the (corrupted) CA. A goal of the scheme is that
the attribute authorities do not even have to be aware of the CAs, implying that
the authorities inherently assume all CAs are honest.

– Type of attack: Complete master-key attack, under corruption of one CA;

– Master key pair Ai : mpka,i (attj ) = (battj ), mski (attj ) = (αi , battj );
– CAi generates: r;
– Secret key: ku (αi , r, b) = (r), ka (attj , αi , r, b) = (αi + rbattj );
– Known variables: K = {r} (by corrupting one CA);
– The goal: Recover αi from ki,j ← ka (attj , αi , r, b), mpki,j ← mpka,i (attj );
– The attack: αi = ki,j − rmpki,j . t
u

6 Discussion
We have presented a linear, heuristic approach to analyzing security—consisting
of a more concise notation—and applied it to existing schemes. We have shown
that several schemes are vulnerable to our attacks, either rendering them fully
or partially insecure. Most of the attacks are similar in that they either exploit
that one monomial occurs more than once in the keys, or known exponents yield
sufficient knowledge to enable an attack. Table 5 lists each attacked scheme
 A Simple yet Powerful Linear Approach to Analyzing Security of ABE 25

and the associated fundamental problem that enables the attack. It also shows
whether a scheme is insecure in the basic (CPA-)security model, or only under
corruption of the central authority (CA) or attribute authorities (A).
We identify the most prevalent issues with the broken multi-authority schemes.
In general, schemes for which we have found an attack without requiring cor-
ruption are structurally more complicated than the single-authority schemes on
which they are (loosely) based. Schemes insecure under corruption are gener-
ally closer to its (provably secure) single-authority variant, but the knowledge
of certain exponents enables an attack. If possible, a distributed generation of
these exponents could prevent this. For future work, it might be interesting to
construct a generic transformation on any single-authority scheme to the multi-
authority setting that provably ensures security against corrupted authorities.

Acknowledgments. We would like to thank the anonymous reviewers of ACNS

for their helpful comments.

References
1. S. Agrawal, and M. Chase, “Simplifying Design and Analysis of Complex Predicate
Encryption Schemes”, in EUROCRYPT’17, pp. 627–656, Springer, 2017.
2. M. Ambrona, G. Barthe, R. Gay, and H. Wee, “Attribute-Based Encryption in the
Generic Group Model: Automated Proofs and New Constructions”, in CCS’17, pp.
647–664, ACM, 2017.
3. N. Attrapadung, “Dual System Encryption via Doubly Selective Security: Frame-
work, Fully Secure Functional Encryption for Regular Languages, and More”, in
EUROCRYPT’14, pp. 557–577, Springer, 2014.
4. A. Beimel, “Secure Schemes for Secret Sharing and Key Distribution”, PhD Thesis,
Ben Gurion University, 1996.
5. J. Bethencourt, A. Sahai, and B. Waters, “Ciphertext-Policy Attribute-Based En-
cryption”, in S&P ’07, pp. 321–334, ACM, 2007.
6. M. Chase, “Multi-Authority Attribute-Based Encryption”, in TCC’07, pp. 515–534,
Springer, 2007.
7. M. Chase, and S. S. M. Chow, “Improving Privacy and Security in Multi-Authority
Attribute-based Encryption”, in CCS’09, pp. 121–130, ACM, 2009.
8. P. Chaudhari, M. L. Das, and A. Mathuria, “On Anonymous Attribute Based En-
cryption”, in ICISS’15, pp. 378–392, Springer, 2015.
9. J. Chen, and H. Ma, “Efficient decentralized attribute-based access control for cloud
storage with user revocation”, in 2014 IEEE International Conference on Commu-
nications (ICC), pp. 3782–3787, IEEE, 2014.
10. S. S. M. Chow, “A Framework of Multi-Authority Attribute-Based Encryption
with Outsourcing and Revocation”, in SACMAT’16, pp. 215–226, ACM, 2016.
11. A. Ge, J. Zhang, R. Zhang, C. Ma, and Z. Zhang, “Security Analysis of a Privacy-
Preserving Decentralized Key-Policy Attribute-Based Encryption Scheme”, Trans-
actions on Parallel and Distributed Systems, 24(11), pp. 2319–2321, IEEE, 2013.
12. V. Goyal, O. Pandey, A. Sahai, and B. Waters, “Attribute-Based Encryption for
Fine-Grained Access Control of Encrypted Data”, in CCS, pp. 89–98, ACM, 2006.
13. J. Han, W. Susilo, Y. Mu, and J. Yan, “Privacy-Preserving Decentralized Key-
Policy Attribute-Based Encryption”, in IEEE Transactions on Parallel and Dis-
tributed Systems, 23(11), pp. 2150–2162, IEEE, 2012.
26 M. Venema, G. Alpár

14. J. Han, W. Susilo, Y. Mu, J. Zhou, and M. H. A. Au, “PPDCP-ABE: Privacy-

Preserving Decentralized Ciphertext-Policy Attribute-Based Encryption”, in ES-
ORICS’14, pp. 73–90, Springer, 2014.
15. J. Han, W. Susilo, Y. Mu, J. Zhou, and M. H. A. Au, “Improving Privacy and
Security in Decentralized Ciphertext-Policy Attribute-Based Encryption”, in Trans-
actions on Information Forensics and Security, 10(3), pp. 665–678, IEEE, 2015.
16. J. Hong, K. Xue, and W. Li, “Comments on “DAC-MACS: Effective Data Access
Control for Multiauthority Cloud Storage Systems”/Security Analysis of Attribute
Revocation in Multiauthority Data Access Control for Cloud Storage Systems”, in
IEEE Transactions on Information Forensics and Security, 10(6), pp. 1315–1317,
IEEE, 2015.
17. L. Ibraimi, Q. Tang, P. Hartel, and W. Jonker, “Efficient and Provable Secure
Ciphertext-Policy Attribute-Based Encryption Schemes”, in ISPEC’09, pp. 1–12,
Springer, 2009.
18. T. Jung, X. Y. Li, Z. Wan, and M. Wan, “Privacy Preserving Cloud Data Access
With Multi-Authorities”, in INFOCOM’13, pp. 2625–2633, IEEE, 2013.
19. T. Jung, X. Y. Li, Z. Wan, and M. Wan, “Control Cloud Data Access Privilege and
Anonymity with Fully Anonymous Attribute-Based Encryption”, in IEEE Trans-
actions on Information Forensics and Security, 10(1), pp. 190–199, IEEE, 2015.
20. T. Jung, X. Y. Li, Z. Wan, and M. Wan, “Rebuttal to “Comments on “Control
Cloud Data Access Privilege and Anonymity With Fully Anonymous Attribute-
Based Encryption”””, in IEEE Transactions on Information Forensics and Security,
11(4), pp. 868–868, IEEE, 2016.
21. A. Lewko, T. Okamoto, A. Sahai, K. Takashima, and B. Waters, “Fully Secure
Functional Encryption: Attribute-Based Encryption and (Hierarchical) Inner Prod-
uct Encryption”, in EUROCRYPT’10, pp. 62–91, Springer, 2010.
22. A. Lewko, and B. Waters, “Decentralizing Attribute-Based Encryption”, in EU-
ROCRYPT’11, pp. 568–588, Springer, 2011.
23. J. Li, K. Ren, B. Zhu, and Z. Wan, “Privacy-Aware Attribute-Based Encryption
with User Accountability”, in ISC’09, pp. 347–362, Springer, 2009.
24. J. Li, Q. Huang, X. Chen, S. S. M. Chow, D. S. Wong, and D. Xie, “Multi-
Authority Ciphertext-Policy Attribute-Based Encryption with Accountability”, in
AsiaCCS’11, pp. 386–390, ACM, 2011.
25. W. Li, K. Xue, Y. Xue, and J. Hong, “TMACS: A Robust and Verifiable Threshold
Multi-Authority Access Control System in Public Cloud Storage”, in IEEE Trans-
actions on Parallel and Distributed Systems, 27(5), pp. 1484–1496, IEEE, 2016.
26. H. Lin, Z. Cao, X. Liang, and J. Shao, “Secure Threshold Multi Authority Attribute
Based Encryption without a Central Authority”, in INDOCRYPT’08, pp. 426–436,
Springer, 2008.
27. C. Ma, A. Ge, and J. Zhang, “Fully Secure Decentralized Ciphertext-Policy
Attribute-Based Encryption in Standard Model”, in Inscrypt’19, pp. 427–447,
Springer, 2019.
28. H. Ma, R. Zhang, and W. Yuan, “Comments on “Control Cloud Data Access
Privilege and Anonymity with Fully Anonymous Attribute-Based Encryption””, in
Trans. on Information Forensics and Security, 11(4), pp. 866–867, IEEE, 2016.
29. Q. M. Malluhi, A. Shikfa, and V. C. Trinh, “Ciphertext-Policy Attribute-based
Encryption Scheme With Optimized Ciphertext Size And Fast Decryption”, in ASI-
ACCS’17, pp. 230–240, ACM, 2017.
30. J. Ning, X. Dong, Z. Cao, and L. Wei, “Accountable Authority Ciphertext-Policy
Attribute-Based Encryption with White-Box Traceability and Public Auditing in
the Cloud”, in ESORICS’15, pp. 270-289, Springer, 2015.
 A Simple yet Powerful Linear Approach to Analyzing Security of ABE 27

31. H. S. G. Pussewalage, and V. A. Oleshchuk, “A Distributed Multi-Authority At-

tribute Based Encryption Scheme for Secure Sharing of Personal Health Records”,
in SACMAT’17, pp. 255–262, ACM, 2017.
32. H. Qian, J. Li, and Y. Zhang, “Privacy-Preserving Decentralized Ciphertext-Policy
Attribute-Based Encryption with Fully Hidden Access Structure”, in ICICS’13, pp.
363–372, Springer, 2013.
33. H. Qian, J. Li, Y. Zhang, and J. Han, “Privacy-Preserving Personal Health Record
Using Multi-Authority Attribute-Based Encryption with Revocation”, in Interna-
tional Journal of Information Security, 14(6), pp. 487–497, Springer, 2015.
34. A. Sahai, and B. Waters, “Fuzzy Identity-Based Encryption”, in EUROCRYPT’05,
pp. 457–473, Springer, 2005.
35. S.-Y. Tan, K.-W. Yeow, and S. O. Hwang, “Enhancement of a Lightweight
Attribute-Based Encryption Scheme for the Internet of Things”, in Internet of
Things Journal, 6(4), pp. 6384–6395, IEEE, 2019.
36. The full version of this paper: “A Bunch of Broken Schemes: A Simple yet Powerful
Linear Approach to Analyzing Security of Attribute-Based Encryption”, available
at: [Link]
37. M. Wang, Z. Zhang, and C. Chen, “Security Analysis of a Privacy-Preserving De-
centralized Ciphertext-Policy Attribute-Based Encryption Scheme”, in Concurrency
and Computation: Practice and Experience, 28(4), pp. 1237–1245, Wiley Online Li-
brary, 2015.
38. B. Waters, “Ciphertext-Policy Attribute-Based Encryption - An Expressive, Effi-
cient, and Provably Secure Realization”, in PKC’11, pp. 53–70, Springer, 2011.
39. H. Wee, “Dual System Encryption via Predicate Encodings”, in TCC’14, pp. 616–
637, Springer, 2014.
40. X. Wu, R. Jiang, and B. Bhargava, “On the Security of Data Access Control for
Multiauthority Cloud Storage Systems”, in IEEE Transactions on Services Com-
puting, 10(2), pp. 258–272, IEEE, 2017.
41. F. Xhafa, J. Feng, Y. Zhang, X. Chen, and J. Li, “Privacy-aware attribute-based
PHR sharing with user accountability in cloud computing”, in Journal of Super-
computering, 71, pp. 1607–1619, Springer, 2014.
42. K. Yang, and X. Jia, “Attribute-Based Access Control for Multi-Authority Systems
in Cloud Storage”, in 2012 32nd IEEE International Conference on Distributed
Computing Systems, pp. 536–545, IEEE, 2012.
43. K. Yang, and X. Jia, “Expressive, Efficient, and Revocable Data Access Control for
Multi-Authority Cloud Storage”, in IEEE Transactions on Parallel and Distributed
Systems, 25(7), IEEE, 2014.
44. K. Yang, X. Jia, K. Ren, B. Zhang, and R. Xie, “DAC-MACS: Effective Data
Access Control for Multiauthority Cloud Storage Systems”, in IEEE Transactions
on Information Forensics and Security, 8(11), pp. 1790–1801, IEEE, 2013.
45. X. Yao, Z. Chen, and Y. Tian, “A lightweight attribute-based encryption scheme
for the Internet of Things”, in Journal on Future Generation Computer Systems,
49, pp. 104–112, Elsevier, 2015.
46. Y. Zhang, X. Chen, J. Li, D. Wong, and H. Li, “Anonymous attribute-based en-
cryption supporting efficient decryption test”, in AsiaCCS, pp. 511–516, ACM, 2013.
47. Z. Zhou, and D. Huang, “On Efficient Ciphertext-Policy Attribute Based Encryp-
tion and Broadcast Encryption”, in CCS’10, pp. 753–755, ACM, 2010.
48. Z. Zhou, D. Huang, and Z. Wang, “Efficient Privacy-Preserving Ciphertext-Policy
Attribute Based-Encryption and Broadcast Encryption”, in IEEE Transactions on
Computers, 64(1), pp. 126–138, IEEE, 2013.
28 M. Venema, G. Alpár

Fig. 2. The relationship between our proposed attacks and chosen-plaintext attacks.
Master-key attack Attribute-key attack

S n =1 Si Sn
0 )
i S0 = i=1 Si
S

Complete Conditional
decryption attack decryption attack

Selective CPA for ABE

Full CPA for ABE

A Formal definition of access structures

Definition 13 (Access structures [4]). Let {a1 , ..., an } be a set of attributes.
An access structure is a collection A of non-empty subsets of {a1 , ..., an }. The
sets in A are called the authorized sets, and the sets that are not in A are called
the unauthorized sets. An access structure A ⊆ 2{a1 ,...,an } is monotonic if for all
B, C holds: B ∈ A and B ⊆ C, then also C ∈ A.

B Proofs of implications
For completeness, we give formal proofs of the implications between the def-
initions of the attacks (i.e. Definitions 2, 3, 4, and 5). More specifically, we
prove that the master-key attacks (MKA) and attribute-key attacks (AKA) im-
ply decryption attacks (DA), and decryption attacks imply selective chosen-
plaintext attacks (sCPA). Furthermore, it is a well-known fact that selective
chosen-plaintext attacks imply full chosen-plaintext attacks [34] (and conversely,
full CPA-security implies selective CPA-security). The relationship between the
attacks is summarized in Figure 2. For instance, if we can perform a master-key
attack (i.e. define a polynomial-time algorithm that computes a master-key that
can decrypt any ciphertext), then we can also perform a complete decryption at-
tack (i.e. define a polynomial-time algorithm that decrypts any ciphertext with
any number of unauthorized secret keys).
Lemma 1 (MKA implies complete DA). If some polynomial-time attacker
BMKA exists that can win the master-key attack (Definition 3) game, then a
polynomial-time attacker BCDA exists that can win the complete decryption attack
(Definition 4) game.
Proof. Let BCDA be the attacker that plays the complete decryption game with
the challenger. Suppose BMKA denotes a polynomial-time attacker that can win
the master-key attack game.
 A Simple yet Powerful Linear Approach to Analyzing Security of ABE 29

– Setup phase: The challenger runs the setup of the scheme, and sends the
master public key to attacker BCDA , which relays it to attacker BMKA .
– Key query phase I: Attacker BMKA generates sets S1 , ..., Sn1 and sends
these to attacker BCDA , which relays these to the challenger. For each set
Si , the challenger generates a secret key SKSi and sends it back to attacker
BCDA , which relays it to attacker BMKA .
– Intermission: The decision phase of attacker BMKA yields as output the
master-key MK0 , which is sent to attacker BCDA .
– Challenge phase: Attacker BCDA can then define any access structure A
such that A 6|= Si for all i ∈ {1, ..., n1 }. The challenger encrypts a random
message m under this access structure, and sends the resulting challenge
ciphertext CT to attacker BCDA .
– Decision phase: Attacker BCDA uses MK0 to decrypt CT with the master-
key decryption algorithm MKDecrypt conform Definition 1, yielding plain-
text m0 , and sends this to the challenger.
Because it was assumed that attacker BMKA wins the MKA-game, MK0 is
such that master-key decryption works on any ciphertext, and by extension
resulting in a correct recovery of plaintext, i.e. m0 = m. t
u
Lemma 2 (AKA implies DA). If some polynomial-time attacker BAKA exists
that can win the attribute-key attack game, then a polynomial-time attacker BDA
exists that can win the decryption attack game. Furthermore, if the set S 0 for
which the attacker recovers a secret key is strictly larger than the collective set
of attributes used in the key query phase, then the decryption attack is complete.
Otherwise, it is conditional.
Proof. Let BDA be the attacker that plays the decryption game with the chal-
lenger. Suppose BAKA denotes a polynomial-time attacker that can win the
attribute-key attack game.
– Setup phase: The challenger runs the setup of the scheme, and sends the
master public key to attacker BDA , which relays it to attacker BAKA .
– Key query phase I: Attacker BAKA generates sets S1 , ..., Sn1 and sends
these to attacker BDA , which relays these to the challenger. For each set, the
challenger generates a secret key SKSi and sends it back to attacker BDA ,
which relays it to attacker BAKA .
– Intermission: The decision phase of attacker BAKA yields as output SKS 0
for set S 0 such that S 0 ) Si for all i ∈ {1, ..., n1 }. Then two cases may
occur, for which attacker BDA defines access structure A with A 6|= Si for all
i ∈ {1, ...,S
n1 } as follows:
n1
• S 0 = i=1 Si , in which case the attack game becomes conditional, and
attacker B
S n1 DA defines A such that A |= S 0 ;
0
• S ) i=1 Si , in which case the attack game becomes Sn1 complete, and
attacker BDA defines A such that A |= S 0 and A 6|= i=1 Si .
– Challenge phase: Attacker BDA sends A to the challenger, which generates
a random message m, encrypts it under the access structure A and sends
the resulting challenge ciphertext CT to attacker BDA .
30 M. Venema, G. Alpár

– Decision phase: Because A |= S 0 holds, attacker BDA can decrypt CT with

secret key SKS 0 , yielding plaintext m0 .

Because it was assumed that attacker BAKA wins the AKA-game, SKS 0 is
valid, and therefore decryption yields the correct plaintext, i.e. m0 = m. t
u

Theorem 1 (DA implies Selective CPA). If some polynomial-time attacker

BDA exists that can win the decryption attack game, then a polynomial-time
attacker BsCPA exists that can win the selective chosen-plaintext attack game.

Proof. Let BsCPA be the attacker that plays the selective CPA game with the
challenger. Suppose BDA denotes a polynomial-time attacker that can win the
decryption attack game.

– Initialization phase: Attacker BsCPA commits to an access structure A to

be used in the challenge phase, and sends it to the challenger.
– Setup phase: The challenger runs the setup and sends the master public
key MPK to attacker BsCPA , which relays it to attacker BDA .
– Key query phase I: Attacker BDA then defines sets S1 , ..., Sn1 such that
A 6|= Si for all i ∈ {1, ..., n1 }. Depending on whether attackerSn1 BDA wins
complete
S n1 or conditional attack games, it also ensures A |
6 = i=1 Si or A |=
S
i=1 i , respectively. Attacker BDA sends the sets to attacker BsCPA , which
relays them to the challenger. Then, the challenger generates secret keys
SKS1 , ..., SKSn1 and sends them back to attacker BsCPA , which relays them
to attacker BDA .
– Challenge phase: Attacker BsCPA generates two messages m0 , m1 of equal
length and sends these to the challenger, which flips a coin b ∈R {0, 1},
encrypts one of the messages mb under the previously chosen access structure
and sends the resulting challenge ciphertext CT to attacker BsCPA , which
relays it to attacker BDA .
– Intermission: The decision phase of attacker BDA then yields as output the
plaintext m0 , and sends it to attacker BsCPA .
– Key query phase II: This phase may be skipped. As such, decryption
attacks also imply selective CPA with non-adaptive key queries.
– Decision phase: Depending on whether m0 = m0 or m0 = m1 , it outputs
guess b0 .

From the assumed success of attacker BDA , it follows that m0 = mb , from

which it follows that attacker BsCPA guesses correctly, i.e. b0 = b. t
u