論文の概要: A quantum algorithm for finding collision-inducing disturbance vectors
in SHA-1
- arxiv url: http://arxiv.org/abs/2210.12762v1
- Date: Sun, 23 Oct 2022 16:01:17 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-18 09:46:09.200868
- Title: A quantum algorithm for finding collision-inducing disturbance vectors
in SHA-1
- Title(参考訳): SHA-1における衝突誘導外乱ベクトルの量子アルゴリズム
- Authors: Jiheng Duan, Minghui Li, Hou Ian
- Abstract要約: 現代の暗号プロトコルは、ユーザ認証やその他のセキュリティ検証のシグネチャとして機能する準ユニクティックな数値を生成するために、洗練されたハッシュ関数に依存している。
セキュリティは、同一の番号にマッチするハッシュテキストを見つけ、いわゆる衝突攻撃を発生させることによって妥協される可能性がある。
本稿では,絡み合った量子状態を利用して,候補外乱ベクトルの同時シード化を行うアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 2.963904090194172
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Modern cryptographic protocols rely on sophisticated hash functions to
generate quasi-unique numbers that serve as signatures for user authentication
and other security verifications. The security could be compromised by finding
texts hash-mappable to identical numbers, forming so-called collision attack.
Seeding a disturbance vector in the hash mapping to obtain a successful
collision is that a major focus of cryptography study in the past two decades
to improve hash protocols. We propose an algorithm that takes advantage of
entangled quantum states for concurrent seeding of candidate disturbance
vectors, out of which the one entailing collision is selected through a
combination of quantum search, phase gating, diffusion gating, and information
feedbacks from classical computing machinery. The complexity reduction is shown
to be on the order of $\mathcal{O}(2^{n/2+1})$ where $n$ is the number of
qubits encoding addresses. We demonstrate the practicality of the proposed by
an implementation scheme based on degenerate optical parametric oscillators.
- Abstract(参考訳): 現代の暗号プロトコルは、ユーザ認証やその他のセキュリティ検証のシグネチャとして機能する準ユニクティックな数値を生成するために洗練されたハッシュ関数に依存している。
セキュリティは、同一の番号にマッチするハッシュテキストを見つけ、いわゆる衝突攻撃を発生させることによって妥協される可能性がある。
ハッシュマッピングに外乱ベクトルをシードして衝突を成功させることは、過去20年間の暗号研究の主要な焦点がハッシュプロトコルを改善することである。
本稿では, 量子探索, 位相ゲーティング, 拡散ゲーティング, および古典計算機械からの情報フィードバックを組み合わせることで, 衝突を伴わない乱ベクトルの同時シード化に, 絡み合った量子状態を利用するアルゴリズムを提案する。
複雑性の低減は$\mathcal{O}(2^{n/2+1})$の順で示され、$n$はアドレスを符号化する量子ビットの数である。
縮退型光パラメトリック発振器に基づく実装方式により提案手法の実用性を示す。
関連論文リスト
- Quantum One-Wayness of the Single-Round Sponge with Invertible
Permutations [55.2480439325792]
スポンジハッシュ(Spnge hashing)は、現在の国際ハッシュ関数標準SHA-3の基盤となる暗号ハッシュアルゴリズムの新たなクラスである。
ウンルーが提唱した「二重側ゼロ探索」予想を証明する。
また、ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要であることも示している。
論文 参考訳(メタデータ) (2024-03-07T18:46:58Z) - 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) - The NISQ Complexity of Collision Finding [2.9405711598281536]
現代の暗号における基本的なプリミティブである衝突耐性ハッシュは、同じハッシュ値を生成する入力を効率的に見つける方法がないことを保証している。
現在、量子敵はNISQのパワーを備えたフルスケールのコンピュータを必要とする。
本稿では, NISQアルゴリズムの3つの異なるモデルについて検討する。
論文 参考訳(メタデータ) (2022-11-23T13:55:28Z) - A Variational Quantum Attack for AES-like Symmetric Cryptography [69.80357450216633]
古典的AES様対称暗号のための変分量子攻撃アルゴリズム(VQAA)を提案する。
VQAAでは、既知の暗号文は、正規グラフを通して構築されるハミルトンの基底状態として符号化される。
論文 参考訳(メタデータ) (2022-05-07T03:15:15Z) - Quantum Proofs of Deletion for Learning with Errors [91.3755431537592]
完全同型暗号方式として, 完全同型暗号方式を初めて構築する。
我々の主要な技術要素は、量子証明器が古典的検証器に量子状態の形でのLearning with Errors分布からのサンプルが削除されたことを納得させる対話的プロトコルである。
論文 参考訳(メタデータ) (2022-03-03T10:07:32Z) - Quantum collision finding for homomorphic hash functions [0.0]
証明可能なハッシュ関数に対して,$oplus$-linearハッシュ関数に対する事前攻撃を含む具体的な攻撃例を示す。
加法的あるいは乗法的なハッシュ関数は、量子コンピュータの隠れ部分群問題アルゴリズムを用いて量子攻撃に対して脆弱である。
論文 参考訳(メタデータ) (2021-07-30T23:01:02Z) - Quantum copy-protection of compute-and-compare programs in the quantum
random oracle model [74.52678585199014]
計算・比較プログラム(Computer-and-compare program)として知られる回避関数のクラスに対する量子コピー保護スキームを導入する。
我々は,量子乱数オラクルモデル(QROM)において,完全悪意のある敵に対する非自明なセキュリティを実現することを証明した。
補完的な結果として、「セキュアソフトウェアリース」という,ソフトウェア保護の概念の弱さが示される。
論文 参考訳(メタデータ) (2020-09-29T08:41:53Z) - Quantum Search for Scaled Hash Function Preimages [1.3299507495084417]
本稿では,Groverのアルゴリズムを量子シミュレーターに実装し,2つのスケールしたハッシュ関数の前像の量子探索を行う。
我々は,Groverのアルゴリズムのいくつかのステップの後に量子レジスタをサンプリングしてショートカットを提案する戦略は,誤差軽減の観点からは限界的な実用的優位性しか得られないことを示した。
論文 参考訳(メタデータ) (2020-09-01T18:00:02Z) - Optimizing Quantum Search with a Binomial Version of Grover's Algorithm [4.220030262107688]
Groverの検索アルゴリズムの重要なコンポーネントである振幅増幅は、1つまたは複数のターゲット状態の確率を体系的に増加させるために反復的アプローチを使用する。
状態をクラスに分割することで増幅手順を強化するための新しい戦略を提案する。
論文 参考訳(メタデータ) (2020-07-21T15:36:35Z) - Targeted Attack for Deep Hashing based Retrieval [57.582221494035856]
本研究では, ディープ・ハッシュ・ターゲット・アタック (DHTA) と呼ばれる新たな手法を提案し, 対象とする攻撃を探索する。
まず、対象の攻撃を点対セットの最適化として定式化し、敵のサンプルのハッシュコードと対象のラベルを持つ対象の集合の平均距離を最小化する。
性能と知覚性のバランスをとるために,摂動に対する$ellinfty$制限の下で,逆例のハッシュコードとアンカーコードとのハミング距離を最小化することを提案する。
論文 参考訳(メタデータ) (2020-04-15T08:36:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。