Traditional encryption systems are designed in such a way that either the whole data is decrypted, if the encryption and decryption keys match, or nothing is decrypted otherwise. However, there are applications that require a more flexible encryption system which supports decrypting data partially. Searchable encryption is a technique that provides functionalities to decrypt data partially by searching encrypted data.
In searchable encryption, each message of data is associated with a set of keywords. Searchable encryption transforms both, the message and the associated keywords, to an encrypted form, in such a way that the encrypted keywords can be queried later. This allows a client to retrieve or decrypt only the messages of the data that contain a particular keyword without decrypting the data. Searchable encryption can be based on either symmetric key or public key cryptography.
In the symmetric key setting, only the client who stores the data on the server can search the encrypted data. This setting is appropriate for situations where the client stores encrypted data on an honest but curious server, in such a way the the encrypted data can be retrieved selectively. Using symmetric key searchable encryption, the server learns as little information as possible after the storage and the search. In public key searchable encryption, anyone can encrypt data using a public key, while only the owner of the corresponding private key can query encrypted data. Public key searchable encryption allows a client to delegate a decryption key to other users, in such a way that the delegated decryption key can decrypt parts of data only.
The main aspects of searchable encryption are security and efficiency. The efficiency of a scheme is evaluated by the complexity of the scheme. The security of a scheme shows the ability of the scheme in hiding both, the message and the associated keywords, from adversaries. To define the security formally, security models are proposed where each model defines certain computational resources and restrictions for the adversary. Since security is never free, there is a trade off between efficiency and security. Searchable encryption schemes that achieve security in a security model with a more powerful adversary have a higher complexity. The best trade off is achieved when the scheme achieves certain level of security with the lowest possible complexity.
The main contributions of this thesis are the efficient and provably secure searchable encryption schemes which have a lower complexity compared to existing schemes. Our focus in this thesis is the complexity of the search, which is the main functionality of searchable encryption. In this thesis we propose: