論文の概要: Verifiable Quantum Advantage without Structure

• arxiv url: http://arxiv.org/abs/2204.02063v3
• Date: Mon, 11 Nov 2024 05:57:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-12 17:14:40.139863
• Title: Verifiable Quantum Advantage without Structure
• Title（参考訳）: 構造を持たない検証可能な量子アドバンテージ
• Authors: Takashi Yamakawa, Mark Zhandry,
• Abstract要約: ランダムなオラクルをSHA2のような具体的な暗号ハッシュ関数に置き換える。 以上の結果の最小限のインスタンス化が可能である。
• 参考スコア（独自算出の注目度）: 15.701707809084716
• License:
• Abstract: We show the following hold, unconditionally unless otherwise stated, relative to a random oracle: - There are NP search problems solvable by quantum polynomial-time machines but not classical probabilistic polynomial-time 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（参考訳）: 量子多項式時間機械では解けるが、古典確率多項式時間機械では解けないNP探索問題が存在する。 -古典的敵に対して一方通行で、衝突にも耐性があるが、量子的に容易に反転できる関数が存在する。 同様の分離は、デジタル署名とCPAセキュアな公開鍵暗号(後者は古典的にCPAセキュアな暗号スキームの仮定を必要とする)に当てはまる。 興味深いことに、分離はPRGのような他の暗号オブジェクトの場合に必ずしも拡張されない。 同一の敵に対して、証明は非相互作用的であり、一方、一様でない敵に対しては、証明は2つのメッセージ公開コインである。 -我々の結果はアーロンソン・アンバニス予想と矛盾しないように見える。 この予想を仮定すると、再び最小の相互作用のラウンドで、公に検証可能な証明可能なランダム性が存在する。 ランダムなオラクルをSHA2のような具体的な暗号ハッシュ関数に置き換えることで、上記の結果のもっともらしいミニ暗号化のインスタンス化が得られる。 以前の類似の結果はすべて、高度に構造化されたオラクルやクリプトマニア以降の代数的仮定の観点から、実質的な構造を必要とした。

関連論文リスト

• Towards Unconditional Uncloneable Encryption [1.18749525824656]
  Uncloneablecryptは、古典的なメッセージを量子暗号文に暗号化する暗号化プリミティブである。 関連するセキュリティゲームにおける敵の成功確率は、キー数を表す$K$が1/2+1/ (2sqrtK)$に2次収束し、1/2$は自明に達成可能であることを示す。
  論文  参考訳（メタデータ） (2024-10-30T14:40:06Z)
• (Quantum) Indifferentiability and Pre-Computation [50.06591179629447]
  微分可能性(Indifferentiability)は、理想的なオブジェクトのセキュリティを分析するための暗号パラダイムである。 その強さにもかかわらず、前処理攻撃に対するセキュリティを提供する無差別性は知られていない。 本稿では、構成可能であるだけでなく、任意の事前計算を考慮に入れた微分可能性の強化を提案する。
  論文  参考訳（メタデータ） (2024-10-22T00:41:47Z)
• Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from $\mathsf{\#P}$-Hardness [10.438299411521099]
  近年の分離により、階層構造が崩壊しても持続する硬さの源から量子暗号を構築する可能性が高まっている。 量子暗号は、$mathsfP#P notsubseteq mathsf(io)BQP/qpoly$という非常に穏やかな仮定に基づいている。
  論文  参考訳（メタデータ） (2024-09-23T17:45:33Z)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。 これまでのところ、不規則な置換は根本的なオープンな問題のままである。 ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
  論文  参考訳（メタデータ） (2024-03-07T18:46:58Z)
• Public-Key Encryption with Quantum Keys [11.069434965621683]
  鍵が量子状態であることが許される量子公開鍵暗号(qPKE)の概念について検討する。 量子公開鍵暗号を構築するには計算仮定が必要であることを示す。
  論文  参考訳（メタデータ） (2023-06-13T11:32:28Z)
• 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)
• 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 [48.94443749859216]
  計算・比較プログラム(Computer-and-compare program)として知られる回避関数のクラスに対する量子コピー保護スキームを導入する。 我々は,量子乱数オラクルモデル(QROM)において,完全悪意のある敵に対する非自明なセキュリティを実現することを証明した。 補完的な結果として、「セキュアソフトウェアリース」という,ソフトウェア保護の概念の弱さが示される。
  論文  参考訳（メタデータ） (2020-09-29T08:41:53Z)

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

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