論文の概要: The Round Complexity of Proofs in the Bounded Quantum Storage Model
- arxiv url: http://arxiv.org/abs/2405.18275v1
- Date: Tue, 28 May 2024 15:24:48 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-29 17:59:58.630116
- Title: The Round Complexity of Proofs in the Bounded Quantum Storage Model
- Title（参考訳）: 境界量子ストレージモデルにおける証明のラウンド複雑度
- Authors: Alex B. Grilo, Philippe Lamontagne,
- Abstract要約: 有界量子記憶モデル(BQSM)におけるプロトコルのラウンド圧縮に関する研究
このモデルでは、悪意のあるパーティは有界量子メモリを持ち、プロトコルに送信される全てのキュービットを格納できない。
標準手法では, NIZKはBQS相手に対する平易なモデルではありそうにないことを示す。
- 参考スコア（独自算出の注目度）: 0.7366405857677227
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The round complexity of interactive proof systems is a key question of practical and theoretical relevance in complexity theory and cryptography. Moreover, results such as QIP = QIP(3) (STOC'00) show that quantum resources significantly help in such a task. In this work, we initiate the study of round compression of protocols in the bounded quantum storage model (BQSM). In this model, the malicious parties have a bounded quantum memory and they cannot store the all the qubits that are transmitted in the protocol. Our main results in this setting are the following: 1. There is a non-interactive (statistical) witness indistinguishable proof for any language in NP (and even QMA) in BQSM in the plain model. We notice that in this protocol, only the memory of the verifier is bounded. 2. Any classical proof system can be compressed in a two-message quantum proof system in BQSM. Moreover, if the original proof system is zero-knowledge, the quantum protocol is zero-knowledge too. In this result, we assume that the prover has bounded memory. Finally, we give evidence towards the "tightness" of our results. First, we show that NIZK in the plain model against BQS adversaries is unlikely with standard techniques. Second, we prove that without the BQS model there is no 2-message zero-knowledge quantum interactive proof, even under computational assumptions.
- Abstract（参考訳）: インタラクティブな証明システムの丸い複雑さは、複雑性理論と暗号における実用的および理論的関連性の鍵となる問題である。
さらに、QIP = QIP(3) (STOC'00) のような結果は、量子資源がそのようなタスクに大いに役立つことを示している。
本研究では,有界量子ストレージモデル(BQSM)におけるプロトコルのラウンド圧縮の研究を開始する。
このモデルでは、悪意のあるパーティは有界量子メモリを持ち、プロトコルに送信される全てのキュービットを格納できない。
1)BQSMにおけるNP(およびQMA)の任意の言語に対する非対話的(統計的)証人(in-interactive (statistical) witness)の識別不可能な証明がある。
このプロトコルでは、検証者のメモリだけがバウンドであることに気付きます。
2. 古典的証明系はBQSMの2次元量子証明系で圧縮できる。
さらに、元の証明系がゼロ知識であるなら、量子プロトコルもゼロ知識である。
この結果、証明者がメモリ境界を持つと仮定する。
最後に、結果の"高潔さ"を示す証拠を与えます。
まず,BQS相手に対する平易なモデルにおけるNIZKは,標準手法では不可能であることを示す。
第二に、BQSモデルがなければ、計算仮定の下でも、2-message 0-knowledgeの量子対話的証明が存在しないことが証明される。
関連論文リスト
- The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳（メタデータ） (2024-02-29T01:35:46Z) - A simple formulation of no-cloning and no-hiding that admits efficient
and robust verification [0.0]
不和合性は古典理論とは別の量子論の特徴である。
ノーハイディング定理(英: no-hiding theorem)は、ブラックホール情報パラドックス(英語版)の文脈で生じる別の例である。
量子論の基本的特徴のどちらも、効率的な検証が可能な単一形式で定式化する。
論文 参考訳（メタデータ） (2023-03-05T12:48:11Z) - Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
量子性の検定は、古典的検証者が証明者が古典的でないことを(のみ)証明できるプロトコルである。
我々は、あるテンプレートに従う量子性のテストを行い、(Kalai et al., 2022)のような最近の提案を捉えた。
すなわち、同じプロトコルは、証明可能なランダム性や古典的な量子計算のデリゲートといったアプリケーションの中心にあるビルディングブロックであるqubitの認定に使用できる。
論文 参考訳（メタデータ） (2023-03-02T14:18:17Z) - Succinct Classical Verification of Quantum Computation [30.91621630752802]
量子計算のための古典的簡潔な対話的引数(BQP)を構築する。
我々のプロトコルは、識別不能難読化(iO)と学習エラー(LWE)の事後セキュリティを前提として安全である。
論文 参考訳（メタデータ） (2022-06-29T22:19:12Z) - Quantum Proofs of Deletion for Learning with Errors [91.3755431537592]
完全同型暗号方式として, 完全同型暗号方式を初めて構築する。
我々の主要な技術要素は、量子証明器が古典的検証器に量子状態の形でのLearning with Errors分布からのサンプルが削除されたことを納得させる対話的プロトコルである。
論文 参考訳（メタデータ） (2022-03-03T10:07:32Z) - LQP: The Dynamic Logic of Quantum Information [77.34726150561087]
本稿では,複合量子システムにおける情報フローの推論のための動的論理形式について紹介する。
本稿では,この論理の文法,関係意味論,音響証明システムについて述べる。
アプリケーションとしては,テレポーテーションプロトコルと標準量子秘密共有プロトコルに対して,正式な正当性を与えるために,我々のシステムを利用する。
論文 参考訳（メタデータ） (2021-10-04T12:20:23Z) - Depth-efficient proofs of quantumness [77.34726150561087]
量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。
本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
論文 参考訳（メタデータ） (2021-07-05T17:45:41Z) - On the Concurrent Composition of Quantum Zero-Knowledge [11.09538194395154]
コンカレントコンポジションにおける量子時間検証器(量子ゼロ知識)に対するゼロ知識セキュアの概念について検討する。
この結果から,QMAの量子知識系が従来よりも優れたパラメータを持つことを示す。
論文 参考訳（メタデータ） (2020-12-05T23:09:29Z) - Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
古典的アリス(Alice)と量子的ボブ(Quantum Bob)が古典的なチャネルを通してのみ通信できるような設定を考える。
悪質な量子逆数の場合,ブラックボックスシミュレーションを用いた2次元量子関数を実現することは,一般に不可能であることを示す。
我々は、QMA関係Rの古典的量子知識(PoQK)プロトコルを入力として、古典的当事者によって検証可能なRのゼロ知識PoQKを出力するコンパイラを提供する。
論文 参考訳（メタデータ） (2020-10-15T17:55:31Z) - Classical proofs of quantum knowledge [10.432041176720842]
検証者が古典的な設定で知識の証明という概念を定義する。
量子知識の非破壊的な古典的証明が何らかの状態に存在すれば、その状態は敵によってクローンできることを示す。
論文 参考訳（メタデータ） (2020-05-04T17:45:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。