論文の概要: On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in
Constant Rounds
- arxiv url: http://arxiv.org/abs/2103.11244v2
- Date: Mon, 14 Jun 2021 13:40:45 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-07 08:23:59.926579
- Title: On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in
Constant Rounds
- Title（参考訳）: 定数円におけるポスト量子ブラックボックスゼロノウレッジの不可能性について
- Authors: Nai-Hui Chia and Kai-Min Chung and Qipeng Liu and Takashi Yamakawa
- Abstract要約: 我々は、$mathbfNPsubseteq mathbfBQP$ でない限り、$mathbfNP$ に対する定ラウンドのブラックボックスゼロ知識引数は存在しないことを示す。
また、$mathbfNP$ が$mathbfNPsubseteq mathbfBQP$ でない限り、$mathbfNP$ が存在しないことを証明する。
- 参考スコア（独自算出の注目度）: 14.190389415911833
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the existence of constant-round post-quantum black-box
zero-knowledge protocols for $\mathbf{NP}$. As a main result, we show that
there is no constant-round post-quantum black-box zero-knowledge argument for
$\mathbf{NP}$ unless $\mathbf{NP}\subseteq \mathbf{BQP}$. As constant-round
black-box zero-knowledge arguments for $\mathbf{NP}$ exist in the classical
setting, our main result points out a fundamental difference between
post-quantum and classical zero-knowledge protocols. Combining previous
results, we conclude that unless $\mathbf{NP}\subseteq \mathbf{BQP}$,
constant-round post-quantum zero-knowledge protocols for $\mathbf{NP}$ exist if
and only if we use non-black-box techniques or relax certain security
requirements such as relaxing standard zero-knowledge to
$\epsilon$-zero-knowledge. Additionally, we also prove that three-round and
public-coin constant-round post-quantum black-box $\epsilon$-zero-knowledge
arguments for $\mathbf{NP}$ do not exist unless $\mathbf{NP}\subseteq
\mathbf{BQP}$.
- Abstract（参考訳）: 我々は,$\mathbf{np}$ に対する定数後量子ブラックボックスゼロ知識プロトコルの存在について検討する。
主な結果として、$\mathbf{NP}\subseteq \mathbf{BQP}$ がなければ、$\mathbf{NP}$ に対する定ラウンドのブラックボックスゼロ知識引数は存在しない。
定数付きブラックボックス ゼロ知識引数 $\mathbf{np}$ が古典的設定に存在するので、我々の主な結果は、ポスト量子と古典的ゼロ知識プロトコルの根本的な違いを指摘している。
従来の結果を組み合わせると、$\mathbf{np}\subseteq \mathbf{bqp}$, constant-round post-quantum zero-knowledge protocol for $\mathbf{np}$ がなければ、非ブラックボックス技術を使用するか、標準ゼロ知識を$\epsilon$-zero-knowledgeに緩和するといったセキュリティ要件を緩和する場合に限り、このプロトコルが存在する。
さらに、3ラウンドおよび公開コインの定数付き黒線ボックス $\epsilon$-zero-knowledge arguments for $\mathbf{np}$ は、$\mathbf{np}\subseteq \mathbf{bqp}$ でない限り存在しないことも証明する。
関連論文リスト
- Classical versus quantum queries in quantum PCPs with classical proofs [0.3004066195320147]
量子古典PCPを一般化し、古典的な証明に$q$の量子クエリを適用できるようにします。
驚くべきことに、このことは、定数量子古典量に対して逆から定数への約束のギャップを増幅できることを示している。
約束のギャップは達成できるが、我々の結果は、$mathsfQCMA$に対する定型クエリ量子古典的PCPが存在しないという強い証拠を与える。
論文 参考訳（メタデータ） (2024-11-01T18:00:56Z) - The Black-Box Simulation Barrier Persists in a Fully Quantum World [9.887919546667598]
我々は、$mathbfBQP$の言語のみが、定ラウンド$textitfully-quantum$ BBZKを許容していることを示す。
量子ゼロ知識の性質を照らし、量子領域で将来のプロトコルを設計するための貴重な洞察を提供する。
論文 参考訳（メタデータ） (2024-09-10T08:17:17Z) - Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
両部非絡み込み入力から次元独立なk-パーティイトディジアンタングル(類似)チャネルを構築する。
NEXP を捉えるためには、$| psi rangle = sqrta | sqrt1-a | psi_+ rangle という形の非負の振幅を持つのに十分であることを示す。
論文 参考訳（メタデータ） (2024-02-23T12:22:03Z) - Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower
bounds [1.3927943269211591]
本研究は、$mathsfPH$の量子検証に基づく3つの一般化を研究する。
まず、[GSSSY22] から、崩壊定理と$mathsfQCPH$に対するカルプ・リプトンの定理を含むいくつかの開問題を解く。
我々は、$mathsfpureQPH$に対する一方の誤り低減と、これらの量子変量$mathsfPH$に関する最初の境界を示す。
論文 参考訳（メタデータ） (2024-01-03T09:12:25Z) - Nonlocality under Computational Assumptions [51.020610614131186]
相関の集合が非局所であるとは、空間的分離な当事者がランダム性を共有し、局所的な操作を実行することによって再現できないことである。
ランダム性や量子時間計算によって再現できない局所的な(効率のよい)測定結果が存在することを示す。
論文 参考訳（メタデータ） (2023-03-03T16:53:30Z) - Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。
我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
論文 参考訳（メタデータ） (2022-07-28T17:50:53Z) - A New Approach to Post-Quantum Non-Malleability [8.859667450008452]
我々は、最初の$mathitconstant$-$mathitround$のポスト量子非有理コミットメントの構築を提供する。
コミットメントに関して、非適合性の標準概念を達成します。
論文 参考訳（メタデータ） (2022-07-12T21:47:39Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Uncertainties in Quantum Measurements: A Quantum Tomography [52.77024349608834]
量子系 $S$ に関連する可観測物は非可換代数 $mathcal A_S$ を形成する。
密度行列 $rho$ は可観測物の期待値から決定できると仮定される。
アーベル代数は内部自己同型を持たないので、測定装置は可観測物の平均値を決定することができる。
論文 参考訳（メタデータ） (2021-12-14T16:29:53Z) - The Acrobatics of BQP [1.7136832159667206]
量子時間(mathsfBQP$)の挙動をブラックボックスで設定すると、$mathsfNP$のような古典的な複雑性クラスと著しく分離できることが示される。
また、独立した関心を持つかもしれない新しいツールも導入します。
ランダム制限法の「量子対応」バージョン、$mathsfAC0$回路のブロック感度に対する集中定理、スパースオークスに対するアーロンソン・アンバイニス・コンジェクチャの(証明可能な)アナログを含む。
論文 参考訳（メタデータ） (2021-11-19T19:40:05Z) - Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and
ReLUs under Gaussian Marginals [49.60752558064027]
ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。
我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
論文 参考訳（メタデータ） (2020-06-29T17:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。