論文の概要: On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs
of Sequential Work
- arxiv url: http://arxiv.org/abs/2010.11658v4
- Date: Fri, 9 Jul 2021 09:06:07 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-28 01:08:00.083776
- Title: On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs
of Sequential Work
- Title（参考訳）: 連続作業証明の圧縮Oracle技術とポスト量子セキュリティについて
- Authors: Kai-Min Chung, Serge Fehr, Yu-Hsuan Huang, Tai-Ning Liao
- Abstract要約: 我々は、量子ランダムオラクルモデル(QROM)における量子アルゴリズムの分析のために、Zhandryによって導入されたいわゆる圧縮オラクル手法を再考する。
我々の主な技術的貢献は、クエリ複雑性の結果を証明するために圧縮されたオラクル技法の並列クエリの一般化を単純化するフレームワークである。
本手法の具体的な暗号的応用として,Cohen と Pietrzak が提唱した "Simple Proofs of Sequential Work" が量子攻撃に対して安全であることを示す。
- 参考スコア（独自算出の注目度）: 10.43571631715192
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We revisit the so-called compressed oracle technique, introduced by Zhandry
for analyzing quantum algorithms in the quantum random oracle model (QROM). To
start off with, we offer a concise exposition of the technique, which easily
extends to the parallel-query QROM, where in each query-round the considered
algorithm may make several queries to the QROM in parallel. This variant of the
QROM allows for a more fine-grained query-complexity analysis.
Our main technical contribution is a framework that simplifies the use of
(the parallel-query generalization of) the compressed oracle technique for
proving query complexity results. With our framework in place, whenever
applicable, it is possible to prove quantum query complexity lower bounds by
means of purely classical reasoning. More than that, for typical examples the
crucial classical observations that give rise to the classical bounds are
sufficient to conclude the corresponding quantum bounds.
We demonstrate this on a few examples, recovering known results (like the
optimality of parallel Grover), but also obtaining new results (like the
optimality of parallel BHT collision search). Our main target is the hardness
of finding a $q$-chain with fewer than $q$ parallel queries, i.e., a sequence
$x_0, x_1,\ldots, x_q$ with $x_i = H(x_{i-1})$ for all $1 \leq i \leq q$.
The above problem of finding a hash chain is of fundamental importance in the
context of proofs of sequential work. Indeed, as a concrete cryptographic
application of our techniques, we prove that the "Simple Proofs of Sequential
Work" proposed by Cohen and Pietrzak remains secure against quantum attacks.
Such an analysis is not simply a matter of plugging in our new bound; the
entire protocol needs to be analyzed in the light of a quantum attack. Thanks
to our framework, this can now be done with purely classical reasoning.
- Abstract（参考訳）: 我々は、zhandryが量子ランダムオラクルモデル(qrom)で量子アルゴリズムを分析するために導入した圧縮オラクル技術について再検討する。
まず、並列クエリQROMに容易に拡張できる手法の簡潔な説明を行い、各クエリラウンドにおいて、考慮されたアルゴリズムが複数のクエリを並列にQROMに生成する。
このQROMの変形により、よりきめ細かいクエリ・複雑度解析が可能になる。
我々の主な技術的貢献は、クエリ複雑性の結果を証明するために圧縮されたオラクル技術を使用する(並列クエリの一般化)フレームワークである。
我々のフレームワークが組み込まれているため、任意の場合に、純粋に古典的な推論によって量子的クエリの複雑さを下げることが可能である。
それよりも、典型的には古典的境界をもたらす重要な古典的観測は、対応する量子境界を結論付けるのに十分である。
我々はこれをいくつかの例で示し、既知の結果(並列Groverの最適性など)を復元すると同時に、新しい結果(並列BHT衝突探索の最適性など)を得る。
私たちの主なターゲットは、$q$以下の並列クエリ、すなわち、$x_0, x_1,\ldots, x_q$ with $x_i = H(x_{i-1})$ for all $1 \leq i \leq q$。
上記のハッシュ連鎖を見つける問題は、シーケンシャルな作業の証明の文脈において重要な問題である。
実際、我々の技術の具体的な暗号的応用として、CohenとPietrzakが提唱した"Simple Proofs of Sequential Work"が量子攻撃に対して安全であることを示す。
このような分析は、単に新しいバウンドをプラグインすることではなく、プロトコル全体を量子攻撃の光で分析する必要がある。
私たちのフレームワークのおかげで、これは純粋に古典的な推論で実現できます。
関連論文リスト
- Grover's oracle for the Shortest Vector Problem and its application in
hybrid classical-quantum solvers [0.38366697175402226]
格子内の最短ベクトルを見つけることは、古典コンピュータと量子コンピュータの両方にとって困難であると考えられている問題である。
SVPのための最も優れた古典的、量子的、あるいはハイブリッドな古典量子アルゴリズムを見つけるためには、十分なセキュリティレベルを提供する暗号系パラメータを選択する必要がある。
グロバーの探索量子アルゴリズムは、一般的な二次的なスピードアップを提供する。
我々はGroverの小さなSVPインスタンスの量子探索と最先端の古典的解法を組み合わせる方法について分析する。
論文 参考訳（メタデータ） (2024-02-21T16:05:49Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳（メタデータ） (2023-11-07T04:59:02Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - The NISQ Complexity of Collision Finding [2.9405711598281536]
現代の暗号における基本的なプリミティブである衝突耐性ハッシュは、同じハッシュ値を生成する入力を効率的に見つける方法がないことを保証している。
現在、量子敵はNISQのパワーを備えたフルスケールのコンピュータを必要とする。
本稿では, NISQアルゴリズムの3つの異なるモデルについて検討する。
論文 参考訳（メタデータ） (2022-11-23T13:55:28Z) - 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) - 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) - Depth-efficient proofs of quantumness [77.34726150561087]
量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。
本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
論文 参考訳（メタデータ） (2021-07-05T17:45:41Z) - Quantum Attacks without Superposition Queries: the Offline Simon's
Algorithm [7.819565615098435]
我々はサイモンのサブルーチンを新しい方法で利用する新しい量子アルゴリズムを導入する。
現状の文献に関して量子時間/古典データのトレードオフを改善した。
我々はデータの複雑さを減らし、過去の重ね合わせ攻撃を改善した。
論文 参考訳（メタデータ） (2020-02-27T21:05:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。