{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,30]],"date-time":"2026-07-30T12:29:27Z","timestamp":1785414567453,"version":"3.56.0"},"reference-count":33,"publisher":"MDPI AG","issue":"15","license":[{"start":{"date-parts":[[2026,7,28]],"date-time":"2026-07-28T00:00:00Z","timestamp":1785196800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62302152"],"award-info":[{"award-number":["62302152"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"award":["62302152"],"award-info":[{"award-number":["62302152"]}],"id":[{"id":"https:\/\/ror.org\/01h0zpd94","id-type":"ROR","asserted-by":"publisher"}]},{"name":"Henan Provincial Key Scientific and Technological Project","award":["242102211074"],"award-info":[{"award-number":["242102211074"]}]},{"name":"Zhengzhou Municipal R&amp;D Special Fund-Supported Research Project","award":["22ZZRDZX30"],"award-info":[{"award-number":["22ZZRDZX30"]}]},{"name":"Open Project of Key Laboratory of Grain Information Processing and Control, Ministry of Education","award":["KFJN2022017"],"award-info":[{"award-number":["KFJN2022017"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>In applications pertaining to sensor network, the Internet of Things, industrial monitoring, and cyber\u2013physical security, graphs are increasingly being outsourced to clouds, where similarity search should be supported without exposing graph content, query graphs, update contents, or database evolution. Existing privacy-preserving graph similarity schemes mainly target static encrypted databases, and as such struggle to handle insertions, deletions, label updates, and long-running index maintenance. This paper proposes DFB-PPGSQ, a dynamic forward-private and epochal backward-private graph similarity matching scheme that moves branch-based lower-bound filtering into a structured encryption framework. DFB-PPGSQ uses epoch-local feature tokens, per-record occurrence handles, one-time update labels, update buffers, deletion tombstones, and shuffle-based branch\u2013tree re-randomization to preserve pruning efficiency while making same-epoch tombstone, traversal, size, timing, and refresh leakage explicit. We formalize the system model, leakage functions, algorithms, and security interpretation, then implement a reproducible Python prototype with HMAC-SHA256 token generation and multi-profile dynamic sensor-topology workloads. Across five random seeds, DFB-PPGSQ keeps server-side filtering latency close to the static branch\u2013tree baseline (46.60 ms versus 44.72 ms at 4000 graphs), avoids immediate full-rebuild updates (0.091 ms insertion and 0.092 ms label update), and keeps metadata-assisted cross-epoch token linkage below 5.6% attack success after refresh in additional industrial and campus IoT stress workloads. Storage, communication, exact GED refinement, side-channel hardening, and verifiable-result protection are treated as deployment costs and limitations rather than being included in the headline latency.<\/jats:p>","DOI":"10.3390\/s26154804","type":"journal-article","created":{"date-parts":[[2026,7,28]],"date-time":"2026-07-28T15:57:28Z","timestamp":1785254248000},"page":"4804","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["DFB-PPGSQ: Dynamic Forward-Private and Epochal Backward-Private Graph Similarity Matching Query over Encrypted Sensor Graph Databases"],"prefix":"10.3390","volume":"26","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6994-1955","authenticated-orcid":false,"given":"Huiying","family":"Hou","sequence":"first","affiliation":[{"name":"The Key Laboratory of Grain Information Processing and Control, Henan University of Technology, Zhengzhou 450001, China"},{"name":"The School of Artificial Intelligence and Big Data, Henan University of Technology, Zhengzhou 450001, China"},{"name":"Henan Province Key Laboratory of Cyberspace Situation Awareness, Zhengzhou Institute of Information Science and Technology, Zhengzhou 450001, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yucong","family":"Ma","sequence":"additional","affiliation":[{"name":"The School of Artificial Intelligence and Big Data, Henan University of Technology, Zhengzhou 450001, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zisu","family":"Zhao","sequence":"additional","affiliation":[{"name":"The School of Artificial Intelligence and Big Data, Henan University of Technology, Zhengzhou 450001, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0274-9691","authenticated-orcid":false,"given":"Xinrui","family":"Ge","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Qingdao University, Qingdao 266071, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2026,7,28]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Li, S., Song, H., and Iqbal, M. (2019). Privacy and Security for Resource-Constrained IoT Devices and Networks: Research Challenges and Opportunities. Sensors, 19.","DOI":"10.3390\/s19081935"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Wang, C., Xing, S., Gao, R., Yan, L., Xiong, N., and Wang, R. (2023). Disentangled Dynamic Deviation Transformer Networks for Multivariate Time Series Anomaly Detection. Sensors, 23.","DOI":"10.3390\/s23031104"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"2030","DOI":"10.1109\/TIFS.2023.3262147","article-title":"PGSim: Efficient and Privacy-Preserving Graph Similarity Query Over Encrypted Data in Cloud","volume":"18","author":"Zheng","year":"2023","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"10478","DOI":"10.1109\/TKDE.2023.3266449","article-title":"PrigSim: Towards Privacy-Preserving Graph Similarity Search as a Cloud Service","volume":"35","author":"Wang","year":"2023","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1932","DOI":"10.1109\/TKDE.2026.3656414","article-title":"Privacy-Preserving Graph Similarity Matching Query Over Encrypted Graph Database","volume":"38","author":"Ge","year":"2026","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1109\/TSMC.1983.6313167","article-title":"A Distance Measure Between Attributed Relational Graphs for Pattern Recognition","volume":"SMC-13","author":"Sanfeliu","year":"1983","journal-title":"IEEE Trans. Syst. Man Cybern."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/s10044-008-0141-y","article-title":"A Survey of Graph Edit Distance","volume":"13","author":"Gao","year":"2010","journal-title":"Pattern Anal. Appl."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"950","DOI":"10.1016\/j.imavis.2008.04.004","article-title":"Approximate Graph Edit Distance Computation by Means of Bipartite Graph Matching","volume":"27","author":"Riesen","year":"2009","journal-title":"Image Vis. Comput."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Yan, X., Yu, P.S., and Han, J. (2004, January 13\u201318). Graph Indexing: A Frequent Structure-Based Approach. Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data, Paris, France.","DOI":"10.1145\/1007568.1007607"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"964","DOI":"10.1109\/TKDE.2014.2349924","article-title":"Efficient Graph Similarity Search Over Large Graph Databases","volume":"27","author":"Zheng","year":"2015","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Zhao, X., Xiao, C., Lin, X., and Wang, W. (2012, January 1\u20135). Efficient Graph Similarity Joins with Edit Distance Constraints. Proceedings of the 2012 IEEE 28th International Conference on Data Engineering, Arlington, VA, USA.","DOI":"10.1109\/ICDE.2012.91"},{"key":"ref_12","unstructured":"Song, D.X., Wagner, D., and Perrig, A. (2000, January 14\u201317). Practical Techniques for Searches on Encrypted Data. Proceedings of the 2000 IEEE Symposium on Security and Privacy, Berkeley, CA, USA."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Boneh, D., Di Crescenzo, G., Ostrovsky, R., and Persiano, G. (2004). Public Key Encryption with Keyword Search. Proceedings of the Advances in Cryptology\u2014EUROCRYPT 2004, Springer.","DOI":"10.1007\/978-3-540-24676-3_30"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Chang, Y.C., and Mitzenmacher, M. (2005). Privacy Preserving Keyword Searches on Remote Encrypted Data. Proceedings of the Applied Cryptography and Network Security, Springer.","DOI":"10.1007\/11496137_30"},{"key":"ref_15","unstructured":"Curtmola, R., Garay, J., Kamara, S., and Ostrovsky, R. (November, January 30). Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions. Proceedings of the 13th ACM Conference on Computer and Communications Security, Alexandria, VI, USA."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Cash, D., Jarecki, S., Jutla, C., Krawczyk, H., Rosu, M.C., and Steiner, M. (2013). Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries. Proceedings of the Advances in Cryptology\u2014CRYPTO 2013, Springer.","DOI":"10.1007\/978-3-642-40041-4_20"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Kamara, S., Papamanthou, C., and Roeder, T. (2012, January 16\u201318). Dynamic Searchable Symmetric Encryption. Proceedings of the 2012 ACM Conference on Computer and Communications Security, Raleigh, NC, USA.","DOI":"10.1145\/2382196.2382298"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Kamara, S., and Papamanthou, C. (2013). Parallel and Dynamic Searchable Symmetric Encryption. Proceedings of the Financial Cryptography and Data Security, Springer.","DOI":"10.1007\/978-3-642-39884-1_22"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Cash, D., Jaeger, J., Jarecki, S., Jutla, C., Krawczyk, H., Rosu, M.C., and Steiner, M. (2014, January 23\u201326). Dynamic Searchable Encryption in Very-Large Databases: Data Structures and Implementation. Proceedings of the 2014 Network and Distributed System Security Symposium, San Diego, CA, USA.","DOI":"10.14722\/ndss.2014.23264"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Stefanov, E., Papamanthou, C., and Shi, E. (2014, January 23\u201326). Practical Dynamic Searchable Encryption with Small Leakage. Proceedings of the 2014 Network and Distributed System Security Symposium, San Diego, CA, USA.","DOI":"10.14722\/ndss.2014.23298"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Bost, R. (2016, January 24\u201328). \u03a3o\u03d5o\u03c2: Forward Secure Searchable Encryption. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria.","DOI":"10.1145\/2976749.2978303"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Bost, R., Minaud, B., and Ohrimenko, O. (November, January 30). Forward and Backward Private Searchable Encryption from Constrained Cryptographic Primitives. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, Dallas, TX, USA.","DOI":"10.1145\/3133956.3133980"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Cao, N., Yang, Z., Wang, C., Ren, K., and Lou, W. (2011, January 20\u201324). Privacy-Preserving Query over Encrypted Graph-Structured Data in Cloud Computing. Proceedings of the 2011 IEEE 31st International Conference on Distributed Computing Systems, Minneapolis, MN, USA.","DOI":"10.1109\/ICDCS.2011.84"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Meng, X., Kamara, S., Nissim, K., and Kollios, G. (2015, January 12\u201316). GRECS: Graph Encryption for Approximate Shortest Distance Queries. Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, CO, USA.","DOI":"10.1145\/2810103.2813672"},{"key":"ref_25","first-page":"3295","article-title":"GraphShield: Dynamic Large Graphs for Secure Queries with Forward Privacy","volume":"34","author":"Du","year":"2020","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Falzon, F., Ghosh, E., Paterson, K.G., and Tamassia, R. (2024, January 14\u201318). PathGES: An Efficient and Secure Graph Encryption Scheme for Shortest Path Queries. Proceedings of the 2024 ACM SIGSAC Conference on Computer and Communications Security, Salt Lake City.","DOI":"10.1145\/3658644.3670305"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Yang, S. (2025). Privacy-Preserving Multi-User Graph Intersection Scheme for Wireless Communications in Cloud-Assisted Internet of Things. Sensors, 25.","DOI":"10.3390\/s25061892"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Cash, D., Grubbs, P., Perry, J., and Ristenpart, T. (2015, January 12\u201316). Leakage-Abuse Attacks against Searchable Encryption. Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, CO, USA.","DOI":"10.1145\/2810103.2813700"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Naveed, M., Kamara, S., and Wright, C.V. (2015, January 12\u201316). Inference Attacks on Property-Preserving Encrypted Databases. Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, CO, USA.","DOI":"10.1145\/2810103.2813651"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Grubbs, P., Lacharite, M.S., Minaud, B., and Paterson, K.G. (2019, January 19\u201323). Learning to Reconstruct: Statistical Learning Theory and Encrypted Database Attacks. Proceedings of the 2019 IEEE Symposium on Security and Privacy, San Francisco, CA, USA.","DOI":"10.1109\/SP.2019.00030"},{"key":"ref_31","unstructured":"Oya, S., and Kerschbaum, F. (2021, January 11\u201313). Hiding the Access Pattern is Not Enough: Exploiting Search Pattern Leakage in Searchable Encryption. Proceedings of the 30th USENIX Security Symposium, Online."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Lewi, K., and Wu, D.J. (2016, January 24\u201328). Order-Revealing Encryption. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria.","DOI":"10.1145\/2976749.2978376"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Chase, M., and Kamara, S. (2010). Structured Encryption and Controlled Disclosure. Proceedings of the Advances in Cryptology\u2014ASIACRYPT 2010, Springer.","DOI":"10.1007\/978-3-642-17373-8_33"}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/26\/15\/4804\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,30]],"date-time":"2026-07-30T04:30:59Z","timestamp":1785385859000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/26\/15\/4804"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,28]]},"references-count":33,"journal-issue":{"issue":"15","published-online":{"date-parts":[[2026,8]]}},"alternative-id":["s26154804"],"URL":"https:\/\/doi.org\/10.3390\/s26154804","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,28]]}}}