Graph encryption

• US 8,874,930 B2
• Filed: 12/09/2009
• Issued: 10/28/2014
• Est. Priority Date: 12/09/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chase, Melissa E., Kamara, Seny F.
• Primary Examiner(s): Vaughan, Michael R
• Assistant Examiner(s): AVERY, JEREMIAH L
• Application Number:
  US12/633,867
• Publication Number:
  US 20110138190A1
• Time in Patent Office: 1,784 Days
• Field of Search: None
• US Class Current: 713/189
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries
• CPC Class Codes: H04L 2209/043 of tables, e.g. lookup, substitution or mapping
• CPC Class Codes: H04L 9/06 the encryption apparatus using shift registers or memories for block-wise or stream coding, e.g. DES systems or RC4; Hash functions; Pseudorandom sequence generators
• 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/0656 Pseudorandom key sequence combined element-for-element with data sequence, e.g. one-time-pad [OTP] or Vernam's cipher
• 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/321 involving a third party or a trusted authority

Abstract

A storage system stores information about a graph in an encrypted form. A query module can submit a token to the storage system to retrieve specified information about the graph, e.g., to determine the neighbors of an entity in the graph, or to determine whether a first entity is connected to a second entity, etc. The storage system formulates its reply to the token in a lookup result. Through this process, the storage system gives selective access to information about the graph to authorized agents, yet otherwise maintains the general secrecy of the graph from the perspective of unauthorized agents, including the storage system itself. A graph processing module can produce encrypted graph information by encrypting any representation of the graph, such as an adjacency matrix, an index, etc.

Claims

1. A method implemented using at least one computing device, the method comprising:

generating a representation of unencrypted graph information, the unencrypted graph information describing relationships among entities within a graph, wherein the entities are represented by nodes in the graph;

encrypting the representation of the unencrypted graph information using one or more keys to produce encrypted graph information;

sending the encrypted graph information over a network to a remote storage system for storage by the remote storage system;

using the one or more keys to generate a token associated with a graph query, the graph query seeking specified information that correctly identifies connectivity of an individual node in the graph, the individual node representing an individual entity;

sending the token over the network to the remote storage system; and

receiving, over the network, a lookup result from the remote storage system that provides the specified information that correctly identifies the connectivity of the individual node, the lookup result being provided in response to the token,

the specified information that correctly identifies the connectivity of the individual node being provided by the remote storage system without revealing the individual node to the remote storage system and without revealing the one or more keys to the remote storage system.

2. The method of claim 1, wherein the representation of the unencrypted graph information corresponds to an adjacency matrix associated with the graph, the adjacency matrix including a plurality of adjacency matrix elements.

3. The method of claim 2, wherein said encrypting comprises processing the adjacency matrix elements to produce respective output matrix elements that together constitute an output matrix.

4. The method of claim 3, wherein the one or more keys include a first key and a second key that is different than the first key, and said processing of the adjacency matrix elements comprises:

using the first key, determining locations of the output matrix elements based on respective locations of the adjacency matrix elements; and

using the second key, determining values of the output matrix elements based on respective values of the adjacency matrix elements, said processing having an effect of concealing the respective locations and the respective values of the adjacency matrix elements from the remote storage system both before the remote storage system has received the token and after the remote storage system has received the token.

5. The method of claim 4, wherein said determining locations uses a pseudo-random permutation operation to determine the locations of the output matrix elements.

6. The method of claim 4, wherein said determining values uses an encryption operation to determine the values of the output matrix elements.

7. The method of claim 1, wherein the representation of the unencrypted graph information corresponds to an index associated with the graph, the index being formed by associating document identifiers with the nodes in the graph and associating document contents with node relationship information in the graph.

8. The method of claim 7, wherein said encrypting comprises encrypting the index to produce an encrypted index.

9. The method of claim 1, further comprising encrypting data items associated with respective entities in the graph.

10. The method of claim 1, wherein the graph query seeks to determine whether the individual entity is connected to a second individual entity.

11. The method of claim 1, wherein said individual entity comprises a single entity, and the graph query seeks to determine a set of entities in the graph, each of which is connected to the individual entity.

20. The method of claim 1, wherein the specified information provided by the remote storage system correctly indicates whether the individual node representing the individual entity is connected to a second individual node representing a second individual entity without revealing the individual node or the second individual node to the remote storage system.

12. A storage system comprising:

a storage device configured to store encrypted graph information, the encrypted graph information associated with a graph comprising a plurality of nodes, wherein the encrypted graph information is encrypted with one or more keys;

computer readable instructions comprising;

logic configured to receive a token associated with a graph query, the graph query seeking specified information from the encrypted graph information relating to connectivity of an individual node in the graph to one or more other nodes in the graph,

logic configured to perform a lookup operation based on the token and the encrypted graph information to provide a lookup result, and

logic configured to send the lookup result in response to the token,

the lookup result correctly reflecting connectivity of the individual node to the one or more other nodes without revealing the individual node to the storage system and without revealing the one or more keys to the storage system; and

one or more processing devices configured to execute the computer readable instructions.

13. The storage system of claim 12, wherein the token is received from a query module over a network.

14. The storage system of claim 12, wherein the individual node represents a first entity and an individual other node represents a second entity, and wherein the lookup result correctly identifies whether the first entity is connected to the second entity without revealing the first entity or the second entity to the storage system.

15. The storage system of claim 12, wherein said graph query seeks to determine a set of entities in the graph, each of which is connected to an individual entity represented by the individual node, and the lookup result correctly identifies the set of entities without revealing the individual entity to the storage system.

16. The storage system of claim 12, wherein the lookup result is provided without revealing, to the storage system:

(a) identities of entities in the graph represented by the nodes; and

(b) relationships among the entities in the graph.

17. One or more computer readable memory devices or storage devices storing computer readable instructions which, when executed by one or more processing devices, cause the one or more processing devices to perform acts comprising:

processinq an input matrix to produce an output matrix, the input matrix including a plurality of input matrix elements representing nodes of a graph and the output matrix including a plurality of output matrix elements, wherein the processing comprises using at least one key to;

determine locations of the output matrix elements in the output matrix, the locations of the output matrix elements comprising scrambled respective locations of corresponding input matrix elements in the input matrix, and

determine values of the output matrix elements, the values of the output matrix elements comprising scrambled values of the corresponding input matrix elements,

said processing having an effect of concealing the input matrix,

wherein the scrambled respective locations comprise new random locations in the output matrix that are determined based on unscrambled locations of the input matrix elements, and

wherein the scrambled values and the scrambled respective locations, when unscrambled with the at least one key, correctly indicate whether individual nodes of the graph are connected.

18. The one or more computer readable memory devices or storage devices of claim 17, wherein said new random locations are determined using a pseudo-random permutation operation.

19. The one or more computer readable memory devices or storage devices of claim 17, wherein said scrambled values are determined using an encryption operation.

21. The one or more computer readable memory devices or storage devices of claim 17, the acts further comprising:

obtaining a query that seeks to determine whether a first entity is connected to a second entity, wherein an individual input matrix element indicates whether the first entity is connected to the second entity; and

using the at least one key to generate a token that expresses an individual scrambled location of the individual input matrix element in the output matrix.

22. The one or more computer readable memory devices or storage devices of claim 21, wherein the token is usable by a storage system storing the output matrix to resolve the query correctly without revealing the at least one key to the storage system, without revealing the first entity to the storage system, and without revealing the second entity to the storage system.