Patent ID: 8130947
Filing Date: 2012-03-06
Classification: G06F,G06Q,H04L

Abstract:
1. A computer implemented method for privacy preserving network analysis, the method comprising: encrypting at a first system by a microprocessor a plurality of vertices of a first subgraph of a graph with a first key of a commutatively encryption scheme, wherein the first system hosts the first subgraph of the graph; sending to a second system the plurality of vertices of the first subgraph encrypted with the first key, wherein the second system hosts a second subgraph of the graph; receiving at the first system a plurality of vertices of the second subgraph of the graph encrypted with a second key from the commutatively encryption scheme, and the plurality of vertices of the first subgraph encrypted with the first key and commutatively encrypted with the second key; commutatively encrypting at the first system by the microprocessor with the first key the plurality of vertices of the second subgraph encrypted with the second key; creating a first matrix with rows and columns corresponding to a union between the plurality of commutatively encrypted vertices of the first subgraph and the plurality of commutatively encrypted vertices of the second subgraph, wherein each element of the first matrix stores a homomorphic threshold encryption of path length in the graph between the corresponding pair of commutatively encrypted vertices of the union; and computing a centrality metric of the graph for a selected vertex based on the first matrix.