論文の概要: Succinct Perfect Zero-knowledge for MIP*
- arxiv url: http://arxiv.org/abs/2503.04517v2
- Date: Wed, 01 Oct 2025 19:10:55 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-03 14:32:17.058784
- Title: Succinct Perfect Zero-knowledge for MIP*
- Title（参考訳）: MIPにおけるアクセント完全ゼロ知識*
- Authors: Honghao Fu, Kieran Mastel, Xingjian Zhang,
- Abstract要約: 本稿では,RE の不正な検証に対する完全ゼロ知識 MIP* プロトコルが存在することを示す。
質問の削減は、正当性検証に対する元のプロトコルの完全なゼロ知識特性を保っていることを示す。
第2に、MIP*の量子情報特徴を提供する制約制約バイナリ制約系(BCS)非局所ゲームは、同期制約変数のBCSゲームに変換され、圧縮の完全性を維持することができることを示す。
- 参考スコア（独自算出の注目度）: 1.839056773828158
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: In their recent breakthrough result, Slofstra and the second author show that there is a two-player one-round perfect zero-knowledge MIP* protocol for RE (STOC'24). We build on their result to show that there exists a succinct two-player one-round perfect zero-knowledge MIP* protocol for RE against dishonest verifiers with polylog question size and O(1) answer size, or with O(1) question size and polylog answer size. To prove our result, we study the three central compression techniques underlying the MIP*=RE proof (Ji et al. '20): question reduction, oracularization, and answer reduction. We show that question reduction preserves the perfect (as well as statistical and computational) zero-knowledge properties of the original protocol against dishonest verifiers, and oracularization and answer reduction preserve the perfect (as well as statistical and computational) zero-knowledge properties of the original protocol against honest verifiers. Secondly, we show that every constraint-constraint binary constraint system (BCS) nonlocal game, which provides a quantum information characterization of MIP*, can be converted to a synchronous constraint-variable BCS game to preserve perfect completeness for our compression. Lastly, we present a parametrized perfect-zero-knowledge transformation of MIP* protocols, which generalizes the transformation in (Slofstra and Kieran STOC'24) . This transformation allows us to preserve the zero-knowledge property against dishonest verifiers in the recursively oracularized protocols in our compression.
- Abstract（参考訳）: 最近のブレークスルーで、Slofstra と第2の著者は、RE (STOC'24) のための完全なゼロ知識 MIP* プロトコルが2つあることを示した。
提案手法は,ポリログの質問サイズとO(1)の回答サイズ,あるいはO(1)の質問サイズとポリログの回答サイズを持つ不完全検証器に対して,REのための簡潔な2人プレイヤ1ラウンド完全ゼロ知識MIP*プロトコルが存在することを示すものである。
MIP*=RE証明(Ji et al '20)に基づく3つの中央圧縮手法について検討した。
質問の削減は、不完全検証に対する元のプロトコルの完全(および統計的および計算的)ゼロ知識特性を保ち、論理化と解答還元は、真正検証に対する元のプロトコルの完全(および統計的および計算的)ゼロ知識特性を保っていることを示す。
第2に、MIP*の量子情報特徴を提供する制約制約バイナリ制約システム(BCS)非局所ゲームは、同期制約変数のBCSゲームに変換され、圧縮の完全性を維持することができることを示す。
最後に、(Slofstra と Kieran STOC'24) の変換を一般化した MIP* プロトコルのパラメタライズされた完全ゼロ知識変換を提案する。
この変換により、圧縮における再帰的論理化プロトコルにおける不完全検証に対するゼロ知識特性を維持できる。
関連論文リスト
- How to Verify that a Small Device is Quantum, Unconditionally [12.663567847694427]
量子性の証明(PoQ)により、量子機械が任意の古典機械で不可能な計算を実行しているかどうかを、古典的検証者が効率的に検証することができる。
本稿では,証明者のメモリ上のバウンダリを仮定して,音質が無条件に保持されるPoQプロトコルを構築するための新しい手法を提案する。
論文 参考訳（メタデータ） (2025-05-29T20:09:22Z) - Robust Conformal Prediction with a Single Binary Certificate [58.450154976190795]
コンフォーマル予測(CP)は、任意のモデルの出力を、真のラベルを(調整可能な)高い確率でカバーすることを保証した予測セットに変換する。
我々は,MCサンプルが著しく低い場合でも,より小さな集合を生成する頑健な共形予測を提案する。
論文 参考訳（メタデータ） (2025-03-07T08:41:53Z) - The Round Complexity of Proofs in the Bounded Quantum Storage Model [0.7366405857677227]
有界量子記憶モデル(BQSM)におけるプロトコルのラウンド圧縮に関する研究
このモデルでは、悪意のあるパーティは有界量子メモリを持ち、プロトコルに送信される全てのキュービットを格納できない。
標準手法では, NIZKはBQS相手に対する平易なモデルではありそうにないことを示す。
論文 参考訳（メタデータ） (2024-05-28T15:24:48Z) - Two prover perfect zero knowledge for MIP* [0.0]
MIP*のすべての言語は、PZK-MIP*プロトコルを2つのプロプライエタリに持つことを示す。
また、通信演算子BCSプロトコルを持つ全ての言語は、2つの証明子PZK通信演算子プロトコルを持つことを示した。
論文 参考訳（メタデータ） (2024-04-01T05:07:22Z) - Truly No-Regret Learning in Constrained MDPs [61.78619476991494]
未知のCMDPで学習するモデルベース原始双対アルゴリズムを提案する。
提案アルゴリズムは,誤差のキャンセルを伴わずにサブ線形後悔を実現する。
論文 参考訳（メタデータ） (2024-02-24T09:47:46Z) - Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints [26.008426384903764]
オフライン強化学習(RL)は、事前に収集されたデータセットを使用して、マルコフ決定プロセス(MDP)の最適ポリシーを見つけることを目的としている。
本研究では,オフラインRLにおけるマルコフ決定過程の線形プログラミング (LP) の再検討を行う。
論文 参考訳（メタデータ） (2022-12-28T15:28:12Z) - Near-Optimal Sample Complexity Bounds for Constrained MDPs [25.509556551558834]
減算CMDPにおける準最適政策を学習するために,サンプルの複雑さを極小値と下位値で表す。
CMDPの学習は,少ない制約違反を許す場合と同等に容易であるが,制約違反を要求しない場合には本質的に困難であることを示す。
論文 参考訳（メタデータ） (2022-06-13T15:58:14Z) - Quantum Proofs of Deletion for Learning with Errors [91.3755431537592]
完全同型暗号方式として, 完全同型暗号方式を初めて構築する。
我々の主要な技術要素は、量子証明器が古典的検証器に量子状態の形でのLearning with Errors分布からのサンプルが削除されたことを納得させる対話的プロトコルである。
論文 参考訳（メタデータ） (2022-03-03T10:07:32Z) - Reinforcement Learning in Linear MDPs: Constant Regret and
Representation Selection [136.4014229319618]
線形構造を持つ有限水平マルコフ決定過程(MDPs)における後悔最小化における状態-作用値関数の表現の役割について検討する。
まず,線形報酬関数を持つ任意のMDPにおいて,一貫した後悔を実現するために,Universally spaning optimal features (UNISOFT) と呼ばれる表現に必要条件を導出する。
論文 参考訳（メタデータ） (2021-10-27T22:07:08Z) - A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。
我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。
この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
論文 参考訳（メタデータ） (2021-06-24T13:46:09Z) - Geometry of Banach spaces: a new route towards Position Based
Cryptography [65.51757376525798]
我々は幾何学的機能解析の観点から位置ベース量子暗号(PBQC)について検討し,その量子ゲームとの関係について考察した。
私たちが関心を持っている主な質問は、PBQCプロトコルのセキュリティを損なうために、攻撃者の連合が共有しなければならない、最適な絡み合いの量を求めることです。
より複雑なバナッハ空間の型プロパティの理解は、仮定を捨て、我々のプロトコルを攻撃するのに使用されるリソースに条件のない低い境界をもたらすことを示します。
論文 参考訳（メタデータ） (2021-03-30T13:55:11Z) - From Information Theory Puzzles in Deletion Channels to Deniability in
Quantum Cryptography [0.0]
まず、実験データに基づいて、後部のエントロピーが定数列によって最小化されることを予想する。
次に,DC-QKEを提案するために,隠蔽通信とデニビリティの接続を確立する。
完全ホモモルフィック暗号をベースとした,効率的な耐保磁・量子セキュリティ投票方式を提案する。
論文 参考訳（メタデータ） (2020-03-25T22:20:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。