論文の概要: Towards Practical Zero-Knowledge Proof for PSPACE
- arxiv url: http://arxiv.org/abs/2511.15071v1
- Date: Wed, 19 Nov 2025 03:22:48 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-11-20 15:51:28.614597
- Title: Towards Practical Zero-Knowledge Proof for PSPACE
- Title（参考訳）: PSPACEのためのZero-Knowledge Proofの実用化に向けて
- Authors: Ashwin Karthikeyan, Hengyu Liu, Kuldeep S. Meel, Ning Luo,
- Abstract要約: この研究は、PSPACE完全文に対する最初の実用的なゼロ知識(ZK)プロトコルを示す。
我々はQ-Res証明の効率的な符号化を開発し、低オーバヘッド演算チェックによる検証を可能にする。
また、QBFに関する勝利戦略の知識を証明するため、ZKプロトコルを設計する。
- 参考スコア（独自算出の注目度）: 26.648887511985652
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Efficient zero-knowledge proofs (ZKPs) have been restricted to NP statements so far, whereas they exist for all statements in PSPACE. This work presents the first practical zero-knowledge (ZK) protocols for PSPACE-complete statements by enabling ZK proofs of QBF (Quantified Boolean Formula) evaluation. The core idea is to validate quantified resolution proofs (Q-Res) in ZK. We develop an efficient polynomial encoding of Q-Res proofs, enabling proof validation through low-overhead arithmetic checks. We also design a ZK protocol to prove knowledge of a winning strategy related to the QBF, which is often equally important in practice. We implement our protocols and evaluate them on QBFEVAL. The results show that our protocols can verify 72% of QBF evaluations via Q-Res proof and 82% of instances' winning strategies within 100 seconds, for instances where such proofs or strategies can be obtained.
- Abstract（参考訳）: 効率的なゼロ知識証明(ZKPs)はNP文に制限されているが、PSPACEの全ての文には存在する。
本研究は,QBF(Quantified Boolean Formula)評価のZK証明を有効にすることで,PSPACE完全文に対する最初の実用的ゼロ知識(ZK)プロトコルを提案する。
中心となる考え方は、ZKにおける定量化された解決証明(Q-Res)を検証することである。
我々はQ-Res証明の効率的な多項式符号化を開発し、低オーバヘッド演算チェックによる検証を可能にする。
また、QBFに関する勝利戦略の知識を証明するため、ZKプロトコルを設計する。
提案プロトコルを実装し,QBFEVALで評価する。
その結果,本プロトコルでは,Q-Res証明によるQBF評価の72%,100秒以内にインスタンスの勝利戦略の82%を検証できることがわかった。
関連論文リスト
- Protocol-level description and self-contained security proof of decoy-state BB84 QKD protocol [1.0923877073891446]
本稿では,デコイ状態のBB84量子鍵分布プロトコルに対する自己完結型情報理論セキュリティ証明を提案する。
我々の証明は、以前の結果と一致したキーレートが得られる。
論文 参考訳（メタデータ） (2025-04-29T04:28:15Z) - Quantum Rewinding for IOP-Based Succinct Arguments [42.12045681000549]
我々は、ベクトルコミットメントスキームが崩壊しているとき、BCS変換のインタラクティブな変種が量子敵に対する標準モデルで安全であることを証明した。
その結果、量子後安全な簡潔な議論の標準モデルを得ることができ、その複雑さを最もよく知ることができる。
論文 参考訳（メタデータ） (2024-11-08T06:33:08Z) - Collaborative CP-NIZKs: Modular, Composable Proofs for Distributed Secrets [3.3373764108905455]
構成性により、ユーザーは異なるNIZKを組み合わせられる。
我々は、NIZKのコラボレーティブ・コミット・アンド・プロブのための、最初の一般的な定義を示す。
論文 参考訳（メタデータ） (2024-07-27T08:45:34Z) - Comprehensive Analysis of BB84, A Quantum Key Distribution Protocol [0.0]
量子鍵分配(QKD)は秘密鍵を共有することでセキュアな通信を可能にする技術である。
最も有名なQKDプロトコルの1つは、1984年にチャールズ・ベネットとジル・ブラザードによって提案されたBB84プロトコルである。
論文 参考訳（メタデータ） (2023-12-09T16:32:54Z) - Robust and efficient verification of graph states in blind
measurement-based quantum computation [52.70359447203418]
Blind Quantum Computing (BQC) は、クライアントのプライバシを保護するセキュアな量子計算手法である。
資源グラフ状態が敵のシナリオで正確に準備されているかどうかを検証することは重要である。
本稿では,任意の局所次元を持つ任意のグラフ状態を検証するための,堅牢で効率的なプロトコルを提案する。
論文 参考訳（メタデータ） (2023-05-18T06:24:45Z) - Succinct Classical Verification of Quantum Computation [30.91621630752802]
量子計算のための古典的簡潔な対話的引数(BQP)を構築する。
我々のプロトコルは、識別不能難読化(iO)と学習エラー(LWE)の事後セキュリティを前提として安全である。
論文 参考訳（メタデータ） (2022-06-29T22:19:12Z) - PRover: Proof Generation for Interpretable Reasoning over Rules [81.40404921232192]
本稿では,ルールベース上の二項質問に応答し,対応する証明を生成するトランスフォーマーモデルを提案する。
本モデルは,効率的な制約付き学習パラダイムを用いて,証明グラフに対応するノードやエッジを予測できることを学習する。
我々は、QAと証明生成のための有望な結果を示すために、合成、手書き、人文による規則ベースの実験を行う。
論文 参考訳（メタデータ） (2020-10-06T15:47:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。