論文の概要: Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations

• arxiv url: http://arxiv.org/abs/2403.04740v3
• Date: Fri, 19 Jul 2024 03:17:22 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-22 23:47:06.638727
• Title: Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations
• Title（参考訳）: 非可逆な置換をもつ単線スポンジの量子一方向性
• Authors: Joseph Carolan, Alexander Poremba,
• Abstract要約: スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。 これまでのところ、不規則な置換は根本的なオープンな問題のままである。 ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
• 参考スコア（独自算出の注目度）: 49.1574468325115
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Sponge hashing is a widely used class of cryptographic hash algorithms which underlies the current international hash function standard SHA-3. In a nutshell, a sponge function takes as input a bit-stream of any length and processes it via a simple iterative procedure: it repeatedly feeds each block of the input into a so-called block function, and then produces a digest by once again iterating the block function on the final output bits. While much is known about the post-quantum security of the sponge construction when the block function is modeled as a random function or one-way permutation, the case of invertible permutations, which more accurately models the construction underlying SHA-3, has so far remained a fundamental open problem. In this work, we make new progress towards overcoming this barrier and show several results. First, we prove the "double-sided zero-search" conjecture proposed by Unruh (eprint' 2021) and show that finding zero-pairs in a random $2n$-bit permutation requires at least $\Omega(2^{n/2})$ many queries -- and this is tight due to Grover's algorithm. At the core of our proof lies a novel "symmetrization argument" which uses insights from the theory of Young subgroups. Second, we consider more general variants of the double-sided search problem and show similar query lower bounds for them. As an application, we prove the quantum one-wayness of the single-round sponge with invertible permutations in the quantum random oracle model.
• Abstract（参考訳）: スポンジハッシュ(Spnge hashing)は、現在の国際ハッシュ関数標準SHA-3の基盤となる暗号ハッシュアルゴリズムのクラスである。 簡単に言えば、スポンジ関数は任意の長さのビットストリームとして入力を受け取り、単純な反復手順で処理し、入力の各ブロックをいわゆるブロック関数に繰り返し供給し、最後に出力されたビットでブロック関数を繰り返すことでダイジェストを生成する。 ブロック関数がランダム関数あるいは片方向の置換としてモデル化された場合、スポンジ構造のクォータム後セキュリティについては、多くのことが知られているが、SHA-3の基盤となる構造をより正確にモデル化した可逆置換の場合、今のところ根本的なオープンな問題のままである。 本研究では,この障壁を克服するための新たな進展と,いくつかの結果を示す。 まず、Unruh (eprint' 2021) が提唱した「二重側ゼロ探索」予想を証明し、ランダムな2n$-ビットの置換でゼロペアを見つけるには、少なくとも$\Omega(2^{n/2})$ 多くのクエリが必要であることを示す。 我々の証明の核には、ヤング部分群の理論からの洞察を利用する新しい「対称性論」がある。 第二に、両面探索問題のより一般的な変種を考察し、類似したクエリの下位境界を示す。 応用として、単一ラウンドスポンジの量子一方向性を量子ランダムオラクルモデルにおける可逆置換で証明する。

関連論文リスト

• Quantum-Computable One-Way Functions without One-Way Functions [0.6349503549199401]
  古典的なオラクルを構築し、$mathsfP = MathsfNP$, but quantum-computable quantum-secure trapdoor one-way function が存在する。 この結果から,複数コピーの擬似乱数状態と擬似乱数ユニタリー,古典通信の公開鍵暗号,シグネチャ,暗黙の転送方式が示唆された。
  論文  参考訳（メタデータ） (2024-11-04T19:40:01Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。 次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
  論文  参考訳（メタデータ） (2023-11-07T04:59:02Z)
• One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
  量子ラスベガスのクエリの複雑さは、量子対向境界と全く同じであることを示す。 これは、逆反転問題に対する実現可能な解を量子クエリーアルゴリズムに変換することで達成される。
  論文  参考訳（メタデータ） (2023-01-05T11:05:22Z)
• 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)
• Quantum Search for Scaled Hash Function Preimages [1.3299507495084417]
  本稿では,Groverのアルゴリズムを量子シミュレーターに実装し,2つのスケールしたハッシュ関数の前像の量子探索を行う。 我々は,Groverのアルゴリズムのいくつかのステップの後に量子レジスタをサンプリングしてショートカットを提案する戦略は,誤差軽減の観点からは限界的な実用的優位性しか得られないことを示した。
  論文  参考訳（メタデータ） (2020-09-01T18:00:02Z)
• Sparse Hashing for Scalable Approximate Model Counting: Theory and Practice [36.8421113576893]
  n 変数上の CNF 式 F が与えられたとき、モデルカウントや #SAT の問題は F の満足な割り当ての数を計算することである。 近年,効率的なアルゴリズム技術開発への取り組みが急増している。
  論文  参考訳（メタデータ） (2020-04-30T11:17:26Z)
• Quantum Attacks without Superposition Queries: the Offline Simon's Algorithm [7.819565615098435]
  我々はサイモンのサブルーチンを新しい方法で利用する新しい量子アルゴリズムを導入する。 現状の文献に関して量子時間/古典データのトレードオフを改善した。 我々はデータの複雑さを減らし、過去の重ね合わせ攻撃を改善した。
  論文  参考訳（メタデータ） (2020-02-27T21:05:54Z)

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

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