  In the use of a cloud storage, sharing of data with efficient access control
is an important requirement in addition to data security and privacy. Cui et
al. (IEEE Trans. on Comp. 2016) proposed \textit{key-aggregate searchable
encryption (KASE)}, which allows a data owner to issue an \textit{aggregate
key} that enables a user to search in an authorized subset of encrypted files
by generating an encrypted keyword called \textit{trapdoor}. While the idea of
KASE is elegant, to the best of our knowledge, its security has never been
discussed formally. In this paper, we discuss the security of KASE formally and
propose provably secure schemes. The construction of a secure KASE scheme is
non-trivial, and we will show that the KASE scheme of Cui et al. is insecure
under our definitions. We first introduce our provably secure scheme, named
\textit{first construction}, with respect to encrypted files and aggregate keys
in a single-server setting. In comparison with the scheme of Cui et al., the
first construction is secure without increased computational costs. Then, we
introduce another provably secure scheme, named \textit{main construction},
with respect to trapdoors in a two-server setting. The main construction
guarantees the privacy of a search, encrypted files, and aggregate keys.
Considering 5,000 encrypted files, the first construction can finish search
within three seconds and the main construction can finish search within six
seconds.
