論文の概要: 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%を検証できることがわかった。

関連論文リスト

• Quantum Key Distribution with Imperfections: Recent Advances in Security Proofs [0.0]
  量子鍵分配(QKD)は、2つの空間的に分離されたパーティが情報理論的に安全な暗号化を確立することを可能にする。 広範囲の盗聴戦略に対して堅牢なセキュリティ証明は、いくつかのQKDプロトコルの理論的健全性を確立している。 ほとんどの証明は、そのようなプロトコルに関わる物理系の理想化されたモデルに基づいており、実際的な実装では満たされない仮定を含むことが多い。
  論文  参考訳（メタデータ） (2026-02-04T21:16:33Z)
• 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)
• The Round Complexity of Proofs in the Bounded Quantum Storage Model [0.7366405857677227]
  有界量子記憶モデル(BQSM)におけるプロトコルのラウンド圧縮に関する研究 このモデルでは、悪意のあるパーティは有界量子メモリを持ち、プロトコルに送信される全てのキュービットを格納できない。 標準手法では, NIZKはBQS相手に対する平易なモデルではありそうにないことを示す。
  論文  参考訳（メタデータ） (2024-05-28T15:24:48Z)
• The Road to Near-Capacity CV-QKD Reconciliation: An FEC-Agnostic Design [53.67135680812675]
  コードワードに基づく新しいQKD調停方式を提案する。 認証された古典チャネル(ClC)と量子チャネル(QuC)は、それぞれ別々の前方誤り訂正(FEC)符号スキームによって保護される。 提案システムは,広範囲のFECスキームとQKD和解を両立させる。
  論文  参考訳（メタデータ） (2024-03-24T14:47:08Z)
• 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)
• Data post-processing for the one-way heterodyne protocol under composable finite-size security [62.997667081978825]
  本研究では,実用的連続可変(CV)量子鍵分布プロトコルの性能について検討する。 ヘテロダイン検出を用いたガウス変調コヒーレント状態プロトコルを高信号対雑音比で検討する。 これにより、プロトコルの実践的な実装の性能を調べ、上記のステップに関連付けられたパラメータを最適化することができる。
  論文  参考訳（メタデータ） (2022-05-20T12:37:09Z)
• COPA: Certifying Robust Policies for Offline Reinforcement Learning against Poisoning Attacks [49.15885037760725]
  本研究は, 中毒発生時におけるオフライン強化学習(RL)の堅牢性を検証することに注力する。 本報告では, 許容可能な毒素トラジェクトリの数を認証する最初の認証フレームワークであるCOPAを提案する。 提案手法のいくつかは理論的に厳密であり,一部はNP-Complete問題であることを示す。
  論文  参考訳（メタデータ） (2022-03-16T05:02:47Z)
• PRover: Proof Generation for Interpretable Reasoning over Rules [81.40404921232192]
  本稿では,ルールベース上の二項質問に応答し,対応する証明を生成するトランスフォーマーモデルを提案する。 本モデルは,効率的な制約付き学習パラダイムを用いて,証明グラフに対応するノードやエッジを予測できることを学習する。 我々は、QAと証明生成のための有望な結果を示すために、合成、手書き、人文による規則ベースの実験を行う。
  論文  参考訳（メタデータ） (2020-10-06T15:47:53Z)

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

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