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

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.