論文の概要: Quantum Time-Lock Puzzles in the Quantum Random Oracle Model
- arxiv url: http://arxiv.org/abs/2609.38894v1
- Date: Wed, 30 Sep 2026 03:41:00 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-01 18:57:27.145976
- Title: Quantum Time-Lock Puzzles in the Quantum Random Oracle Model
- Title（参考訳）: 量子ランダムOracleモデルにおける量子時間ロックパズル
- Abstract要約: タイムロックパズルの応用例としては、タイムリリース暗号、封印された入札、電子投票、公正契約署名、コインフリップ、ビザンティン合意などがある。
タイムロックパズルは古典的ランダムオラクルモデルでは不可能であることが知られている。
我々は、パズル自体が量子状態である量子時間ロックパズルを考える。
- 参考スコア（独自算出の注目度）: 5.752344485306172
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A time-lock puzzle allows a sender to hide a message in a puzzle such that recovering the message requires substantially more sequential computation than the time required to generate the puzzle, even when parallel computation is allowed. Applications of time-lock puzzles include timed-release encryption, sealed-bid auctions, electronic voting, fair contract signing, coin flipping, and Byzantine consensus. However, time-lock puzzles are known to be impossible in the classical random oracle model. To overcome the classical barrier, in this work we consider quantum time-lock puzzles, in which the puzzle itself is a quantum state. Our construction in the quantum random oracle model achieves generation in one oracle round, solving in at most $T$ oracle rounds, and security against polynomial-width quantum adversaries of depth $o(T)$ for every polynomially bounded delay $T=T(λ)$, resolving an open problem posed by Mahmoody, Moran, and Vadhan (2011).
- Abstract（参考訳）: タイムロックパズルは、並列計算が許される場合でも、送信者がパズルにメッセージを隠蔽し、メッセージの回収に要する時間はパズルを生成するのに要する時間よりもはるかに多くのシーケンシャルな計算を必要とするようにする。
タイムロックパズルの応用例としては、タイムリリース暗号、封印された入札、電子投票、公正契約署名、コインフリップ、ビザンティン合意などがある。
しかし、時間ロックパズルは古典的なランダムオラクルモデルでは不可能であることが知られている。
古典的障壁を克服するために、この研究では、パズル自体が量子状態である量子時間ロックパズルを考える。
量子ランダムオラクルモデルにおける我々の構成は、1つのオラクルラウンドで生成し、少なくとも$T$のオラクルラウンドで解決し、深さ$o(T)$の多項式幅の量子逆数に対するセキュリティを、Mahmoody, Moran, Vadhan (2011) によって引き起こされた開問題を解消する。
関連論文リスト
- Succinct Arguments for QMA in the Quantum Random Oracle Model [50.20559283775139]
量子乱数オラクルモデル(QROM)におけるQMAの最初の簡潔な議論を、暗号的仮定や証明されていない予想に頼ることなく構築する。
我々の結果は、量子インタラクティブなオラクル証明(QIOP)を同じ言語の量子引数にコンパイルする効率保存変換である。
論文 参考訳（メタデータ） (2026-09-29T12:54:55Z) - EFI Pairs Without One-Way Puzzles: Oracle Separations from Communication Complexity [0.0]
片道パズルは EFI 対であり、ホールドがオープンかどうかを暗示する。
単方向パズルが存在しない1つの古典的オラクルを、有界検証器でも構成する。
EFIペアは、古典的に神託をクエリするすべての区別器を生き残り、それについてアドバイスし、最後に1つの重ね合わせクエリを作る。
論文 参考訳（メタデータ） (2026-09-10T17:54:55Z) - Quantum Meta-Complexity Is All You Need: Characterizing One-Way Puzzles via Time-Bounded Kolmogorov Complexity [0.30458514384586394]
量子暗号の時間境界メタ複雑化プログラムを開始する。
最近の研究は、ワンウェイ関数を持たない量子暗号の最小探索プリミティブであるワンウェイパズルを特徴づけている。
論文 参考訳（メタデータ） (2026-09-02T14:54:44Z) - Time-Delayed Publicly Verifiable Quantum Computation for Classical Verifiers [4.613517417540153]
一般に検証可能なデリゲートは、リソース集約型の計算タスクを、より強力で信頼性の低いサーバにアウトソースしたいという、よく知られた問題である。
本稿では,コミットメントスキームと時間ロックパズルを利用した実用的な非対話型スキームを提案する。
論文 参考訳（メタデータ） (2026-04-26T03:42:54Z) - 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) - Taming Quantum Time Complexity [45.867051459785976]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳（メタデータ） (2023-11-27T14:45:19Z) - Multi-Armed Bandits and Quantum Channel Oracles [56.72223170618133]
我々は、報酬のランダム性に制限されたアクセスしか持たないバンディットモデルを導入するが、それでも重ね合わせの腕に問い合わせることができる。
これは、オラクルが正の故障確率を持つ場合、非構造化探索ではスピードアップが不可能である、という事前の結果を一般化する。
論文 参考訳（メタデータ） (2023-01-20T13:01:40Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
量子計算の2つのモデル: CQ_dとQC_d。
CQ_dは、d-d-deepth量子コンピュータのシナリオを何度も捉え、QC_dは測定ベースの量子計算に類似している。
CQ_dとQC_dの類似性にもかかわらず、2つのモデルは本質的にはCQ_d $nsubseteq$QC_dとQC_d $nsubseteq$CQ_dである。
論文 参考訳（メタデータ） (2022-01-06T03:10:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。