3ラウンドFeistel暗号に対するGroverのアルゴリズムを用いた効率的な鍵回復攻撃

• Item type: Symposium(1)
• 公開日: 2021-10-19
• タイトル: 3ラウンドFeistel暗号に対するGroverのアルゴリズムを用いた効率的な鍵回復攻撃
• タイトル / 言語: en
• タイトル: Quantum Key Recovery Attack with Grover Search on 3-Round Feistel-KF Structure
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 共通鍵暗号，選択平文攻撃，Groverのアルゴリズム，Q1 model
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 茨城大学大学院理工学研究科
• 著者所属: 茨城大学
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Engineering, Ibaraki University
• 著者所属(英): en
• 著者所属(英): Ibaraki University
• 著者名: 台座, 崇規; 米山, 一樹
• 著者名(英): Takanori, Daiza; Kazuki, Yoneyama
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 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 に相当する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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論文集; p. 833-840, 発行日 2021-10-19
• 出版者 / 言語: ja
• 出版者: 情報処理学会