{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,26]],"date-time":"2025-09-26T04:53:15Z","timestamp":1758862395682,"version":"3.37.3"},"reference-count":36,"publisher":"Oxford University Press (OUP)","issue":"7","license":[{"start":{"date-parts":[[2021,3,22]],"date-time":"2021-03-22T00:00:00Z","timestamp":1616371200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"name":"Privacy-preserving Cloud Data Mining-as-a-Service","award":["LP160101766"],"award-info":[{"award-number":["LP160101766"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61822202","62032005","61872089"],"award-info":[{"award-number":["61822202","62032005","61872089"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Science Foundation of Fujian Provincial Science and Technology Agency","award":["2020J02016"],"award-info":[{"award-number":["2020J02016"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,7,15]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The edge authentication of graphs has been studied in the literature because graphs are one of the most widely used data organization structures. The majority of such schemes cannot be used to authenticate general directed graphs (GDGs); other schemes cannot be used for addressing either the issue of dynamic update or the issue of information leakage (such as the existence of nodes\/edges and structural relationship of the graph). Also, all the existing schemes do not consider the forward security: if the signer\u2019s secret key has been compromised, all previously generated signatures remain valid. This property provides high-level security protection for authentication schemes. To address these issues, in this work, we propose a forward-secure edge authentication scheme for GDGs. Observe that existing such schemes can only give a proof such that \u2018there is an edge between nodes $u$ and $v$\u2019. Our scheme, however, can directly give a proof such that \u2018there is no edge between nodes $u$ and $v$\u2019, which makes the function of edge authentication schemes more diverse. Moreover, our proposed scheme is proven to be secure against an adaptive chosen-message adversary in the random oracle model. To show its desirable performance, we analyze the computational costs of our scheme and compare it with other related schemes in terms of features.<\/jats:p>","DOI":"10.1093\/comjnl\/bxab004","type":"journal-article","created":{"date-parts":[[2021,1,30]],"date-time":"2021-01-30T20:08:48Z","timestamp":1612037328000},"page":"1653-1665","source":"Crossref","is-referenced-by-count":3,"title":["Forward-Secure Edge Authentication for Graphs"],"prefix":"10.1093","volume":"65","author":[{"given":"Fei","family":"Zhu","sequence":"first","affiliation":[{"name":"School of Science , RMIT University, 124 La Trobe St, Melbourne, VIC 3000, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xun","family":"Yi","sequence":"additional","affiliation":[{"name":"School of Science , RMIT University, 124 La Trobe St, Melbourne, VIC 3000, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alsharif","family":"Abuadbba","sequence":"additional","affiliation":[{"name":"CSIRO\u2019s Data61 & Cyber Security CRC , Marsfield, NSW 2122, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ibrahim","family":"Khalil","sequence":"additional","affiliation":[{"name":"School of Science , RMIT University, 124 La Trobe St, Melbourne, VIC 3000, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Surya","family":"Nepal","sequence":"additional","affiliation":[{"name":"CSIRO\u2019s Data61 & Cyber Security CRC , Marsfield, NSW 2122, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xinyi","family":"Huang","sequence":"additional","affiliation":[{"name":"Fujian Provincial Key Laboratory of Network Security and Cryptology , College of Mathematics and Informatics, Fujian Normal University, Fuzhou 350117, China"},{"name":"Blockchain Laboratory of Agricultural Vegetables , Weifang University of Science and Technology, 166 Xueyuan Rd, WeiFang, Shandong, 262700, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2021,3,22]]},"reference":[{"article-title":"Outsourcing graph databases with label-constrain query verification","year":"2015","author":"Kalikinkar","key":"2022071813365404900_ref1"},{"key":"2022071813365404900_ref2","doi-asserted-by":"crossref","first-page":"866","DOI":"10.1109\/TKDE.2017.2776221","article-title":"Efficient and scalable integrity verification of data and query results for graph databases","volume":"30","author":"Arshad","year":"2018","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"2022071813365404900_ref3","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1007\/s10207-013-0198-5","article-title":"Privacy-preserving authentication of trees and graphs","volume":"12","author":"Kundu","year":"2013","journal-title":"Int. J. Inf. Secur."},{"key":"2022071813365404900_ref4","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1007\/s00453-009-9355-7","article-title":"Efficient authenticated data structures for graph connectivity and geometric search problems","volume":"60","author":"Goodrich","year":"2011","journal-title":"Algorithmica"},{"key":"2022071813365404900_ref5","first-page":"180","article-title":"A universal designated multi-verifier transitive signature scheme","volume-title":"Proceedings of INSCRYPT 2017, Xi\u2019an","author":"Zhu","year":"2017"},{"key":"2022071813365404900_ref6","first-page":"236","article-title":"Transitive signature schemes","volume-title":"Proceedings of CT-RSA 2002, San Jose, CA","author":"Micali","year":"2002"},{"key":"2022071813365404900_ref7","first-page":"129","article-title":"Directed transitive signature scheme","volume-title":"Proceedings of CT-RSA 2007, San Francisco, CA","author":"Yi","year":"2007"},{"volume-title":"The cryptographic impact of groups with infeasible inversion","year":"2003","author":"Hohenberger","key":"2022071813365404900_ref8"},{"key":"2022071813365404900_ref9","first-page":"244","article-title":"Homomorphic signature schemes","volume-title":"Proceedings of CT-RSA 2002, San Jose, CA","author":"Johnson","year":"2002"},{"article-title":"RSA secureID breach costs EMC $66 million","year":"2011","author":"Hoffman","key":"2022071813365404900_ref10"},{"article-title":"Two remarks on public key cryptology","year":"1997","author":"Ross","key":"2022071813365404900_ref11"},{"key":"2022071813365404900_ref12","first-page":"431","article-title":"A forward-secure digital signature scheme","volume-title":"Proceedings of CRYPTO 1999, Santa Barbara, CA","author":"Bellare","year":"1999"},{"key":"2022071813365404900_ref13","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/j.tcs.2008.01.042","article-title":"A simple transitive signature scheme for directed trees","volume":"396","author":"Neven","year":"2008","journal-title":"Theor. Comput. Sci."},{"article-title":"On directed transitive signature","year":"2009","author":"Xu","key":"2022071813365404900_ref14"},{"key":"2022071813365404900_ref15","first-page":"35","article-title":"Short transitive signatures for directed trees","volume-title":"Proceedings of CT-RSA 2012, San Francisco, CA","author":"Camacho","year":"2012"},{"article-title":"A candidate group with infeasible inversion","year":"2018","author":"Altug","key":"2022071813365404900_ref16"},{"key":"2022071813365404900_ref17","first-page":"295","article-title":"Authenticated data structures for graph and geometric searching","volume-title":"Proceedings of CT-RSA 2003, San Francisco, CA","author":"Goodrich","year":"2003"},{"key":"2022071813365404900_ref18","first-page":"609","article-title":"How to authenticate graphs without leaking","volume-title":"Proceedings of EDBT 2010, Lausanne","author":"Kundu","year":"2010"},{"key":"2022071813365404900_ref19","first-page":"218","article-title":"A certified digital signature","volume-title":"Proceedings of CRYPTO 1989, Santa Barbara, CA","author":"Merkle","year":"1989"},{"key":"2022071813365404900_ref20","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/s00453-003-1076-8","article-title":"A general model for authenticated data structures","volume":"39","author":"Martel","year":"2004","journal-title":"Algorithmica"},{"key":"2022071813365404900_ref21","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1007\/3-540-39200-9_26","article-title":"Aggregate and verifiably encrypted signatures from bilinear maps","volume-title":"Proceedings of EUROCRYPT 2003, Warsaw","author":"Boneh","year":"2003"},{"key":"2022071813365404900_ref22","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-30108-0_10","article-title":"Signature bouquets: Immutability for aggregated\/condensed signatures","volume-title":"Proceedings of ESORICS, Sophia Antipolis","author":"Mykletun","year":"2004"},{"key":"2022071813365404900_ref23","first-page":"171","article-title":"On structural signatures for tree data structures","volume-title":"Proceedings of ACNS 2012","author":"Samelin","year":"2012"},{"key":"2022071813365404900_ref24","first-page":"223","article-title":"Security of graph data: Hashing schemes and definitions","volume-title":"Proceedings of CODASPY 2014, San Antonio, TX","author":"Arshad","year":"2014"},{"key":"2022071813365404900_ref25","first-page":"398","article-title":"Redactable graph hashing, revisited\u2014(extended abstract)","volume-title":"Proceedings of ACISP 2017, Auckland","author":"Erwig","year":"2017"},{"key":"2022071813365404900_ref26","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/j.ins.2019.06.032","article-title":"Privacy-preserving authentication for general directed graphs in industrial iot","volume":"502","author":"Zhu","year":"2019","journal-title":"Inform. Sci."},{"key":"2022071813365404900_ref27","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1007\/s00145-011-9115-0","article-title":"Practical chosen ciphertext secure encryption from factoring","volume":"26","author":"Hofheinz","year":"2013","journal-title":"J Cryptol"},{"key":"2022071813365404900_ref28","first-page":"274","article-title":"One-way accumulators: A decentralized alternative to digital sinatures (extended abstract)","volume-title":"Proceedings of EUROCRYPT 1993, Lofthus","author":"Benaloh","year":"1993"},{"key":"2022071813365404900_ref29","first-page":"253","article-title":"Universal accumulators with efficient nonmembership proofs","volume-title":"Proceedings of ACNS 2007, Zhuhai","author":"Li","year":"2007"},{"key":"2022071813365404900_ref30","first-page":"106","article-title":"Universal classes of hash functions (extended abstract)","volume-title":"Proceedings of STOC 1977, Boulder, CO","author":"Carter","year":"1977"},{"key":"2022071813365404900_ref31","first-page":"123","article-title":"Secure hash-and-sign signatures without the random oracle","volume-title":"Proceedings of EUROCRYPT 1999, Prague","author":"Gennaro","year":"1999"},{"key":"2022071813365404900_ref32","first-page":"299","article-title":"Towards a smart contract-based, decentralized, public-key infrastructure","volume-title":"Proceedings of CANS 2017, Hong Kong","author":"Patsonakis","year":"2017"},{"key":"2022071813365404900_ref33","first-page":"61","article-title":"Dynamic accumulators and application to efficient revocation of anonymous credentials","volume-title":"Proceedings of CRYPTO 2002, Santa Barbara, CA","author":"Camenisch","year":"2002"},{"key":"2022071813365404900_ref34","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1137\/0217017","article-title":"A digital signature scheme secure against adaptive chosen-message attacks","volume":"17","author":"Goldwasser","year":"1988","journal-title":"SIAM J. Comput."},{"key":"2022071813365404900_ref35","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1007\/3-540-44448-3_10","article-title":"A new forward-secure digital signature scheme","volume-title":"Proceedings of ASIACRYPT 2000, Kyoto","author":"Abdalla","year":"2000"},{"key":"2022071813365404900_ref36","first-page":"292","article-title":"Efficient asynchronous accumulators for distributed PKI","volume-title":"Proceedings of SCN 2016, Amalfi","author":"Reyzin","year":"2016"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/65\/7\/1653\/44921757\/bxab004.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/65\/7\/1653\/44921757\/bxab004.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,19]],"date-time":"2023-10-19T20:26:40Z","timestamp":1697747200000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/65\/7\/1653\/6178962"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,22]]},"references-count":36,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2021,3,22]]},"published-print":{"date-parts":[[2022,7,15]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxab004","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"type":"print","value":"0010-4620"},{"type":"electronic","value":"1460-2067"}],"subject":[],"published-other":{"date-parts":[[2022,7,15]]},"published":{"date-parts":[[2021,3,22]]}}}