  Graph encryption schemes play a crucial role in facilitating secure queries
on encrypted graphs hosted on untrusted servers. With applications spanning
navigation systems, network topology, and social networks, the need to
safeguard sensitive data becomes paramount. Existing graph encryption methods,
however, exhibit vulnerabilities by inadvertently revealing aspects of the
graph structure and query patterns, posing threats to security and privacy. In
response, we propose a novel graph encryption scheme designed to mitigate
access pattern and query pattern leakage through the integration of oblivious
RAM and trusted execution environment techniques, exemplified by a Trusted
Execution Environment (TEE). Our solution establishes two key security
objectives: (1) ensuring that adversaries, when presented with an encrypted
graph, remain oblivious to any information regarding the underlying graph, and
(2) achieving query indistinguishability by concealing access patterns.
Additionally, we conducted experimentation to evaluate the efficiency of the
proposed schemes when dealing with real-world location navigation services.
