Is it possible to match encrypted documents using user-defined search terms? 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.
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 &amp; 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 &amp; 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.