Encrypted search cloud service with cryptographic sharing

• US 10,592,685 B2
• Filed: 01/24/2018
• Issued: 03/17/2020
• Est. Priority Date: 04/27/2017
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Yeo, Kevin, Patel, Sarvar, Persiano, Giuseppe
• Primary Examiner(s): Rahman, Shawnchoy
• Application Number:
  US15/878,871
• Publication Number:
  US 20180314847A1
• Time in Patent Office: 783 Days
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries
• CPC Class Codes: H04L 63/0435 wherein the sending and receiving network entities apply symmetric encryption, i.e. same key used for encryption and decryption cryptographic mechanisms or cryptographic arrangements for symmetric key encryption H04L9/06
• CPC Class Codes: H04L 63/062 for key distribution, e.g. centrally by trusted party cryptographic mechanisms or cryptographic arrangements for key distribution involving a central third party H04L9/0819
• CPC Class Codes: H04L 63/08 for authentication of entities cryptographic mechanisms or cryptographic arrangements for entity authentication H04L9/32
• CPC Class Codes: H04L 63/10 for controlling access to devices or network resources
• CPC Class Codes: H04L 9/0631 Substitution permutation network [SPN], i.e. cipher composed of a number of stages or rounds each involving linear and nonlinear transformations, e.g. AES algorithms
• CPC Class Codes: H04L 9/0819 Key transport or distribution, i.e. key establishment techniques where one party creates or otherwise obtains a secret value, and securely transfers it to the other(s) network architectures or network communication protocols for key distribution in a packet data network H04L63/062
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/0866 involving user or device identifiers, e.g. serial number, physical or biometrical information, DNA, hand-signature or measurable physical characteristics
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage
• CPC Class Codes: H04L 9/3234 involving additional secure or trusted devices, e.g. TPM, smartcard, USB or software token network architectures or network communication protocols for supporting authentication of entities using an additional device in a packet data network H04L63/0853

Abstract

A method for sharing read access to a document stored on memory hardware. The method includes receiving a shared read access command from a sharor sharing read access to a sharee for a document stored on memory hardware in communication with the data processing hardware, and receiving a shared read access request from the sharee. The shared read access command includes an encrypted value and a first cryptographic share value based on a write key, a read key, a document identifier, and a sharee identifier. The method also includes multiplying the first and second cryptographic share values to determine a cryptographic read access value. The cryptographic read access value authorizes read access to the sharee for the document. The method also includes storing a read access token for the sharee including the cryptographic read access value and the encrypted value in a user read set of the memory hardware.

Claims

1. A method comprising:

receiving, at data processing hardware, a shared read access command from a sharor sharing read access to a sharee for a document stored on memory hardware in communication with the data processing hardware, the shared read access command comprising an encrypted value and a first cryptographic share value based on a write key for the document, a read key for the document, a document identifier identifying the document, and a sharee identifier identifying the sharee;

receiving, at the data processing hardware, a shared read access request from the sharee, the shared read access request comprising the sharee identifier, the document identifier, and a second cryptographic share value based on the read key for the document and a sharee cryptographic key associated with the sharee;

multiplying, by the data processing hardware, the first cryptographic share value and the second cryptographic share value to determine a cryptographic read access value, the cryptographic read access value authorizing read access to the sharee for the document; and

storing, by the data processing hardware, a read access token for the sharee in a user read set of the memory hardware, the read access token comprising the cryptographic read access value and the encrypted value, the user read set comprising a list of sharee identifiers associated with sharees having read access to the document.

2. The method of claim 1, wherein the sharor is configured to:

send the read key for the document to the sharee over a secure and authenticated communication link;

create metadata for the document;

compute the encrypted value by encrypting the metadata for the document using the read key; and

send the shared read access command to the data processing hardware.

3. The method of claim 1, wherein the first cryptographic share value is calculated based on a function of the write key and the document identifier divided by a function of the read key and the sharee identifier.

4. The method of claim 1, wherein the second cryptographic share value is calculated based on a function of the read key and the sharee identifier divided by a function of the sharee cryptographic key and the document identifier.

5. The method of claim 1, further comprising:

receiving, at the data processing hardware, a revoke read access command from the sharor revoking read access from the sharee for the document stored on the memory hardware; and

removing, by the data processing hardware, the read access token for the sharee from the user read set.

6. The method of claim 5, further comprising:

in response to receiving the revoke read access command, determining, by the data processing hardware, whether a corresponding write access token exists for the sharee in a user write set of the memory hardware; and

when the corresponding write access token exists, removing, by the data processing hardware, the write access token from the memory hardware.

7. The method of claim 1, further comprising, after storing the read access token for the sharee:

receiving, at the data processing hardware, a search query for a keyword in the document from the sharee, the search query comprising a cryptographic search value based on the read key for the document, the keyword, and the sharee cryptographic key associated with the sharee;

retrieving, by the data processing hardware, the read access token for the sharee from the user read set of the memory hardware;

computing, by the data processing hardware, a cryptographic word set token based on the received cryptographic search value and the retrieved read access token for the sharee;

determining, by the data processing hardware, whether the computed cryptographic word set token matches a corresponding cryptographic word set token of a word set stored in the memory hardware; and

when the computed cryptographic word set token matches the corresponding cryptographic word set token of the word set;

retrieving, by the data processing hardware, encrypted word metadata of the document associated with the keyword from the memory hardware; and

sending, by the data processing hardware, a search result set to the sharee, the search result set comprising the encrypted value and the encrypted word metadata.

8. The method of claim 7, wherein the sharee is configured to:

decrypt the encrypted value using the read key; and

decrypt the encrypted word metadata using the read key.

9. The method of claim 1, further comprising:

receiving, at the data processing hardware, a write access token from the sharee based on the write key for the document, the document identifier, the sharee identifier and the sharee cryptographic key; and

storing, by the data processing hardware, the write access token in a user write set of the memory hardware, the user write set comprising a list of sharee identifiers associated with sharees having write access to the document,

wherein the sharee is configured to receive the write key for the document from the sharor over a secure and authenticated communication link.

10. The method of claim 9, further comprising:

receiving, at the data processing hardware, a revoke write access command from the sharor revoking write access from the sharee for the document stored on the memory hardware; and

removing, by the data processing hardware, the write access token for the sharee from the user write set.

11. A method comprising:

receiving, at a sharee device associated with a sharee, shared write access permissions from a sharor sharing write access to the sharee for a document stored on a distributed storage system, the shared write access permissions comprising a read key for the document, a write key for the document, and encrypted metadata for the document;

determining, by the sharee device, a cryptographic write access value based on the write key for the document, a document identifier identifying the document, a sharee identifier identifying the sharee, and a sharee cryptographic key associated with the sharee, the cryptographic write access value authorizing write access to the sharee for the document; and

sending a write access token for the sharee from the sharee device to the distributed storage system, the write access token comprising the cryptographic write access value, the distributed storage system in response to receiving the write access token, configured to store the write access token in a user write set, the user write set comprising a list of sharee identifiers associated with sharees having write access to the document.

12. The method of claim 11, wherein the sharor is configured to revoke write access from the sharee for the document stored on the distributed storage system by sending a revoke write access command to the distributed storage system, the distributed storage system in response to receiving the revoke write access command, configured to remove the write access token for the sharee from the user write set.

13. The method of claim 11, further comprising:

determining, by the sharee device, a cryptographic read access value based on the write key for the document, the document identifier, and the sharee cryptographic key, the cryptographic read access value authorizing read access to the sharee for the document; and

sending a read access token for the sharee comprising the cryptographic read access value and the encrypted metadata for the document to the distributed storage system, the distributed storage system, in response to receiving the read access token, configured to store the read access token in a user read set, the user read set comprising a list of sharee identifiers associated with sharees having read access to the document.

14. The method of claim 13, wherein the sharor is configured to revoke read access from the sharee for the document stored on the distributed storage system by sending a revoke read access command to the distributed storage system, the distributed storage system in response to receiving the revoke read access command, configured to:

remove the write access token for the sharee from the user write set; and

remove the read access token for the sharee from the user read set.

15. The method of claim 11, wherein the sharor is configured to:

create the metadata for the document;

encrypt the metadata for the document using the read key; and

send the shared write access permissions to the sharee over a secure and authenticated communication link.

16. The method of claim 11, wherein receiving the shared write access permissions from the sharor comprises receiving the shared write access permissions from the sharor over a secure and authenticated communication link.

17. The method of claim 11, further comprising, after sending the write access token for the sharee to the distributed storage system:

creating, by the sharee device, word metadata for the document associated with a word in the document to be edited;

encrypting, by the sharee device, the word metadata using the read key for the document;

computing, by the user device, a cryptographic edit value based on the read key for the document, a word identifier associated with the word in the document to be edited, the sharee cryptographic key associated with the sharee, the sharee identifier and the write key for the document; and

sending an edit operation request comprising the cryptographic edit value, the edit operation request requesting the distributed storage system to process an edit operation on the word in the document to be edited.

18. The method of claim 17, wherein the distributed storage system, in response to receiving the edit operation request from the sharee device, is configured to:

retrieve the write access token from the user write set;

compute a cryptographic word set token based on the cryptographic edit value and the retrieved write access token for the sharee;

determine whether the edit operation requested by the edit operation request comprises a delete operation; and

when the edit operation requested by the edit operation request comprises a delete operation, process the delete operation by removing a corresponding cryptographic word set token of a word set stored by the distributed storage system.

19. The method of claim 17, wherein the distributed storage system, in response to receiving the edit operation request from the sharee device, is configured to:

retrieve the write access token from the user write set;

compute a cryptographic word set token based on the cryptographic edit value and the retrieved write access token for the sharee;

determine whether the edit operation requested by the edit operation request comprises an overwrite operation; and

when the edit operation requested by the edit operation request comprises an overwrite operation, process the overwrite operation by overwriting a corresponding cryptographic word set token of a word set stored by the distributed storage system with the computed cryptographic word set token and the encrypted word metadata.

20. The method of claim 17, wherein the distributed storage system, in response to receiving the edit operation request from the sharee device, is configured to:

retrieve the write access token from the user write set;

compute a cryptographic word set token based on the cryptographic edit value and the retrieved write access token for the sharee;

determine whether the edit operation requested by the edit operation request comprises an add operation; and

when the edit operation requested by the edit operation request comprises an add operation, process the add operation by adding the computed cryptographic word set token and the encrypted word metadata to a word set stored by the distributed storage system.

21. A system comprising:

a sharor device configured to create metadata for a document stored on a storage system, encrypt the metadata using a read key for the document and calculate a first cryptographic share value for the document, the first cryptographic share value based on a write key for the document, the read key, a document identifier identifying the document, and a sharee identifier identifying a sharee to receive shared read access to the document;

a sharee device associated with the sharee and configured to receive the read key for the document from the sharor device over a secure and authenticated communication channel and calculate a second cryptographic share value for the document, the second cryptographic share value based on based on the read key and a sharee cryptographic key associated with the sharee;

data processing hardware of the storage system in communication with the sharor device and the sharee device;

memory hardware in communication with the data processing hardware, the memory hardware storing instructions that when executed on the data processing hardware cause the data processing hardware to perform operations comprising;

receiving a shared read access command from the sharor device sharing read access to the sharee for the document, the shared read access command comprising the encrypted metadata for the document and the first cryptographic share value;

receiving a shared read access request from the sharee device, the shared read access request comprising the sharee identifier, the document identifier, and the second cryptographic share value;

determining a cryptographic read access value based on the first cryptographic share value and the second cryptographic share value, the cryptographic read access value authorizing read access to the sharee for the document; and

storing a read access token for the sharee comprising the cryptographic read access value and the encrypted value in a user read set of the memory hardware, the user read set comprising a list of sharee identifiers associated with sharees having read access to the document.

22. The system of claim 21, wherein determining the cryptographic read access value comprises multiplying the first cryptographic share value and the second cryptographic share value.

23. The system of claim 22, wherein the operations further comprise:

receiving a revoke read access command from the sharor device revoking read access from the sharee for the document stored on the storage system; and

removing the read access token for the sharee from the user read set.

24. The system of claim 23, wherein the operations further comprise:

in response to receiving the revoke read access command, determining whether a corresponding write access token exists for the sharee in a user write set of the memory hardware; and

when the corresponding write access token exists, removing the write access token from the memory hardware.

25. The system of claim 21, wherein the operations further comprise, after storing the read access token for the sharee:

receiving a search query for a keyword in the document from the sharee device, the search query comprising a cryptographic search value based on the read key for the document, the keyword, and the sharee cryptographic key associated with the sharee;

retrieving the read access token for the sharee from the user read set of the memory hardware;

computing a cryptographic word set token based on the received cryptographic search value and the retrieved read access token for the sharee;

determining whether the computed cryptographic word set token matches a corresponding cryptographic word set token of a word set stored in the memory hardware; and

when the computed cryptographic word set token matches the corresponding cryptographic word set token of the word set;

retrieving encrypted word metadata of the document associated with the keyword from the memory hardware; and

sending a search result set to the sharee device, the search result set comprising the encrypted document metadata and the encrypted word metadata.

26. The system of claim 25, wherein the sharee device is configured to:

decrypt the encrypted document metadata using the read key; and

decrypt the encrypted word metadata using the read key.

27. A system comprising:

a sharor device associated with a creator of a document stored on a distributed storage system;

a sharee device associated with a sharee in communication with the sharor device over a secure and authenticated communication channel, the sharee device configured to;

receive shared write access permissions from the sharor device sharing write access for the document, the shared write access permissions comprising a read key for the document, a write key for the document and encrypted metadata for the document;

determine a cryptographic write access value based on the write key, a document identifier identifying the document, a sharee identifier identifying the sharee, and a sharee cryptographic key associated with the sharee, the cryptographic write access value authorizing write access to the sharee for the document; and

determine a cryptographic read access value based on the write key for the document, the document identifier, and the sharee cryptographic key;

data processing hardware of the distributed storage system in communication with the sharor device and the sharee device; and

memory hardware in communication with the data processing hardware, the memory hardware storing instructions that when executed on the data processing hardware cause the data processing hardware to perform operations comprising;

receiving a write access token from the sharee device, the write access token comprising the cryptographic write access value;

storing the write access token in a user write set, the user write set comprising a list of sharee identifiers associated with sharees having write access to the document;

receiving a read access token for the sharee device comprising the cryptographic read access value and the encrypted metadata for the document from the sharee device; and

storing the read access token in a user read set, the user read set comprising a list of sharee identifiers associated with sharees having read access to the document.

28. The system of claim 27, wherein the operations further comprise:

receiving a revoke write access command from the sharor device to revoke write access from the sharee for the document stored on the distributed storage system; and

in response to receiving the revoke write access command, removing the write access token for the sharee from the user write set.

29. The system of claim 27, wherein the operations further comprise:

receiving a revoke read access command from the sharor device to revoke read access from the sharee for the document stored on the distributed storage system; and

in response to receiving the revoke read access command;

removing the write access token for the sharee from the user write set; and

removing the read access token for the sharee from the user read set.