Cryptology ePrint Archive: Report 2015/266

GRECS: Graph Encryption for Approximate Shortest Distance Queries

Xianrui Meng and Seny Kamara and 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.

Category / Keywords: Graph encryption; structured encryption; graph algorithms; shortest distance queries; searchable encryption

Original Publication (with minor differences): 22nd ACM Conference on Computer and Communications Security (CCS) 2015
DOI: 10.1145/2810103.2813672

Date: received 22 Mar 2015, last revised 21 Oct 2015

Contact author: xmeng at cs bu edu

Available format(s): PDF | BibTeX Citation

Version: 20151021:181730 (All versions of this report)

Short URL: ia.cr/2015/266

Discussion forum: Show discussion | Start new discussion