Computer Science

Computer Science ›› 2024, Vol. 51 ›› Issue (5): 400-413.doi: 10.11896/jsjkx.230200031

• Information Security • Previous Articles     Next Articles

Correctness Verifiable Outsourcing Computation Scheme of Shortest Path Querying over Encrypted Graph Data

DING Hongfa1,2, YU Yingying1, JIANG Heling1   

  1. 1 College of Information,Guizhou Key Laboratory of Big Data Statistical Analysis,Guizhou University of Finance and Economics,Guiyang 550025,China
    2 State Key Laboratory of Pubic Big Data,Guizhou University,Guiyang 550025,China
  • Received:2023-02-06 Revised:2023-06-21 Online:2024-05-15 Published:2024-05-08
  • About author:DING Hongfa,born in 1988,Ph.D,associate professor,master supervisor,is a member of CCF(No.36866M).His main research interests include data security and privacy protection,cryptographic algorithm and protocol design.
  • Supported by:
    National Natural Science Foundation of China(62002080) and Natural Science Researching Program of D.o.E. of Guizhou(Qian Edu. & Tech. [2023] 065, Qian Edu. & Tech. [2023]014).

PDF (PC)

277

Abstract: Mass graph data such as geolocation and social networks are widely used and contain massive privacy,usually,it requires varied query services through secure outsourcing computation schemes.However,it is still an open challenge to design correctness verifiable outsourcing computation protocols for graph data.To this end,a correctness-verifiable outsourcing computation scheme of accurate shortest path over encrypted graph data is proposed.In this scheme,a breadth-first shortest path algorithm for encrypted graph data is constructed by using additive homomorphic encryption to support the outsourcing computation of exact shortest distance queries over encrypted graph data.Secondly,a probabilistic correctness verification mechanism of shortest path outsourcing computation result is constructed by using the bilinear mapping accumulator.Analysis and proof show that this scheme implements the correctness-verifiable accurate shortest path outsourcing computation with probabilistic reliability,it has the security of IND-CCA2 under the random oracle model.Comparisons and experiments indicate that the proposed scheme has significant advantages compared with other related schemes in terms of security and functionality,compared with existing verifiable graph data outsourcing computation schemes,the overheads in the initialization and encryption phase,the query phase,and the verification and decryption phase reduces by 0.15%~23.19%,12.91%~30.89% and 1.13%~18.62%,respectively.

Key words: Graph data outsourcing computation, Verifiable, Shortest path query, Cryptographic accumulator, Homomorphic encryption

CLC Number: 

  • TP309
[1]SAFIOLLAH H,YOGESH S,CALHEIROS R N,et al.Scalable graph processing frameworks:A taxonomy and open challenges [J].ACM Computing Surveys,2018,51(3):1-53.
[2]RAJ E D,MANOGARAN G,SRIVASTAVA G,et al.Information granulation-based community detection for social networks [J].IEEE Transactions on Computational Social Systems,2021,8(1):122-133.
[3]JI S L,MITTAL P,BEYAH R.Graph data anonymization,de-anonymization attacks,and de-anonymizability quantification:a survey [J].IEEE Communications Surveys & Tutorials,2017,19(2):1305-1326.
[4]QIAN J W,LI X Y,ZHANG C H,et al.Social network de-anony-mization and privacy inference with knowledge graph model [J].IEEE Transactions on Dependable & Secure Computing,2019,16(4):679-692.
[5]ZHANG Z C.Facebook data breach study [J].Youth Journalist,2018,(24):89-90.
[6]BOSCH C,HARTEL P,JONKER W,et al.A survey of pro-vably secure searchable encryption [J].ACM Computing Surveys,2014,47(2):1-51.
[7]CASH D,JARECKI S,JUTLA C,et al.Highly-scalable searcha-ble symmetric encryption with support for Boolean queries[C]//2013 CRYPTO 33rd Annual Cryptology Conference.Springer,2013:353-373.
[8]CHASE M,KAMARA S.Structured encryption and controlled disclosure [C]//2010 ASIACRYPT 16th International Confe-rence on the Theory and Application of Cryptology and Information Security.Springer,2010:577-594.
[9]PENG Y,FAN Z,CHOI B,et al.Authenticated subgraph similarity search in outsourced graph databases [J].IEEE Transactions on Knowledge & Data Engineering,2015,27(7):1838-1860.
[10]YAO X,ZOU Y Z,CHEN Z G,et al.Topic-based rank search with verifiable social data outsourcing [J].Journal of Parallel and Distributed Computing,2019,134:1-12.
[11]SUNTACI G,GHAZI A,BOHM K.Secrecy and performance models for query processing on outsourced graph data [J].Dis-tributed and Parallel Databases,2021,39(1):35-77.
[12]CHANG Z,ZOU L,LI F F.Privacy preserving subgraph ma-tching on large graphs in cloud [C]//the 2016 International Conference on Management of Data.ACM,2016:199-2123.
[13]XU Z F,ZHOU F C,LI Y X,et al.Privacy-preserving subgraph matching protocol for two parties [J].International Journal of Foundations of Computer Science,2019,30(4):571-588.
[14]ZHOU F C,XU Z F,LI Y X,et al.Private graph intersection protocol [C]//the 22nd Australasian Conference on Information Security and Privacy.Springer,2017:235-248.
[15]HU M D,CHEN L X.Top-H Query on Structured EncryptedGraph [J].Journal of Cryptologic Research,2023,10(6):1183-1196.
[16]YIN S X,ZHE F,YI P P,et al.Privacy-preserving reachability query services [C]//International Conference on Database Systems for Advanced Applications.2014:203-219.
[17]MENG X R,KAMARA S,NISSIM K,et al.GRECS:Graph encryption for approximate shortest distance queries [C]//the 22nd ACM SIGSAC Conference on Computer and Communications Security.ACM,2015:504-517.
[18]ZHU H,WU B,XIE M Y,et al.Secure shortest path searchover encrypted graph supporting synonym query in cloud computing [C]//The 15th IEEE International Conference on Trust,Security,and Privacy in Computing and Communications.IEEE,2016:497-504.
[19]SHEN M,MA B L,ZHU L H,et al.Cloud-based approximate constrained shortest distance queries over encrypted graphs with privacy protection [J].IEEE Transactions on Information Forensics and Security,2018,13(4):940-953.
[20]LIU C,ZHU L H,HE X J,et al.Enabling privacy-preservingshortest distance queries on encrypted graph data [J].IEEE Transactions on Dependable and Secure Computing,2021,18(1):192-204.
[21]WANG Q,REN K,DU M M,et al.SecGDB:Graph encryption for exact shortest distance queries with efficient updates [C]//the 21st International Conference on Financial Cryptography and Data Security.Springer,2017:79-97.
[22]ZHANG C,ZHU L H,XU C,et al.PGAS:Privacy-preserving graph encryption for accurate constrained shortest distance queries [J].Information Sciences,2020,506:325-345.
[23]YU Y Y,DING H F,JIANG H L.Privacy-Preserving Out-sourced Computation Scheme for Accurate Shortest Distance of Graph Data[J].Computer Engineering,2023,49(9):158-171.
[24]GENNARO R,GENTRY C,PARNO B.Non-interactive verifiable computing:outsourcing computation to untrusted workers [C]//2010 CRYPTO 30th Annual Cryptology Conference.Springer,2010:465-482.
[25]FAN Z,PENG Y,CHOI B,et al.Towards efficient authenticated subgraph query service in outsourced graph databases [J].IEEE Transactions on Services Computing,2014,7(4):696-713.
[26]CHEN H W,QU Q,LIN Y X,et al.Authenticityverification onsocial data outsourcing [J].Computers & Security,2021,100(1):102077.
[27]YAO X,ZHANG R,ZHANG Y C,et al.Verifiable social data outsourcing [C]//the 2017 IEEE Conference on Computer Communications.IEEE,2017:1-9.
[28]YAO X,ZHANG R,HUANG D Q,et al.Verifiable query proces-sing over outsourced social graph[J].IEEE/ACM Transactions on Networking,2021,29(5):2312-2326.
[29]ZUO X J,LI L X,LUO S S,et al.Privacy-preserving verifiable graph intersection scheme with cryptographic accumulators in social networks[J].IEEE Internet of Things Journal,2021,8(6):4590-4603.
[30]ZHU Y X,LI H,CUI J T,et al.Verifiable subgraph matching with cryptographic accumulators in cloud computing [J].IEEE Access,2019,7:169636-169645.
[31]LIU X Y,LI J J,AN Y Z,et al.Efficient algorithm on anonymi-zing social networks with reachability preservation [J].Ruan Jian Xue Bao/Journal of Software,2016,27(8):1904-1921.
[32]WEI C K,JI S L,LIU C C,et al.AsgLDP:Collecting and gene-rating decentralized attributed graphs with local differential privacy [J].IEEE Transactions on Information Forensics and Security,2020,15(1):3239-3254.
[1] GUO Chuntong, WU Wenyuan. Verifiable Decryption Scheme Based on MLWE and MSIS [J]. Computer Science, 2024, 51(5): 331-345.
[2] LU Xingyuan, CHEN Jingwei, FENG Yong, WU Wenyuan. Privacy-preserving Data Classification Protocol Based on Homomorphic Encryption [J]. Computer Science, 2023, 50(8): 321-332.
[3] GAO Guangyong, HAN Tingting, XIA Zhihua. Recoverable Data Aggregation Protocol for Wireless Sensor Networks Based on Reversible DigitalWatermarking [J]. Computer Science, 2023, 50(8): 333-341.
[4] HUANG Baohua, PENG Li, ZHAO Weihong, CHEN Ningjiang. Practical Byzantine Consensus Algorithm Based on Verifiable Random Functions [J]. Computer Science, 2023, 50(6A): 220300064-6.
[5] ZHAO Min, TIAN Youliang, XIONG Jinbo, BI Renwan, XIE Hongtao. Neural Network Model Training Method Based on Homomorphic Encryption [J]. Computer Science, 2023, 50(5): 372-381.
[6] LYU You, WU Wen-yuan. Privacy-preserving Linear Regression Scheme and Its Application [J]. Computer Science, 2022, 49(9): 318-325.
[7] QIN Xiao-yue, HUANG Ru-wei, YANG Bo. NTRU Type Fully Homomorphic Encryption Scheme over Prime Power Cyclotomic Rings [J]. Computer Science, 2022, 49(5): 341-346.
[8] LYU You, WU Wen-yuan. Linear System Solving Scheme Based on Homomorphic Encryption [J]. Computer Science, 2022, 49(3): 338-345.
[9] REN Hua, NIU Shao-zhang, WANG Mao-sen, YUE Zhen, REN Ru-yong. Homomorphic and Commutative Fragile Zero-watermarking Based on SVD [J]. Computer Science, 2022, 49(3): 70-76.
[10] WANG Meng-yu, YIN Xin-chun, NING Jian-ting. Lightweight Medical Data Sharing Scheme with Access Policy Hiding and Key Tracking [J]. Computer Science, 2022, 49(3): 77-85.
[11] YANG Hong-jian, HU Xue-xian, LI Ke-jia, XU Yang, WEI Jiang-hong. Study on Privacy-preserving Nonlinear Federated Support Vector Machines [J]. Computer Science, 2022, 49(12): 22-32.
[12] GUO Yan-qing, LI Yu-hang, WANG Wan-wan, FU Hai-yan, WU Ming-kan, LI Yi. FL-GRM:Gamma Regression Algorithm Based on Federated Learning [J]. Computer Science, 2022, 49(12): 66-73.
[13] CHEN Bin, XU Huan, XI Jian-fei, LEI Mei-lian, ZHANG Rui, QIN Shi-han. Power Internet of Things Device Access Management Based on Cryptographic Accumulator [J]. Computer Science, 2022, 49(11A): 210900218-6.
[14] ZHU Zong-wu, HUANG Ru-wei. Secure Multi-party Computing Protocol Based on Efficient Fully Homomorphic Encryption [J]. Computer Science, 2022, 49(11): 345-350.
[15] ZHANG Xiao-yan, LI Qin-wei, FU Fu-jie. Secret Verification Method of Blockchain Transaction Amount Based on Digital Commitment [J]. Computer Science, 2021, 48(9): 324-329.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.