US 10,541,983 B1Granted

Secure storage and searching of information maintained on search systems

AssigneeAmazon Technologies, Inc.

InventorsAfshin Khashei Varnamkhasti, Bogdan Ciprian Pistol

Life of this patent

Estimating the term…

Loading patent…

Abstract

Systems and techniques are disclosed for secure storage and searching of information on insecure search systems. One of the methods is implemented by a system of one or more computers being in communication with clients and search engines. A request associated with storage of client information in a search engine is obtained. First cryptographic information is generated based on a portion of the client information, such that the first cryptographic is to be utilized for indexing by the search engine. Second cryptographic information is generated based on performing an order-preserving encryption process on portion of the client information, such that the second cryptographic information is to be utilized to recover order associated with information included in the portion. The first cryptographic information and the second cryptographic information are provided for storage in the search system.

Claims20

Dependent claims

A system comprising:

a first data store containing a plurality of items, each item corresponding to at least a first field and a second field, and representing values for each of the first and second fields;
a second data store containing an index of the plurality of items, wherein each item of the plurality of items is indexed within the index according to at least a cryptographic hash of the value of the first field represented by the item;
a plurality of secret sharing computing devices storing encrypted versions of the values of the second field represented by the plurality of items, the encrypted versions encrypted according to an order-preserving encryption algorithm, wherein each encrypted version is split according to a secret sharing algorithm into a plurality of shares stored among multiple secret sharing computing devices of the plurality of secret sharing computing devices;
and
a computing device configured to:
receive a search request specifying search criteria comprising a set of desired cryptographic hash values and sort criteria identifying the second field;
determine, from at least the index, one or more items, from the plurality of items, that satisfy the search criteria;
retrieve, from one or more of the plurality of secret sharing computing devices, encrypted versions of the values of the second field represented by the one or more items;
sort the one or more items according to the encrypted versions of the values of the second field represented by the one or more items;
and
return, in response to the search request, information identifying the one or more items and a sorting of the one or more items according to the encrypted versions of the values of the second field.

8 more elements

A method implemented by a system of one or more computers, wherein the method comprises:

maintaining, by the system, indexing information associated with items of information received from an information retrieval system, each item of information including a plurality of fields and values associated with the plurality of fields,
wherein indexing information includes, for each value, a cryptographic hash of the value and a plurality of secret shares of an order-preserved encrypted (OPE) value of the value, such that a quorum of secret shares are required to generate the OPE value;
receiving a search request indicating search criteria and sort criteria, wherein the search criteria is received as cryptographic hashes;
identifying, based on the index information, search results corresponding to the search criteria, and sorting the search results based on an obtained quorum of secret shares for each value, associated with the sort criteria, that is included in the search results;
and
providing, in response to the search request, information indicating sorted search results.

3 more elements

Non-transitory computer storage media storing instructions that when executed by a system of one or more computers, cause the system to perform operations, the system being in communication with one or more clients and one or more search engines, wherein the operations comprise:

obtaining, from a client, a request associated with storage of client information in a search engine of the one or more search engines;
generating first cryptographic information based on the client information, the first cryptographic information being cryptographically processed from a portion of the client information, wherein the first cryptographic information is to be utilized by the search engine for indexing;
generating second cryptographic information comprising performing an order-preserving encryption process on the portion of the client information, wherein the second cryptographic information is to be utilized by the search engine to recover an order associated with information included in the portion;
and
providing, for storage in the search engine, the first cryptographic information and the second cryptographic information.

2 more elements

Dependencies are inferred from the claim text.