Paper 2015/266

GRECS: Graph Encryption for Approximate Shortest Distance Queries

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

Abstract

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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. MINOR revision.22nd ACM Conference on Computer and Communications Security (CCS) 2015
DOI
10.1145/2810103.2813672
Keywords
Graph encryptionstructured encryptiongraph algorithmsshortest distance queriessearchable encryption
Contact author(s)
xmeng @ cs bu edu
History
2015-10-21: last of 2 revisions
2015-03-23: received
See all versions
Short URL
https://ia.cr/2015/266
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/266,
      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{https://eprint.iacr.org/2015/266}},
      url = {https://eprint.iacr.org/2015/266}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.