GRAPH ENCRYPTION

• US 20110138190A1
• Filed: 12/09/2009
• Published: 06/09/2011
• Est. Priority Date: 12/09/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kamara, Seny F., Chase, Melissa E.
• Granted Patent: US 8,874,930 B2
• Time in Patent Office: Days
• 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 for producing and querying encrypted graph information, the method being implemented using computing functionality, comprising:

generating a representation of unencrypted graph information, the unencrypted graph information describing relationships among entities within a graph;

encrypting the representation of the unencrypted graph information to produce encrypted graph information;

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

generating a token associated with a graph query, the graph query seeking specified information relating to at least one entity in the graph;

sending the token to the storage system; and

receiving, in response to the token, a lookup result from the storage system that provides the specified information,

the lookup result being provided without revealing at least aspects of the unencrypted graph information to unauthorized agents, one unauthorized agent being the storage system itself.

2. The method of claim 1, wherein the storage system corresponds to a network-accessible system for storing the encrypted graph information.

3. 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.

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

5. The method of claim 4, wherein said processing of the adjacency matrix elements comprises:

determining locations of the output matrix elements based on respective locations of the adjacency matrix elements; and

determining values of the output matrix elements based on respective values of the adjacency matrix elements,

said processing having an effect of concealing the locations and the values of the adjacency matrix elements.

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

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

8. 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 respective nodes in the graph, and associating document contents with node relationship information in the graph.

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

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

11. The method of claim 1, wherein said at least one entity comprises a first entity and a second entity, and wherein the graph query seeks to determine whether the first entity is connected to the second entity.

12. The method of claim 1, wherein said at least one 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 single entity.

13. A storage system implemented using computing functionality, comprising:

a storage module for storing encrypted graph information, the encrypted graph information associated with a graph; and

a lookup module for processing a graph query submitted by a query module, comprising;

logic configured to receive a token associated with the graph query, the graph query seeking specified information from the encrypted graph information relating to at least one entity 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 to the query module,

the lookup result being provided without revealing at least aspects of unencrypted graph information to unauthorized agents.

14. The storage system of claim 13, wherein the storage system corresponds to a network-accessible system for storing the encrypted graph information.

15. The storage system of claim 13, wherein said at least one entity comprises a first entity and a second entity, and wherein the graph query seeks to determine whether the first entity is connected to the second entity.

16. The storage system of claim 13, wherein said at least one 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 single entity.

17. The storage system of claim 13, wherein the lookup result is provided without revealing, to the storage system, at least one of:

(a) identities of entities in the graph; and

(b) relationships among entities in the graph.

18. A computer readable medium for storing computer readable instructions, the computer readable instructions providing an encryption module when executed by one or more processing devices, the computer readable instructions comprising:

logic configured to process an input matrix to produce an output matrix, the input matrix including a plurality of input matrix elements and the output matrix including a plurality of output matrix elements that together constitute an output matrix, said logic comprising;

logic configured to determine locations of the output matrix element based on respective locations of the input matrix elements; and

logic configured to determine values of the output matrix elements based on respective values of the input matrix elements,

said processing having an effect of concealing the locations and the values of the input matrix elements.

19. The computer readable medium of claim 18, wherein said logic configured to determine locations uses a pseudo-random permutation operation to determine the locations of the output matrix elements.

20. The computer readable medium of claim 18, wherein said logic configured to determine values uses an encryption operation to determine the values of the output matrix elements.