論文の概要: Succinct Perfect Zero-knowledge for MIP*

• arxiv url: http://arxiv.org/abs/2503.04517v1
• Date: Thu, 06 Mar 2025 15:05:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-07 15:58:24.047275
• Title: Succinct Perfect Zero-knowledge for MIP*
• Title（参考訳）: MIPにおけるアクセント完全ゼロ知識*
• Authors: Honghao Fu, Xingjian Zhang,
• Abstract要約: ポリログの問合せサイズとO(1)の解答サイズを持つREのための2つのプレイヤー1ラウンド完全ゼロ知識MIP*プロトコルが存在することを示す。 MIP*=RE証明に基づく4つの中央圧縮手法を解析する。 また,制約制約と制約可変バイナリ制約システムの非局所ゲーム間の変換についても検討する。
• 参考スコア（独自算出の注目度）: 2.8289044717329905
• License:
• Abstract: In the recent breakthrough result of Slofstra and Mastel (STOC'24), they show that there is a two-player one-round perfect zero-knowledge MIP* protocol for RE. We build on their result to show that there exists a succinct two-player one-round perfect zero-knowledge MIP* protocol for RE with polylog question size and O(1) answer size, or with O(1) question size and polylog answer size. To prove our result, we analyze the four central compression techniques underlying the MIP*= RE proof (Ji et al. '20) -- question reduction, oracularization, answer reduction, and parallel repetition -- and show that they all preserve the perfect (as well as statistical and computational) zero-knowledge properties of the original protocol. Furthermore, we complete the study of the conversion between constraint-constraint and constraint-variable binary constraint system (BCS) nonlocal games, which provide a quantum information characterization of MIP* protocols. While Paddock (QIP'23) established that any near-perfect strategy for a constraint-variable game can be mapped to a constraint-constraint version, we prove the converse, fully establishing their equivalence.
• Abstract（参考訳）: Slofstra と Mastel (STOC'24) の最近のブレークスルーで、RE のための2つのプレイヤーの完全なゼロ知識 MIP* プロトコルがあることが示されている。 これらの結果に基づいて,ポリログの質問サイズとO(1)の回答サイズ,あるいはO(1)の質問サイズとポリログの回答サイズを持つREのための,簡潔な2人プレイヤ1ラウンド完全ゼロ知識MIP*プロトコルが存在することを示す。 MIP*=RE証明(Ji et al '20)の根底にある4つの中央圧縮技術(質問の削減、論理化、回答の削減、並列反復)を分析し、それらがすべて、元のプロトコルの完全性(および統計的および計算的)ゼロ知識特性を保存することを示す。 さらに、制約制約と制約可変バイナリ制約システム(BCS)非局所ゲーム間の変換の研究を完了し、MIP*プロトコルの量子情報特性を提供する。 Paddock (QIP'23) は制約可変ゲームに対するほぼ完全な戦略を制約制約制約バージョンにマッピングできることを確立したが、その逆を証明し、その等価性を完全に確立した。

関連論文リスト

• 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)
• Under-Approximating Expected Total Rewards in POMDPs [68.8204255655161]
  我々は、部分的に観測可能なマルコフ決定プロセス(POMDP)において、ゴール状態に達するための最適な総報酬を考える。 我々は、MILP(mixed-integer linear programming)を用いて、そのような最小限の確率シフトを見つけ、実験により、我々の手法がかなりうまく拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-01-21T16:43:03Z)
• 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)

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

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