論文の概要: Cryptography from Lossy Reductions: Towards OWFs from ETH, and Beyond

• arxiv url: http://arxiv.org/abs/2505.21442v1
• Date: Tue, 27 May 2025 17:15:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-28 17:05:58.822173
• Title: Cryptography from Lossy Reductions: Towards OWFs from ETH, and Beyond
• Title（参考訳）: ロスシーリダクションからの暗号:ETHからOWFへ、そしてそれ以上へ
• Authors: Pouria Fallahpour, Alex B. Grilo, Garazi Muguruza, Mahshid Riahinia,
• Abstract要約: ワンウェイ関数(OWF)は現代の暗号の基礎となる。 我々は、OWFが存在するか、あるいは、いかなる保証問題に対しても損失を減らしていることを示す。
• 参考スコア（独自算出の注目度）: 1.0687104237121408
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: One-way functions (OWFs) form the foundation of modern cryptography, yet their unconditional existence remains a major open question. In this work, we study this question by exploring its relation to lossy reductions, i.e., reductions~$R$ for which it holds that $I(X;R(X)) \ll n$ for all distributions~$X$ over inputs of size $n$. Our main result is that either OWFs exist or any lossy reduction for any promise problem~$\Pi$ runs in time~$2^{\Omega(\log\tau_\Pi / \log\log n)}$, where $\tau_\Pi(n)$ is the infimum of the runtime of all (worst-case) solvers of~$\Pi$ on instances of size~$n$. In fact, our result requires a milder condition, that $R$ is lossy for sparse uniform distributions (which we call mild-lossiness). It also extends to $f$-reductions as long as $f$ is a non-constant permutation-invariant Boolean function, which includes And-, Or-, Maj-, Parity-, Modulo $k$, and Threshold $k$-reductions. Additionally, we show that worst-case to average-case Karp reductions and randomized encodings are special cases of mildly-lossy reductions and improve the runtime above as $2^{\Omega(\log \tau_\Pi)}$ when these mappings are considered. Restricting to weak fine-grained OWFs, this runtime can be further improved as~$\Omega(\tau_\Pi)$. Taking~$\Pi$ as~$kSAT$, our results provide sufficient conditions under which (fine-grained) OWFs exist assuming the Exponential Time Hypothesis (ETH). Conversely, if (fine-grained) OWFs do not exist, we obtain impossibilities on instance compressions (Harnik and Naor, FOCS 2006) and instance randomizations of~$kSAT$ under the ETH. Finally, we partially extend these findings to the quantum setting; the existence of a pure quantum mildly-lossy reduction for $\Pi$ within the runtime~$2^{o(\log\tau_\Pi / \log\log n)}$ implies the existence of one-way state generators.
• Abstract（参考訳）: ワンウェイ関数(OWF)は現代の暗号の基礎を形成するが、その無条件の存在は大きな疑問である。 本研究では、損失還元(英語版)との関係、すなわち、$I(X;R(X)) \ll n$ for all distributions~$X$ over inputs of size $n$であるような還元(英語版)~$R$)について検討する。 我々の主な結果は、OWF が存在するか、あるいは任意の約束問題に対して損失の少ない$$\Pi$ run in time~$2^{\Omega(\log\tau_\Pi / \log\log n)}$, where $\tau_\Pi(n)$ is the infimum of the runtime of all (worst-case) solvers of~$$\Pi$ on instance of size~$n$である。 実のところ、我々の結果はより穏やかな条件を必要としており、R$はスパース均一分布(軽さと呼ばれる)に対して損失である。 また、$f$は、And-、Or-、Mag-、Parity-、Modulo $k$、Threshold $k$-reductionsを含む非コンスタントな置換不変ブール関数である。 さらに、平均ケースのカープ削減とランダム化エンコーディングは、このマッピングを考慮すれば、上述の270Omega(\log \tau_\Pi)}のランタイムを改善する特別なケースであることを示す。 弱い粒度のOWFに制限されるため、このランタイムは~$\Omega(\tau_\Pi)$としてさらに改善できる。 この結果から, 指数時間仮説 (ETH) を仮定した(きめ細かい) OWF が存在するような条件が得られた。 逆に、(きめの細かい) OWF が存在しなければ、インスタンス圧縮(Harnik and Naor, FOCS 2006)と、ETHの下でのインスタンスランダム化–$kSAT$を得る。 2^{o(\log\tau_\Pi / \log\log n)}$は、一方向状態発生器の存在を意味する。

関連論文リスト

• Batched Stochastic Bandit for Nondegenerate Functions [8.015503209312786]
  本稿では,非退化関数に対するバッチ帯域学習問題について検討する。 本稿では,非退化関数に対するバッチバンドイット問題をほぼ最適に解くアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-09T12:50:16Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits [4.811176167998627]
  我々は、未知の分布から生じる無限に多くのバンドイットアームを用いて純粋探索を研究する。 私たちのゴールは、平均的な報酬が1-delta$の1つの高品質なアームを、最高の$eta$-fraction of armsの1つとして$varepsilon$内で効率的に選択することにあります。
  論文  参考訳（メタデータ） (2023-06-03T04:00:47Z)
• Algorithms for Acyclic Weighted Finite-State Automata with Failure Arcs [66.47284608209692]
  Oleft(|E| + s |Sigma| |Q| T_textmax log|Sigma|right)$で実行される一般非巡回WFSAのアルゴリズムを提案する。 障害遷移トポロジーがCRFで実証された条件を満たすと、$T_textmax$ factorを落とすことができる。 後者の場合 (ring-weighted acyclic WFSAs) では、$style Oleft(|E| + |Sigma| |) を持つ別のアルゴリズムの複雑さを与える。
  論文  参考訳（メタデータ） (2023-01-17T13:15:44Z)
• On Submodular Contextual Bandits [92.45432756301231]
  作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。 Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
  論文  参考訳（メタデータ） (2021-12-03T21:42:33Z)
• Cascading Bandit under Differential Privacy [21.936577816668944]
  本研究では,カスケードバンドにおける自己差分プライバシー(DP)と局所差分プライバシー(LDP)について検討する。 DPでは,$epsilon$-indistinguishability を保証し,$mathcalO(fraclog3 Tepsilon)$を任意の小さな$xi$に対して後悔するアルゴリズムを提案する。 Epsilon$,$delta$)-LDPの下では、プライバシの予算とエラー確率のトレードオフを通じて、K2$依存を緩和します。
  論文  参考訳（メタデータ） (2021-05-24T07:19:01Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time [5.812499828391904]
  リスト化可能部分空間のリカバリにおいて、入力は$n$ポイント$alpha n$(ある$alpha ll 1/2$)の集合であり、それらは分布$mathcalD$から引き出される。 本研究は, より高速な固定ポリノミカルランニング時間を用いて, アンフェクタブルな集中防止誤差の3つの側面について, 結果を改善するものである。
  論文  参考訳（メタデータ） (2020-02-12T18:30:09Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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