Key-Aggregate Searchable Encryption (KASE) for Group Data Sharing via Cloud Storage

[pdf-embedder url=”https://wellapets.com/wp-content/uploads/2019/06/Key-Aggregate-Searchable-Encryption-KASE.pdf” title=”Key-Aggregate Searchable Encryption (KASE)”]

Abstract—The capability of selectively sharing encrypted data with different users via public cloud storage may greatly ease
security concerns over inadvertent data leaks in the cloud. A key challenge to designing such encryption schemes lies in the
efficient management of encryption keys. The desired flexibility of sharing any group of selected documents with any group of
users demands different encryption keys to be used for different documents. However, this also implies the necessity of securely
distributing to users a large number of keys for both encryption and search, and those users will have to securely store the
received keys, and submit an equally large number of keyword trapdoors to the cloud in order to perform search over the shared
data. The implied need for secure communication, storage, and complexity clearly renders the approach impractical. In this
paper, we address this practical problem, which is largely neglected in the literature, by proposing the novel concept of keyaggregate
searchable encryption (KASE) and instantiating the concept through a concrete KASE scheme, in which a data owner
only needs to distribute a single key to a user for sharing a large number of documents, and the user only needs to submit a
single trapdoor to the cloud for querying the shared documents. The security analysis and performance evaluation both confirm
that our proposed schemes are provably secure and practically efficient.
Index Terms—Searchable encryption, data sharing, cloud storage, data privacy

INTRODUCTION
Cloud storage has emerged as a promising solution
for providing ubiquitous, convenient, and on-demand
accesses to large amounts of data shared over the
Internet. Today, millions of users are sharing personal
data, such as photos and videos, with their friends
through social network applications based on cloud
storage on a daily basis. Business users are also being
attracted by cloud storage due to its numerous benefits,
including lower cost, greater agility, and better
resource utilization.
However, while enjoying the convenience of sharing
data via cloud storage, users are also increasingly
concerned about inadvertent data leaks in the cloud.
Such data leaks, caused by a malicious adversary or
a misbehaving cloud operator, can usually lead to
serious breaches of personal privacy or business secrets
(e.g., the recent high profile incident of celebrity
photos being leaked in iCloud). To address users’
concerns over potential data leaks in cloud storage,
a common approach is for the data owner to encrypt all the data before uploading them to the cloud, such
that later the encrypted data may be retrieved and decrypted
by those who have the decryption keys. Such
a cloud storage is often called the cryptographic cloud
storage [6]. However, the encryption of data makes it
challenging for users to search and then selectively
retrieve only the data containing given keywords. A
common solution is to employ a searchable encryption
(SE) scheme in which the data owner is required to
encrypt potential keywords and upload them to the
cloud together with encrypted data, such that, for
retrieving data matching a keyword, the user will
send the corresponding keyword trapdoor to the cloud
for performing search over the encrypted data.
Although combining a searchable encryption
scheme with cryptographic cloud storage can
achieve the basic security requirements of a cloud
storage, implementing such a system for large scale
applications involving millions of users and billions
of files may still be hindered by practical issues
involving the efficient management of encryption
keys, which, to the best of our knowledge, are largely
ignored in the literature. First of all, the need for
selectively sharing encrypted data with different
users (e.g., sharing a photo with certain friends in
a social network application, or sharing a business
document with certain colleagues on a cloud drive)
usually demands different encryption keys to be
used for different files. However, this implies the
number of keys that need to be distributed to users,
both for them to search over the encrypted files
and to decrypt the files, will be proportional to the
number of such files. Such a large number of keys must not only be distributed to users via secure
channels, but also be securely stored and managed
by the users in their devices. In addition, a large
number of trapdoors must be generated by users
and submitted to the cloud in order to perform a
keyword search over many files. The implied need for
secure communication, storage, and computational
complexity may render such a system inefficient and
impractical.
In this paper, we address this challenge by proposing
the novel concept of key-aggregate searchable encryption
(KASE), and instantiating the concept through a
concrete KASE scheme. The proposed KASE scheme
applies to any cloud storage that supports the searchable
group data sharing functionality, which means any
user may selectively share a group of selected files
with a group of selected users, while allowing the
latter to perform keyword search over the former. To
support searchable group data sharing the main requirements
for efficient key management are twofold.
First, a data owner only needs to distribute a single
aggregate key (instead of a group of keys) to a user for
sharing any number of files. Second, the user only needs to
submit a single aggregate trapdoor (instead of a group of
trapdoors) to the cloud for performing keyword search over
any number of shared files. To the best of our knowledge,
the KASE scheme proposed in this paper is the first
known scheme that can satisfy both requirements (the
key-aggregate cryptosystem [4], which has inspired
our work, can satisfy the first requirement but not the
second).
Contributions. More specifically, our main contributions
are as follows.
1) We first define a general framework of keyaggregate
searchable encryption (KASE) composed
of seven polynomial algorithms for security
parameter setup, key generation, encryption,
key extraction, trapdoor generation, trapdoor
adjustment, and trapdoor testing. We then
describe both functional and security requirements
for designing a valid KASE scheme.
2) We then instantiate the KASE framework by
designing a concrete KASE scheme. After providing
detailed constructions for the seven algorithms,
we analyze the efficiency of the scheme,
and establish its security through detailed analysis.
3) We discuss various practical issues in building
an actual group data sharing system based on
the proposed KASE scheme, and evaluate its
performance. The evaluation confirms our system
can meet the performance requirements of
practical applications.
The rest of the paper is organized as follows. First,
we review some background knowlege in Section 2.
We then define the general KASE framework in Section

1. We describe related work in Section 4. We
   design a concrete KASE scheme and analyze its efficiency
   and security in Section 5. We implement and
   evaluate a KASE-based group data sharing system in
   Section 6. Finally, we conclude the paper in Section 7.