# A Privacy-Preserving Graph Encryption Scheme Based on Oblivious RAM

**Authors:** Seyni Kane, Anis Bkakria  
**arXiv:** [2405.19259](https://arxiv.org/abs/2405.19259)  
**Date:** 2024-05-29  
**Summary page:** https://www.summarizepaper.com/en/paper/2405.19259v1/

## Key points

- Graph encryption schemes play a critical role in enabling secure queries on encrypted graphs stored on untrusted servers.
- Existing methods have vulnerabilities that can disclose elements of the graph structure and query patterns, jeopardizing security and privacy.
- The authors propose a novel graph encryption scheme integrating oblivious RAM and trusted execution environment techniques to address these vulnerabilities.
- The primary objectives of their solution are to keep adversaries unaware of any information about the underlying graph and achieve query indistinguishability by concealing access patterns.
- The paper discusses cryptographic techniques like Fully Homomorphic Encryption (FHE) and secure Multi-Party Computation (MPC), which offer high security but low efficiency.
- Solutions that trade off some security for improved efficiency by allowing controlled leakage are also mentioned.
- Reference is made to Ghosh, Kamara, and Tamassia's practical graph encryption scheme supporting shortest path queries with a balanced trade-off between efficiency and security.
- The research contributes valuable insights into enhancing graph encryption schemes for heightened security while balancing efficiency considerations.

## Summary

In this paper, the authors Seyni Kane and Anis Bkakria delve into the realm of graph encryption schemes. They emphasize the critical role of such schemes in enabling secure queries on encrypted graphs stored on untrusted servers. The applications of these schemes are vast and range from navigation systems to social networks, highlighting the necessity to protect sensitive data. However, existing methods have been found to possess vulnerabilities that inadvertently disclose elements of the graph structure and query patterns, jeopardizing security and privacy. To address these vulnerabilities, the authors propose a novel graph encryption scheme that integrates oblivious RAM and trusted execution environment techniques. This is exemplified through a Trusted Execution Environment (TEE). The primary objectives of their solution are twofold: firstly, ensuring that adversaries presented with an encrypted graph remain unaware of any information pertaining to the underlying graph; and secondly, achieving query indistinguishability by concealing access patterns. Furthermore, the authors conducted experiments to assess the efficiency of their proposed schemes in real-world scenarios involving location navigation services. They highlight the challenges in designing secure, expressive, and efficient graph encryption schemes while discussing cryptographic techniques like Fully Homomorphic Encryption (FHE) and secure Multi-Party Computation (MPC). These techniques offer high security but low efficiency. The paper also touches upon solutions that trade off some security for improved efficiency by allowing controlled leakage. The paper references Ghosh, Kamara, and Tamassia's (GKT) practical graph encryption scheme supporting shortest path queries with a balanced trade-off between efficiency and security. This scheme encrypts graphs using a recursive algorithm that partitions nodes based on connectivity patterns. In conclusion, this research contributes valuable insights into enhancing graph encryption schemes for heightened security while balancing efficiency considerations. By addressing access pattern and query pattern leakage through innovative techniques like oblivious RAM integration and TEE utilization, the proposed scheme holds promise for safeguarding sensitive data in various applications effectively.