論文の概要: 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})$で累積メモリコストを発生させることを証明している。
関連論文リスト
- Time Is All It Takes: Spike-Retiming Attacks on Event-Driven Spiking Neural Networks [87.16809558673403]
スパイキングニューラルネットワーク(SNN)は離散スパイクで計算し、時間構造を利用する。
イベント駆動SNNにおけるスパイク数と振幅を保存しながら、既存のスパイクを繰り返すタイミングのみの敵について検討する。
論文 参考訳（メタデータ） (2026-02-03T09:06:53Z) - MaskPro: Linear-Space Probabilistic Learning for Strict (N:M)-Sparsity on Large Language Models [53.36415620647177]
半構造化された空間は、M$M$の重みからN$の要素を戦略的に保持することで、有望なソリューションを提供する。
既存の(N:M)互換のアプローチは通常、かなりのエラーに悩まされるルールベースの階層的な欲求探索と、禁止的なトレーニングコストを引き起こす勾配駆動学習の2つのカテゴリに分類される。
MaskProという新しい線形空間確率的フレームワークを提案する。これは、M$連続重みごとに事前のカテゴリー分布を学習し、その後、この分布を活用して(N:M)スパーシリティを$N$-wayサンプリングを通じて生成することを目的としている。
論文 参考訳（メタデータ） (2025-06-15T15:02:59Z) - Cloning Games, Black Holes and Cryptography [50.022147589030304]
クローンゲーム解析のための新しいツールキットを提案する。
このフレームワークにより、バイナリフェーズ状態に基づいて新しいクローンゲームを分析することができる。
連成位相の変分最適境界は、ブラックホールの理想化されたモデルで衝突する情報について定量的な洞察を与えることを示す。
論文 参考訳（メタデータ） (2024-11-07T14:09:32Z) - SGD with memory: fundamental properties and stochastic acceleration [15.25021403154845]
非確率設定では、損失収束$L_tsim C_Lt-xiの最適指数$xi$は、平滑なGDの倍である。
メモリ1のアルゴリズムでは、安定性を維持しながら、任意に$C_L$を小さくすることができる。
論文 参考訳（メタデータ） (2024-10-05T16:57:40Z) - A Quantum Approach For Reducing Communications in Classical Secure Computations with Long Outputs [2.3465488122819123]
我々は、2つの当事者が長い出力でセキュアな計算を行いたいという古典的な暗号問題について研究する。
本研究では,セキュリティを近似したセキュアな関数サンプリングを実現するために,まず量子暗号プロトコルを設計する。
論文 参考訳（メタデータ） (2023-10-08T16:07:46Z) - 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) - Invertible Bloom Lookup Tables with Less Memory and Randomness [23.724300017513574]
Invertible Bloom Lookup Tables (IBLT) は、セット和解プロトコル、エラー訂正符号、高度な暗号プリミティブの設計に応用されている。
IBLTは同時に空間効率が良く、ランダム性が低い新しい構成を提案する。
k$ の独立ハッシュ関数 $h:U to [Cn]$ for some enough large constant $C$ guarantees with probability $1 - 2-Omega(k)$ that least $n/2$ key will have a unique hash value。
論文 参考訳（メタデータ） (2023-06-13T07:15:02Z) - A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian
Process Bandits [118.22458816174144]
そこで本稿では,エポックで動作するロバストな除去型アルゴリズムを提案し,探索と頻繁な切替を併用して,小さなアクションサブセットを選択し,各アクションを複数タイミングで実行する。
我々のアルゴリズムであるGP Robust Phased Elimination (RGP-PE) は、探索とエクスプロイトによる汚職に対するロバストネスのバランスに成功している。
GPバンディット設定におけるロバスト性の最初の実証的研究を行い,アルゴリズムが様々な敵攻撃に対してロバストであることを示す。
論文 参考訳（メタデータ） (2022-02-03T21:19:36Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。