論文の概要: Compressed Permutation Oracles Revisited

• arxiv url: http://arxiv.org/abs/2609.28469v1
• Date: Wed, 23 Sep 2026 17:57:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-25 00:05:18.140439
• Title: Compressed Permutation Oracles Revisited
• Title（参考訳）: Compressed Permutation Oraclesが再考
• Abstract要約: 置換の圧縮は、以前の手法に抵抗する暗号構造の量子セキュリティを分析するために使われてきた。 我々はこの分析を再検討し、厳密な$(N1/2)$に束縛された音質を改善する。 その結果, SHA1 と SHA2 で用いられるスポンジハッシュ構造と Davies-Meyer 圧縮関数に対して, きつく, コンクリートの衝突, およびプレイメージ下界が得られた。
• 参考スコア（独自算出の注目度）: 4.039245878626346
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The compressed permutation oracle has been used to analyze the quantum security of a number of cryptographic constructions which resisted prior techniques. However, these analyses were fundamentally limited by the poor soundness of the method: the technique was proven sound only up to $O(N^{1/12})$ queries to permutations on $N$ elements. We revisit this analysis, improving the soundness bound to a tight $Ω(N^{1/2})$. In addition to being tighter, our proof is conceptually simpler and more direct, and gives the same bound in the ideal cipher model. The main technical idea is to construct the compression isometry from a simple POVM on the naive purification, a technique which may find wider applications. As immediate applications, our results yield tight, concrete collision and pre-image lower bounds for the sponge hash construction underlying SHA3 and the Davies--Meyer compression function used in SHA1 and SHA2. More broadly, the improved soundness theorem provides a general-purpose tool for analyzing quantum security in settings where random permutations or ideal ciphers serve as the underlying primitive.
• Abstract（参考訳）: 圧縮置換オラクルは、以前の技術に抵抗する多くの暗号構造の量子セキュリティを分析するために使われてきた。 しかし、これらの分析は、この手法の低音性によって基本的に制限され、この手法は最大$O(N^{1/12})$クエリーで$N$要素の置換が可能であることが証明された。 この分析を再検討し、厳密な$Ω(N^{1/2})$に束縛された音質を改善する。 より厳密なことに加えて、我々の証明は概念的にシンプルで直接的であり、理想的な暗号モデルに同じ境界を与える。 主な技術的アイデアは、単純なPOVMから、より広いアプリケーションを見つける技術であるネイブ精製に基づいて圧縮アイソメトリを構築することである。 直近の応用として, SHA1 と SHA2 で用いられる SHA3 と Davies-Meyer 圧縮関数のスポンジハッシュ構造に対して, きつい, コンクリート衝突, 画像下界が得られる。 より広義に、改良された音質定理は、ランダムな置換や理想的な暗号が基礎となるプリミティブとして機能する設定において、量子セキュリティを解析するための汎用ツールを提供する。

関連論文リスト

• Simon's Algorithm for the Even-Mansour Cipher on Quantum Hardware [0.815557531820863]
  本稿では,NISQハードウェア上でのSimonの周期ファイリングアルゴリズムを用いて,E even-Mansour暗号の量子暗号解析の概念の証明を行う。 N = 3 および N = 4 に対して、ibm_miami プロセッサ上での N ビット構成の秘密鍵復元を成功させる。 この結果から,Simonのアルゴリズムは,現在の量子ハードウェア上での短ビット長に対して,Even-Mansour暗号に有効であることが示唆された。
  論文  参考訳（メタデータ） (2026-04-28T11:16:11Z)
• Compressed Permutation Oracles [0.6768558752130311]
  我々は、圧縮された置換オラクルの音質を発達させ、証明する。 我々は、基本的にすべての既知の量子クエリの低い境界をランダムな置換モデルで再証明する。
  論文  参考訳（メタデータ） (2025-09-23T03:13:48Z)
• Analytic Rényi Entropy Bounds for Device-Independent Cryptography [0.0]
  デバイス非依存(DI)暗号はセキュリティの最高レベルを表している。 本稿では,CHSHゲームに基づくプロトコルに対して,より厳密な有限サイズセキュリティ証明を得るための簡単な方法を提案する。
  論文  参考訳（メタデータ） (2025-07-10T01:15:28Z)
• Cloning Games, Black Holes and Cryptography [50.022147589030304]
  クローンゲーム解析のための新しいツールキットを提案する。 このフレームワークにより、バイナリフェーズ状態に基づいて新しいクローンゲームを分析することができる。 連成位相の変分最適境界は、ブラックホールの理想化されたモデルで衝突する情報について定量的な洞察を与えることを示す。
  論文  参考訳（メタデータ） (2024-11-07T14:09:32Z)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。 これまでのところ、不規則な置換は根本的なオープンな問題のままである。 ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
  論文  参考訳（メタデータ） (2024-03-07T18:46:58Z)
• A Variational Quantum Attack for AES-like Symmetric Cryptography [69.80357450216633]
  古典的AES様対称暗号のための変分量子攻撃アルゴリズム(VQAA)を提案する。 VQAAでは、既知の暗号文は、正規グラフを通して構築されるハミルトンの基底状態として符号化される。
  論文  参考訳（メタデータ） (2022-05-07T03:15:15Z)
• On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs of Sequential Work [10.43571631715192]
  我々は、量子ランダムオラクルモデル(QROM)における量子アルゴリズムの分析のために、Zhandryによって導入されたいわゆる圧縮オラクル手法を再考する。 我々の主な技術的貢献は、クエリ複雑性の結果を証明するために圧縮されたオラクル技法の並列クエリの一般化を単純化するフレームワークである。 本手法の具体的な暗号的応用として,Cohen と Pietrzak が提唱した "Simple Proofs of Sequential Work" が量子攻撃に対して安全であることを示す。
  論文  参考訳（メタデータ） (2020-10-22T12:44:08Z)

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

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