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.

収録刊行物

詳細情報 詳細情報について

  • CRID
    1050855522098190336
  • NII論文ID
    170000186005
  • Web Site
    http://id.nii.ac.jp/1001/00214404/
  • 本文言語コード
    ja
  • 資料種別
    conference paper
  • データソース種別
    • IRDB
    • CiNii Articles

問題の指摘

ページトップへ