3ラウンドFeistel暗号に対するGroverのアルゴリズムを用いた効率的な鍵回復攻撃
書誌事項
- タイトル別名
-
- Quantum Key Recovery Attack with Grover Search on 3-Round Feistel-KF Structure
抄録
Feistel-KF 構造は Feistel 構造の特殊な形の一つであり,i 番目のラウンド関数は F_i ( i 番目の鍵 XOR x) の形で表される.関数 F_i は入出力長が n/2 ビットの公開されたランダム関数である.3 ラウンドの Feistel-KF は古典攻撃に対し,online クエリ数 D + offline クエリ数 T << 2^{n/4} において安全であることが Lampe と Seurin によって示されている.また,2012 年に Isobe と Shibutani が meet-in-the-middle attack により (D,T)=(O(1),O(2^{n/2})) の古典攻撃を示した.しかし,彼らの攻撃では 2 個の段鍵を同時に導出しているため,Grover の量子アルゴリズムをそのまま当てはめ,2 個の段鍵の Grover 探索を行うことにより量子攻撃に拡張しようとすると,O(2^{n/2}) の計算量が必要となる.本稿では,量子モデルにおいて Grover のアルゴリズムを用い,段鍵を 1 個ずつ導出することにより(D,T)=(O(1),O(2^{n/4})) の量子攻撃を示す.本攻撃は暗号化オラクルへの量子クエリを行わないため,Q1 model に相当する.
Feistel-2 (Feistel-KF) structure is a variant of Feistel structure such that the i-th round function is given by F_i(i-th key XOR x). Lampe and Seurin showed that 3-round Feistel-KF cipher is secure in the classical setting if D+T << 2^(n/4). In 2012, Isobe and Shibutani showed a meet-in-the-middle attack which works for (D,T)=(O(1),O(2^(n/2))) on 3-round Feistel-KF. In their attack, two round keys are recovered simulataneously. Hence, a naive application of Grover's algorithm needs the Grover search for two values in T = O(2^(n/2)). In this paper, in the quantum setting, we introduce a known plaintext attack and a chosen plaintext attack on 3-round Feistel-KF using Grover's algorithm by recovering the round key one by one in (D,T)=(O(1),O(2^(n/4))). Our attack does not need any quantum query to the encryption oracle and works in the Q1 model.
収録刊行物
-
- コンピュータセキュリティシンポジウム2021論文集
-
コンピュータセキュリティシンポジウム2021論文集 833-840, 2021-10-19
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1050855522098190336
-
- NII論文ID
- 170000186005
-
- Web Site
- http://id.nii.ac.jp/1001/00214404/
-
- 本文言語コード
- ja
-
- 資料種別
- conference paper
-
- データソース種別
-
- IRDB
- CiNii Articles