論文の概要: Weak Zero-Knowledge and One-Way Functions

• arxiv url: http://arxiv.org/abs/2602.16156v1
• Date: Wed, 18 Feb 2026 03:09:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-19 15:58:30.5014
• Title: Weak Zero-Knowledge and One-Way Functions
• Title（参考訳）: 弱ゼロ知識とワンウェイ関数
• Authors: Rohit Chatterjee, Yunqi Li, Prashant Nalini Vasudevan,
• Abstract要約: 最悪のハード言語に対する弱いゼロ知識(ZK)プロトコルの存在の意味について検討する。 これらのプロトコルには、無視できない完全性、健全性、ゼロ知識エラーがある。
• 参考スコア（独自算出の注目度）: 3.833834886573873
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the implications of the existence of weak Zero-Knowledge (ZK) protocols for worst-case hard languages. These are protocols that have completeness, soundness, and zero-knowledge errors (denoted $ε_c$, $ε_s$, and $ε_z$, respectively) that might not be negligible. Under the assumption that there are worst-case hard languages in NP, we show the following: 1. If all languages in NP have NIZK proofs or arguments satisfying $ ε_c+ε_s+ ε_z < 1 $, then One-Way Functions (OWFs) exist. This covers all possible non-trivial values for these error rates. It additionally implies that if all languages in NP have such NIZK proofs and $ε_c$ is negligible, then they also have NIZK proofs where all errors are negligible. Previously, these results were known under the more restrictive condition $ ε_c+\sqrt{ε_s}+ε_z < 1 $ [Chakraborty et al., CRYPTO 2025]. 2. If all languages in NP have $k$-round public-coin ZK proofs or arguments satisfying $ ε_c+ε_s+(2k-1).ε_z < 1 $, then OWFs exist. 3. If, for some constant $k$, all languages in NP have $k$-round public-coin ZK proofs or arguments satisfying $ ε_c+ε_s+k.ε_z < 1 $, then infinitely-often OWFs exist.
• Abstract（参考訳）: 最悪のハード言語に対する弱いゼロ知識(ZK)プロトコルの存在の意味について検討する。 これらは完全性、健全性、ゼロ知識エラー(それぞれ$ε_c$、$ε_s$、$ε_z$)を持つプロトコルであり、無視できないかもしれない。 1) NPのすべての言語が、$ ε_c+ε_s+ε_z < 1 $ を満たす NIZK 証明や引数を持つなら、ワンウェイ関数 (OWFs) が存在する。 これはこれらのエラー率に対して可能なすべての非自明な値をカバーする。 さらに、NP のすべての言語がそのような NIZK 証明を持ち、$ε_c$ が無視可能であるなら、すべての誤りが無視できる NIZK 証明も持つ。 以前は、これらの結果はより制限的な条件 $ ε_c+\sqrt{ε_s}+ε_z < 1 $ [Chakraborty et al , CRYPTO 2025] で知られていた。 2. NP のすべての言語が、$k$の公約 ZK 証明または$ ε_c+ε_s+(2k-1) を満たす引数を持つ。 ε_z < 1 $ ならば OWF が存在する。 3. ある定数$k$の場合、NPのすべての言語が$k$の公約ZK証明または$ ε_c+ε_s+kを満たす引数を持つ。 ε_z < 1 $ ならば、無限大の OWF が存在する。

関連論文リスト

• Cryptography from Lossy Reductions: Towards OWFs from ETH, and Beyond [1.0687104237121408]
  ワンウェイ関数(OWF)は現代の暗号の基礎を形成するが、その無条件の存在は大きな疑問である。 OWF が存在するか,あるいは任意の保証問題に対して損失の少ない$Pi$ が 2,Omega(logtau_Pi / loglog n)$ で実行されることを示す。
  論文  参考訳（メタデータ） (2025-05-27T17:15:30Z)
• ProofWala: Multilingual Proof Data Synthesis and Theorem-Proving [53.67926215943612]
  $rm P Small ROOFW Small ALA$は、ニューラル定理プローサと2つの確立された対話的証明アシスタント(ITP)間の相互作用を可能にする 私たちは、$rm P Small ROOFWsmall ALA$生成のCoqとLeanのデータの組み合わせでトレーニングされたモデルが、標準のprov-at-k$メトリック上で、Lean-onlyとCoq-onlyのモデルを上回っていることを示します。
  論文  参考訳（メタデータ） (2025-02-07T05:35:46Z)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
  両部非絡み込み入力から次元独立なk-パーティイトディジアンタングル(類似)チャネルを構築する。 NEXP を捉えるためには、$| psi rangle = sqrta | sqrt1-a | psi_+ rangle という形の非負の振幅を持つのに十分であることを示す。
  論文  参考訳（メタデータ） (2024-02-23T12:22:03Z)
• Bounds on $k$-Uniform Quantum States [22.266687858571363]
  我々は、$(mathbbCd)otimes N$における$k$-uniform状態の存在に対するパラメータ$k$の新しい上限を提供する。 a $k$-uniform state in $(mathbbCd)otimes N$ は純 $(N,1,k+1)_d$ 量子誤り訂正符号に対応するため、最小距離 $k+1$ of pure $(N,1,k+1))_d$ 量子誤り訂正符号にも新たな上限を与える。
  論文  参考訳（メタデータ） (2023-10-10T07:38:13Z)
• Efficient Quantum State Synthesis with One Query [0.0]
  本稿では,古典的オラクルへの単一クエリ(重ね合わせ)を実現する時間類似量子アルゴリズムを提案する。 我々は、すべての$n$-qubit状態が、適切な有限ゲート集合上の$On/n)$-size回路によって0.01エラー内に構築可能であることを証明した。
  論文  参考訳（メタデータ） (2023-06-02T17:49:35Z)
• Learning low-degree functions from a logarithmic number of random queries [77.34726150561087]
  任意の整数 $ninmathbbN$, $din1,ldots,n$ および任意の $varepsilon,deltain(0,1)$ に対して、有界関数 $f:-1,1nto[-1,1]$ に対して、少なくとも$d$ の次数を学ぶことができる。
  論文  参考訳（メタデータ） (2021-09-21T13:19:04Z)
• Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error [1.6522364074260811]
  誤差が小さいEquality関数のランダム化および量子化通信複雑性を$epsilon$で調べる。 任意の$log(n/epsilon)-log(sqrtn/epsilon)+3$プロトコルが少なくとも$log(n/epsilon)-log(sqrtn/epsilon)-O(1)$ qubitsを通信することを示す。
  論文  参考訳（メタデータ） (2021-07-25T13:52:42Z)
• RNNs can generate bounded hierarchical languages with optimal memory [113.73133308478612]
  RNNは、自然言語構文の足場を反映した境界階層言語を効率的に生成できることを示す。 Dyck-($k$,$m$)は、よくネストされた括弧($k$型)と$m$バウンドされたネスト深さの言語である。 明示的な構成により,$O(m log k)$ hidden units の RNN がメモリの指数的削減に十分であることを示す。
  論文  参考訳（メタデータ） (2020-10-15T04:42:29Z)
• 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)

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

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