論文の概要: Verifiable Quantum Advantage without Structure
- arxiv url: http://arxiv.org/abs/2204.02063v2
- Date: Fri, 17 Jun 2022 04:23:35 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-18 05:36:18.147241
- Title: Verifiable Quantum Advantage without Structure
- Title(参考訳): 構造のない検証可能な量子優位性
- Authors: Takashi Yamakawa, Mark Zhandry
- Abstract要約: ランダムなオラクルをSHA2のような具体的な暗号ハッシュ関数に置き換える。
以上の結果の最小限のインスタンス化が可能である。
- 参考スコア(独自算出の注目度): 18.816869896281666
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We show the following hold, unconditionally unless otherwise stated, relative
to a random oracle with probability 1:
- There are NP search problems solvable by BQP machines but not BPP machines.
- There exist functions that are one-way, and even collision resistant,
against classical adversaries but are easily inverted quantumly. Similar
separations hold for digital signatures and CPA-secure public key encryption
(the latter requiring the assumption of a classically CPA-secure encryption
scheme). Interestingly, the separation does not necessarily extend to the case
of other cryptographic objects such as PRGs.
- There are unconditional publicly verifiable proofs of quantumness with the
minimal rounds of interaction: for uniform adversaries, the proofs are
non-interactive, whereas for non-uniform adversaries the proofs are two message
public coin.
- Our results do not appear to contradict the Aaronson-Ambanis conjecture.
Assuming this conjecture, there exist publicly verifiable certifiable
randomness, again with the minimal rounds of interaction.
By replacing the random oracle with a concrete cryptographic hash function
such as SHA2, we obtain plausible Minicrypt instantiations of the above
results. Previous analogous results all required substantial structure, either
in terms of highly structured oracles and/or algebraic assumptions in
Cryptomania and beyond.
- Abstract(参考訳): 確率1: - BQPマシンでは解けるが、BPPマシンでは解けないNP探索問題が存在する。
-古典的敵に対して一方向的で、衝突耐性さえあるが、量子的に容易に反転する関数が存在する。
同様の分離は、デジタル署名とCPAセキュアな公開鍵暗号(後者は古典的にCPAセキュアな暗号スキームの仮定を必要とする)に当てはまる。
興味深いことに、分離はPRGのような他の暗号オブジェクトの場合に必ずしも拡張されない。
同一の敵に対して、証明は非相互作用的であり、一方、一様でない敵に対しては、証明は2つのメッセージ公開コインである。
-我々の結果はアーロンソン・アンバニス予想と矛盾しないように見える。
この予想を仮定すると、再び最小の相互作用のラウンドで、公に検証可能な証明可能なランダム性が存在する。
ランダムオラクルをSHA2のような具体的な暗号ハッシュ関数に置き換えることで、上記の結果の可算最小化が得られる。
以前の類似の結果はすべて、高度に構造化されたオラクルやクリプトマニア以降の代数的仮定の観点から、実質的な構造を必要とする。
関連論文リスト
- Quantum One-Wayness of the Single-Round Sponge with Invertible
Permutations [55.2480439325792]
スポンジハッシュ(Spnge hashing)は、現在の国際ハッシュ関数標準SHA-3の基盤となる暗号ハッシュアルゴリズムの新たなクラスである。
ウンルーが提唱した「二重側ゼロ探索」予想を証明する。
また、ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要であることも示している。
論文 参考訳(メタデータ) (2024-03-07T18:46:58Z) - Public-Key Encryption with Quantum Keys [11.069434965621683]
鍵が量子状態であることが許される量子公開鍵暗号(qPKE)の概念について検討する。
量子公開鍵暗号を構築するには計算仮定が必要であることを示す。
論文 参考訳(メタデータ) (2023-06-13T11:32:28Z) - Publicly-Verifiable Deletion via Target-Collapsing Functions [81.13800728941818]
ターゲットの折り畳みは、公開可能な削除(PVD)を可能にすることを示す。
我々は、弱い暗号的仮定から公開可能な削除を支援する様々なプリミティブを得るために、このフレームワークを構築している。
論文 参考訳(メタデータ) (2023-03-15T15:00:20Z) - Encryption with Quantum Public Keys [1.7725414095035827]
本稿では,一方の関数とより弱い仮定から量子公開鍵暗号スキームを構築するという課題について考察する。
本研究では,一方の関数からの量子公開鍵暗号,擬似乱数関数様状態と擬似乱数関数様状態との3つのスキームを提案する。
論文 参考訳(メタデータ) (2023-03-09T16:17:19Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳(メタデータ) (2022-10-12T17:54:02Z) - 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) - Hidden Cosets and Applications to Unclonable Cryptography [15.248351992500078]
隠れた部分空間状態から隠れたコセット状態への一般化について研究する(最初にアーロンソンとクリスティアン (STOC '12]) によって導入された)。
我々は、コセット状態といくつかの応用の無視不可能な性質を探求する。
論文 参考訳(メタデータ) (2021-07-12T19:04:01Z) - Quantum Pseudorandomness and Classical Complexity [0.08158530638728499]
暗号擬似乱数量子状態と擬似乱数ユニタリ変換が存在することを示す。
本稿では、暗号、複雑性理論、量子トモグラフィーにおけるこれらの結果の影響について論じる。
論文 参考訳(メタデータ) (2021-03-16T20:54:12Z) - Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin's
Post-Quantum Security [67.06003361150228]
作業の証明(英: proof of work、PoW)は、当事者が計算タスクの解決にいくらかの労力を費やしたことを他人に納得させることができる重要な暗号構造である。
本研究では、量子戦略に対してそのようなPoWの連鎖を見つけることの難しさについて検討する。
我々は、PoWs問題の連鎖が、マルチソリューションBernoulliサーチと呼ばれる問題に還元されることを証明し、量子クエリの複雑さを確立する。
論文 参考訳(メタデータ) (2020-12-30T18:03:56Z) - Quantum copy-protection of compute-and-compare programs in the quantum
random oracle model [74.52678585199014]
計算・比較プログラム(Computer-and-compare program)として知られる回避関数のクラスに対する量子コピー保護スキームを導入する。
我々は,量子乱数オラクルモデル(QROM)において,完全悪意のある敵に対する非自明なセキュリティを実現することを証明した。
補完的な結果として、「セキュアソフトウェアリース」という,ソフトウェア保護の概念の弱さが示される。
論文 参考訳(メタデータ) (2020-09-29T08:41:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。