Bandwidth-Efficient Two-Server ORAMs with O(1) Client Storage

• URL: http://arxiv.org/abs/2503.21126v2
• Date: Wed, 16 Apr 2025 01:34:50 GMT
• Title: Bandwidth-Efficient Two-Server ORAMs with O(1) Client Storage
• Authors: Wei Wang, Xianglong Zhang, Peng Xu, Rongmao Chen, Laurence Tianruo Yang,
• Abstract summary: Two-server ORAM, designed for secure two-party RAM computation, stores data across two non-colluding servers.<n>This paper presents two new client-friendly two-server ORAM schemes that achieve practical logarithmic bandwidth under O(1) local storage.
• Score: 8.731979518509597
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Oblivious RAM (ORAM) allows a client to securely retrieve elements from outsourced servers without leakage about the accessed elements or their virtual addresses. Two-server ORAM, designed for secure two-party RAM computation, stores data across two non-colluding servers. However, many two-server ORAM schemes suffer from excessive local storage or high bandwidth costs. To serve lightweight clients, it is crucial for ORAM to achieve concretely efficient bandwidth while maintaining O(1) local storage. Hence, this paper presents two new client-friendly two-server ORAM schemes that achieve practical logarithmic bandwidth under O(1) local storage, while incurring linear symmetric key computations. The core design features a hierarchical structure and a pairwise-area setting for the elements and their tags. Accordingly, we specify efficient read-only and write-only private information retrieval (PIR) algorithms in our schemes to ensure obliviousness in accessing two areas respectively, so as to avoid the necessity of costly shuffle techniques in previous works. We empirically evaluate our schemes against LO13 (TCC'13), AFN17 (PKC'17), and KM19 (PKC'19) in terms of both bandwidth and time cost. The results demonstrate that our schemes reduce bandwidth by approximately 2-4x compared to LO13, and by 16-64x compared to AFN17 and KM19. For a database of size 2^14 blocks, our schemes are over 64x faster than KM19, while achieving similar performance to LO13 and AFN17 in the WAN setting, with a latency of around 1 second.

Related papers

• COMPASS: A Compiler Framework for Resource-Constrained Crossbar-Array Based In-Memory Deep Learning Accelerators [6.172271429579593]
  We propose a compiler framework for resource-constrained crossbar-based processing-in-memory (PIM) deep neural network (DNN) accelerators.<n>We propose an algorithm to determine the optimal partitioning that divides the layers so that each partition can be accelerated on chip.
  arXiv  Detail & Related papers  (2025-01-12T11:31:25Z)
• Palermo: Improving the Performance of Oblivious Memory using Protocol-Hardware Co-Design [13.353250150074066]
  Oblivious RAM (ORAM) hides the memory access patterns, enhancing data privacy by preventing attackers from discovering sensitive information. The performance of ORAM is often limited by its inherent trade-off between security and efficiency. This paper presents Palermo: a protocol- hardware co-design to improve ORAM performance.
  arXiv  Detail & Related papers  (2024-11-08T08:31:12Z)
• Breaking the Memory Barrier: Near Infinite Batch Size Scaling for Contrastive Loss [59.835032408496545]
  We propose a tile-based strategy that partitions the contrastive loss calculation into arbitrary small blocks. We also introduce a multi-level tiling strategy to leverage the hierarchical structure of distributed systems. Compared to SOTA memory-efficient solutions, it achieves a two-order-of-magnitude reduction in memory while maintaining comparable speed.
  arXiv  Detail & Related papers  (2024-10-22T17:59:30Z)
• Optimal Offline ORAM with Perfect Security via Simple Oblivious Priority Queues [0.0]
  We study the so-called offline ORAM in which the sequence of memory access locations to be hidden is known in advance. We obtain the first optimal offline ORAM with perfect security from oblivious priority queues via time-forward processing. Building on our construction, we additionally present efficient external-memory instantiations of our oblivious, perfectly-secure construction.
  arXiv  Detail & Related papers  (2024-09-18T14:31:33Z)
• H$_2$O$_2$RAM: A High-Performance Hierarchical Doubly Oblivious RAM [14.803814604985957]
  Oblivious RAM (ORAM) with Trusted Execution Environments (TEE) has found numerous real-world applications due to their complementary nature.<n>We introduce several new efficient oblivious components to build a high-performance hierarchical O$$RAM (H$$O$RAM)<n>The results indicate that H$$O$RAM reduces execution time by up to $sim 103$ times and saves memory usage by $5sim44$ times compared to stateoftheart solutions.
  arXiv  Detail & Related papers  (2024-09-11T10:31:14Z)
• vTensor: Flexible Virtual Tensor Management for Efficient LLM Serving [53.972175896814505]
  Large Language Models (LLMs) are widely used across various domains, processing millions of daily requests. Large Language Models (LLMs) are widely used across various domains, processing millions of daily requests.
  arXiv  Detail & Related papers  (2024-07-22T14:37:58Z)
• RAMP: A Flat Nanosecond Optical Network and MPI Operations for Distributed Deep Learning Systems [68.8204255655161]
  We introduce a near-exascale, full-bisection bandwidth, all-to-all, single-hop, all-optical network architecture with nanosecond reconfiguration called RAMP. RAMP supports large-scale distributed and parallel computing systems (12.8Tbps per node for up to 65,536 nodes.
  arXiv  Detail & Related papers  (2022-11-28T11:24:51Z)
• Adaptable Butterfly Accelerator for Attention-based NNs via Hardware and Algorithm Co-design [66.39546326221176]
  Attention-based neural networks have become pervasive in many AI tasks. The use of the attention mechanism and feed-forward network (FFN) demands excessive computational and memory resources. This paper proposes a hardware-friendly variant that adopts a unified butterfly sparsity pattern to approximate both the attention mechanism and the FFNs.
  arXiv  Detail & Related papers  (2022-09-20T09:28:26Z)
• Single Round-trip Hierarchical ORAM via Succinct Indices [5.437298646956505]
  Rank ORAM can retrieve data with a single round-trip of communication. A emphcompressed client-side data structure stores, implicitly, the location of each element at the server.
  arXiv  Detail & Related papers  (2022-08-16T01:15:26Z)
• NumS: Scalable Array Programming for the Cloud [82.827921577004]
  We present NumS, an array programming library which optimize NumPy-like expressions on task-based distributed systems. This is achieved through a novel scheduler called Load Simulated Hierarchical Scheduling (LSHS) We show that LSHS enhances performance on Ray by decreasing network load by a factor of 2x, requiring 4x less memory, and reducing execution time by 10x on the logistic regression problem.
  arXiv  Detail & Related papers  (2022-06-28T20:13:40Z)
• Parallelising the Queries in Bucket Brigade Quantum RAM [69.43216268165402]
  Quantum algorithms often use quantum RAMs (QRAM) for accessing information stored in a database-like manner. We show a systematic method to significantly reduce the effective query time by using Clifford+T gate parallelism. We conclude that, in theory, fault-tolerant bucket brigade quantum RAM queries can be performed approximately with the speed of classical RAM.
  arXiv  Detail & Related papers  (2020-02-21T14:50:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.