US 2010/0306221 A1 · EXTENDING RANDOM NUMBER SUMMATION AS AN ORDER-PRESERVING ENCRYPTION SCHEME

Abstract

A method and system for cryptographically indexing, searching for, and retrieving documents is provided. In some embodiments, an encryption system is provided that generates a document index that allows users to retrieve documents by performing encrypted queries for keywords associated with the documents. In some embodiments, each keyword maps to the same number of encrypted document identifiers. In some embodiments, an extractor graph is employed to map an indication of each keyword to a number of buckets storing encrypted document identifiers. In some embodiments, an order-preserving encryption system is provided. The encryption system uses an ordered index that maps encrypted instances of ordered attribute values to documents that are associated with those values. The ordered index enables queries containing query operators that rely on order, such as less than (“<”) or greater than (“>”), to be successfully performed on encrypted attribute values.

Claims20

Dependent claims

A method in a networked computer system for searching for encrypted documents, the method comprising:

generating a searchable document index for a plurality of documents by,
for each value in a sequence, the sequence corresponding to a range of an ordered attribute for the documents,
determining a number of encrypted instances to generate for the value,
generating the determined number of encrypted instances for the value, wherein each encrypted instance is equal to the previously generated encrypted instance plus a randomly generated amount, and
storing the generated encrypted instances, and
for each of the plurality of documents,
identifying a value of the ordered attribute associated with the document, and
randomly selecting one of the encrypted instances corresponding to the identified value;
and
identifying an encrypted document that matches a query by
receiving a query from a user, the query having at least one associated value,
determining a lower bound on encrypted instances associated with the query,
determining an upper bound on encrypted instances associated with the query,
sending the 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.

12 more elements

Dependencies are inferred from the claim text.

Extending random number summation as an order-preserving encryption scheme

Life of this patent

Extending random number summation as an order-preserving encryption scheme

Life of this patent

Abstract

Claims20