FAST SEARCHABLE ENCRYPTION METHOD

• US 20090300351A1
• Filed: 05/29/2009
• Published: 12/03/2009
• Est. Priority Date: 05/30/2008
• Status: Abandoned Application

• Current Assignee: NEC Company Limited
• Original Assignee: NEC Company Limited
• Inventors: Fukushima, Toshikaza, Tian, Ye, Zeng, Ke, Wang, Liming, Lei, Hao
• Application Number:
  US12/474,785
• Publication Number:
  US 20090300351A1
• Time in Patent Office: Days
• US Class Current: 713/165
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/986 Document structures and storage, e.g. HTML extensions
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage

Abstract

The present invention provides a method, apparatus and system for fast searchable encryption. The data owner encrypts files and stores the ciphertext to the server. The data owner generates an encrypted index according to each keyword of the files, and stores the encrypted index to the server. The index is composed of keyword item sets each being identified by a keyword item set locator and containing at least one or more file locators of the files associated with the corresponding keyword. Each file locator contains ciphertext of information for retrieval of an encrypted file and only with the correct file locator decryption key can the ciphertext be decrypted. Data owner issues a keyword item set locator as well as file locator decryption key to a searcher to enable the searcher to search on the encrypted index and retrieve files related to a certain keyword.

Claims

1. A method for searchable encryption, comprising:

setting one or more file locator generation keys;

generating one or more keyword item set locators by mapping a string containing at least a keyword to a unique value;

generating one or more file locators by encrypting file acquisition information of each of a plurality of files with at least one file locator generation key; and

forming an encrypted index by one or more keyword item sets each being identified by a keyword item set locator and containing at least one or more file locators of the files associated with the corresponding keyword.

2. The method according to claim 1, further comprising:

setting a file encryption key for each file; and

encrypting each file with a corresponding file encryption key.

3. The method according to claim 1, wherein the file acquisition information comprises at least an encrypted resource identifier and a file decryption key of the file.

4. The method according to claim 3, wherein the file acquisition information further comprises a flag for confirmable decryption.

5. The method according to claim 1, wherein each file locator in a key item set is accompanied by an index locator, and the method further comprises:

generating an index locating indicator for each file by mapping a string containing at least an encrypted resource identifier of the file to an unique value; and

generating an index locator for each file locator in a key item set by mapping a string containing at least the file locator, the corresponding keyword item set locator and the index locating indicator of the file to a unique value.

6. The method according to claim 5, wherein the index locating indicator is generated as a hash value of a string containing at least the encrypted resource identifier and a secret key.

7. The method according to claim 1, wherein the keyword item set locator is generated as a hash value of a string containing at least the corresponding keyword and a master encryption key.

8. The method according to claim 1, wherein the keyword item set locator is generated by encrypting the corresponding keyword with a file locator generation key.

9. The method according to claim 1, wherein the one or more file locator generation keys are set in accordance with one or more privacy levels.

10. The method according to claim 9, wherein each file locator generation key is a hash value of a string containing at least a master encryption key and a value indicating the privacy level.

11. The method according to claim 9, wherein the file locator generation key of each privacy level is a hash value of the file locator generation key of a preceding higher privacy level.

12. The method according to claim 9, wherein the file locator generation key of each privacy level is d₀ power of the file locator generation key of a preceding lower privacy level, where d₀ is a privacy key.

13. The method according to claim 1, wherein each file locator generation key is a hash value of a string containing at least a keyword and a master encryption key.

14. An apparatus for searchable encryption, comprising:

an encryption/decryption setting unit configured to set one or more file locator generation keys;

a keyword item set locator generation unit configured to generate one or more keyword item set locators by mapping a string containing at least a keyword to a unique value; and

a file locator generation unit configured to generate one or more file locators by encrypting file acquisition information of each of a plurality of files with at least one file locator generation key; and

an index forming unit configured to form an encrypted index by one or more keyword item sets each being identified by a keyword item set locator and containing at least one or more file locators of the files associated with the corresponding keyword.

15. The apparatus according to claim 14, wherein the encryption/decryption setting unit is further configured to set a file encryption key for each of the plurality of files, and the apparatus further comprises a file encryption unit configured to encrypt each file with a corresponding file encryption key.

16. The apparatus according to claim 14, wherein the file acquisition information comprises at least an encrypted resource identifier and a file decryption key of the file.

17. The apparatus according to claim 16, wherein the file acquisition information further comprises a flag for confirmable decryption.

18. The apparatus according to claim 14, further comprising:

an index locating indicator generation unit configured to generate an index locating indicator for each file by mapping a string containing at least an encrypted resource identifier of the file to an unique value; and

an index locator generation unit configured to generate an index locator for each file locator in a key item set by mapping a string containing at least the file locator, the corresponding keyword item set locator and the index locating indicator of the file to a unique value,

wherein the index forming unit forms such encrypted index that each file locator in a key item set is accompanied by an associated index locator.

19. The apparatus according to claim 16, wherein the index locating indicator generation unit is configured to generate a hash value of a string containing at least the encrypted resource identifier and a secret key as the index locating indicator.

20. The apparatus according to claim 14, wherein the keyword item set locator generation unit is configured to generate a hash value of a string containing at least the corresponding keyword and a master encryption key as the keyword item set locator.

21. The apparatus according to claim 14, wherein the keyword item set locator generation unit is configured to generate the keyword item set locator by encrypting the corresponding keyword with a file locator generation key.

22. The apparatus according to claim 14, wherein the encryption/decryption setting unit is configure to set the one or more file locator generation keys in accordance with one or more privacy levels.

23. The apparatus according to claim 22, wherein the encryption/decryption setting unit is configure to set a hash value of a string containing at least a master encryption key and a value indicating the privacy level as the file locator generation key.

24. The apparatus according to claim 22, wherein the encryption/decryption setting unit is configured to set the file locator generation key of each privacy level to a hash value of the file locator generation key of a preceding higher privacy level.

25. The apparatus according to claim 22, wherein the encryption/decryption setting unit is configured to set the file locator generation key of each privacy level to d₀ power of the file locator generation key of a preceding lower privacy level, where d₀ is a privacy key.

26. The apparatus according to claim 14, wherein the encryption/decryption setting unit is configured to set a hash value of a string containing at least a keyword and a master encryption key as the file locator generation key.

27. A method used in encrypted file search, comprising:

storing an encrypted index comprising one or more keyword item sets, each keyword item set being identified by a keyword item set locator and containing at least one or more file locators each accompanied by an index locator;

receiving an index locating indicator; and

deleting a file locator from a keyword item set if the index locator accompanying the file locator equals to a value calculated by mapping a string containing at least the file locator, the keyword item set locator identifying the keyword item set and the received index locating indicator.

28. The method according to claim 27, further comprising:

receiving one or more keyword item set locators; and

searching for one or more keyword item set identified by the received one or more keyword item set locators,

wherein the deleting is performed within said one or more keyword item set.

29. The method according to claim 27, further comprising:

receiving a keyword item set locator;

searching for a keyword item set identified by the received keyword item set locator;

outputting file locators contained in said keyword item set;

receiving a set of encrypted resource identifiers; and

outputting encrypted files identified by encrypted resource identifiers which match the received encrypted resource identifiers.

30. The method according to claim 29, further comprising filtering out encrypted resource identifiers of encrypted files to be excluded in search from the set of encrypted resource identifiers after receiving the set of encrypted resource identifiers.

31. An apparatus used in encrypted file search, comprising:

a storage unit configured to store an encrypted index comprising one or more keyword item sets, each keyword item set being identified by a keyword item set locator and containing at least one or more file locators each accompanied by an index locator; and

an index updating unit configured to delete a file locator from a keyword item set if the index locator accompanying the file locator equals to a value calculated by mapping a string containing at least the file locator, the keyword item set locator identifying the keyword item set, and a received index locating indicator.

32. The apparatus according to claim 31, further comprising:

an index search unit configured to search for a keyword item set identified by a keyword item set locator in the encrypted index.

33. The apparatus according to claim 31, further comprising:

a file search unit configured to search for an encrypted files identified by an encrypted resource identifier.

34. The apparatus according to claim 33, further comprising:

a filter unit configured to filter out encrypted resource identifiers of files to be excluded in search from a received set of encrypted resource identifiers.

35. A method for encrypted file search, comprising:

receiving a keyword item set locator and a file locator decryption key;

retrieving one or more file locators with the keyword item set locator;

decrypting each file locator with the file locator decryption key to derive one or more encrypted resource identifiers and corresponding file decryption keys;

retrieving one or more encrypted files identified by the one or more encrypted resource identifier; and

decrypting each encrypted file with the corresponding file decryption key.

36. The method according to claim 35, further comprising:

receiving a flag; and

confirming decryption of each file locator by comparing the received flag with a flag derived from the decryption of the file locator.

37. The method according to claim 35, further comprising:

computing a hash value of the file locator decryption key to obtain the file locator decryption key of a lower privacy level.

38. The method according to claim 35, further comprising:

computing e₀ power of the file locator decryption key to obtain the file locator decryption key of a lower privacy level, where e₀ is a public key.

39. An apparatus for encrypted file search, comprising:

a search request unit configured to generate a search request containing at least a keyword item set locator;

a file locator decryption unit configured to decrypt one or more file locators with a file locator decryption key to derive one or more encrypted resource identifiers and corresponding file decryption keys;

a file acquisition unit configured to retrieve one or more encrypted files identified by the one or more encrypted resource identifier; and

a file decryption unit configured to decrypt each encrypted file with the corresponding file decryption key.

40. The apparatus according to claim 39, wherein the file locator decryption unit is further configured to confirm decryption of each file locator by comparing a received flag with a flag derived from the decryption of the file locator.

41. The apparatus according to claim 39, wherein the file locator decryption unit is further configured to compute a hash value of the file locator decryption key to obtain the file locator decryption key of a lower privacy level.

42. The apparatus according to claim 39, wherein the file locator decryption unit is further configured to compute e₀ power of the file locator decryption key to obtain the file locator decryption key of a lower privacy level, where e₀ is a public key.