論文の概要: Towards Practical Data-Dependent Memory-Hard Functions with Optimal Sustained Space Trade-offs in the Parallel Random Oracle Model

• arxiv url: http://arxiv.org/abs/2508.06795v1
• Date: Sat, 09 Aug 2025 02:57:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-12 21:23:28.552238
• Title: Towards Practical Data-Dependent Memory-Hard Functions with Optimal Sustained Space Trade-offs in the Parallel Random Oracle Model
• Title（参考訳）: 並列ランダムOracleモデルにおける空間トレードオフを最適化した実践的データ依存型メモリハード機能の実現に向けて
• Authors: Jeremiah Blocki, Blake Holman,
• Abstract要約: メモリハード関数(MHF)は、平等主義的な作業証明を構築するのに有用な暗号プリミティブである。 我々は[BH22]のような高価な構造に依存しない新しいMHF EGSampleを開発した。
• 参考スコア（独自算出の注目度）: 8.916420423563478
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Memory-Hard Functions (MHF) are a useful cryptographic primitive to build egalitarian proofs-of-work and to help protect low entropy secrets (e.g., user passwords) against brute-forces attacks. Ideally, we would like for a MHF to have the property that (1) an honest party can evaluate the function in sequential time $\Omega(N)$, and (2) any parallel party that evaluates the function is forced to lockup $\Omega(N)$ memory for $\Omega(N)$ sequential steps. Unfortunately, this goal is not quite achievable, so prior work of Blocki and Holman [BH22] focused on designing MHFs with strong tradeoff guarantees between sustained-space complexity (SSC) and cumulative memory costs (CMC). However, their theoretical construction is not suitable for practical deployment due to the reliance on expensive constructions of combinatorial graphs. Furthermore, there is no formal justification for the heuristic use of the dynamic pebbling game in MHF analysis so we cannot rule out the possibility that there are more efficient attacks in the Parallel Random Oracle Model (PROM). Towards the goal of developing a practical MHF with provably strong SSC/CMC tradeoffs we develop a new MHF called EGSample which does not rely on expensive combinatorial constructions like [BH22]. In the dynamic pebbling model, we prove equivalent SSC/CMC tradeoffs for EGSample i.e., any the dynamic pebbling strategy either (1) locks up $\Omega(N)$ memory for $\Omega(N)$ steps, or (2) incurs cumulative memory cost at least $\Omega(N^{3-\epsilon})$. We also develop new techniques to directly establish SSC/CMC tradeoffs in the parallel random oracle model. In particular, we prove that {\em any} PROM algorithm evaluating our MHF either (1) locks up $\Omega(N)$ blocks of memory for $\Omega(N)$ steps or (2) incurs cumulative memory cost at least $\Omega(N^{2.5-\epsilon})$.
• Abstract（参考訳）: メモリハード関数(MHF)は、平等主義的証明を構築する上で有用な暗号プリミティブであり、低エントロピーシーシークレット(例えばユーザパスワード)をブルートフォース攻撃から保護するのに役立つ。 理想的には、(1)正直な当事者が$\Omega(N)$、(2)関数を評価する任意の並列パーティが$\Omega(N)$メモリを$\Omega(N)$シーケンシャルステップでロックアップしなければなりません。 残念ながら、この目標はあまり達成できないため、Blocki と Holman [BH22] の以前の作業は、持続的空間複雑性(SSC)と累積メモリコスト(CMC)の間の強いトレードオフを保証する MHF の設計に重点を置いていた。 しかし、それらの理論的な構成は、組合せグラフの高価な構築に依存しているため、実践的な展開には適していない。 さらに,MHF解析における動的ペブブリングゲームのヒューリスティック使用に対する公式な正当性は存在せず,並列ランダムOracleモデル(PROM)により効率的な攻撃が存在する可能性を排除できない。 実証可能な強力なSSC/CMCトレードオフを持つ実用的なMHFを開発することを目的として,[BH22]のような高価な組合せ構造に依存しないEGSampleと呼ばれる新しいMHFを開発する。 動的ペブブリングモデルでは、ESGample の SSC/CMC トレードオフ、すなわち、(1)$\Omega(N)$ memory for $\Omega(N)$ steps または (2) Incurs cumulative memory cost at least $\Omega(N^{3-\epsilon})$ をロックアップする。 また,並列ランダムオラクルモデルにおいて,SSC/CMCトレードオフを直接確立するための新しい手法を開発した。 特に、我々のMHFを評価するProperMアルゴリズムは、(1)$\Omega(N)$のメモリブロックを$\Omega(N)$のステップでロックするか、(2)少なくとも$\Omega(N^{2.5-\epsilon})$で累積メモリコストを発生させることを証明している。

関連論文リスト

• The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits [10.329863009504303]
  我々は、$O(fracnDelta2)$の最適なサンプル複雑さを利用するサブ線形メモリを持つストリーミングアルゴリズムは、$Omega(fraclog (1/Delta)log (1/Delta)$ passを必要とすることを示した。 この結果は,[ICML'21] の$O(log(frac1Delta))$-passアルゴリズムと一致し, [ICML'21] は$O(1)$メモリしか使用せず, Assadi と Wang が提案したオープンな質問に答える。
  論文  参考訳（メタデータ） (2023-09-06T16:41:41Z)
• H$_2$O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models [110.06476624089679]
  メモリフットプリントを大幅に削減する新しいKVキャッシュの実装手法を提案する。 我々のアプローチは、トークンのごく一部が、注意点の計算において、ほとんどの価値に寄与する、という観察に基づいている。 我々は,最近のトークンとH$のバランスを動的に保持するKVキャッシュ消去ポリシーであるヘビーヒッター(H$O)を提案する。
  論文  参考訳（メタデータ） (2023-06-24T20:11:14Z)
• Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
  計算・比較プログラム(Computer-and-compare program)として知られる回避関数のクラスに対する量子コピー保護スキームを導入する。 我々は,量子乱数オラクルモデル(QROM)において,完全悪意のある敵に対する非自明なセキュリティを実現することを証明した。 補完的な結果として、「セキュアソフトウェアリース」という,ソフトウェア保護の概念の弱さが示される。
  論文  参考訳（メタデータ） (2020-09-29T08:41:53Z)

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

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