Private Graph: Privacy-Preserving Spectral Analysis of Encrypted Graphs in the Cloud

Abstract : With the wide deployment of public clouds, owners of big graphs want to use the cloud to handle the scalability issues. However, the privacy and ownership of the graphs in the cloud has become a major concern. In this paper, we study privacy-preserving algorithms for graph spectral analysis of outsourced encrypted graph in the cloud. We consider a cloud-centric framework with three collaborative parties: data contributors, data owner, and a honest-but-curious cloud provider. For a N×N graph matrix, our algorithms achieve a practical work allocation with preserved privacy: the cloud handles expensive storage and computation in O(N2) complexity, and data owner and data contributors' algorithms cost only O(N). We have developed the privacy-preserving versions of the two approximate eigendecomposition algorithms: the Lanczos algorithm and the Nyström algorithm, based on different encryption methods: additive homomorphic encryption (AHE) methods and somewhat homomorphic encryption (SHE) methods. Both dense and sparse matrices are studied, while sparse matrices also involve a differentially private data submission protocol to allow the trade-off between data sparsity and privacy. Experimental results show that the Nyströ algorithm with sparse encoding can dramatically reduce data owners' costs; SHE-based methods have lower computational time while AHE-based methods have lower communication costs.

 EXISTING SYSTEM :

 More recent works have achieved keyword privacy for keyword search over encrypted data, i.e., the keywords in queries are protected from the cloud server. Solutions for both single-keyword search and multi-keyword search have been proposed in the literature. Verifiable computation schemes aim to minimize computation effort of the client, but not storage or communication cost. They require the client and the server to interactively authenticate the computation result. Moreover, the client needs to have a copy of the outsourced data, and the data over which computation is verified cannot be changed in the future. Homomorphic message authenticator schemes which were proposed recently, avoid a local copy of the outsourced data on the client side. Homomorphic message authenticator schemes allow a client to authenticate a collection of data with his secret key sk, and later to authenticate the computation result of a running program over the data.

 DISADVANTAGE :

 Homomorphic message authenticator schemes which were proposed recently, avoid a local copy of the outsourced data on the client side. Homomorphic message authenticator schemes allow a client to authenticate a collection of data with his secret key sk, and later to authenticate the computation result of a running program over the data

 PROPOSED SYSTEM :

  In this paper, we investigate the problem of achieving verifiability for privacy-preserving multi-keyword search over encrypted cloud data. Different from the honest but- curious model used in existing privacy-preserving keyword search schemes, we assume a partially honest model, in which the cloud server may return wrong results due to system faults or incentive to reduce computation cost. We design an efficient, verifiable and privacy-preservingmulti-keyword ranked searchable encryption (MRSE)scheme for outsourced cloud data under the partiallyhonest cloud server model. It is realized by integratingan adapted homomorphic MAC technique with a privacypreservingmulti-keyword search scheme. The proposedscheme is very efficient as it relies on only one-wayfunction for security.

 ADVANTAGE :

 We also provide the random challenge technique to verifytop-k search results for a given query. With this solution,the client can be sure that the top-k results are authentic for probability close to 1. We provide detailed analysis on security, privacy, verifiabilityand efficiency of VPSearch. Specifically, theunderlying homomorphic MAC scheme used in VPSearchcan be proved to be secure.