Granted Patent B1

US 9,679,155 · App. 14/738,473 · Granted Jun 13, 2017

Abstract

Claims (35)

1. A method for performing prefix search of encrypted cloud stored data comprising:

receiving, at a network intermediary, a search request with a search term directed to encrypted files stored in a cloud storage service, the cloud stored encrypted files being encrypted using an order-preserving encryption algorithm;

generating a minimum possible plaintext string using the search term as prefix and padding the search term to a first character length using one or more trailing characters indicative of a minimum possible value related to the search term;

generating a maximum possible plaintext string using the search term as prefix and padding the search term to the first character length using one or more trailing characters indicative of a maximum possible value related to the search term;

encrypting the minimum possible plaintext string and the maximum possible plaintext string using the order-preserving encryption algorithm used to encrypt the cloud stored encrypted files;

generating a minimum ciphertext from the minimum possible plaintext string and a maximum ciphertext from the maximum possible plaintext string;

determining a set of common leading digits from the minimum ciphertext and the maximum ciphertext;

generating a cloud service search request including the set of common leading digits as an encrypted prefix search term;

sending the cloud service search request with the encrypted prefix search term to the cloud storage service; and

receiving a search result from the cloud storage service.

2. The method of claim 1 , wherein receiving the search result from the cloud storage service comprises:

receiving the search result including a listing of document indexes identifying one or more encrypted files in the cloud storage service having an encrypted text with a prefix matching the encrypted prefix search term; and

providing the search result to a requesting user device.

3. The method of claim 1 , wherein receiving the search result from the cloud storage service comprises:

receiving the search result including an encrypted file stored in the cloud storage service having an encrypted text with a prefix matching the encrypted prefix search term;

decrypting the returned encrypted file; and

providing the decrypted file as the search result to a requesting user device.

4. The method of claim 1 , wherein generating the minimum possible plaintext string using the search term as prefix and padding the search term to the first character length using one or more trailing characters indicative of the minimum possible value related to the search term comprises:

determining the character type of the search term; and

padding one or more trailing characters to the search term using the minimum possible value associated with the character type of the search term.

5. The method of claim 4 , wherein padding one or more trailing characters to the search term using the minimum possible value associated with the character type of the search term comprises:

padding one or more trailing characters to the search term using the minimum possible value associated with the character type of the search term based on the ASCII values assigned to the character type.

6. The method of claim 1 , wherein generating the maximum possible plaintext string using the search term as prefix and padding the search term to the first character length using one or more trailing characters indicative of the maximum possible value related to the search term comprises:

determining the character type of the search term; and

padding one or more trailing characters to the search term using the maximum possible value associated with the character type of the search term.

7. The method of claim 6 , wherein padding one or more trailing characters to the search term using the maximum possible value associated with the character type of the search term comprises:

padding one or more trailing characters to the search term using the maximum possible value associated with the character type of the search term based on the ASCII values assigned to the character type.

8. A system for performing prefix search of encrypted cloud stored data, comprising:

a network proxy server comprising a computer and configured as a network intermediary between a user device and a cloud storage service storing encrypted files being encrypted using an order-preserving encryption algorithm, the network proxy server being configured to receive a search request with a search term directed to encrypted files stored in a cloud storage service, to generate a minimum possible plaintext string using the search term as prefix and padding the search term to a first character length using one or more trailing characters indicative of a minimum possible value related to the search term, to generate a maximum possible plaintext string using the search term as prefix and padding the search term to the first character length using one or more trailing characters indicative of a maximum possible value related to the search term, to encrypt the minimum possible plaintext string and the maximum possible plaintext string using the order-preserving encryption algorithm used to encrypt the cloud stored encrypted files, to generate a minimum ciphertext from the minimum possible plaintext string and a maximum ciphertext from the maximum possible plaintext string, to determine a set of common leading digits from the minimum ciphertext and the maximum ciphertext, to generate a cloud service search request including the set of common leading digits as an encrypted prefix search term, to send the cloud service search request with the encrypted prefix search term to the cloud storage service, and to receive a search result from the cloud storage service.

9. The system of claim 8 , wherein the network proxy server is further configured to receive the search result including a listing of document indexes identifying one or more encrypted files in the cloud storage service having an encrypted text with a prefix matching the encrypted prefix search term and to provide the search result to a requesting user device.

10. The system of claim 8 , wherein the network proxy server is further configured to receive the search result including an encrypted file stored in the cloud storage service having an encrypted text with a prefix matching the encrypted prefix search term, to decrypt the returned encrypted file, and to provide the decrypted file as the search result to a requesting user device.

11. The system of claim 8 , wherein the network proxy server is further configured to determine the character type of the search term and to pad one or more trailing characters to the search term using the minimum possible value associated with the character type of the search term.

12. The system of claim 11 , wherein the network proxy server is further configured to pad one or more trailing characters to the search term using the minimum possible value associated with the character type of the search term based on the ASCII values assigned to the character type.

13. The system of claim 8 , wherein the network proxy server is further configured to determine the character type of the search term and to pad one or more trailing characters to the search term using the maximum possible value associated with the character type of the search term.

14. The system of claim 13 , wherein the network proxy server is further configured to pad one or more trailing characters to the search term using the maximum possible value associated with the character type of the search term based on the ASCII values assigned to the character type.

Assignments (15)