TSKT-ORAM: A Two-Server k-ary Tree Oblivious RAM without Homomorphic Encryption

Jinsheng Zhang, Qiumao Ma, Wensheng Zhang, Daji QiaoFuture 2017 · DOI

TL;DR

This paper introduces TSKT-ORAM, a novel two-server Oblivious RAM (ORAM) system that uses a k-ary tree structure and a delayed eviction technique to protect data access patterns. TSKT-ORAM achieves significant improvements in communication cost, storage, and access delay compared to existing ORAM schemes, making it more practical for cloud storage.

What Problem Does This Paper Address?

Cloud storage offers convenience and scalability, but users are concerned about the privacy of their data. While encrypting data protects its content, the access pattern (which data is accessed, when, and how often) can still reveal sensitive information to cloud providers or attackers. Oblivious RAM (ORAM) is a cryptographic technique designed to hide these access patterns. However, many existing ORAM solutions are either computationally expensive, require significant client-side storage, or have high communication overhead, limiting their practical adoption in real-world cloud environments. This paper aims to develop a more efficient and practical ORAM solution.

Methods

The core of TSKT-ORAM lies in its novel architecture and techniques:

  • k-ary Tree Structure: Instead of a binary tree, TSKT-ORAM uses a k-ary tree for server storage. This reduces the height of the tree, which directly translates to lower communication costs and access delays.
  • Two-Server Architecture: The system utilizes two independent, non-colluding servers. This is a common approach in ORAM to distribute data and computations, enhancing security.
  • XOR-based PIR: The scheme employs XOR-based Private Information Retrieval (PIR) for data retrieval. This is a more efficient alternative to homomorphic encryption, which is often used in other ORAM schemes but incurs significant computational overhead.
  • Delayed and Aggregated Eviction: A key innovation is the delayed eviction technique. Instead of evicting data blocks immediately after each access, TSKT-ORAM aggregates these operations within a "k-node" (a group of nodes in the k-ary tree). This allows for more efficient processing and reduces the overall communication and computation burden. Evictions are categorized into "intra k-node" (within a k-node, which can be delayed) and "inter k-node" (between k-nodes, which must be performed immediately).

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and performance analysis rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • k-ary trees are not just for faster lookups: The paper demonstrates that a k-ary tree structure in ORAM can significantly reduce communication and access delay by lowering tree height, a benefit beyond simple data retrieval speed.
  • Delayed eviction is a game-changer for efficiency: By strategically delaying and aggregating eviction operations within k-nodes, TSKT-ORAM avoids the constant overhead of immediate evictions, leading to substantial performance gains. This is particularly effective because intra-k-node evictions can be handled more efficiently due to shared storage within a k-node.
  • XOR is a powerful substitute for heavy crypto: Replacing computationally intensive homomorphic encryption with simpler XOR operations for PIR significantly reduces server-side computation and access delay, making the system more practical.
  • Two servers are sufficient for strong privacy: The paper shows that a two-server setup, combined with the proposed techniques, can achieve a high level of privacy (failure probability of 2⁻⁸⁰) without requiring more complex multi-server configurations.

Key Results

  • Communication Cost: For N ranging from 2¹⁶ to 2³⁴, TSKT-ORAM achieves a communication cost of only 22-46 data blocks per query, which is significantly lower than many state-of-the-art ORAM schemes.
  • Failure Probability: The system is proven to protect data access pattern privacy with a failure probability of 2⁻⁸⁰ when the system parameter k ≥ 128.
  • Computational Cost: TSKT-ORAM incurs a computational cost less than half of that of CNE-ORAM, a comparable multi-server ORAM scheme.
  • Access Delay: Practical comparisons suggest that TSKT-ORAM's access delay is less than half that of CNE-ORAM, due to reduced communication and computation.
  • Storage Cost: The total storage cost for TSKT-ORAM is approximately 48N·B, which is about one-fourth of that of CNE-ORAM.

Limitations and Future Work

  • Storage Efficiency: While TSKT-ORAM is storage-efficient compared to some schemes, it still requires servers to allocate storage space of 24N blocks to store only N real data blocks. The authors suggest future work on developing ORAM constructions that are not only communication-efficient but also storage-efficient.
  • Practical Implementation: The paper focuses on theoretical analysis and asymptotic comparisons. While practical comparisons are made, further real-world implementation and testing would be valuable.
  • System Parameter Tuning: The security and performance of TSKT-ORAM depend on system parameters like k and c. Optimal tuning for various scenarios might require further investigation.

Summary updated

Abstract

This paper proposes TSKT-oblivious RAM (ORAM), an efficient multi-server ORAM construction, to protect a client’s access pattern to outsourced data. TSKT-ORAM organizes each of the server storages as a k-ary tree and adopts XOR-based private information retrieval (PIR) and a novel delayed eviction technique to optimize both the data query and data eviction process. TSKT-ORAM is proven to protect the data access pattern privacy with a failure probability of 2 - 80 when system parameter k ≥ 128 . Meanwhile, given a constant-size local storage, when N (i.e., the total number of outsourced data blocks) ranges from 2 16 – 2 34 , the communication cost of TSKT-ORAM is only 22–46 data blocks. Asymptotic analysis and practical comparisons are conducted to show that TSKT-ORAM incurs lower communication cost, storage cost and access delay in practical scenarios than the compared state-of-the-art ORAM schemes.
BibTeX
@inproceedings{zhang2017tskt,
  author = {Jinsheng Zhang and Qiumao Ma and Wensheng Zhang and Daji Qiao},
  title = {{TSKT-ORAM: A Two-Server k-ary Tree Oblivious RAM without Homomorphic Encryption}},
  booktitle = {Future},
  year = {2017},
  doi = {10.3390/fi9040057},
}
Figure