Fugu-MT 論文翻訳(概要): Optimal Offline ORAM with Perfect Security via Simple Oblivious Priority Queues

論文の概要: Optimal Offline ORAM with Perfect Security via Simple Oblivious Priority Queues

arxiv url: http://arxiv.org/abs/2409.12021v1
Date: Wed, 18 Sep 2024 14:31:33 GMT
ステータス: 処理完了
システム内更新日: 2024-09-19 17:24:06.757853
Title: Optimal Offline ORAM with Perfect Security via Simple Oblivious Priority Queues
Title（参考訳）: 簡易優先キューによる完全セキュリティを備えた最適オフラインORAM
Authors: Thore Thießen, Jan Vahrenhold,
Abstract要約: 我々は,メモリアクセスのシーケンスを事前に把握している,いわゆるオフラインORAMについて検討する。我々は、時間フォワード処理により、不要な優先度待ち行列から完全なセキュリティを備えた、最初の最適オフラインORAMを得る。我々の構築に基づいて、我々はまた、不明瞭で完全にセキュアな構成の効率的な外部メモリインスタンス化を提示する。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Oblivious RAM (ORAM) is a well-researched primitive to hide the memory access pattern of a RAM computation; it has a variety of applications in trusted computing, outsourced storage, and multiparty computation. In this paper, we study the so-called offline ORAM in which the sequence of memory access locations to be hidden is known in advance. Apart from their theoretical significance, offline ORAMs can be used to construct efficient oblivious algorithms. We obtain the first optimal offline ORAM with perfect security from oblivious priority queues via time-forward processing. For this, we present a simple construction of an oblivious priority queue with perfect security. Our construction achieves an asymptotically optimal (amortized) runtime of $\Theta(\log N)$ per operation for a capacity of $N$ elements and is of independent interest. Building on our construction, we additionally present efficient external-memory instantiations of our oblivious, perfectly-secure construction: For the cache-aware setting, we match the optimal I/O complexity of $\Theta(\frac{1}{B} \log \frac{N}{M})$ per operation (amortized), and for the cache-oblivious setting we achieve a near-optimal I/O complexity of $O(\frac{1}{B} \log \frac{N}{M} \log\log_M N)$ per operation (amortized).
Abstract（参考訳）: ORAM(Oblivious RAM)は、RAM計算のメモリアクセスパターンを隠すための、よく研究されているプリミティブである。本稿では,メモリアクセスのシーケンスを事前に把握している,いわゆるオフラインORAMについて検討する。その理論的な重要性とは別に、オフラインのORAMは効率の悪いアルゴリズムを構築するのに使える。我々は、時間フォワード処理により、不要な優先度待ち行列から完全なセキュリティを備えた、最初の最適オフラインORAMを得る。そこで本研究では,完全なセキュリティを備えた不要な優先度待ち行列を簡易に構築する。我々の構成は、一演算あたりの$\Theta(\log N)$の漸近的に最適な(アモタイズされた)ランタイムを、N$要素のキャパシティに対して達成し、独立した関心を持つ。キャッシュを意識した設定では、$\Theta(\frac{1}{B} \log \frac{N}{M})$ per operation (amortized) の最適I/O複雑性にマッチし、キャッシュ公開設定では、ほぼ最適の$O(\frac{1}{B} \log \frac{N}{M} \log\log_M N)$ per operation(amortized)を達成します。

関連論文リスト

H$_2$O$_2$RAM: A High-Performance Hierarchical Doubly Oblivious RAM [14.803814604985957]
ORAM (Oblivious RAM) とTrusted Execution Environments (TEE) は、その相補的な性質から多くの現実世界のアプリケーションを発見した。我々は、高性能階層型O$RAM(H$O$RAM)を構築するために、新しい効率の悪いコンポーネントをいくつか導入する。その結果、H$O$RAMは実行時間を最大103$倍に削減し、ステート・オブ・テクト・ソリューションと比較してメモリ使用量を5sim44$倍に削減した。
論文参考訳（メタデータ） (2024-09-11T10:31:14Z)
A Training-free Sub-quadratic Cost Transformer Model Serving Framework With Hierarchically Pruned Attention [43.211427581302715]
大規模言語モデルにおける文脈長を増大させるため,HiP(Hierarchically Pruned Attention)を提案する。 HiPは注意機構の時間的複雑さを$O(T log T)$に減らし、空間的複雑さを$O(T)$に減らし、$T$はシーケンス長である。 HiPは, 劣化を最小限に抑えつつ, プリフィルとデコードの両方のレイテンシとメモリ使用率を著しく低減することを示す。
論文参考訳（メタデータ） (2024-06-14T08:32:45Z)
Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文参考訳（メタデータ） (2024-06-07T12:07:16Z)
Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations [92.1840862558718]
実用的な分散システムでは、労働者は概して均質ではなく、非常に多様な処理時間を持つ。本稿では、任意に遅い計算を扱うための新しい並列手法Freyaを提案する。 Freyaは従来の手法と比較して,複雑性の保証が大幅に向上していることを示す。
論文参考訳（メタデータ） (2024-05-24T13:33:30Z)
Hierarchical Context Merging: Better Long Context Understanding for Pre-trained LLMs [61.40047491337793]
本稿では,大規模言語モデルの制約を克服する新しいトレーニングフリースキームである階層型cOntext MERging(HOMER)を提案する。 HomeRは、長いインプットを管理可能なチャンクに分割する、分別/対数アルゴリズムを使用する。トークン削減技術がマージ毎に先行し、メモリ使用効率が保証される。
論文参考訳（メタデータ） (2024-04-16T06:34:08Z)
DDC-PIM: Efficient Algorithm/Architecture Co-design for Doubling Data Capacity of SRAM-based Processing-In-Memory [6.367916611208411]
等価データ容量を効果的に2倍にする効率的なアルゴリズム/アーキテクチャ共設計手法であるDDC-PIMを提案する。 DDC-PIMはMobileNetV2で約2.84タイム、EfficientNet-B0で約2.69タイム、精度の損失は無視できる。最先端のマクロと比較して、DDC-PIMは重量密度と面積効率をそれぞれ最大8.41タイムと2.75タイムに改善する。
論文参考訳（メタデータ） (2023-10-31T12:49:54Z)
Cumulative Memory Lower Bounds for Randomized and Quantum Computation [1.52292571922932]
累積記憶は時間空間の複雑さの尺度である。逐次古典計算と量子回路の両方において、累積メモリの複雑さに関する最初の下位境界を証明した。
論文参考訳（メタデータ） (2023-01-13T17:57:02Z)
Single Round-trip Hierarchical ORAM via Succinct Indices [5.437298646956505]
ランクORAMは1回の通信でデータを取得することができる。 emphcompressedクライアント側データ構造は、暗黙的に、各要素の位置をサーバに格納する。
論文参考訳（メタデータ） (2022-08-16T01:15:26Z)
Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文参考訳（メタデータ） (2022-06-30T03:15:23Z)
Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文参考訳（メタデータ） (2022-06-17T09:24:41Z)
Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文参考訳（メタデータ） (2022-06-07T18:00:01Z)

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

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