Paper 2015/266

GRECS: Graph Encryption for Approximate Shortest Distance Queries

Xianrui Meng, Seny Kamara, Kobbi Nissim, and George Kollios


We propose graph encryption schemes that efficiently support approximate shortest distance queries on large-scale encrypted graphs. Shortest distance queries are one of the most fundamental graph operations and have a wide range of applications. Using such graph encryption schemes, a client can outsource large-scale privacy-sensitive graphs to an untrusted server without losing the ability to query it. Other applications include encrypted graph databases and controlled disclosure systems. We propose GRECS (stands for GRaph EnCryption for approximate Shortest distance queries) which includes three oracle encryption schemes that are provably secure against any semi-honest server. Our first construction makes use of only symmetric-key operations, resulting in a computationally-efficient construction. Our second scheme makes use of somewhat-homomorphic encryption and is less computationally-efficient but achieves optimal communication complexity (i.e. uses a minimal amount of bandwidth). Finally, our third scheme is both computationally-efficient and achieves optimal communication complexity at the cost of a small amount of additional leakage. We implemented and evaluated the efficiency of our constructions experimentally. The experiments demonstrate that our schemes are efficient and can be applied to graphs that scale up to 1.6 million nodes and 11 million edges.

Available format(s)
Publication info
Published elsewhere. MINOR revision.22nd ACM Conference on Computer and Communications Security (CCS) 2015
Graph encryptionstructured encryptiongraph algorithmsshortest distance queriessearchable encryption
Contact author(s)
xmeng @ cs bu edu
2015-10-21: last of 2 revisions
2015-03-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Xianrui Meng and Seny Kamara and Kobbi Nissim and George Kollios},
      title = {GRECS: Graph Encryption for Approximate Shortest Distance Queries},
      howpublished = {Cryptology ePrint Archive, Paper 2015/266},
      year = {2015},
      doi = {10.1145/2810103.2813672},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.