14. A computer-readable storage medium containing instructions for generating a document index by operations comprising: for each of a plurality of values of an attribute of documents, the values having an ordering, determining a number of different encrypted instances to generate for the value, and generating 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 the number of encrypted instances of at least one of the values is greater than one, wherein each encrypted instance is unique, and wherein each of the generated encrypted instances of the value decrypts to the value, storing the generated encrypted instances of the value; and generating 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; providing the generated mapping to a document storage service; and identifying an encrypted document that matches a query that specified a value for the attribute by, determining a lower bound on encrypted instances associated with the value specified by the query, determining an upper bound on encrypted instances associated with the value specified by the query, sending the determined lower and upper bounds to a document storage service, and receiving from the document storage service an indication of at least one document associated with an encrypted instance between the lower and upper bounds.
19. The computer-readable storage medium of claim 14 , wherein generating the determined number of different encrypted instances of a first value of the set of ordered values comprises: generating a first encrypted instance of the first value by encrypting the first value; generating a second encrypted instance of the first value by adding a randomly-generated value to the first encrypted instance of the first value; generating a third encrypted instance of the first value by adding a randomly-generated value to the second encrypted instance of the first value; and generating a fourth encrypted instance of the first value by adding a randomly-generated value to the third encrypted instance of the first value, so that the first value is associated with at least four different encrypted instances of the first value and each encrypted instances is associated with exactly one value of the set of ordered values.