Is it possible to match encrypted documents using user-defined search terms?

Question

Suppose I am storing a number of encrypted documents in a database. I would like to make it possible to identify the subset of documents whose contents match user-specified search terms without a) maintaining a plaintext index or b) decrypting documents on the fly. Is there any way to accomplish this securely?

By the same token, I'm wondering if a collection of encrypted documents can be sorted according to an encrypted attribute (e.g., document title) without first decrypting all attribute values.

Answer 1

Yes. If you encrypt the documents with this purpose in mind (you have to use a special kind of encryption algorithm), then yes, it is possible to do this, for certain kinds of search queries.

There is a rich research literature on this topic. The buzzword is "search on encrypted data". I'll point you to a few sample papers in this space. Do a literature search, and you should be able to find many more for yourself.

• CryptDB: Protecting Confidentiality with Encrypted Query Processing, Raluca Ada Popa, Catherine M. S. Redfield, Nickolai Zeldovich, and Hari Balakrishnan. SOSP 2011. See also the CryptDB web page.

• Secure Indexes, Eu-Jin Goh.

• Practical Techniques for Searches on Encrypted Data, Dawn Xiaodong Song, David Wagner, and Adrian Perrig. IEEE Security & Privacy 2000.

• Public key encryption with keyword search, Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano. EUROCRYPT 2004.

• Designing Secure Indexes for Encrypted Databases, Erez Shmueli, Ronen Waisenberg, Yuval Elovici, and Ehud Gudes. Database Security 2005.

• How to Search on Encrypted Data, Eu-Jin Goh. Slides.

• Private Searching On Streaming Data, Rafail Ostrovsky and William E. Skeith III. CRYPTO 2005.

• New Constructions and Applications for Private Stream Search (Extended Abstract), John Bethencourt, Dawn Song, and Brent Waters. IEEE Security & Privacy 2006.

• Secure Ranked Keyword Search over Encrypted Cloud Data, Cong Wang, Ning Cao, Jin Li, Kui Ren, and Wenjing Lou. ICDCS 2010.

• Enabling Efficient Fuzzy Keyword Search over Encrypted Data in Cloud Computing, Jin Li, Qian Wang, Cong Wang, Ning Cao, Kui Ren, and Wenjing Lou.

• New Security Models and Provably-Secure Schemes for Basic Query Support in Outsourced Databases Amanatidis, Boldyreva, O'Neill. 2007

• Privacy Preserving Keyword Searches on Remote Encrypted Data Chang and Mitzenmacher. 2005

• Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries Cash et al. in CRYPTO 2013

• Multi-key Searchable Encryption Popa and Zeldovich. 2013.

• Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions Curtmola et al. 2006

The best scheme for your situation will depend upon your application requirements. If you have a read-mostly database (updates are rarer than searches), then I would suggest a scheme based upon encrypted indexes. If you need to make modifications frequently, or if searching is relatively rare, the other schemes might be preferable.