DFB-PPGSQ: Dynamic Forward-Private and Epochal Backward-Private Graph Similarity Matching Query over Encrypted Sensor Graph Databases

In applications pertaining to sensor network, the Internet of Things, industrial monitoring, and cyber–physical 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–tree 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–tree 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.