21. A system having a memory and a processor, the system comprising: a component configured to, for each of a plurality of values of an attribute of documents, the values having an ordering: determine a number of different encrypted instances of the value to generate, wherein the number of different encrypted instances determined for at least one of the plurality of values is greater than one, generate the determined number of different encrypted instances of the value so that the value serves as a basis for generating each of the determined number of different encrypted instances of the value, wherein more than one encrypted instance of the at least one of the plurality of values is generated, and store the generated encrypted instances of the value, wherein each encrypted instance of the value can be decrypted into the value; a component configured to generate a mapping of the values of the attribute to each document having that value for the attribute, wherein the mapping maps different encrypted instances of a value to different documents; a component configured to provide the generated mapping to a document storage service; and a component configured to identify an encrypted document that matches a query that specified a value for the attribute, wherein the component configured to identify the encrypted document that matches a query that specified a value for the attribute is further configured to: determine a lower bound on encrypted instances associated with the value specified by the query, determine an upper bound on encrypted instances associated with the value specified by the query, send the determined lower and upper bounds to a document storage service, and receive from the document storage service an indication of at least one document associated with an encrypted instance between the lower and upper bounds wherein each of the components comprises computer-executable instructions stored in the memory for execution by the system.
21. A system having a memory and a processor, the system comprising: a component configured to, for each of a plurality of values of an attribute of documents, the values having an ordering: determine a number of different encrypted instances of the value to generate, wherein the number of different encrypted instances determined for at least one of the plurality of values is greater than one, generate the determined number of different encrypted instances of the value so that the value serves as a basis for generating each of the determined number of different encrypted instances of the value, wherein more than one encrypted instance of the at least one of the plurality of values is generated, and store the generated encrypted instances of the value, wherein each encrypted instance of the value can be decrypted into the value; a component configured to generate a mapping of the values of the attribute to each document having that value for the attribute, wherein the mapping maps different encrypted instances of a value to different documents; a component configured to provide the generated mapping to a document storage service; and a component configured to identify an encrypted document that matches a query that specified a value for the attribute, wherein the component configured to identify the encrypted document that matches a query that specified a value for the attribute is further configured to: determine a lower bound on encrypted instances associated with the value specified by the query, determine an upper bound on encrypted instances associated with the value specified by the query, send the determined lower and upper bounds to a document storage service, and receive from the document storage service an indication of at least one document associated with an encrypted instance between the lower and upper bounds wherein each of the components comprises computer-executable instructions stored in the memory for execution by the system. 27. The system of claim 21 , further comprising: a component configured to generate a searchable document index at least in part by: for each of the plurality of documents, identifying a value associated with the document, randomly selecting one of the encrypted instances corresponding to the identified value, and storing a mapping between the document and only the randomly selected encrypted instance without storing a mapping between the document and the other encrypted instances.