TY - GEN
T1 - Privacy-preserving reachability query services for massive networks
AU - Jiang, Jiaxin
AU - Yi, Peipei
AU - CHOI, Koon Kau
AU - ZHANG, Zhiwei
AU - Yu, Xiaohui
N1 - Funding Information:
We thank Zhe Fan for his insightful comments on the earlier versions of this work. J. Jiang, P. Yi, B. Choi and Z. Zhang are partially supported by HKRGC GRFs 12201315 and 12232716, and HKBU FRG2/13-14/073.
PY - 2016/10/24
Y1 - 2016/10/24
N2 - This paper studies privacy-preserving reachability query services under the paradigm of data outsourcing. Specifically, graph data have been outsourced to a third-party service provider (SP), query clients submit their queries to the SP, and the SP returns the query answers to the clients. However, the SP may not always be trustworthy. Hence, this paper investigates protecting the structural information of the graph data and the query answers from the SP. Existing techniques are either insecure or not scalable. This paper proposes a privacy-preserving labeling, called ppTopo. To our knowledge, ppTopo is the first work that can produce reachability index on massive networks and is secure against known plaintext attacks (KPA). Specifically, we propose a scalable index construction algorithm by employing the idea of topological folding, recently proposed by Cheng et al. We propose a novel asymmetric scalar product encryption in modulo 3 (ASPE3). It allows us to encrypt the index labels and transforms the queries into scalar products of encrypted labels. We perform an experimental study of the proposed technique on the SNAP networks. Compared with the existing methods, our results show that our technique is capable of producing the encrypted indexes at least 5 times faster for massive networks and the client's decryption time is 2-3 times smaller for most graphs.
AB - This paper studies privacy-preserving reachability query services under the paradigm of data outsourcing. Specifically, graph data have been outsourced to a third-party service provider (SP), query clients submit their queries to the SP, and the SP returns the query answers to the clients. However, the SP may not always be trustworthy. Hence, this paper investigates protecting the structural information of the graph data and the query answers from the SP. Existing techniques are either insecure or not scalable. This paper proposes a privacy-preserving labeling, called ppTopo. To our knowledge, ppTopo is the first work that can produce reachability index on massive networks and is secure against known plaintext attacks (KPA). Specifically, we propose a scalable index construction algorithm by employing the idea of topological folding, recently proposed by Cheng et al. We propose a novel asymmetric scalar product encryption in modulo 3 (ASPE3). It allows us to encrypt the index labels and transforms the queries into scalar products of encrypted labels. We perform an experimental study of the proposed technique on the SNAP networks. Compared with the existing methods, our results show that our technique is capable of producing the encrypted indexes at least 5 times faster for massive networks and the client's decryption time is 2-3 times smaller for most graphs.
KW - Data and query privacies
KW - Graph databases
KW - Reachability queries
UR - http://www.scopus.com/inward/record.url?scp=84996569920&partnerID=8YFLogxK
U2 - 10.1145/2983323.2983799
DO - 10.1145/2983323.2983799
M3 - Conference proceeding
AN - SCOPUS:84996569920
T3 - International Conference on Information and Knowledge Management, Proceedings
SP - 145
EP - 154
BT - CIKM 2016 - Proceedings of the 2016 ACM Conference on Information and Knowledge Management
PB - Association for Computing Machinery (ACM)
T2 - 25th ACM International Conference on Information and Knowledge Management, CIKM 2016
Y2 - 24 October 2016 through 28 October 2016
ER -