論文の概要: From Worst-Case Hardness of $\mathsf{NP}$ to Quantum Cryptography via Quantum Indistinguishability Obfuscation

• arxiv url: http://arxiv.org/abs/2506.19542v1
• Date: Tue, 24 Jun 2025 11:50:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-25 19:48:23.61408
• Title: From Worst-Case Hardness of $\mathsf{NP}$ to Quantum Cryptography via Quantum Indistinguishability Obfuscation
• Title（参考訳）: $\mathsf{NP}$の最悪のハードネスから量子不特定性難読化による量子暗号へ
• Authors: Tomoyuki Morimae, Yuki Shirakawa, Takashi Yamakawa,
• Abstract要約: Indistinguishability obfuscation (iO) は多くの意味を持つ強力な暗号プリミティブとして登場した。 本研究では、量子iOのパワーの研究を開始する。
• 参考スコア（独自算出の注目度）: 8.093227427119325
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Indistinguishability obfuscation (iO) has emerged as a powerful cryptographic primitive with many implications. While classical iO, combined with the infinitely-often worst-case hardness of $\mathsf{NP}$, is known to imply one-way functions (OWFs) and a range of advanced cryptographic primitives, the cryptographic implications of quantum iO remain poorly understood. In this work, we initiate a study of the power of quantum iO. We define several natural variants of quantum iO, distinguished by whether the obfuscation algorithm, evaluation algorithm, and description of obfuscated program are classical or quantum. For each variant, we identify quantum cryptographic primitives that can be constructed under the assumption of quantum iO and the infinitely-often quantum worst-case hardness of $\mathsf{NP}$ (i.e., $\mathsf{NP} \not\subseteq \mathsf{i.o.BQP}$). In particular, we construct pseudorandom unitaries, QCCC quantum public-key encryption and (QCCC) quantum symmetric-key encryption, and several primitives implied by them such as one-way state generators, (efficiently-verifiable) one-way puzzles, and EFI pairs, etc. While our main focus is on quantum iO, even in the classical setting, our techniques yield a new and arguably simpler construction of OWFs from classical (imperfect) iO and the infinitely-often worst-case hardness of $\mathsf{NP}$.
• Abstract（参考訳）: Indistinguishability obfuscation (iO) は多くの意味を持つ強力な暗号プリミティブとして登場した。 古典的iOは、無限大の最悪のハードネスである$\mathsf{NP}$と組み合わせて、一方向関数(OWF)と様々な高度な暗号プリミティブを暗示することが知られているが、量子iOの暗号的含意はいまだに理解されていない。 本研究では、量子iOのパワーの研究を開始する。 我々は、難読化アルゴリズム、評価アルゴリズム、難読化プログラムの記述が古典的か量子的かによって区別される量子iOのいくつかの自然変種を定義する。 各変種について、量子iOと無限大の量子最悪ケース硬度$\mathsf{NP}$(つまり$\mathsf{NP} \not\subseteq \mathsf{i.o.BQP}$)の仮定で構築できる量子暗号プリミティブを同定する。 特に、擬似ランダムユニタリー、QCCC量子公開鍵暗号、(QCCC)量子対称鍵暗号、およびそれらによって暗示されるいくつかのプリミティブを構築する。 我々の主な焦点は量子iOであるが、古典的設定においても、我々の手法は古典的(不完全な) iO から新しいより単純な OWF の構成をもたらし、無限大の最悪の硬さは$\mathsf{NP}$である。

関連論文リスト

• Efficient Quantum Pseudorandomness from Hamiltonian Phase States [41.94295877935867]
  我々は、ハミルトニアン相状態(HPS)問題と呼ばれる量子硬度仮定を導入する。 我々は、我々の仮定が少なくとも完全に量子的であることを示し、すなわち片方向関数を構成するのに使用できない。 仮定とその変形により、多くの擬似ランダム量子プリミティブを効率的に構築できることを示す。
  論文  参考訳（メタデータ） (2024-10-10T16:10:10Z)
• 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 Truncated Differential and Boomerang Attack [10.853582091917236]
  本稿では,truncated differential と boomerang cryptanalysis に焦点をあてる。 まず、対称暗号の切り詰められた微分を求めるために設計された量子アルゴリズムを提案する。 我々は、圧倒的な確率で、我々のアルゴリズムによって出力される切り離された微分は、キー空間のキーの大部分に対して高い差分確率を持つ必要があることを証明した。
  論文  参考訳（メタデータ） (2024-07-21T11:34:29Z)
• Revocable Cryptography from Learning with Errors [61.470151825577034]
  我々は、量子力学の非閉鎖原理に基づいて、キー呼び出し機能を備えた暗号スキームを設計する。 我々は、シークレットキーが量子状態として表現されるスキームを、シークレットキーが一度ユーザから取り消されたら、それらが以前と同じ機能を実行する能力を持たないことを保証して検討する。
  論文  参考訳（メタデータ） (2023-02-28T18:58:11Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。 本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
  論文  参考訳（メタデータ） (2021-07-05T17:45:41Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。 我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。 我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-14T11:05:26Z)

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

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