Attribute-based encryption (ABE), as introduced by Sahai and Waters in 2005, allows
for fine-grained access control on encrypted data, where ciphertexts and keys are associated
with access policies over attributes and subsets of attributes, and a key can
decrypt a ciphertext if and only if the associated set of attributes satisfies the associated
access policy. There are two types of ABE systems: Ciphertext-Policy ABE (CP-ABE),
where ciphertexts are associated with access policies and keys are associated with sets
of attributes, and Key-Policy ABE (KP-ABE), where keys are associated with access
policies and ciphertexts are associated with sets of attributes. Due to its promising applications
related to access control and its importance in enabling more secure solutions
to cloud computing, ABE has attracted much attention in the research community, and
a series of work has been done very recently, some for achieving better expressiveness,
some others for enhancing higher efficiency, and of course some for getting higher security
level. In this thesis, we investigate several aspects of ABE that are crucial to its
applicability in practice. These aspects include:
1. Efficient Access Policy Generation: we propose an efficient algorithm to specify
access policies defined over attributes in ABE. We use the natural and efficient
form of access trees with interior nodes as threshold gates in specifying the access
policies. By using this algorithm, we can obtain smaller ciphertexts (resp. keys)
in CP-ABE (resp. KP-ABE) when compared with existing algorithms;
2. Multi-Authority CP-ABE: we propose a new multi-authority CP-ABE system
which, to the best of our knowledge, is the first one shown adaptively secure against adaptive authority corruption attacks in the standard model. The system
is also the first one which can prevent individual authorities from decrypting the
ciphertexts;
3. Traceable ABE: one of the major issues of deploying ABE systems in practice is
about tracing malicious users. We formalize the notion of traceability and propose
three systems with traceability, which are the first ones being both adaptively
secure and highly expressive. Furthermore, the overhead incurred by traceability
in these systems is also the smallest to date.
Most existing ABE schemes supporting high expressiveness (i.e. supporting any
monotone access structures) use Linear Secret Sharing Schemes (LSSS) to realize the
access policies. However, in practice users often use other natural forms, such as access
trees, Boolean formulas, or minimal form access structures, to express their access
policies. In 2010, Lewko and Waters proposed an algorithm which can convert any
Boolean formula to a corresponding LSSS matrix. In the first part of this thesis, we
propose an improved algorithm which takes threshold-gate access trees as input and
outputs the corresponding LSSS matrices. We show that our algorithm attains smaller
(at least the same in the worst case) size of LSSS, which implies smaller ciphertexts
(resp. keys) in CP-ABE (resp. KP-ABE) systems. In particular, as the simplest example,
for a (2,n)-threshold policy, our algorithm will generate an LSSS matrix with size = n, while Lewko-Waters' algorithm will generate an LSSS matrix with size ≥ n log n.
When Sahai and Waters introduced the first ABE system, they also raised an open
problem: build a multi-authority ABE system where attributes could naturally be managed
by different and independent authorities rather than being limited to just one single
authority. This problem is motivated by practical scenarios where a single-authority
ABE may not be appropriate: A user wants to encrypt a message with access policy
("UNIV.X.CS" AND "UNIV.X.Alumni" AND "COMP.Y.Engineer") so that only receivers
who are the computer science alumni of University X and currently working
as an engineer for Company Y can decrypt, where the authority UNIV.X Registry may only manage attributes for the students, staff and alumni of University X, and COMP.Y
Registry may be the authority handling its employees' attributes. In 2011, Lewko and
Waters proposed the first fully secure multi-authority CP-ABE system in the random
oracle model, and left the construction of a fully secure multi-authority CP-ABE in
the standard model as an open problem. Also, there is no CP-ABE system which can
completely prevent individual authorities from decrypting ciphertexts. In the second
part of this thesis, we propose a new multi-authority CP-ABE system for simultaneously
addressing these two problems positively. This new system achieves the same
expressiveness and comparable efficiency with Lewko-Waters' system.
In an ABE (CP-ABE as an example) system, decryption privileges are defined over
attributes that could be shared by multiple users. As the decryption privileges corresponding
to the common attributes could be shared by multiple users rather than being
exclusively owned by one user, a malicious user with some decryption privileges, shared
with multiple users, might have an intention to leak partial or even all the decryption
privileges to someone else, for example, for financial gain or for some other incentives,
if there is no tracing mechanism for finding such malicious users out. There are
two levels of traceability: (1) given a well-formed decryption key, a White-box tracing
algorithm can find out the original key owner; and (2) given a decryption-device
while the underlying decryption algorithm or key may not be given, a Black-box tracing
algorithm, which treats the decryption-device as an oracle, can find out at least
one of the malicious users whose keys have been used for constructing the decryptiondevice.
In the third part of this thesis, we propose a White-box Traceable CP-ABE
system, a Black-box Traceable CP-ABE system and a Black-box Traceable KP-ABE
system, which are the first ones being both adaptively secure and highly expressive (i.e.
supporting any monotone access structures). Furthermore, the overhead incurred by
traceability in these systems is also the smallest one to date, i.e., only constant (resp.
O(√K)) number of additional elements in the ciphertext and private key (resp. public
key) in the white-box (resp. black-box) traceable system, where K is the number of
users in the system.
| Date of Award | 15 Jul 2014 |
|---|
| Original language | English |
|---|
| Awarding Institution | - City University of Hong Kong
|
|---|
| Supervisor | Shek Duncan WONG (Supervisor) & Xiaotie DENG (Supervisor) |
|---|