×

PGAS: privacy-preserving graph encryption for accurate constrained shortest distance queries. (English) Zbl 1456.68035

Summary: The constrained shortest distance (CSD) query is used to determine the shortest distance between two vertices of a graph while ensuring that the total cost remains lower than a given threshold. The virtually unlimited storage and processing capabilities of cloud computing have enabled the graph owners to outsource their graph data to cloud servers. However, it may introduce privacy challenges that are difficult to address. In recent years, some relevant schemes that support the shortest distance query on the encrypted graph have been proposed. Unfortunately, some of them have unacceptable query accuracy, and some of them leak sensitive information that jeopardizes the graph privacy. In this work, we propose Privacy-preserving Graph encryption for Accurate constrained Shortest distance queries, called PGAS. This solution is capable of providing accurate CSD queries and ensures the privacy of the graph data. Besides, we also propose a secure integer comparison protocol and a secure minimum value protocol that realize two kinds of operations on encrypted integers. We provide theoretical security analysis to prove that PGAS achieves CQA-2 Security with less privacy leakage. In addition, the performance analysis and experimental evaluation based on real-world dataset show that PGAS achieves 100% accuracy with acceptable efficiency.

MSC:

68P25 Data encryption (aspects in computer science)

Software:

GraphLab; GRECS
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Akiba, T.; Iwata, Y.; Yoshida, Y., Fast exact shortest-path distance queries on large networks by pruned landmark labeling, Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2013, New York, NY, USA, June 22-27, 2013, 349-360 (2013)
[2] Bode, C.; Irnich, S., The shortest-path problem with resource constraints with (k, 2)-loop elimination and its application to the capacitated arc-routing problem, Eur. J. Oper. Res., 238, 2, 415-426 (2014) · Zbl 1338.90423
[3] Boneh, D.; Goh, E.; Nissim, K., Evaluating 2-DNF formulas on ciphertexts, Theory of Cryptography, Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, USA, February 10-12, 2005, Proceedings, 325-341 (2005) · Zbl 1079.94534
[4] Cao, N.; Yang, Z.; Wang, C.; Ren, K.; Lou, W., Privacy-preserving query over encrypted graph-structured data in cloud computing, 2011 International Conference on Distributed Computing Systems, ICDCS 2011, Minneapolis, Minnesota, USA, June 20-24, 2011, 393-402 (2011)
[5] Chase, M.; Kamara, S., Structured encryption and controlled disclosure, Advances in Cryptology - ASIACRYPT 2010 - 16th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 5-9, 2010. Proceedings, 577-594 (2010) · Zbl 1253.94042
[6] Cramer, R.; Shoup, V., Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption, Advances in Cryptology - EUROCRYPT 2002, International Conference on the Theory and Applications of Cryptographic Techniques, Amsterdam, The Netherlands, April 28-May 2, 2002, Proceedings, 45-64 (2002) · Zbl 1055.94011
[7] Curtmola, R.; Garay, J. A.; Kamara, S.; Ostrovsky, R., Searchable symmetric encryption: improved definitions and efficient constructions, J. Comput. Secur., 19, 5, 895-934 (2011)
[8] Gentry, C., Fully homomorphic encryption using ideal lattices, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31-June 2, 2009, 169-178 (2009) · Zbl 1304.94059
[9] Gentry, C.; Sahai, A.; Waters, B., Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based, Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I, 75-92 (2013) · Zbl 1310.94148
[10] Grubbs, P.; Sekniqi, K.; Bindschaedler, V.; Naveed, M.; Ristenpart, T., Leakage-abuse attacks against order-revealing encryption, 2017 IEEE Symposium on Security and Privacy, SP 2017, San Jose, CA, USA, May 22-26, 2017, 655-672 (2017)
[11] Hansen, P., Bicriterion path problems, (Fandel, G.; Gal, T., Multiple Criteria Decision Making Theory and Application (1980), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 109-127 · Zbl 0444.90098
[12] Hassin, R., Approximation schemes for the restricted shortest path problem, Math. Oper. Res., 17, 1, 36-42 (1992) · Zbl 0763.90083
[13] Huang, X.; Yu, R.; Kang, J.; Wang, N.; Maharjan, S.; Zhang, Y., Software defined networking with pseudonym systems for secure vehicular clouds, IEEE Access, 4, 3522-3534 (2016)
[14] Kang, J.; Yu, R.; Huang, X.; Maharjan, S.; Zhang, Y., On-demand pseudonym systems in geo-distributed mobile cloud computing, 3rd IEEE International Conference on Cyber Security and Cloud Computing, CSCloud 2016, Beijing, China, June 25-27, 2016, 136-141 (2016)
[15] Keller, M.; Scholl, P., Efficient, oblivious data structures for MPC, Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014, Proceedings, Part II, 506-525 (2014) · Zbl 1317.94116
[16] Ko, S.; Han, W., Turbograph++: A scalable and fast graph analytics system, Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference 2018, Houston, TX, USA, June 10-15, 2018, 395-410 (2018)
[17] Lewi, K.; Wu, D. J., Order-revealing encryption: new constructions, applications, and lower bounds, Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24-28, 2016, 1167-1178 (2016)
[18] Li, J.; Lin, D.; Squicciarini, A. C.; Li, J.; Jia, C., Towards privacy-preserving storage and retrieval in multiple clouds, IEEE Trans. Cloud Comput., 5, 3, 499-509 (2017)
[19] Li, T.; Liu, Z.; Jia, C.; Fu, Z.; Li, J., Key-aggregate searchable encryption under multi-owner setting for group data sharing in the cloud, IJWGS, 14, 1, 21-43 (2018)
[20] Liu, X.; Choo, K. R.; Deng, R. H.; Lu, R.; Weng, J., Efficient and privacy-preserving outsourced calculation of rational numbers, IEEE Trans. Dependable Sec. Comput., 15, 1, 27-39 (2018)
[21] Liu, X.; Deng, R. H.; Choo, K. R.; Weng, J., An efficient privacy-preserving outsourced calculation toolkit with multiple keys, IEEE Trans. Inf. Forensics Secur., 11, 11, 2401-2414 (2016)
[22] Liu, Z.; Li, T.; Li, P.; Jia, C.; Li, J., Verifiable searchable encryption with aggregate keys for data sharing system, Future Gener. Comput. Syst., 78, 778-788 (2018)
[23] Low, Y.; Gonzalez, J.; Kyrola, A.; Bickson, D.; Guestrin, C.; Hellerstein, J. M., Graphlab: a new framework for parallel machine learning, UAI 2010, Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence, Catalina Island, CA, USA, July 8-11, 2010, 340-349 (2010)
[24] Meng, X.; Kamara, S.; Nissim, K.; Kollios, G., GRECS: graph encryption for approximate shortest distance queries, Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, CO, USA, October 12-16, 2015, 504-517 (2015)
[25] Miao, Y.; Weng, J.; Liu, X.; Choo, K. R.; Liu, Z.; Li, H., Enabling verifiable multiple keywords search over encrypted cloud data, Inf. Sci., 465, 21-37 (2018)
[26] Mouratidis, K.; Yiu, M. L., Shortest path computation with no information leakage, PVLDB, 5, 8, 692-703 (2012)
[27] Naveed, M.; Kamara, S.; Wright, C. V., Inference attacks on property-preserving encrypted databases, Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, CO, USA, October 12-16, 2015, 644-655 (2015)
[28] Qin, Z.; Yu, T.; Yang, Y.; Khalil, I.; Xiao, X.; Ren, K., Generating synthetic decentralized social graphs with local differential privacy, Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, Dallas, TX, USA, October 30-November 03, 2017, 425-438 (2017)
[29] Sharma, S.; Powers, J.; Chen, K., Privategraph: privacy-preserving spectral analysis of encrypted graphs in the cloud, IEEE Trans. Knowl. Data Eng., 31, 5, 981-995 (2019)
[30] Shen, M.; Ma, B.; Zhu, L.; Mijumbi, R.; Du, X.; Hu, J., Cloud-based approximate constrained shortest distance queries over encrypted graphs with privacy protection, IEEE Trans. Inf. Forensics Secur., 13, 4, 940-953 (2018)
[31] Song, D. X.; Wagner, D. A.; Perrig, A., Practical techniques for searches on encrypted data, 2000 IEEE Symposium on Security and Privacy, Berkeley, California, USA, May 14-17, 2000, 44-55 (2000)
[32] Storandt, S., Route planning for bicycles - exact constrained shortest paths made practical via contraction hierarchy, Proceedings of the Twenty-Second International Conference on Automated Planning and Scheduling, ICAPS 2012, Atibaia, São Paulo, Brazil, June 25-19, 2012 (2012)
[33] Tsaggouris, G.; Zaroliagis, C. D., Multiobjective optimization: improved FPTAS for shortest paths and non-linear objectives with applications, Theory Comput. Syst., 45, 1, 162-186 (2009) · Zbl 1175.90366
[34] van Dijk, M.; Gentry, C.; Halevi, S.; Vaikuntanathan, V., Fully homomorphic encryption over the integers, Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30-June 3, 2010. Proceedings, 24-43 (2010) · Zbl 1279.94130
[35] Wang, S.; Xiao, X.; Yang, Y.; Lin, W., Effective indexing for approximate constrained shortest path queries on large road networks, PVLDB, 10, 2, 61-72 (2016)
[36] Wang, X.; Chen, W.; Chou, J.; Bryan, C.; Guan, H.; Chen, W.; Pan, R.; Ma, K., Graphprotector: a visual interface for employing and assessing multiple privacy preserving graph algorithms, IEEE Trans. Vis. Comput. Graph., 25, 1, 193-203 (2019)
[37] Wang, X. S.; Nayak, K.; Liu, C.; Chan, T. H.; Shi, E.; Stefanov, E.; Huang, Y., Oblivious data structures, Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, Scottsdale, AZ, USA, November 3-7, 2014, 215-226 (2014)
[38] Xue, K.; Hong, J.; Ma, Y.; Wei, D. S.L.; Hong, P.; Yu, N., Fog-aided verifiable privacy preserving access control for latency-sensitive data sharing in vehicular cloud computing, IEEE Netw., 32, 3, 7-13 (2018)
[39] Xue, K.; Li, S.; Hong, J.; Xue, Y.; Yu, N.; Hong, P., Two-cloud secure database for numeric-related SQL range queries with privacy preserving, IEEE Trans. Inf. Forensics Secur., 12, 7, 1596-1608 (2017)
[40] Yang, Y.; Li, Z.; Wang, X.; Hu, Q., Finding the shortest path with vertex constraint over large graphs, Complexity, 2019, 8728245:1-8728245:13 (2019) · Zbl 1420.05171
[41] Yang, Y.; Liu, X.; Deng, R. H., Expressive query over outsourced encrypted data, Inf. Sci., 442-443, 33-53 (2018) · Zbl 1440.68066
[42] Zhang, C.; Zhu, L.; Xu, C., PTBI: an efficient privacy-preserving biometric identification based on perturbed term in the cloud, Inf. Sci., 409, 56-67 (2017)
[43] Zhang, C.; Zhu, L.; Xu, C.; Sharif, K.; Liu, X., PPTDS: a privacy-preserving truth discovery scheme in crowd sensing systems, Inf. Sci., 484, 183-196 (2019)
[44] Zhang, Y.; Chen, X.; Li, J.; Wong, D. S.; Li, H.; You, I., Ensuring attribute privacy protection and fast decryption for outsourced data security in mobile cloud computing, Inf. Sci., 379, 42-61 (2017) · Zbl 1429.68068
[45] Zhou, R.; Zhang, X.; Du, X.; Wang, X.; Yang, G.; Guizani, M., File-centric multi-key aggregate keyword searchable encryption for industrial internet of things, IEEE Trans. Ind. Inf., 14, 8, 3648-3658 (2018)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.