  Existing semantically secure public-key searchable encryption schemes take
search time linear with the total number of the ciphertexts. This makes
retrieval from large-scale databases prohibitive. To alleviate this problem,
this paper proposes Searchable Public-Key Ciphertexts with Hidden Structures
(SPCHS) for keyword search as fast as possible without sacrificing semantic
security of the encrypted keywords. In SPCHS, all keyword-searchable
ciphertexts are structured by hidden relations, and with the search trapdoor
corresponding to a keyword, the minimum information of therelations is
disclosed to a search algorithm as the guidance to find all matching
ciphertexts efficiently. We construct a simple SPCHS scheme from scratch in
which the ciphertexts have a hidden star-like structure. We prove our scheme to
be semantically secure based on the decisional bilinear Diffie-Hellman
assumption in the Random Oracle (RO) model. The search complexity of our scheme
is dependent on the actual number of the ciphertexts containing the queried
keyword, rather than the number of all ciphertexts. Finally, we present a
generic SPCHS construction from anonymous identity-based encryption and
collision-free full-identity malleable Identity-Based Key Encapsulation
Mechanism (IBKEM) with anonymity. We illustrate two collision-free
full-identity malleable IBKEM instances, which are semantically secure and
anonymous, respectively, in the RO and standard models. The latter instance
enables us to construct an SPCHS scheme with semantic security in the standard
model.
