2014 · 183 citations · 24 references
ComputingCloud ComputingComputer ScienceCloud StorageCryptographyDatabasesCloud EncryptionData EncryptionStorage SecurityEncrypted Database SystemsEncrypted StorageEncryptionEncryption Scheme SecuritySearch Over Encrypted DataSearchable EncryptionSecure Cloud StorageSemantic Security
Searchable (symmetric) encryption allows encryption while still enabling search for keywords. Its immediate application is cloud storage where a client outsources its files while the (cloud) service provider should search and selectively retrieve those. Searchable encryption is an active area of research and a number of schemes with different efficiency and security characteristics have been proposed in the literature. Any scheme for practical adoption should be efficient -- i.e. have sub-linear search time --, dynamic -- i.e. allow updates -- and semantically secure to the most possible extent. Unfortunately, efficient, dynamic searchable encryption schemes suffer from various drawbacks. Either they deteriorate from semantic security to the security of deterministic encryption under updates, they require to store information on the client and for deleted files and keywords or they have very large index sizes. All of this is a problem, since we can expect the majority of data to be later added or changed. Since these schemes are also less efficient than deterministic encryption, they are currently an unfavorable choice for encryption in the cloud. In this paper we present the first searchable encryption scheme whose updates leak no more information than the access pattern, that still has asymptotically optimal search time, linear, very small and asymptotically optimal index size and can be implemented without storage on the client (except the key). Our construction is based on the novel idea of learning the index for efficient access from the access pattern itself. Furthermore, we implement our system and show that it is highly efficient for cloud storage.
24
Practical techniques for searches on encrypted data
Dawn Xiaoding Song, David Wagner, Adrian Perrig · 2002 · 3.3K citations
Benny Chor, Eyal Kushilevitz, Oded Goldreich et al. · Journal of the ACM · 1998 · 1.6K citations · Full text
Software protection and simulation on oblivious RAMs
Oded Goldreich, Rafail Ostrovsky · Journal of the ACM · 1996 · 1.6K citations · Full text
Executing SQL over encrypted data in the database-service-provider model
Hakan Hacígümüş, B. R. Iyer, Chen Li et al. · 2002 · 1.1K citations
Raluca Ada Popa, Catherine M. S. Redfield, Nickolai Zeldovich et al. · 2011 · 1.1K citations · Full text