論文の概要: Lower Bounds on Black-Box Constructions of Pseudorandom Functions

• arxiv url: http://arxiv.org/abs/2608.14501v1
• Date: Fri, 14 Aug 2026 17:15:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-17 20:14:29.451351
• Title: Lower Bounds on Black-Box Constructions of Pseudorandom Functions
• Title（参考訳）: 擬似関数のブラックボックス構成に関する下界
• Authors: Bar Alon, Itai Dinur, Muthuramakrishnan Venkitasubramaniam,
• Abstract要約: Goldreich、Goldwasser、Micaliは擬似乱数生成器(PRG)へのブラックボックスアクセスを用いた擬似乱数関数(PRF)を構築した。 本研究では, PRG からの完全ブラックボックス構成について検討する。 我々の主な結果は、そのような構造が$o(mathsfin/logmathsfin)$ emphnon-adaptivecall to the PRG, where $mathsfinを持つことができないことを示している。
• 参考スコア（独自算出の注目度）: 13.173892310083254
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In their seminal work, Goldreich, Goldwasser, and Micali [CRYPTO 1984] constructed a pseudorandom function (PRF) using a black-box access to a pseudorandom generator (PRG). When combined with Levin's domain extension technique, the GGM construction invokes the PRG $ω(\log n)$ times, where $n$ denotes the input length to the PRG. To this day, no black-box construction achieving fewer calls is known. Recently, Beimel, Malkin, and Mazor [CRYPTO 2024] showed that for a certain family of constructions, which they termed \emph{tree constructions}, the GGM construction is optimal. However, the basic challenge of whether a PRF can be built with just \emph{one invocation} of the PRG still remains open. In this work, we consider fully black-box constructions of PRFs from PRGs, where both the construction and the reduction are required to be black-box, and the number of interactions the reduction makes with the adversary is independent of the number of oracle calls the adversary makes to its underlying function within each interaction. Our main result shows that no such construction can have $o(n/\log n)$ and $o(\mathsf{in}/\log\mathsf{in})$ \emph{non-adaptive} calls to the PRG, where $\mathsf{in}$ is the input length of the PRF. This impossibility holds even for weak PRFs with one-bit output, where the adversary is restricted to making i.i.d. uniformly random queries. In addition, we prove a lower bound for weak PRFs with sufficiently long outputs that holds even when the construction is allowed to make adaptive queries to the PRG.
• Abstract（参考訳）: Goldreich, Goldwasser, Micali (CRYPTO 1984) は、擬似乱数生成器 (PRG) へのブラックボックスアクセスを用いた擬似乱数関数 (PRF) を構築した。 レヴィンのドメイン拡張技法と組み合わせると、GGMの構成はPRG $ω(\log n)$ timesを呼び出し、$n$はPRGへの入力長を表す。 現在まで、電話の少ないブラックボックスの建設は知られていない。 最近、Beimel, Malkin, and Mazor (CRYPTO 2024) は、ある構成の族に対して、それらが 'emph{tree constructions' と呼んだとき、GGM の構成は最適であることを示した。 しかし、PRGのemph{one invocation}だけでPRFを構築できるかどうかという基本的な問題は、まだ未解決のままである。 本研究では,PRG からの PRF の完全ブラックボックス構成について検討し,その構成と削減の両方がブラックボックスでなければならないこと,削減と敵との相互作用の回数は,相手がそれぞれの相互作用の中で基礎となる機能に作用するオラクルの数とは無関係であることを示す。 我々の主な結果は、そのような構造が$o(n/\log n)$と$o(\mathsf{in}/\log\mathsf{in})$ \emph{non-adaptive}コールを持つことができないことを示している。 この不合理性は、1ビットの出力を持つ弱いPRFに対しても成り立ち、敵は一様ランダムなクエリに制限される。 さらに, PRG に対して適応的なクエリが可能である場合でも, 十分に長い出力を持つ弱い PRF に対する低いバウンダリの証明を行う。

関連論文リスト

• Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPs [56.28491566735463]
  既存のマルコフ決定過程のアルゴリズムは、$smashtildeO(dH2sqrtT)$を後悔する。 本稿では,最悪の場合において既存の境界を復元し,構造化されたMDPに対して改善する,$smashtildeO(dH2bar_TsqrtT)$の後悔を実現するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-05-19T12:39:32Z)
• Cryptanalysis of the Legendre Pseudorandom Function over Extension Fields [0.0]
  レジェンドレット擬似関数(Regendre Pseudorandom Function、PRF)は、レジェンドレットシンボル上に構築された高効率な暗号プリミティブである。 最近の関心は拡張フィールドの$mathbbF_pr$よりもインスタンス化に移行している。 本稿では, 1 度レジェンダー PRF を $mathbbF_pr$ で動作させる, 包括的な暗号解析手法を提案する。
  論文  参考訳（メタデータ） (2026-04-06T16:35:32Z)
• Dimension-Independent Convergence of Underdamped Langevin Monte Carlo in KL Divergence [50.719298242863744]
  Underdamped Langevin dynamics (ULD) は Gibbs 分布の$propto e-V$ に広く使われているサンプルである。 離散化LDDにおける最初の次元自由なKL分散境界を証明した。
  論文  参考訳（メタデータ） (2026-03-02T22:14:38Z)
• On Limits on the Provable Consequences of Quantum Pseudorandomness [2.683233968306505]
  量子擬似ランダム性が他のものから構築される可能性は低いことを示すいくつかの証拠を示す。 我々は、1つの量子擬似ランダム性が存在するが、別の擬似ランダム性が存在しない新しい神託世界を研究する。
  論文  参考訳（メタデータ） (2025-10-06T21:38:04Z)
• Black-Box Separation Between Pseudorandom Unitaries, Pseudorandom Isometries, and Pseudorandom Function-Like States [6.67838905076129]
  Pseudorandom関数(PRF)は古典暗号における最も基本的なプリミティブの1つである。 量子暗号では、PRFは存在せず、それらの量子アナログが存在する可能性がある。 本稿では、これらの自然量子アナログが等価であるかどうかを部分的に解決する。
  論文  参考訳（メタデータ） (2025-10-06T04:50:37Z)
• New constructions of pseudorandom codes [23.22566380210149]
  Pseudorandom error-correcting codes (PRCs) は、生成AIモデルをウォーターマークする新しい暗号プリミティブである。 本研究では,一定誤差率に対して頑健なPRCが存在するという仮定を考察する。 これは$textitunconditionally$ indistinguishable from random by $textpoly(n)$ time, $O(n1.5-varepsilon) spaceである。
  論文  参考訳（メタデータ） (2024-09-11T19:14:39Z)
• Crooked indifferentiability of the Feistel Construction [53.572703605492904]
  Feistelの構築は擬似乱数置換とブロック暗号を構築するための基本的な技術である。 本稿では, アルゴリズム置換攻撃に対しても, 簡単な構成法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2024-04-15T04:29:24Z)
• Communication-Constrained Bandits under Additive Gaussian Noise [111.06688156723018]
  クライアントが学習者にコミュニケーション制約のあるフィードバックを提供する分散マルチアームバンディットについて検討する。 我々は、この下限を小さな加法係数にマッチさせるマルチフェーズ帯域幅アルゴリズム、$mathtUEtext-UCB++$を提案する。
  論文  参考訳（メタデータ） (2023-04-25T09:31:20Z)
• On Submodular Contextual Bandits [92.45432756301231]
  作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。 Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
  論文  参考訳（メタデータ） (2021-12-03T21:42:33Z)

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

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