Techniques for efficiently searching encrypted searchable spaces. For example, embodiments of the present invention provide techniques for searching a plurality of files that are stored in encrypted (or ciphertext) form. According to embodiments of the present invention, the search can usually be performed by decrypting only a portion of the encrypted searchable space. According to an embodiment of the present invention, the search techniques determine a set of files comprising one or more files from the plurality of encrypted files that contain a user-specified query element. The set of files is usually determined by decrypting only a subset of the plurality of encrypted files.