論文の概要: Post-Quantum Perfect Zero-Knowledge Arguments for NP From Any One-Way Permutation
- arxiv url: http://arxiv.org/abs/2610.33185v1
- Date: Fri, 23 Oct 2026 18:27:44 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-27 22:27:13.266241
- Title: Post-Quantum Perfect Zero-Knowledge Arguments for NP From Any One-Way Permutation
- Title（参考訳）: ワンウェイ置換によるNPのゼロ知識問題に対するポスト量子完全解法
- Abstract要約: 量子後片道置換がすべてのNPに対する完全ゼロ知識古典的議論に十分であることを示す。
- 参考スコア（独自算出の注目度）: 2.9360071145551068
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we show for the first time that post-quantum one-way permutations are sufficient for perfect zero-knowledge classical arguments for all of NP with security guaranteed against quantum adversaries. We first establish that Naor, Ostrovsky,Venkatesen, and Yung's bit commitment scheme built from any permutation using interactive hashing, called the NOVY scheme, is sum-binding and collapse-binding against quantum polynomial-time committers provided the permutation is post-quantum one-way. We then show that the collapse-binding property of the NOVY scheme allows for Blum's perfect zero-knowledge argument for HAMCYCLE to remain so exactly as it stands against quantum adversaries.
- Abstract（参考訳）: 本稿では,量子逆数に対するセキュリティが保証されたNPのすべてに対して,量子後一方向の置換が完全ゼロ知識の古典的議論に十分であることを示す。
まず、Nor, Ostrovsky, Venkatesen, and Yung's bit commitment scheme built from any permutation using interactive hashing, called the NOVY scheme, is sum-binding and collapse-binding against quantum polynomial-time committer if the permutation is post-quantum one-way。
すると、NOVY スキームの崩壊結合性は HAMCYCLE に対する Blum の完全なゼロ知識の議論が、量子敵に逆らうようにそのままであることを示す。
関連論文リスト
- Succinct Arguments for QMA in the Quantum Random Oracle Model [50.20559283775139]
量子乱数オラクルモデル(QROM)におけるQMAの最初の簡潔な議論を、暗号的仮定や証明されていない予想に頼ることなく構築する。
我々の結果は、量子インタラクティブなオラクル証明(QIOP)を同じ言語の量子引数にコンパイルする効率保存変換である。
論文 参考訳（メタデータ） (2026-09-29T12:54:55Z) - Quantum Lifting for Invertible Permutations and Ideal Ciphers [47.33103206862089]
量子乱数置換と理想的な暗号モデルにおけるセキュリティを確立するための最初の持ち上げ定理を導出する。
これらの定理は、任意の量子逆数の成功確率と、少数の古典的クエリのみを作る古典的アルゴリズムの成功確率を関連付ける。
論文 参考訳（メタデータ） (2025-04-25T09:07:55Z) - Quantum Rewinding for IOP-Based Succinct Arguments [42.12045681000549]
我々は、ベクトルコミットメントスキームが崩壊しているとき、BCS変換のインタラクティブな変種が量子敵に対する標準モデルで安全であることを証明した。
その結果、量子後安全な簡潔な議論の標準モデルを得ることができ、その複雑さを最もよく知ることができる。
論文 参考訳（メタデータ） (2024-11-08T06:33:08Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Commitments to Quantum States [11.217084610985674]
コミットフェーズの後、コミットした状態が送信者の視点から隠されている場合、量子メッセージへのコミットが結合される。
量子状態コミットメント(QSC)の隠蔽は、古典的なメッセージに対するコミットメントスキームによってもたらされることを示す。
量子状態へのコミットは多くの新しい暗号可能性への扉を開く。
論文 参考訳（メタデータ） (2022-10-11T04:34:36Z) - Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier [73.70426431502803]
キリアンの4メッセージ簡潔な引数系は、標準モデルでは量子後安全であることを示す。
これにより、任意の偽の仮定から最初の量子後簡潔な論証システムが得られる。
論文 参考訳（メタデータ） (2021-03-15T05:09:17Z) - A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds [12.525959293825318]
我々は,統計音性およびブラックボックス$epsilon$-zero-knowledgeを満たすNPのラウンド・インタラクティブ証明を構築した。
我々の研究の核心は、シミュレーターが悪意のある検証者のコミットメッセージを抽出できる新しい量子巻き戻し技術である。
論文 参考訳（メタデータ） (2020-11-05T05:40:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。