論文の概要: Non-Adaptive Cryptanalytic Time-Space Lower Bounds via a Shearer-like Inequality for Permutations

• arxiv url: http://arxiv.org/abs/2505.00894v1
• Date: Thu, 01 May 2025 22:17:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-05 17:21:19.856302
• Title: Non-Adaptive Cryptanalytic Time-Space Lower Bounds via a Shearer-like Inequality for Permutations
• Title（参考訳）: 非適応的クリプトアナリシス時間空間下界のシアーライクな不等式による置換
• Authors: Itai Dinur, Nathan Keller, Avichai Marmor,
• Abstract要約: 適応性は、(おそらく無制限の)前処理時間による暗号解析時空間トレードオフにおいて、かなりの余分なパワーを提供することを示す。 本稿では,検索と決定の幅広い問題に対して,非適応的前処理アルゴリズムを解析できる新しいモデルを提案する。
• 参考スコア（独自算出の注目度）: 10.282294365033785
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The power of adaptivity in algorithms has been intensively studied in diverse areas of theoretical computer science. In this paper, we obtain a number of sharp lower bound results which show that adaptivity provides a significant extra power in cryptanalytic time-space tradeoffs with (possibly unlimited) preprocessing time. Most notably, we consider the discrete logarithm (DLOG) problem in a generic group of $N$ elements. The classical `baby-step giant-step' algorithm for the problem has time complexity $T=O(\sqrt{N})$, uses $O(\sqrt{N})$ bits of space (up to logarithmic factors in $N$) and achieves constant success probability. We examine a generalized setting where an algorithm obtains an advice string of $S$ bits and is allowed to make $T$ arbitrary non-adaptive queries that depend on the advice string (but not on the challenge group element). We show that in this setting, the $T=O(\sqrt{N})$ online time complexity of the baby-step giant-step algorithm cannot be improved, unless the advice string is more than $\Omega(\sqrt{N})$ bits long. This lies in stark contrast with the classical adaptive Pollard's rho algorithm for DLOG, which can exploit preprocessing to obtain the tradeoff curve $ST^2=O(N)$. We obtain similar sharp lower bounds for several other cryptanalytic problems. To obtain our results, we present a new model that allows analyzing non-adaptive preprocessing algorithms for a wide array of search and decision problems in a unified way. Since previous proof techniques inherently cannot distinguish between adaptive and non-adaptive algorithms for the problems in our model, they cannot be used to obtain our results. Consequently, our proof uses a variant of Shearer's lemma for this setting, due to Barthe, Cordero-Erausquin, Ledoux, and Maurey (2011). This seems to be the first time a variant of Shearer's lemma for permutations is used in an algorithmic context.
• Abstract（参考訳）: アルゴリズムにおける適応性の力は、理論計算機科学の様々な領域で集中的に研究されている。 本稿では,適応性が,前処理時間(おそらく無制限)の暗号解析時空間トレードオフにおいて,重要な余分なパワーを与えることを示す,多数のシャープな下界結果を得る。 特に、$N$要素の一般群における離散対数問題(DLOG)を考える。 この問題の古典的な 'baby-step giant-step' アルゴリズムは、時間複雑性$T=O(\sqrt{N})$, using $O(\sqrt{N})$ bits of space ($N$の対数係数まで) を持ち、一定の成功確率を達成する。 アルゴリズムが$S$ビットのアドバイス文字列を取得し、アドバイス文字列に依存する任意の非適応クエリを$T$にすることができる(チャレンジ群要素に依存しない)、一般化された設定について検討する。 この設定では、アドバイス文字列が$\Omega(\sqrt{N})$ bits 以上でない限り、ベビーステップの巨大ステップアルゴリズムのオンライン時間複雑性は改善できない。 これは、DLOG に対する古典的適応ポラードの rho アルゴリズムとは対照的であり、これは事前処理を利用してトレードオフ曲線 $ST^2=O(N)$ を得ることができる。 いくつかの他の暗号解析問題に対して、同様の鋭い下界を得る。 そこで本研究では,検索と決定の幅広い問題に対して,非適応前処理アルゴリズムを統一的に解析できる新しいモデルを提案する。 従来の証明手法では,適応的アルゴリズムと非適応的アルゴリズムを区別できないため,結果を得るためには使用できない。 その結果、我々の証明は、Barthe, Cordero-Erausquin, Ledoux, Maurey (2011) によるシェラーの補題の変種を用いている。 アルゴリズムの文脈で、置換のためのシェラーの補題の変種が使われるのは、これが初めてと思われる。

関連論文リスト

• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Deterministic Nonsmooth Nonconvex Optimization [82.39694252205011]
  次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。 我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-16T13:57:19Z)
• Choosing the Right Algorithm With Hints From Complexity Theory [16.33500498939925]
  我々は,メトロポリスのアルゴリズムが,合理的な問題サイズを考慮に入れた全てのアルゴリズムの中で,明らかに最良のものであることを示す。 このタイプの人工アルゴリズムは、$O(n log n)$ランタイムを持つので、重要度に基づくコンパクト遺伝的アルゴリズム(sig-cGA)は、高い確率で、DLB問題を解くことができる。
  論文  参考訳（メタデータ） (2021-09-14T11:12:32Z)
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
  本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。 複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。 少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
  論文  参考訳（メタデータ） (2021-06-14T07:36:25Z)
• Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint [20.104148319012854]
  サイズ制約に関して、必ずしも単調ではない部分モジュラ函数に対して存在および並列化可能である。 最適な適応性とほぼ最適な複雑性クエリを持つアルゴリズムによって達成される最適な近似係数を、0.193 - varepsilon$に改善する。
  論文  参考訳（メタデータ） (2020-09-03T22:43:55Z)
• The $(1+(\lambda,\lambda))$ Genetic Algorithm for Permutations [0.0]
  我々は、$(lambda,lambda)$の遺伝的アルゴリズムが、$O(n2)$のフィットネスクエリで最適であることを示す。 また,Hamと呼ばれる置換に基づく問題に対して,このアルゴリズムの最初の解析を行った。
  論文  参考訳（メタデータ） (2020-04-18T17:04:57Z)
• Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
  基本アルゴリズムを選択できるメタアルゴリズムを開発した。 基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
  論文  参考訳（メタデータ） (2020-03-03T18:46:34Z)
• Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives [10.291482850329892]
  混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。 数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。 さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
  論文  参考訳（メタデータ） (2020-01-17T18:47:02Z)

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

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