Graph encryption

摘要

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.

主权项

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.