Towards Provably Secure Efficiently Searchable Encryption

Saeed Sedghi

Promotores: Prof.dr. W. Jonker (UT) and Prof.dr. P.H. Hartel (UT)
Co-promotor: Dr. S. Nikova (UT)
Universiteit Twente
Date: 17 February, 2012


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:

  • A searchable encryption scheme in the symmetric key setting which is secure in the symmetric key searchable encryption model. This security model is the only security model proposed in the symmetric key setting. Our scheme, called SES, has a lower complexity for the search compared to existing symmetric key searchable encryption schemes.
  • A public key searchable encryption scheme which is secure in the random oracle model. A ransom oracle is a function that maps an input value to a true random output value. In the random oracle model anyone including the adversary has access to a random oracle. Our scheme, called SEPE, allows searching and enforcing an access control policy, while revealing as little as possible about the data and the policy. The SEPE scheme has a lower complexity to perform the search and enforce an access control policy compared to existing schemes.
  • A public key searchable encryption scheme which is secure in the selective security model. The adversary in the selective security model must inform in advance of the attack which keyword is intended to be attacked. Our scheme, called SEPS, supports wildcards in the queried keyword. The SEPS scheme is more efficient that existing schemes which allow searching keywords with wildcards on encrypted data.
  • A public key searchable encryption scheme which is fully secure. The full security model is the strongest proposed security model. Our scheme, called SEPF, has a lower search complexity compared to existing fully secure schemes.