计算机科学

计算机科学 ›› 2024, Vol. 51 ›› Issue (5): 400-413.doi: 10.11896/jsjkx.230200031

• 信息安全 • 上一篇    下一篇

正确性可验证的密文图数据最短路径外包计算方案

丁红发1,2, 于莹莹1, 蒋合领1   

  1. 1 贵州财经大学信息学院贵州省大数据统计分析重点实验室 贵阳 550025
    2 贵州大学公共大数据国家重点实验室 贵阳 550025
  • 收稿日期:2023-02-06 修回日期:2023-06-21 出版日期:2024-05-15 发布日期:2024-05-08
  • 通讯作者: 丁红发(hongfa.ding@foxmail.com)
  • 基金资助:
    国家自然科学基金(62002080);贵州省教育厅自然科学研究项目(黔教技[2023]065号,黔教技[2023]014号)

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)

294

摘要： 地理位置、社交网络等海量图数据应用广泛且包含大量隐私,通常需要安全的外包计算来提供多样化的查询服务。然而,如何设计正确性可验证的图数据外包计算协议仍是公开的难题。为此,提出了加密图数据上正确性可验证的精确最短路径外包计算方案。该方案利用加法同态加密构造密态图数据上的广度优先最短路径计算算法,支持加密图数据的精确最短距离查询外包计算;其次,基于双线性映射累加器构造最短路径外包计算结果的概率正确性验证机制。分析和证明表明,该方案能以概率可靠性实现正确性可验证的精确最短路径的外包计算,具备随机预言模型下的IND-CCA2安全。对比实验结果表明,所提方案相比其他相关方案在安全性、功能性方面有显著优势,性能上较已有可验证图数据外包计算方案在初始化及加密环节、查询环节、验证及解密环节的时间开销分别降低了0.15%～23.19%,12.91%～30.89%和1.13%～18.62%。

关键词: 图数据外包计算, 可验证, 最短路径查询, 密码累加器, 同态加密

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

中图分类号: 

  • 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.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发