論文の概要: Non-Trivial Zero-Knowledge Implies One-Way Functions
- arxiv url: http://arxiv.org/abs/2602.17651v1
- Date: Thu, 19 Feb 2026 18:56:24 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-20 15:21:29.412659
- Title: Non-Trivial Zero-Knowledge Implies One-Way Functions
- Title（参考訳）: 非Trivial Zero-Knowledge は 1-Way 関数に影響を及ぼす
- Authors: Suvradip Chakraborty, James Hulett, Dakshita Khurana, Kabir Tomer,
- Abstract要約: 我々は, ゼロ知識エムの最悪の複雑性から, ワンウェイ関数のキャラクタリゼーションを得る。
以上の結果から,最悪の場合の硬さから一方通行の機能を構築できる可能性が示唆された。
- 参考スコア（独自算出の注目度）: 7.5752750293638735
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A recent breakthrough [Hirahara and Nanashima, STOC'2024] established that if $\mathsf{NP} \not \subseteq \mathsf{ioP/poly}$, the existence of zero-knowledge with negligible errors for $\mathsf{NP}$ implies the existence of one-way functions (OWFs). In this work, we obtain a characterization of one-way functions from the worst-case complexity of zero-knowledge {\em in the high-error regime}. We say that a zero-knowledge argument is {\em non-trivial} if the sum of its completeness, soundness and zero-knowledge errors is bounded away from $1$. Our results are as follows, assuming $\mathsf{NP} \not \subseteq \mathsf{ioP/poly}$: 1. {\em Non-trivial} Non-Interactive ZK (NIZK) arguments for $\mathsf{NP}$ imply the existence of OWFs. Using known amplification techniques, this result also provides an unconditional transformation from weak to standard NIZK proofs for all meaningful error parameters. 2. We also generalize to the interactive setting: {\em Non-trivial} constant-round public-coin zero-knowledge arguments for $\mathsf{NP}$ imply the existence of OWFs, and therefore also (standard) four-message zero-knowledge arguments for $\mathsf{NP}$. Prior to this work, one-way functions could be obtained from NIZKs that had constant zero-knowledge error $ε_{zk}$ and soundness error $ε_{s}$ satisfying $ε_{zk} + \sqrt{ε_{s}} < 1$ [Chakraborty, Hulett and Khurana, CRYPTO'2025]. However, the regime where $ε_{zk} + \sqrt{ε_{s}} \geq 1$ remained open. This work closes the gap, and obtains new implications in the interactive setting. Our results and techniques could be useful stepping stones in the quest to construct one-way functions from worst-case hardness.
- Abstract（参考訳）: 最近のブレークスルー (Hirahara and Nanashima, STOC'2024) は、$\mathsf{NP} \not \subseteq \mathsf{ioP/poly}$ が成立すれば、$\mathsf{NP}$ に対して無視できる誤差を持つゼロ知識の存在は片道函数 (OWFs) の存在を意味することを証明した。
本研究は,ゼロ知識の最悪の複雑性から一方向関数のキャラクタリゼーションを得る。
ゼロ知識の議論は、その完全性、健全性、ゼロ知識の誤りの総和が1ドルから1ドルに制限されている場合、非自明である。
我々の結果は以下の通りである: $\mathsf{NP} \not \subseteq \mathsf{ioP/poly}$: 1. {\em Non-trivial} 非相互 ZK (NIZK) 論法を $\mathsf{NP}$ に対して仮定すると、OWF の存在が暗示される。
この結果は、既知の増幅手法を用いて、すべての有意な誤差パラメータに対する弱値から標準のNIZK証明への無条件変換も提供する。
我々はまた、対話的設定にも一般化する:$\mathsf{NP}$の非自明な定値ゼロ知識引数は、OWFの存在を暗示するものであり、従って(標準)$\mathsf{NP}$の4つのメッセージゼロ知識引数も意味する。
この研究に先立ち、一方向関数はゼロ知識誤差$ε_{zk}$と音響誤差$ε_{s}$を満足する$ε_{zk} + \sqrt{ε_{s}} < 1$ [Chakraborty, Hulett and Khurana, CRYPTO'2025] を持つNIZKから得られる。
しかし、$ε_{zk} + \sqrt{ε_{s}} \geq 1$ が開な状態のままである。
この研究はギャップを埋め、インタラクティブな環境における新たな意味を得る。
結果と技術は,最悪の場合の硬さから片道関数を構築するために,石を踏むのに役立つ可能性がある。
関連論文リスト
- Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
論文 参考訳（メタデータ） (2025-10-12T15:42:44Z) - Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth [6.8680041558282054]
並列量子計算は,従来よりも計算能力が高いことを示す。
我々は、新しい量子コンピュータに計算上の優位性を持たせて、より高次元の非局所ゲーム理論を橋渡しする。
論文 参考訳（メタデータ） (2024-08-29T09:40:55Z) - Quantum Sabotage Complexity [0.7812210699650152]
ここでは$mathsfQ(f_mathsfsab)$を示し、$f_mathsfsab$の量子クエリ複雑性を示す。
f$がインデックス関数であるとき、$mathsfQ(f_mathsfsab)=Theta(sqrtmathsfsab)$は、$mathsfQ(f_mathsfsab)=Theta(sqrtmathsf)の可能性を除外する。
論文 参考訳（メタデータ） (2024-08-22T17:57:58Z) - No-Regret M${}^{\natural}$-Concave Function Maximization: Stochastic Bandit Algorithms and Hardness of Adversarial Full-Information Setting [27.973926244529267]
オンラインM$natural$-concave関数問題について検討し,Murota と Shioura (1999) によるインタラクティブ版について検討した。
バンドイット設定では、$O(T-1/2)$-simple regretと$O(T2/3)$-regretアルゴリズムを、M$natural$-concave関数のノイズ値オーラクルに$T$倍のアクセスで提示する。
完全な情報フィードバックであっても,ラウンド毎に実行されたアルゴリズムは,任意の一定の$cに対して,O(T1-c)$後悔を達成できないことを証明しています。
論文 参考訳（メタデータ） (2024-05-21T01:31:44Z) - An Over-parameterized Exponential Regression [18.57735939471469]
LLM(Large Language Models)の分野での最近の発展は、指数的アクティベーション関数の使用への関心を喚起している。
ニューラル関数 $F: mathbbRd times m times mathbbRd times mathbbRd times mathbbRd times mathbbRd times mathbbRd times mathbbRd times mathbbRd times mathbbRdd
論文 参考訳（メタデータ） (2023-03-29T07:29:07Z) - The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。
すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
論文 参考訳（メタデータ） (2022-09-04T10:01:39Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Low-degree learning and the metric entropy of polynomials [44.99833362998488]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳（メタデータ） (2022-03-17T23:52:08Z) - ReLU Network Approximation in Terms of Intrinsic Parameters [5.37133760455631]
固有パラメータ数の観点からReLUネットワークの近似誤差について検討する。
我々は、3つの固有パラメータしか持たないReLUネットワークを設計し、任意の誤差でH"古い連続関数を近似する。
論文 参考訳（メタデータ） (2021-11-15T18:20:38Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。