論文の概要: Single Round-trip Hierarchical ORAM via Succinct Indices

• arxiv url: http://arxiv.org/abs/2208.07489v3
• Date: Thu, 13 Jun 2024 00:16:38 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-15 02:48:35.012282
• Title: Single Round-trip Hierarchical ORAM via Succinct Indices
• Title（参考訳）: Sccinct Indices を用いた単一ラウンドトリップ階層型ORAM
• Authors: William Holland, Olga Ohrimenko, Anthony Wirth,
• Abstract要約: ランクORAMは1回の通信でデータを取得することができる。 emphcompressedクライアント側データ構造は、暗黙的に、各要素の位置をサーバに格納する。
• 参考スコア（独自算出の注目度）: 5.437298646956505
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Access patterns to data stored remotely create a side channel that is known to leak information even if the content of the data is encrypted. To protect against access pattern leakage, Oblivious RAM is a cryptographic primitive that obscures the (actual) access trace at the expense of additional access and periodic shuffling of the server's contents. A class of ORAM solutions, known as Hierarchical ORAM, has achieved theoretically \emph{optimal} logarithmic bandwidth overhead. However, to date, Hierarchical ORAMs are seen as only theoretical artifacts. This is because they require a large number of communication round-trips to locate (shuffled) elements at the server and involve complex building blocks such as cuckoo hash tables. To address the limitations of Hierarchical ORAM schemes in practice, we introduce Rank ORAM; the first Hierarchical ORAM that can retrieve data with a single round-trip of communication (as compared to a logarithmic number in previous work). To support non-interactive communication, we introduce a \emph{compressed} client-side data structure that stores, implicitly, the location of each element at the server. In addition, this location metadata enables a simple protocol design that dispenses with the need for complex cuckoo hash tables. Rank ORAM requires asymptotically smaller memory than existing (non-Hierarchical) state-of-the-art practical ORAM schemes (e.g., Ring ORAM) while maintaining comparable bandwidth performance. Our experiments on real network file-system traces demonstrate a reduction in client memory, against existing approaches, of a factor of~$100$. For example, when {outsourcing} a database of $17.5$TB, required client-memory is only $290$MB vs. $40$GB for standard approaches.
• Abstract（参考訳）: リモートに保存されたデータへのアクセスパターンは、たとえデータが暗号化されたとしても、情報を漏らすことが知られているサイドチャネルを生成する。 アクセスパターンの漏洩を防ぐために、Oblivious RAMは(実際に)アクセストレースを隠蔽する暗号プリミティブであり、サーバのコンテンツの追加アクセスと定期的なシャッフルを犠牲にしている。 階層型ORAM(Hierarchical ORAM)と呼ばれるORAMソリューションのクラスは理論上、対数帯域幅オーバーヘッドを達成している。 しかし、現在まで階層型ORAMは理論的な成果物にすぎないと見なされている。 これは、サーバに(シャッフルされた)要素を見つけ出し、cuckooハッシュテーブルのような複雑なビルディングブロックを含むために、多数の通信ラウンドトリップを必要とするためである。 実際に,階層型ORAM方式の限界に対処するために,単一ラウンドトリップの通信でデータを取得することができる最初の階層型ORAMであるRange ORAMを導入する。 非インタラクティブ通信をサポートするために,サーバに各要素の位置を暗黙的に格納するクライアント側データ構造を導入する。 さらに、この位置メタデータは、複雑なcuckooハッシュテーブルを必要としない単純なプロトコル設計を可能にする。 Rank ORAMは、既存の(非階層的な)最先端のORAMスキーム(例えば、Ring ORAM)よりも漸近的に小さいメモリを必要とする。 実ネットワークファイルシステムトレースに関する実験では,クライアントメモリの削減効果が既存手法と比較して100ドル程度に抑えられた。 例えば、$7.5$TBのデータベースを {outsourcing} する場合、標準的なアプローチでは、必要となるクライアントメモリは290$MBであるのに対して、40$GBである。

関連論文リスト

• Hierarchical Context Merging: Better Long Context Understanding for Pre-trained LLMs [61.40047491337793]
  本稿では,大規模言語モデルの制約を克服する新しいトレーニングフリースキームである階層型cOntext MERging(HOMER)を提案する。 HomeRは、長いインプットを管理可能なチャンクに分割する、分別/対数アルゴリズムを使用する。 トークン削減技術がマージ毎に先行し、メモリ使用効率が保証される。
  論文  参考訳（メタデータ） (2024-04-16T06:34:08Z)
• RelayAttention for Efficient Large Language Model Serving with Long System Prompts [59.50256661158862]
  本稿では,長いシステムプロンプトを含むLCMサービスの効率を向上させることを目的とする。 これらのシステムプロンプトの処理には、既存の因果注意アルゴリズムにおいて、大量のメモリアクセスが必要である。 本稿では,DRAMから入力トークンのバッチに対して,DRAMから隠れた状態を正確に1回読み取ることのできるアテンションアルゴリズムであるRelayAttentionを提案する。
  論文  参考訳（メタデータ） (2024-02-22T18:58:28Z)
• Topology-aware Embedding Memory for Continual Learning on Expanding Networks [63.35819388164267]
  本稿では,メモリリプレイ技術を用いて,メモリ爆発問題に対処する枠組みを提案する。 Topology-aware Embedding Memory (TEM) を用いたPDGNNは最先端技術よりも優れている。
  論文  参考訳（メタデータ） (2024-01-24T03:03:17Z)
• Systems Architecture for Quantum Random Access Memory [0.6386668251980657]
  量子ランダムアクセスメモリ(QRAM)は、量子クエリを実現するための有望なアーキテクチャである。 提案するQRAMの固有バイアスノイズレジリエンスを、NISQ(Noisy Intermediate-Scale Quantum)またはFTQC(Fault-Tolerant Quantum Computing)ハードウェア上で実装する方法を示す。
  論文  参考訳（メタデータ） (2023-06-05T20:52:28Z)
• Efficient and Error-Resilient Data Access Protocols for a Limited-Sized Quantum Random Access Memory [7.304498344470287]
  我々は、QRAMのサイズを増大させることなく、より大きなデータサイズへのアクセスに注力する。 そこで本研究では,QRAMレベルを$n$にすることなく,単語長がより大きいデータを読み込む新しいプロトコルを提案する。 データクエリプロセスの並列性を活用することで,O(n+k)$の時間複雑性を実現し,エラースケーリング性能を向上させる。
  論文  参考訳（メタデータ） (2023-03-09T12:21:18Z)
• NumS: Scalable Array Programming for the Cloud [82.827921577004]
  タスクベース分散システム上でNumPyのような表現を最適化する配列プログラミングライブラリであるNumSを提案する。 これはLoad Simulated Hierarchical Scheduling (LSHS)と呼ばれる新しいスケジューラによって実現される。 LSHSは、ネットワーク負荷を2倍減らし、メモリを4倍減らし、ロジスティック回帰問題において実行時間を10倍減らし、Rayの性能を向上させる。
  論文  参考訳（メタデータ） (2022-06-28T20:13:40Z)
• PIM-DRAM:Accelerating Machine Learning Workloads using Processing in Memory based on DRAM Technology [2.6168147530506958]
  MLワークロードにおける行列ベクトル演算を高速化する処理インメモリ(PIM)プリミティブを提案する。 提案したアーキテクチャ,マッピング,データフローは,GPUよりも最大で23倍,6.5倍のメリットが得られることを示す。
  論文  参考訳（メタデータ） (2021-05-08T16:39:24Z)
• ROME: Robustifying Memory-Efficient NAS via Topology Disentanglement and Gradient Accumulation [106.04777600352743]
  微分可能なアーキテクチャサーチ(DARTS)は、スーパーネット全体がメモリに格納されているため、メモリコストが大幅に低下する。 シングルパスのDARTSが登場し、各ステップでシングルパスのサブモデルのみを選択する。 メモリフレンドリーだが、計算コストも低い。 RObustifying Memory-Efficient NAS (ROME) と呼ばれる新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-11-23T06:34:07Z)
• Parallelising the Queries in Bucket Brigade Quantum RAM [69.43216268165402]
  量子アルゴリズムは、しばしばデータベースのような方法で格納された情報にアクセスするために量子RAM(QRAM)を使用する。 本稿では,Clifford+Tゲートの並列性を利用して,効率的なクエリ時間を大幅に短縮する手法を提案する。 理論的には、フォールトトレラントバケットの量子RAMクエリは古典的なRAMの速度とほぼ一致する。
  論文  参考訳（メタデータ） (2020-02-21T14:50:03Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。