Existing solutions for dynamic shortest distance queries under privacy protection suffer from low efficiency in both querying and updating, and are typically restricted to decremental updates in unweighted graphs. To overcome these limitations, we propose a novel approach, the structured encryption scheme for shortest distance queries based on dynamic hub labeling ( \(\textsf{STE}\) - \(\textsf{DHL}\) ), designed to facilitate efficient querying and full updates while ensuring privacy. Our method involves constructing a hub labeling index based on the concept of tree decomposition, which is then encrypted using lightweight cryptographic primitives. By leveraging collaboration among servers, we facilitate efficient querying and updating of shortest distances. Additionally, to optimize storage and enhance computational accuracy and efficiency, we integrate symmetric homomorphic encryption to design ciphertext comparison protocols. Security analysis confirms that our approach complies with the CQA2 security. Evaluation on real-world datasets demonstrates that \(\textsf{STE}\) - \(\textsf{DHL}\) reduces query time by 50% compared to existing schemes, with an update overhead on ciphertexts of only 1.5 \(\times \) –3.5 \(\times \) compared to plaintexts.
