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.