CRYPTREC EX-3202-2022

軽量暗号の安全性に関する調査及び評価(GIFT-COFB, Xoodyak)
三菱電機株式会社
内藤祐介

2022 年 12 月

エグゼクティブサマリー
NIST が主催の Lightweight Cryptography Standardization Process[19] の最終候補である GIFT-COFB [2, 3, 1] と Xoodyak [11, 10] の安全性に関する文献の調査結果をまとめる．

GIFT-COFB の安全性に関する文献調査

GIFT-COFB は，ブロック暗号ベースの認証暗号である．設計者が主張する安全性は，シングルユーザで，秘匿性について，オンライン計算で 64 bit，オフライン計算で 112 bit 以上，偽造不可
能性について，オンライン計算で 58 bit，オフライン計算で 112 bit 以上である．GIFT-COFB で用いられているブロック暗号 GIFT-128 と，GIFT-COFBの安全性に関する文献調査の結果は以下の通りある．

GIFT-128 の安全性 GIFT-128 は，鍵サイズとブロックサイズが 128 bit，
40 ラウンドのブロック暗号である [5]．これまでの最適な攻撃は，差分攻撃法
で，ラウンド数を 27 ラウンドに削減した GIFT-128 を破ることができる [25]．

GIFT-128 のラウンド数は 40 ラウンド，攻撃可能なラウンド数は 27 ラウン
ドと十分にマージンがあるため，GIFT-128 はオフライン計算に関して設計者が主張する 112 bit 以上の安全性を持つと考えられる．

GIFT-COFB の安全性 GIFT-COFB は，利用モードとして文献 [8] の COFBを用いている．COFB の安全性では，ブロック暗号を Pseudo-Random Per-mutation (PRP) と仮定している．上記の通り，GIFT-128 の安全性は担保されているため，GIFT-COFB の安全性は COFB の安全性に依存する．文献[8, 4] で，ブロックサイズを n bit，ブロック暗号を PRP 安全と仮定すると，シングルユーザに対して，秘匿性のオンライン計算に対して n/2 bit，偽造不可能性のオンライン計算に対して n/2 − log2 n bit となることが証明されている．GIFT-COFB は n = 128 であり，上記の通り，GIFT-128 はオフライン計算に関して 112 bit 以上の安全性を持つことから，設計者が主張する安
全性を持つと考えられる．

Xoodyak の安全性に関する調査 Xoodyak は，置換ベースのアルゴリズム
であり，ハッシュ関数と認証暗号の 2 つのアルゴリズムを備える．設計者が主張する安全性は，Collision Resistance，Second Preimage Resistance，Preimage Resistance に関して 128 bit，m-Target Preimage Resistance に関して min{256 − log2 m, 128} bit，認証暗号について，シングルユーザで，秘匿性と偽造不可能性について，オンライン計算で 160bit，オフライン計算で128bit である．Xoodyak で用いられる置換 Xoodoo[12] と Xoodyak の安全性に関する文献調査の結果は以下の通りある．

Xoodoo[12] の安全性

Xoodoo[12] は 384 bit，12 ラウンドの置換である．

Xoodoo[12] 単体では，文献 [16] で，オフライン計算量が 233 の Zero-sum
Distinguisher が提案されており，Xoodyak の設計者が主張するオフライン計
算で 128 bit の安全性はない．ただし，文献 [11] で設計者が述べているように，この攻撃が Xoodyak の安全性に直接影響を及ぼすものではないことに注意されたい．

Xoodyak のハッシュ関数の安全性 Xoodyak のハッシュ関数利用モードは，
Sponge 構造 [6] である．Sponge 構造は，b bit のランダム置換を用いる場合，
b bit のうち r bit が入力メッセージの処理で用いられるレートと呼ばれるパラメータで，残りの c bit (c = b − r) が安全性に寄与するキャパシティ
と呼ばれるパラメータである．Sponge 構造は，Indiﬀerentiability の意味で，

c/2 bit の安全性を持つ．Xoodyak のハッシュ関数は，b = 384, c = 256 で，
Indiﬀerentiability の安全性証明により，Xoodoo[12] をブラックボックスとする攻撃に対しては，Xoodyak は設計者が主張する安全性を持つ．Xoodoo[12]の構造を含めて考えると，Xoodoo[12] 単体での安全性は無いため，Sponge
構造の Indiﬀerentiability の安全性は Xoodyak の安全性に適用できない．一方で，Xoodyak のハッシュ関数に対する攻撃は今のところ存在しないため，

Xoodyak のハッシュ関数は設計者が主張する安全性を持つと考えられる．
Xoodyak の認証暗号の安全性 Xoodyak の認証暗号利用モードは，文献 [7, 12]に記載の置換をプリミティブとする Duplex 構造をベースに設計されている．

Duplex 構造の安全性は文献 [12] で，ランダム関数との識別不可能性が示されており，Xoodyak の認証暗号の安全性は，Duplex 構造の安全性に依存する．
Duplex 構造の安全性の結果に，Xoodyak のパラメータを適用すると，秘匿性に関しては，置換がブラックボックスの場合に，設計者が主張する安全性を持つと考えられる．一方で，偽造不可能性に関しては，文献 [12] の結果を用いると，置換がブラックボックスの場合に，オンライン計算で 64 bit，オ
フライン計算で 128 bit の安全性となるが，設計者が主張する安全性は，オンライン計算で 160 bit，オフライン計算で 128 bit と異なる．今のところ，設計者が主張する偽造不可能性を破る攻撃は存在しないが，安全性証明と著者の主張に差があることに注意が必要である．また，Xoodoo[12] の構造を含めて考えると，Xoodoo[12] 単体での安全性は無いため，Duplex 構造の安全性
は Xoodyak の安全性に適用できない．Xoodoo[12] の構造を含めた Xoodyakの認証暗号に対する攻撃は，ラウンド数を 6 ラウンドに削減した Xoodyak の認証暗号に対する Conditional Cube 攻撃 [24] が最適であり，Xoodoo[12] の
ラウンド数は 12 ラウンドと十分にマージンがあるため，Xoodyak の認証暗号は設計者が主張する安全性を持つと考えられる．

目次
1

本報告書の構成

5

2

準備

5

2.1

記号の定義

2.2

プリミティブの定義

2.3

2.4

3

3.2

6

2.2.1

置換に関する定義 . . . . . . . . . . . . . . . . . . . . .

6

2.2.2

ブロック暗号に関する定義 . . . . . . . . . . . . . . . .

6

認証暗号に関する定義 . . . . . . . . . . . . . . . . . . . . . .
2.3.1 認証暗号の関数一覧と機能 . . . . . . . . . . . . . . . .

7
7

2.3.2

AE 安全性: 理想的な認証暗号との識別不可能性 . . . .

8

2.3.3

Priv 安全性: 秘匿機能に関する安全性 . . . . . . . . . .

9

2.3.4

Auth 安全性: 改ざん検知機能に関する安全性 . . . . . 10

ハッシュ関数に関する定義 . . . . . . . . . . . . . . . . . . . . 10

2.4.1

Indiﬀerentiability . . . . . . . . . . . . . . . . . . . . . 11

2.4.2

Collision Resistance . . . . . . . . . . . . . . . . . . . 12

2.4.3

Second Preimage Resistance . . . . . . . . . . . . . . . 12

2.4.4

Preimage Resistance . . . . . . . . . . . . . . . . . . . 12

2.4.5

m-Target Preimage Resistance . . . . . . . . . . . . . 12

4.2

12

COFB の仕様 . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.1.1

記号，パラメータの定義 . . . . . . . . . . . . . . . . . 13

3.1.2

ガロア体の定義 . . . . . . . . . . . . . . . . . . . . . . 13

3.1.3

COFB で用いられる関数 . . . . . . . . . . . . . . . . . 13

3.1.4
3.1.5

COFB の暗号化関数 COFB.E . . . . . . . . . . . . . . 14
COFB の復号 COFB.D . . . . . . . . . . . . . . . . . . 15

GIFT-128 の仕様 . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2.1

鍵スケジュールの仕様 . . . . . . . . . . . . . . . . . . 17

3.2.2

ラウンド関数の仕様 . . . . . . . . . . . . . . . . . . . 19

GIFT-COFB の安全性に関する文献調査の結果
4.1

5. . . . . . . . . . . . . . . . . . . . . . .

GIFT-COFB のアルゴリズム仕様
3.1

4. . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

GIFT-128 の安全性評価に関する文献調査結果 . . . . . . . . . 21
4.1.1

GIFT-128 に対する差分攻撃 . . . . . . . . . . . . . . . 21

4.1.2

GIFT-128 に対する線形攻撃 . . . . . . . . . . . . . . . 21

4.1.3

GIFT-128 に対する Integral 攻撃 . . . . . . . . . . . . 21

GIFT-COFB の安全性評価に関する文献調査結果 . . . . . . . 21
4.2.1

文献 [2] の COFB の安全性 . . . . . . . . . . . . . . . . 22

4.2.2

設計者が主張する GIFT-COFB の安全性について . . . 22

4.2.3

文献 [9] の COFB の安全性バウンドの誤りについて . . 22

4.2.4
5

Xoodyak のアルゴリズム仕様
5.1

5.2

24

利用モードの仕様 . . . . . . . . . . . . . . . . . . . . . . . . . 24

5.1.1

記号，パラメータの定義 . . . . . . . . . . . . . . . . . 24

5.1.2

Xoodyak のハッシュ関数利用モード . . . . . . . . . . 24

Xoodyak の認証暗号利用モードの仕様 . . . . . . . . . . . . . 25
5.2.1

Xoodyak の認証暗号利用モードの暗号化関数 Xoodyak.E 26

5.2.2

Xoodyak の認証暗号利用モードの復号関数 Xoodyak.D 28

5.3

Xoodoo[12] の仕様 . . . . . . . . . . . . . . . . . . . . . . . . 29

5.4

Xoodoo[12] で用いられる演算 . . . . . . . . . . . . . . . . . . 29

5.3.1
5.4.1
6

文献 [3] の COFB の安全性バウンドの誤りについて . . 23

ステートの状態 . . . . . . . . . . . . . . . . . . . . . . 29

Xoodoo[12] の入出力と手続き . . . . . . . . . . . . . . 29

Xoodyak の安全性に関する文献調査の結果

31

6.1

Xoodoo[12] の安全性 . . . . . . . . . . . . . . . . . . . . . . . 32

6.2

Xoodyak のハッシュ関数の安全性 . . . . . . . . . . . . . . . . 32

6.3

6.2.1

Xoodoo[12] がブラックボックスの場合の安全性 . . . . 32

6.2.2

Xoodoo[12] の構造を入れる場合の安全性 . . . . . . . . 33

Xoodyak の認証暗号の安全性 . . . . . . . . . . . . . . . . . . 33
6.3.1 設計者が主張する Xoodoo[12] がブラックボックスの場
合の安全性 . . . . . . . . . . . . . . . . . . . . . . . . 33

6.3.2

Xoodoo[12] がブラックボックスの場合の安全性に関する考察 . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

6.3.3
7

結論

Xoodoo[12] の構造を入れる場合の安全性について . . . 3535

本報告書の構成

1

本報告書の構成は以下の通りである．

• 2 章で記号の定義，プリミティブの定義，認証暗号に関する定義，ハッシュ関数に関する定義を説明する．

• 3 章で GIFT-COFB の仕様を記載する．
• 4 章で GIFT-COFB の安全性に関する文献調査の結果を報告する．
• 5 章で Xoodyak の仕様を記載する．
• 6 章で Xoodyak の安全性に関する文献調査の結果を報告する．
• 7 章で結論を述べる．

準備2

本章では，記号の定義，GIFT-COFB と Xoodyak に必要なプリミティブの定義，認証暗号とハッシュ関数の定義を記載する．

2.1

記号の定義

本評価報告書では以下の記号を用いる．

• ε: 空列．
• ∅: 空集合．
• [i, j]:i ≤ j となる整数 i, j に対し，i 以上 j 以下の整数の集合．[i, j] ={i, i + 1, . . . , j} である．
• (j] := [0, j]，[j] := [1, j]．
• 0i : 全てのビットが 0 の i bit の値．
• 1i : 全てのビットが 1 の i bit の値．
• {0, 1}i : 全ての i bit の値の集合．i は非負の整数，{0, 1}0 := {ε} とする．

• {0, 1}∗ : 全てのビット列の集合．{0, 1}∗ = ∪i∈{0,1,2,...} {0, 1}i である．
• {0, 1}≤i : ビット長が i 以下の全ての値の集合．i は非負の整数とする．
• X ← Y : X に値 Y を代入する．

$

• T ←
− T : 集合 T から値をランダムに選んで，その値を T に代入する．
• |X|： i bit の値 X のビット長．|X| = i である．
• X ⊕ Y : |X| = |Y | の値 X と Y の XOR 演算の結果の値．
• X∥Y : 2 つのビット列 X と Y をビット結合した値．

2.2

プリミティブの定義

認証暗号は，ブロック暗号や置換など入出力長が固定のプリミティブをベースに設計される．Xoodyak のハッシュ関数と認証暗号は置換を用いて設計されており，GIFT-COFB の認証暗号はブロック暗号を用いて設計されている．
ここでは，置換の定義，Xoodyak の利用モードの安全性に必要なランダム置
換の定義，ブロック暗号の定義，そして GIFT-COFB の利用モードで用いる
ブロック暗号に対する安全性仮定である PseudoRandom Permutation(PRP)
安全性の定義を説明する．

2.2.1

置換に関する定義

置換のサイズを b bit とする．置換 f : {0, 1}b → {0, 1}b は，{0, 1}b から{0, 1}b への全単射関数である．
Xoodyak のモードの安全性を証明する際に，置換 f をランダム置換に置き換える．ランダム置換は，b bit の全ての置換の集合からランダムに 1 つ選んだものである．

2.2.2

ブロック暗号に関する定義

ブロック暗号の鍵サイズを k bit，ブロックサイズを n bit とする．ブロッ
ク暗号 E : {0, 1}k × {0, 1}n → {0, 1}n は，鍵成分を固定すると n bit の置換となり，別の鍵成分を用いると別の n bit の置換となる，2k 個の n bit の置換を持つ関数である．鍵 K ∈ {0, 1}k を用いるブロック暗号を EK と書くことにする．

GIFT-COFB のモードの安全性を保証する際に，ブロック暗号 EK を PRP安全と仮定する．ここでは，EK の PRP 安全性の定義を示す．PRP 安全性
は，EK とランダム関数 π の識別不可能性を考える．具体的には，攻撃者 A に対する以下のアドバンテージ関数が無視できるくらい小さいと仮定する．ここで，攻撃者 A はクエリー後 1 bit の値を出力する．そして，AO をオラクル

O にアクセスする攻撃者 A の出力とする．
][ EK= 1 − Pr [Aπ = 1] .
Advprp
E (A) := Pr A

2.3

認証暗号に関する定義

認証暗号の関数一覧と機能を説明し，認証暗号の安全性である，AE 安全性，Priv 安全性，Auth 安全性を定義する．

2.3.1

認証暗号の関数一覧と機能

認証暗号は，データの秘匿機能と改ざん検知機能を持つ共通鍵暗号アルゴ
リズムである．認証暗号は，暗号化関数と復号関数を備える．認証暗号 Π の暗号化関数を Π.E ，復号関数を Π.D とするする．
認証暗号の暗号化関数 Π.E の入力は以下の 4 つである．

• 秘密鍵 K: 暗号化関数と復号関数で用いる秘密のデータ．
• ナンス N : 鍵が変わるまで暗号化関数の呼び出し毎に値が異なるデー
タで，改ざん検知対象となるデータ．

• Associated Data A: 秘匿はしないが改ざん検知対象となるデータ．
• 平文 M : 秘匿と改ざん検知対象となるデータ．
この入力に対し，Π.E の出力は以下の 2 つである．

• 暗号文 C: 平文 M の暗号化データ．
• タグ T : N ，C ，T の改ざんをチェックするためのデータ．
ここで，鍵 K を用いる認証暗号の暗号化関数 Π.E を Π.EK ，入力 (K, N, A, M )の出力を Π.EK (N, A, M ) と書くことにする．Π.EK (N, A, M ) = (C, T ) である．
認証暗号の復号関数 Π.D の入力は以下の 4 つである．

• 秘密鍵 K ．
• ナンス N : 暗号化関数とは異なり，鍵を変更する前でも同じ値としてよく，改ざん検知対象となるデータ．

• Associated Data A: 秘匿はしないが，改ざん検知対象となるデータ．
• 暗号文 C: 平文の暗号化データで，改ざん検知対象となるデータ．
• タグ T ′ : N ，C ，T ′ の改ざん検知を行うためのデータ．
この入力に対し，Π.D の出力は以下の 2 つである．

• 改ざんされていないことが確認できた場合，平文 M ．
• 改ざんされていることが確認できた場合，改ざんがあったことを表す記号 reject．

ここで，鍵 K を用いる認証暗号の復号関数 Π.D を Π.DK ，入力 (K, N, A, C, T ′ )に対する出力を Π.DK (N, A, C, T ′ ) と書くことにする．改ざんされていない
ことが確認できた場合，Π.EK (N, A, C, T ′ ) = M ，改ざんされていることが確認できた場合，Π.EK (N, A, C, T ′ ) = reject である．
そして，認証暗号の暗号化関数 Π.E と復号関数 Π.D は，次の性質を持つ関数とする．

• Π.E の入力値の空間の任意の鍵 K ，ナンス N ，Associated Data A，暗号文 M に対し，M = Π.DK (Π.EK (N, A, M )) が成り立つ．
また，認証暗号の暗号化関数の入力のナンス N と，復号関数で計算される
平文 M に関する条件を以下に記載する．

• 認証暗号の暗号化関数の入力のナンス N は，鍵を変えない限り同じ値を使わないことが必要である．この条件をナンスリスペクトと呼ぶ．

• 多くの認証暗号では，復号関数の計算で，改ざん検知のチェックを行う
前に入力の暗号文を復号する．この，改ざん検知のチェック前の平文をUnveriﬁed Plaintext と呼ぶ．復号関数は改ざんされていないことが確認できない限り，Unveriﬁed Plaintext は出力しないことが必要である．

AE 安全性: 理想的な認証暗号との識別不可能性

2.3.2

認証暗号の安全性である AE 安全性は，理想的な認証暗号との識別不可能性で，文献 [18] で定義されている．以下，認証暗号 Π のシングルユーザでのAE 安全性を定義する．
理想的な認証暗号は，理想的な暗号化オラクルである $ と理想的な復号オラクルである ⊥ から構成される．これらのオラクルの説明は以下のとおりである．

• $ は，Π.EK と同じインターフェースを持ち，クエリー (N, A, M ) に対して，ビット長が |Π.EK (N, A, M )| の乱数を返す．

• ⊥ は，Π.DK と同じインターフェースを持ち，クエリー (N, A, C, T ′ ) に対して，常に reject を返す．
次に，認証暗号 Π の AE 安全性を破る攻撃者 A を説明する．攻撃者 A は，

Real World と Ideal World で以下のオラクルにアクセスする．ここで，P は認証暗号で用いるプリミティブを理想化したものであり，認証暗号のプリミ
ティブを理想化したモデルで出現する．例えば，Xoodyak のモードは，置換を理想化したランダム置換で安全性証明が行われており，その時の P はラン
ダム置換である．一方で，COFB などスタンダードモデルで安全性証明を行う場合，P は無視する．

• Real World でのオラクルの組は，(Π.EK , Π.DK , P ) である．鍵 K は鍵空間からランダムに選ぶ．

• Ideal World でのオラクルの組は，($, ⊥, P ) である．
そして，攻撃者 A は，全てのクエリーに対するレスポンスを受け取った後，

1 bit の値を出力する．ここで，攻撃者 A は，Trivial なクエリーでなければ，自由に選択できる．Trivial なクエリーは，確率 1 で攻撃に成立するクエリーのことである．具体的には，暗号化関数 Π.EK のレスポンスをそのまま復号
関数 Π.EK へのクエリーとするものを指す．また，ナンスリスペクトの状況を考える場合，Π.EK /$ へのクエリーのナンスは全て異なる値である．
次に，AE 安全性の攻撃者 A のアドバンテージ関数を定義する．オラクルの組 (O1 , O2 , O3 ) へアクセスした場合の攻撃者 A の出力値を AO1 ,O2 ,O3 とす
る．AE 安全性の攻撃者 A のアドバンテージ関数の定義は以下の通りである．
[][ Π.EK ,Π.DK ,P
]
$,⊥,P
Advae
(A)
:=
Pr
A
=
1
−
Pr
A
=
1
.
Π
ここで，スタンダードモデルでの安全性を考える場合，P を無視する．

2.3.3

Priv 安全性: 秘匿機能に関する安全性

Priv 安全性は，認証暗号の秘匿機能に関する安全性で，Π.EK と理想的な暗号化オラクルである $ との識別不可能性である．
認証暗号 Π の Priv 安全性を破る攻撃者 A を説明する．攻撃者 A は，RealWorld と Ideal World で以下のオラクルにアクセスする．P は，プリミティ
ブを理想化したもので，プリミティブを理想化したモデルを考える場合，出現し，スタンダードモデルでの安全性を考える場合，無視する．

• Real World でのオラクルの組は，(Π.EK , P ) である．鍵 K は鍵空間からランダムに選ぶ．

• Ideal World でのオラクルの組は，($, P ) である．
そして，攻撃者 A は，全てのクエリーに対するレスポンスを受け取った後，1

bit の値を出力する．ここで，ナンスリスペクトの状況を考える場合，Π.EK /$へのクエリーのナンスは全て異なる値とする．
次に，Priv 安全性の攻撃者 A のアドバンテージ関数を定義する．オラクルの組 (O1 , O2 ) へアクセスした場合の攻撃者 A の出力値を AO1 ,O2 とすると，Priv 安全性の攻撃者 A のアドバンテージ関数の定義は以下の通りである．
[][ Π.EK ,P]
Advpriv= 1 − Pr A$,P = 1 .
Π (A) := Pr A
ここで，スタンダードモデルでの安全性を考える場合，P を無視する．

AE 安全性と Priv 安全性の関係について，Priv 安全性は AE 安全性の復号
オラクルを取り除いたものなので，認証暗号 Π が AE 安全であれば，Priv 安
全性も担保される．そして，AE 安全性のアドバンテージ関数のバウンドから復号オラクルへのクエリーを除いたものが Priv 安全性のアドバンテージ関
数のバウンドとなる．

2.3.4

Auth 安全性: 改ざん検知機能に関する安全性

Auth 安全性は，認証暗号の偽造不可能性に関する安全性である．
認証暗号 Π の Auth 安全性を破る攻撃者 A を説明する．攻撃者 A は，以下のオラクルにアクセスする．P は，プリミティブを理想化したもので，プリミティブを理想化したモデルを考える場合，出現し，スタンダードモデルでの安全性を考える場合，無視する．また，鍵 K は鍵空間からランダムに選ぶ．

• Π の暗号化関数 Π.EK ，復号関数数 Π.DK ，理想化したプリミティブ P ．
攻撃者のゴールは，Π.DK に，平文 (reject ではない値) がレスポンスとして返ってくる値をクエリーすることである．A は，各クエリーの値を，Trivial
なクエリーでなければ，自由に選択できる．Trivial なクエリーは，確率 1 で攻撃に成立するクエリーのことで，暗号化関数 Π.EK のレスポンスをそのま
ま復号関数 Π.DK へのクエリーとするもを指す．また，ナンスリスペクトの状況を考える場合，各クエリーのナンスは全て異なる値である．
次に，Auth 安全性の攻撃者 A のアドバンテージ関数を定義する．攻撃者

A から Π.DK へのあるクエリーに対するレスポンスが平文となるイベントを“AΠ.EK ,Π.DK ,P forges” と書くことにする．この時，Auth 安全性の攻撃者 Aのアドバンテージ関数の定義は以下の通りである．

[ Π.EK ,Π.DK ,P]forges .
AdvauthΠ (A) := Pr A
ここで，スタンダードモデルでの証明の場合，P を無視する．

AE 安全性と Auth 安全性の関係について，認証暗号 Π の Auth 安全性を破る攻撃者が存在すれば，AE 安全性を破る攻撃者を構成できるため，認証
暗号 Π が AE 安全であれば，Auth 安全性も担保される．そして，AE 安全性のアドバンテージ関数のバウンドが Auth 安全性のアドバンテージ関数のバ
ウンドとなる．

2.4

ハッシュ関数に関する定義

ハッシュ関数は，任意長のデータを固定長のデータに変換する鍵なしの関数で，改ざん検知アルゴリズム，公開鍵暗号，デジタル署名など多くの暗号
アルゴリズムの部品として用いられている．これらの暗号アルゴリズムの安全性を担保するためには，ハッシュ関数が，Indiﬀerentiability，Collision

Resistance，Second Preimage Resistance，Preimage Resistance，m-Target
Preimage Resistance などの安全性を持つ必要がある．以下，これらの安全性を定義する．
ここで，ハッシュ関数のプリミティブを P とする．P は，例えば置換などがある．プリミティブ P を用いる，出力長 ℓ bit のハッシュ関数を H P :{0, 1}∗ → {0, 1}ℓ とする．

2.4.1

Indiﬀerentiability

Indiﬀerentiability は，文献 [17] で定義された，ハッシュ関数と理想的なハッシュ関数であるランダムオラクル F : {0, 1}∗ → {0, 1}ℓ との識別不可能性である．Indiﬀerentiability では，プリミティブ P を理想化する．P が置換の場
合，ランダム置換を用いる．そして，ハッシュ関数 H P が Indiﬀerentiabilityの意味で安全ならば，文献 [20] で示された通りシングルステージの安全性ゲー
ムに限定するが，ハッシュ関数 H P をランダムオラクルとして用いることができる．すなわち，ランダムオラクルモデルで安全な暗号アルゴリズムに，Indiﬀerentiability 安全なハッシュ関数を用いてもその安全性は担保される．また，Indiﬀerentiability 安全なハッシュ関数は，Indiﬀerentiability，Collision

Resistance，Second Preimage Resistance，Preimage Resistance，m-Target
Preimage Resistance に関して，安全である．
まず，Indiﬀerentiability の攻撃者 A を説明する．攻撃者 A は，Real Worldと Ideal World で以下のオラクルにアクセスする．

• Real World でのオラクルの組は，(H P , P ) である．
• Ideal World でのオラクルの組は，(F, S) である．S は F にアクセス可
能なシミュレータであり，プリミティブ P と同じインターフェースを持つ．
攻撃者 A は，オラクルへのクエリーに対するレスポンスを全て受け取った後，

1 bit の値を出力する．
次に，Indiﬀerentiability の攻撃者 A のアドバンテージ関数を定義する．オラクルの組 (O1 , O2 ) にアクセスする攻撃者 A の出力を AO1 ,O2 とすると，ア
ドバンテージ関数は以下の通りである．
[ P
]
[
]
H ,P
= 1 − Pr AF ,S = 1 .
Advindiﬀ
H P (A) := Pr A
そして，任意の攻撃者に対し，上記のアドバンテージ関数が無視できるくらい小さい確率となるシミュレータ S が存在する場合，そのハッシュ関数 H P
を Indiﬀerentiability 安全とする．すなわち，ハッシュ関数 H P の Indiﬀeren-

tiability 安全性を証明する場合，シミュレータ S を定義し，そのシミュレータ
に対してアドバンテージ関数のバウンドが無視できる確率となることを示す．

2.4.2Collision Resistance

ハッシュ関数が Collision Resistance の意味で安全とは，H P (M ) = H P (M ′ )となる異なる 2 つの入力メッセージ M, M ′ を見つけることが困難，具体的にはこの確率が無視できるくらい小さいことである．より詳しい定義は文献[21] を参照されたい．

2.4.3

Second Preimage Resistance

ハッシュ関数が Second Preimage Resistance の意味で安全とは，入力メッ
セージ M が与えられた時に，H P (M ) = H P (M ′ ) となる M とは異なる入力
メッセージ M ′ を見つけることが困難，具体的にはこの確率が無視できるくらい小さいことである．より詳しい定義は文献 [21] を参照されたい．

2.4.4

Preimage Resistance

ハッシュ関数が Preimage Resistance の意味で安全とは，入力メッセージ

M のハッシュ値 H P (M ) が与えられた時に，H P (M ) = H P (M ′ ) となる入力
メッセージ M ′ を見つけることが困難，具体的にはこの確率が無視できるくらい小さいことである．より詳しい定義は文献 [21] を参照されたい．

2.4.5

m-Target Preimage Resistance

ハッシュ関数が Preimage Resistance の意味で安全とは，m 個の入力メッ
セージ M1 , . . . , Mm のハッシュ値 H P (M1 ), . . . , H P (Mm ) が与えられた時に，ある i ∈ [m] に関して，H P (Mi ) = H P (M ′ ) となる入力メッセージ M ′ を見つけることが困難，具体的にはこの確率が無視できるくらい小さいことである．

GIFT-COFB のアルゴリズム仕様

3

本章で，GIFT-COFB のアルゴリズムの仕様を記載する．GIFT-COFB は，
ブロック暗号ベースの認証暗号利用モード COFB とブロック暗号 GIFT-128
を組み合わせた方式である．以下，COFB の仕様を記載し，最後に GIFT-128の仕様を記載する．詳細な仕様は文献 [2, 3] を参照されたい．

3.1

COFB の仕様

ブロック暗号ベースの認証暗号利用モード COFB の仕様を記載する．まず，COFB 記号とパラメータを定義する．次に，COFB で用いられるガロア

体，COFB で用いられる関数の仕様を記載する．最後に，COFB の暗号化関
数 COFB.E と復号関数 COFB.D の仕様を記載する．

3.1.1

記号，パラメータの定義

COFB が用いるブロック暗号の記号は 2.2.2 章に記載のものを用いる．GIFT-128
は，k = 128，n = 128 である．COFB の鍵を K とする．COFB の鍵は，COFB
で用いられるブロック暗号の鍵である．K のビット長は k bit である．

3.1.2

ガロア体の定義

COFB は GF (2n/2 ) 上のかけ算と加算を用いる．COFB では，GF (2n/2 ) 上のかけ算または加算を行う際に，n/2 bit の値を GF (2n/2 ) 上の値に変換し演算を行う．そして，演算後，演算結果を n/2 bit の値に変換する．a0 , a1 , · · · , an/2−1 ∈{0, 1} に対して，n/2 bit の値 an/2−1 . . . a0 に対して GF (2n/2 ) 上の演算を行う場合，GF (2n/2 ) 上の値 (多項式)an/2−1 xn−1 + · · · + a1 x + a0 に変換する．

GF (2n/2 ) 上の値から n/2 bit の値に変換する際は，この逆の変換を行う．
GF (2n/2 ) 上のかけ算を行う際は，α を生成元とする原始多項式 p(x) を 1
つ固定し，かけ算を行う．α をビット表現すると 10 となる．GIFT-COFB では，以下の 64 次の原始多項式が用いられる．

p(x) = x64 + x4 + x3 + x + 1
COFB では生成元 α (= 10) と 11 のかけ算が用いられる．以下，10 を整数
2 で表現し，11 を整数 3 で表現する．
GF (2n/2 ) 上の値 X に，2 を i 回掛ける場合 2i X ，3 を i 回掛ける場合 3i Xと書くことにする．

3.1.3

COFB で用いられる関数

COFB で用いられる 3 つの関数 Trunc, Pad, G の仕様を以下に示す．
• Trunci は，n bit の値 X を入力とし，X の最初の i bit を出力する関数である．i ≤ n であり，この i bit の値を Trunci (X) と書くことにする．
また，i は自然数であり，i ≤ n である．

• Pad は，n bit 以下の値 X を入力とし，|X| = n の場合 X を出力し，|X| < n の場合 X∥10n−|X|−1 を出力する関数である．この出力値をPad(X) とする．

• G は，n bit の値 Y を入力とし，Y を上位 n/2 bit Y [1]，下位 n/2 bit
Y [2] に分割し，Y [2]∥(Y [1] ≪ 1) を出力する関数である．この出力値をG(Y ) と書くことにする．Y = Y [1]∥Y [2] であり，(Y [1] ≪ 1) は Y [1]を左に 1 bit 巡回シフトした値である．

3.1.4

COFB の暗号化関数 COFB.E

COFB の暗号化関数 COFB.E の入出力は以下の通りである．t はタグ長で，n 以下の自然数である．
入力• 鍵 K ∈ {0, 1}k• ナンス N ∈ {0, 1}n• Associated Data A ∈ {0, 1}∗• 平文 M ∈ {0, 1}∗
出力• 暗号文 C ∈ {0, 1}|M |• タグ T ∈ {0, 1}t
COFB の暗号化関数 COFB.E の手続きは以下の通りである．
1. Associated Data A を n bit のデータブロック A[1], A[2], . . . , A[a] に分割する．ここで，|A[1]| = · · · = |A[a − 1]| = n，|A[a]| ≤ n であり，

A = A[1]∥A[2]∥ · · · ∥A[a] である．
2. 図 1(1) を実行する．ここでは，ナンス N と Associated Data ブロックA[1], A[2], . . . , A[a] を処理し，L ∈ {0, 1}n/2 と Y [a] ∈ {0, 1}n を生成する．

3. 平文 M を n bit のデータブロック M [1], M [2], . . . , M [m] に分割する．
ここで，|M [1]| = · · · = |M [m − 1]| = n，|M [m]| ≤ n であり，M =M [1]∥M [2]∥ · · · ∥M [m] である．
4. m ≥ 2 の場合，図 1(2) を実行する．ここでは，平文ブロック M [1], · · · , M [m−1] ∈ {0, 1}n を暗号化し，暗号文ブロック C[1], · · · , C[m − 1] ∈ {0, 1}nと Y [a + m − 1] ∈ {0, 1}n を生成する．

5. M ̸= ε の場合，図 1(3) を実行する．ここでは，平文ブロック M [m] ∈{0, 1}≤n を暗号化し，暗号文ブロック C[m] ∈ {0, 1}|M [m]| とタグ T ∈{0, 1}t を生成し，C = C[1]∥ · · · ∥C[m] とする．

6. M = ε の場合，図 1(4) を実行し，タグ T ∈ {0, 1}t を生成する．C = ε
とする．

3.1.5

COFB の復号 COFB.D

COFB の復号関数 COFB.D の入出力は以下の通りである．t はタグ長で，n 以下の自然数である．
入力• 鍵 K ∈ {0, 1}k• Associated Data A ∈ {0, 1}∗• 暗号文 C ∈ {0, 1}|M |• タグ T ′ ∈ {0, 1}t
出力• 暗号文 M ∈ {0, 1}|C| ，または，タグの改ざんを示す記号 ⊥̸∈ {0, 1}|C|
COFB の復号関数 COFB.D の手続きは以下のとおりである．ここで，COFB.Dの出力値を COFB.DK (N, A, C, T ′ ) とする．

1. Associated Data A を n bit のデータブロック A[1], A[2], . . . , A[a] に分割する．ここで，|A[1]| = · · · = |A[a − 1]| = n，|A[a]| ≤ n であり，

A = A[1]∥A[2]∥ · · · ∥A[a] である．
2. 図 2(1) を実行する．ここでは，ナンス N と Associated Data ブロックA[1], A[2], . . . , A[a] を処理し，L ∈ {0, 1}n/2 と Y [a] ∈ {0, 1}n を生成する．

3. 暗号文 C を n bit のデータブロック C[1], M [2], . . . , C[c] に分割する．
ここで，|C[1]| = · · · = |C[c − 1]| = n，|C[c]| ≤ n であり，C =C[1]∥C[2]∥ · · · ∥C[c] である．
4. c ≥ 2 の場合，図 2(2) を実行する．ここでは，暗号文ブロック C[1], · · · , C[c−1] ∈ {0, 1}n を復号し，平文ブロック M [1], · · · , M [c − 1] ∈ {0, 1}n とY [a + c − 1] ∈ {0, 1}n を生成する．
5. C ̸= ε の場合，図 2(3) を実行する．ここでは，暗号文ブロック C[c] ∈{0, 1}≤n を復号し，平文ブロック M [c] ∈ {0, 1}|M [c]| とタグ T ∈ {0, 1}tを生成し，M = M [1]∥ · · · ∥M [c] とする．

図 1: COFB の暗号化関数 COFB.E の手続き

EK

G
⊕

⊕

C[1]

⊕

G

M[1]

⊕
⊕

EK

⊕

C[m]

Trunc|M[m]|Y[a+m-1]
G

⊕

Pad

⊕

M[m]

EK

G

M[2]

⊕

⊕

EK

T

⊕

EK

2a+13iL||0n/2⊕

TrunctG

A[2] 22L||0n/2

if |M| mod n = 0 ∧ M ≠ ε then j = i+1
else j = i+2⊕

2a+m-23jL||0n/2(3) M[m]の暗号化、タグ生成

Y[a]2a3iL||0n/2

EK

C[2]

A[1] 2L||0n/2(2) M[1],...,M[m-1]の暗号化

N

Truncn/2(1) AD処理 L

G

⊕

⊕

M[m-1]

⊕

G
⊕

Y[a]

⊕

EK

2a-13iL||0n/2
Y[a]

EK

Y[a+m-1]

if |A| mod n = 0 ∧ A ≠ ε then i = 1
else i = 2

EK

2a+m-23iL||0n/2

⊕

Pad

A[a]

TrunctT(4) M = ε の場合のタグ生成

C[m-1]⊕

G

A[a-1] 2a-1L||0n/2

6. C = ε の場合，図 2(4) を実行し，タグ T ∈ {0, 1}t を生成し，M = εとする．

7. T = T ′ の場合，COFB.DK (N, A, C, T ′ ) = M とする．
8. T ̸= T ′ の場合，COFB.DK (N, A, C, T ′ ) = reject とする．

3.2

GIFT-128 の仕様

GIFT-128 の仕様を記載する．GIFT-COFB は GIFT-128 の暗号化関数のみ用いるため，ここでは，暗号化関数の仕様を記載する．

GIFT-128 は，鍵サイズとブロックサイズがともに 128 bit のブロック暗号
であり，ラウンド関数を 40 回繰り返す構造を持つ．128 bit の平文ブロックを

128 bit のステート S の初期値とし，40 回ラウンド関数を繰り返しステート S
をアップデートする．40 ラウンド後の S の値が GIFT-128 の出力の暗号文ブ
ロックとなる．各ラウンド関数では，鍵から GIFT-128 の鍵スケジュールで生成されたラウンド鍵が用いられる．以下に，ラウンド関数と鍵スケジュー
ルの仕様を示す．

3.2.1

鍵スケジュールの仕様

初期化

まず，鍵ステート KS の初期値を記載する．鍵の先頭から i bit 目の値を bi−1 とする．すなわち，b0 ∥b1 ∥ · · · ∥b127 は鍵である．そして，鍵ステー
トの初期値は以下のように決まる．W0 , W1 , . . . , W7 の各ワードは 16 bit の値
である．

W0

W2
KS = 
W
 4
W6

∥
∥
∥
∥

W1





b127




W3 
 ←  b95

b
W5 
 63
W7
b31

鍵スケジュールの手続き

···

b112

∥

b111

···

b98

b97

···

b80

∥

b79

···

b66

b65

···

b48

∥

b47

···

b34

b33

···

b16

∥

b15

···

b2

b1

b96




b64 

b32 

b0

鍵スケジュールでは，各ラウンドの 64bit のラウ

ンド鍵 RK を鍵ステート KS から生成したのち，鍵ステートをアップデート
する．
まず，ラウンド鍵の生成法を以下に示す．

U ← W2 ∥W3 , V ← W6 ∥W7 , RK ← U ∥V
次に，鍵ステートのアップデート方法を以下に示す．
W6 ≫ 2 ∥ W17 ≫ 12
W0 ∥ W1
 W2 ∥ W3 ∥W1 ←  W0
 W
W ∥ W 
∥
W3
2
5


 4
W4
∥
W5
W6 ∥ W7図 2: COFB の暗号化関数 COFB.D の手続き

EK

Y[0]

G
⊕

C[1]

⊕

G

M[1]

⊕
⊕

C[2]

⊕

⊕

EK

⊕

EK

M[2]

T

⊕

EK

2a+13iL||0n/2⊕⊕

TrunctGG

A[2] 22L||0n/2

if |C| mod n = 0 ∧ C ≠ ε then j = i+1
else j = i+2

M[m]

C[c]

Pad

⊕

⊕

G

Trunc|C[c]|Y[a+c-1]

EK

EK

2a+c-23jL||0n/2(3) C[c]の復号、タグ生成

Y[a]2a3iL||0n/2⊕

A[1] 2L||0n/2(2) C[1],...,C[c-1]の復号

X[0]

N

Truncn/2(1) AD処理 L

G⊕

M[c-1]⊕G

Y[a]Trunct

⊕

Pad

A[a]
⊕

EK

2a-13iL||0n/2
Y[a]

⊕

EK

T

Y[a+c-1]

if |A| mod n = 0 ∧ A ≠ ε then i = 1
else i = 2

EK

2a+c-23iL||0n/2⊕(4) C = ε の場合のタグ生成

C[c-1]⊕

G

A[a-1] 2a-1L||0n/2ここで，1 ワード W に対し，W ≫ i は W を ibit 右巡回シフトした値である．r ラウンドで用いられるラウンド鍵 RK は，上記のアップデートを r − 1
回繰り返した後の鍵ステート KS から生成された値である．

3.2.2

ラウンド関数の仕様

初期化

ステート S の初期値を記載する．平文ブロックの先頭から i bit 目の値を bi−1 とする．すなわち，b0 ∥b1 ∥ · · · ∥b127 は平文ブロックである．そして，ステートの初期値は以下のように定義される．S0 , S1 , S2 , S3 の各ワード
は 32bit の値である．



S0





b124

 

 S1  ← b125
S=
S 
b
 2
 126
S3
b127
ラウンド関数の手続き

···

b8

b4

···

b9

b5

···

b10

b6

···

b11

b7

b0




b1 

b2 

b3

ラウンド関数は SubCells，PermBits，AddRoundKeyの 3 ステップから構成される．SubCells，PermBits，AddRoundKey の順番で実行し，ステート S をアップデートする．

SubCells の手続きは以下のとおりである．各処理は 32bit ワード単位で行われている．

S1 ← S1 ⊕ (S0 &S2 )S0 ← S0 ⊕ (S1 &S3 )S2 ← S2 ⊕ (S0 | S1 )S3 ← S3 ⊕ S2
S1 ← S1 ⊕ S3
S3 ←∼ S3S2 ← S2 ⊕ (S0 &S1 ){S0 , S1 , S2 , S3 } ← {S3 , S1 , S2 , S0 }ここで，& は AND 演算，| は OR 演算，∼ は NOT 演算である．

PermBits の手続きは，S0 , S1 , S2 , S3 の各ワードに対し，表 1 に記載のビット置換を行う．表 1 の Index の列は各ワード Si のビット位置を示しており，

S1 , S2 , S3 , S4 の各列は，Index の列に記載のビット位置を移動した先のビッ
ト位置を示している．例えば，S0 の 31bit 目の値は，PermBits 適用後 S0 の29bit 目となる．なお，各ワードの先頭のビット位置を 0，最後のビット位置は 31 である．

AddRoundKey の手続きは以下の通りである．

Index31

表 1: PermBits のビット置換表
30 29 28 27 26 25 24

23

22

21

S0

29

25

21

17

13

9

5

1

30

26

22

S1

30

26

22

18

14

10

6

2

31

27

23

S2

31

27

23

19

15

11

7

3

28

24

20

S2

28

24

20

16

12

8

4

0

29

25

21

Index

20

19

18

17

16

15

14

13

12

11

10

S0

18

14

10

6

2

31

27

23

19

15

11

S1

19

15

11

7

3

28

24

20

16

12

8

S2

16

12

8

4

0

29

25

21

17

13

9

S2

17

13

9

5

1

30

26

22

18

14

10

Index

9

8

7

6

5

4

3

2

1

0

S0

7

3

28

24

20

16

12

8

4

0

S1

4

0

29

25

21

17

13

9

5

1

S2

5

1

30

26

22

18

14

10

6

2

S2

6

2

31

27

23

19

15

11

7

3

• まず，ラウンド鍵 RK を 2 つの 32bit の値 U と V に分ける．RK = U ∥Vである．
• 次に，以下のように S1 , S2 , S3 をアップデートする．
S1 ← S1 ⊕ V
S2 ← S2 ⊕ U
S3 ← S3 ⊕ 0x800000XY
ここで，XY は 8bit の値 00c5 c4 c3 c2 c1 c0 であり，6bit の値 c5 c4 c3 c2 c1 c0は以下の 6-bit LFSR で更新される．

c5 ∥c4 ∥c3 ∥c2 ∥c1 ∥c0 ← c4 ∥c3 ∥c2 ∥c1 ∥c0 ∥(c5 ⊕ c4 ⊕ 1)
各ビット ci の初期値は 0 であり，r ラウンド目 c5 ∥c4 ∥c3 ∥c2 ∥c1 ∥c0 は，
上記の LFSR を r 回適用した値である．

4

GIFT-COFB の安全性に関する文献調査の結果
GIFT-COFB の安全性は，GIFT-COFB の利用モードである COFB の安全性評価と，プリミティブ GIFT-128 の安全性評価をそれぞれ行い，2 つの評価

結果を組み合わせることで，示される．COFB の安全性評価では，ブロック暗号を PRP 安全と仮定し，COFB が AE 安全性を評価する．GIFT-128 の安全性評価では，GIFT-128 が PRP 安全となることを評価する．以下，GIFT-128と GIFT-COFB(すなわち，COFB) の安全性に関する文献調の結果を報告
する．

4.1

GIFT-128 の安全性評価に関する文献調査結果

GIFT-128 に対する解析論文はいくつか発表されている．調査時点で，攻撃可能なラウンド数の最大値は 27 ラウンドで，差分攻撃を用いた鍵復元である．GIFT-128 の PRP 安全性を破る攻撃法はなく，PRP 安全性を満たすと考えられる．以下，差分攻撃，線形攻撃，Integral 攻撃に対する攻撃論文の調査結果を記載する．

GIFT-128 に対する差分攻撃

4.1.1

文献 [25] は，MILP を用いて 20 ラウンドの GIFT-128 に対する確率 2−121.813の Distinguisher を提案した．そして，この Distinguisher を用いて，27 ラウ
ンドの GIFT-128 に対する鍵復元攻撃を行っている．鍵復元に必要な時間，
データ量，メモリーは，それぞれ (2124.83 , 2123.53 , 280 ) である．

GIFT-128 に対する線形攻撃

4.1.2

文献 [22, 23] は，SAT を用いて 19 ラウンドの GIFT-128 に対する確率

2−123.11の Distinguisher を提案した．そして，この Distinguisher を用いて，

25 ラウンドの GIFT-128 に対する鍵復元攻撃を行っている．鍵復元に必要な時間，データ量，メモリーは，(2126.77 , 2124.75 , 296 )，または (2127.77 , 2125.75 , 296 )
である．

4.1.3

GIFT-128 に対する Integral 攻撃

GIFT-128 の設計者により 11 ラウンドの Distinguisher が発見されている
[5]．

4.2

GIFT-COFB の安全性評価に関する文献調査結果

上記の通り，調査時点で，GIFT-128 は PRP 安全であり，GIFT-COFB の安全性は COFB の安全性に依存する．以下，COFB に関する文献調査の結果を報告する．

4.2.1

文献 [2] の COFB の安全性

文献 [2] で，以下の COFB の AE 安全性バウンドが示されている．

Theorem 1 (COFB の AE 安全性). COFB の AE 安全性を破るナンスリス
ペクトの任意の攻撃者 A に対し，以下の不等式を満たす EK に対する PRP
攻撃者 A′ が存在する．ここで，A の動作時間を t とし，クエリー回数を q ，復号関数へのクエリー回数を qf ，全てのクエリーのブロック長の和を σ ，全ての復号関数へのクエリーのブロック長の和を σf ，q ′ = q + qf + σ + σf とする．

(q ′ )

σ + 1 qf (n + 4)
+ n/2+12n/2
2
3σ 2 + qf + 2(q + σ + σf ) · σf
+
.
2n

prp
′
Advae
COFB (A) ≤ AdvE (A ) +

2
2n

+

また，A′ の動作時間は t + O(q ′ ) であり，クエリー数は q ′ である．■
このバウンドはおよそ 2n/2 /n 回のクエリーでコンスタントの値になるた
め，COFB は n/2 − log2 nbit の AE 安全性を持つ．

4.2.2

設計者が主張する GIFT-COFB の安全性について

COFB の秘匿に関する安全性である Priv 安全性について，AE 安全性の定義で qf = 0，σf = 0 とすると，AE 安全性は Priv 安全性の定義そのものになるため，上記の AE 安全性のバウンドから COFB の秘匿に関する安全性である Priv 安全性のバウンドを得ることができる．上記のバウンドから，COFB
がオンラインクエリに関して n/2 bit の Priv 安全性を持つことが言える．そして，GIFT-COFB のパラメータ n = 128，k = 128 を用いると，文献 [2] でGIFT-COFB の設計者が主張する，オンラインクエリに関して 64 bit，オフ
ラインクエリに関して 112 bit 以上の Priv 安全性を持つことが言える．

COFB の改ざん検知に関する安全性である Auth 安全性について，AE 安全性の定義より，COFB の Auth 安全性を破る攻撃者が存在すれば，AE 安全を破る攻撃者が構成できるため，上記の AE 安全性のバウンドは，COFB の Auth
安全性のバウンドとなる．よって，COFB は n/2 − log2 n bit の Auth 安全性を持つことが言える．GIFT-COFB のパラメータである n = 128，k = 128
を用いると，文献 [2] で GIFT-COFB の設計者が主張する，オンラインクエ
リに関して 58 bit，オフラインクエリに関して 112 bit 以上の Priv 安全性を持つことが言える．

4.2.3

文献 [9] の COFB の安全性バウンドの誤りについて

文献 [9] では，AE 安全性について以下のことが主張されている．

Claim 1 (文献 [9] の定理 2). COFB の AE 安全性を破る任意のナンスリス
ペクトの攻撃者 A に対し，以下の不等式成り立つ EK に対する PRP 攻撃者

A′ が存在する．ここで，A の動作時間を t とし，暗号化関数へのクエリー回
数を qe ，復号関数へのクエリー回数を qf ，全ての暗号化関数へのクエリーのブロック長の和を σe ，全ての復号関数へのクエリーのブロック長の和を σf ，q ′ = qe + qf + σe + σf とする．
prp
′
Advae
COFB (A) ≤ AdvE (A )+σe(qe + σe + 2σf ) · σf + qf
0.5(q ′ )2
+ n/2 +.
n22n2

また，A′ の動作時間は t + O(q ′ ) であり，クエリー数は q ′ である．■
しかし，文献 [15] で，文献 [9] が主張する上記のバウンドが間違いであることが示されている．文献 [15] では，qe = 1 で，以下の確率で成功する COFBへの偽造攻撃が示されている．

qd
.
2n/2
この結果は，qe = 1，qd = 2n/2 で，COFB をコンスタントの確率で破ることができることを示しているが，文献 [9] のバウンドはコンスタントにならないため，文献 [15] の偽造攻撃と矛盾する．これは，文献 [9] のバウンドが間違っていることを意味する．

4.2.4

文献 [3] の COFB の安全性バウンドの誤りについて

文献 [3] では，AE 安全性について以下のことが主張されている．

Claim 2 (文献 [3] の COFB の安全性バウンド). ナンスリスペクトの COFBの AE 安全性を破る任意の攻撃者 A に対し，以下の不等式成り立つ EK に対する PRP 攻撃者 A′ が存在する．ここで，A の動作時間を t とし，暗号化関数へのクエリー回数を qe ，復号関数へのクエリー回数を qf ，全ての暗号化関数へのクエリーのブロック長の和を σe ，全ての復号関数へのクエリーのブロッ
ク長の和を σf ，q ′ = qe + qf + σe + σf とする．
(q )1
qf (n + 4)
prp
ae′
AdvCOFB (A) ≤ AdvE (A ) + 2n + n/2 + 2n/2+12
22
3σ + qf + 2(q + σ + σf ) · σf.
+2n
また，A′ の動作時間は t + O(q ′ ) であり，クエリー数は q ′ である．■
しかし，文献 [14] で，文献 [3] が主張する上記のバウンドが間違いである
ことが示されている．文献 [14] では，以下の確率で成功する COFB の AE 安
全性を破る攻撃が示されている．なお，この攻撃では，qf = 0 である．

qe
.
2n/2

例えば，qe = 2n/4 ，qf = 0 の場合，この攻撃成功確率は 1/2n/4 となるが，上記の文献 [3] のバウンドは 1/2n/4 よりも小さいため，この攻撃と矛盾する．
これは，文献 [3] のバウンドが間違っていることを意味する．

Xoodyak のアルゴリズム仕様

5

本章で，Xoodyak のアルゴリズムの仕様を記載する．Xoodyak は，置換ベースのハッシュ関数と，認証暗号を含む鍵付き関数から構成される．本報
告書では，ハッシュ関数と認証暗号の仕様を示す．まず，ハッシュ関数の利用モードの仕様を記載する．次に，認証暗号の利用モードを記載する．最後に，Xoodyak の置換 Xoodoo[12] の仕様を記載する．また，詳細な仕様は文献 [11] を参照されたい．

5.1

利用モードの仕様

Xoodyak がサポートするハッシュ関数利用モードと認証暗号利用モードの仕様を記載する．

5.1.1

記号，パラメータの定義

f を Xoodyak で用いる b bit の置換とする．Xoodyak のハッシュ関数利用モードのブロックサイズを Rhash ，Xoodyak の認証暗号利用モードの 2 つのブロックサイズを Rkin ，Rkout とする．Rkin は，鍵，ナンス，AD を処理する際に使うパラメータで，Rkout は，平文，暗号文，タグを処理する際に使うパラメータである．ℓ をハッシュ関数の出力サイズ，k を鍵サイズ，n をナン
スのサイズ，t をタグサイズとする．ただし，k + n + 16 ≤ Rkin とする．また，各サイズはビット長で，8 の倍数とする．(0xVW) を，1 byte 値 0xVW を

8bit 表現した値とする．V と W は 16 進数の値である．(0x01) = 00000001，(0x03) = 00000011，(0x40) = 01000000，(0x81) = 10000001 である．なお，
Xoodyak では，Rhash = 128，Rkin = 352，Rkout = 192，b = 384，ℓ = 256，k = 128，t = 128，n = 128 である．

5.1.2

Xoodyak のハッシュ関数利用モード

Xoodyak のハッシュ関数利用モードの入出力は以下の通りである．
入力• メッセージ M ∈ {0, 1}∗
出力(1) メッセージの処理
M1||(0x01) M2||(0x01)
0Rhash+80b-Rhash-8

⊕

⊕

⊕

f

Mm-1||(0x01) Mm||0Rhash-|Mm|||(0x01)
⊕

f

⊕

f

S1
S2

0b-Rhash-16||(0x01)(2) ハッシュ値の生成(0x01)||0Rhash
S1
S2

f

Zh

Z1
(0x01)||0Rhash

msbRhash⊕ff

msbRhash⊕

図 3: Xoodyak のハッシュ関数利用モードの手続き• ハッシュ値 Z ∈ {0, 1}ℓXoodyak のハッシュ関数利用モードの手続きは以下の通りである．
1. 入力のメッセージ M を Rhash bit のメッセージブロック M1 , M2 , . . . , Mmに分割する．ここで，|M1 | = · · · = |Mm−1 ]| = Rhash ，|Mm | ≤ Rhash
であり，M = M1 ∥M2 ∥ · · · ∥Mm ，m = ⌈|M |/Rhash ⌉ である．

2. 図 3(1) を実行する．ここでは，メッセージブロック M1 , M2 , . . . , Mmを処理し，S1 ∈ {0, 1}Rhash +8 と S2 ∈ {0, 1}b−Rhash −8 を生成する．

3. 図 3(2) を実行する．ここでは，Rhash bit の出力ブロック Z1 , . . . , Zh を生成する．h = ⌈ℓ/Rhash ⌉ である．

4. ハッシュ値を Z = msbℓ (Z1 ∥ · · · ∥Zh ) とする．

5.2

Xoodyak の認証暗号利用モードの仕様

Xoodyak の認証暗号利用モードは暗号化関数 Xoodyak.E と復号関数 Xoodyak.Dから構成される．以下，これらの関数の仕様を記載する．

5.2.1

Xoodyak の認証暗号利用モードの暗号化関数 Xoodyak.E

Xoodyak の認証暗号利用モードの暗号化関数 Xoodyak.E の入出力は以下の通りである．
入力• 鍵 K ∈ {0, 1}k• ナンス N ∈ {0, 1}n• Associated Data A ∈ {0, 1}∗• 平文 M ∈ {0, 1}∗
出力• 暗号文 C ∈ {0, 1}|M |• タグ T ∈ {0, 1}t
Xoodyak の認証暗号利用モードの暗号化関数の手続きは以下の通りである．
1. 図 4(1) を実行し，鍵 K ，ナンス N から初期値 SK,N を生成する．
2. Associated Data A を Rkin bit のデータブロック A1 , A2 , . . . , Aa に分割する．ここで，|A1 | = · · · = |Aa−1 | = Rkin ，|Aa | ≤ Rkin であり，

A = A1 ∥A2 ∥ · · · ∥Aa ，a = ⌈|A|/Rkin ⌉ である．
3. 図 4(2) を実行する．ここでは，Associated Data ブロック A1 , A2 , . . . , Aa
を処理し，SA,1 と SA,2 を生成する．|SA,1 | = Rkin + 8 と |SA,2 | =b − (Rkin + 8) であり，1 回目の f を計算して以降の 2 本の並列の線のうち，上の線は Rkin + 8 bit，下の線は b − (Rkin + 8) bit である．

4. 平文 M を Rkout bit のデータブロック M1 , M2 , . . . , Mm に分割する．ここで，|M1 | = · · · = |Mm−1 | = Rkout ，|Mm | ≤ Rkout であり，M =M1 ∥M2 ∥ · · · ∥Mm ，m = ⌈|M |/Rkout ⌉ である．
5. 図 4(3) を実行する．ここでは，平文ブロック M1 , · · · , Mm を暗号化し，暗号文ブロック C1 , · · · , Cm と，SM,1 と SM,2 を生成する．各 i ∈ [m]に対し，|Mi | = |Ci |，|SM,1 | = Rkout + 8，|SM,2 | = b − (Rkout + 8) であり，1 回目の f を計算して以降の 2 本の並列の線のうち，上の線はRkout + 8 bit，下の線は b − (Rkout + 8) bit である．
6. 図 4(4) を実行する．ここでは，出力ブロック Z1 , . . . , Zd を生成する．
d = ⌈t/Rkout ⌉ である．2 本の並列の線のうち，上の線は Rkout + 8 bit，
下の線は b − (Rkout + 8) bit である．

7. 暗号文を C = C1 ∥ · · · ∥Cm ，タグを T = msbt (Z1 ∥ · · · ∥Zd ) とする．

図 4: Xoodyak の認証暗号利用モードの暗号化関数 Xoodyak.E の手続き⊕

Rkin+8f⊕

Rkout+8⊕f⊕(0x01)||0Rkout

Z1

f

f

msbRkout

C1
M1||(0x01)
msbRkout

0b-Rkout-16||(0x40)

SM,2

⊕

⊕
f Rkout+8(4) タグ生成

SM,1⊕

Rkin+80b-Rkin-16||(0x80)

SA,2

SA,1

f

0b-Rkin-16||(0x03)(3) 暗号化

SK,N

f

SK,N

f

⊕

SA,2

SA,1

f

f

⊕

(0x01)||0Rkout⊕

msbRkout

Zd

f

⊕

SM,2

SM,1

Cm-1
Cm
Mm-1||(0x01)
Mm||0Rkout-| Mm|||(0x01)
msb|Mm|msbRkout⊕

Aa-1||(0x01) Aa||0Rkin-|Aa|||(0x01)

K||N||enc8(|N|)||(0x01)||0b-Rkin-16||(0x02)(2) AD処理 A1||(0x01) A2||(0x01)(1) 初期値の設定

5.2.2

Xoodyak の認証暗号利用モードの復号関数 Xoodyak.D

Xoodyak の認証暗号利用モードの復号関数 Xoodyak.D の入出力は以下の通りである．
入力• 鍵 K ∈ {0, 1}k• Associated Data A ∈ {0, 1}∗• 暗号文 C ∈ {0, 1}|M |• タグ T ′ ∈ {0, 1}t
出力• 暗号文 M ∈ {0, 1}|C| ，または，タグの改ざんを示す記号 ⊥̸∈ {0, 1}|C|
Xoodyak の認証暗号利用モードの復号関数の手続きは以下の通りである．
ここで，Xoodyak.D の出力値を Xoodyak.DK (N, A, C, T ′ ) と書くことにする．

1. 図 5(1) を実行し，鍵 K ，ナンス N から初期値 SK,N を生成する．
2. Associated Data A を Rkin bit のデータブロック A1 , A2 , . . . , Aa に分割する．ここで，|A1 | = · · · = |Aa−1 | = Rkin ，|Aa | ≤ Rkin であり，

A = A1 ∥A2 ∥ · · · ∥Aa ，a = ⌈|A|/Rkin ⌉ である．
3. 図 5(2) を実行する．ここでは，Associated Data ブロック A1 , A2 , . . . , Aa
を処理し，SA,1 と SA,2 を生成する．|SA,1 | = Rkin + 8 と |SA,2 | =b − (Rkin + 8) であり，1 回目の f を計算して以降の 2 本の並列の線のうち，上の線は Rkin + 8 bit，下の線は b − (Rkin + 8) bit である．

4. 暗号文 C を Rkout bit のデータブロック C1 , C2 , . . . , Cc に分割する．ここで，|C1 | = · · · = |Cm−1 | = Rkout ，|Cm | ≤ Rkout であり，C =C1 ∥C2 ∥ · · · ∥Cc ，c = ⌈|C|/Rkout ⌉ である．
5. 図 5(3) を実行する．ここでは，暗号文ブロック C1 , · · · , Cc を復号し，平文ブロック M1 , · · · , Mc ，そして，SC,1 ，SC,2 を生成する．各 i ∈ [c]に対し，|Mi | = |Ci |，|SC,1 | = Rkout + 8，|SC,2 | = b − (Rkout + 8) であり，1 回目の f を計算して以降の 2 本の並列の線のうち，上の線はRkout + 8 bit，下の線は b − (Rkout + 8) bit である．
6. 図 5(4) を実行し，出力ブロック Z1 , . . . , Zd を生成する．d = ⌈t/Rkout ⌉である．2 本の並列の線のうち，上の線は Rkout + 8 bit，下の線は b −(Rkout + 8) bit である．
7. 平文を M = M1 ∥ · · · ∥Mc ，タグを T = msbt (Z1 ∥ · · · ∥Zd ) とする．

8. T = T ′ ならば Xoodyak.DK (N, A, C, T ′ ) = M とする．
9. T ̸= T ′ ならば Xoodyak.DK (N, A, C, T ′ ) = reject とする．

5.3

Xoodoo[12] の仕様

Xoodoo[12] は 384bit の置換であり，ラウンド関数を 12 回繰り返す構造を持つ．Ri を i ラウンド目のラウンド関数とする．i ∈ [12] で，各ラウンド関
数 Ri は 384bit の置換である．

5.3.1

ステートの状態

Xoodoo[12] では，384bit のステート S を各ラウンド関数 Ri の内で 3 つの128bit の値 S0 , S1 , S2 に分割する．S = S0 ∥S1 ∥S2 である．各 128bit の値を
plane と呼び，このインデックスを y ∈ (2] で表現する．さらに，各 planeSy を
4 つの 32bit の値 S0,y , S1,y , S2,y , S3,y に分割する．Sy = S0,y , ∥S1,y ∥S2,y ∥S3,yである．各 32bit の値を lane と呼び，このインデックスを x ∈ (4] で表現する．そして，各 32bit の laneSx,y の z bit 目を Sx,y,z とする．z ∈ (31] であり，Sx,y = Sx,y,0 ∥Sx,y,1 ∥ · · · ∥Sx,y,31 である．

5.4

Xoodoo[12] で用いられる演算

Xoodoo[12] の各ラウンド関数 Ri では以下の演算が用いられる．
′← Sx,y,z とし，• Sy ≪ (t, v): 各 (x, z) ∈ (3] × (31] に対し，Sx+t,y,z+v′とする．
その後，各 (x, z) ∈ (3] × (31] に対し，Sx,y,z ← Sx,y,z• Sy : Sy のビット単位の補数．Sy の各ビット 0 は 1，1 は 0 とする．
• Sy + Sy′ : Sy と Sy′ のビット単位で XOR 演算をした値．
• Sy · Sy′ : Sy と Sy′ のビット単位で AND 演算をした値．

5.4.1

Xoodoo[12] の入出力と手続き

Xoodoo[12] の入出力は以下の通りである．
入力• X ∈ {0, 1}384
出力図 5: Xoodyak の認証暗号利用モードの復号関数 Xoodyak.D の手続き⊕⊕

Rkin+8Rkin+8⊕f

0b-Rkout-16||(0x40)

SC,2

SC,1

Rkout+8(4) タグ生成

⊕

Z1

f

f

msbRkout⊕

M1||(0x01)⊕(0x01)||0Rkout

f Rkout+8

0b-Rkin-16||(0x80)

SA,2
⊕

⊕

msbRkout

C1

SA,1

f

0b-Rkin-16||(0x03)

f(3) 復号

SK,N

f

SK,N

f

f

SA,2

SA,1

⊕

Zd

f

msbRkout⊕

Mc-1||(0x01)⊕(0x01)||0Rkout

⊕

Cc-1

f

msbRkout⊕⊕Cc
msbRkout

Aa-1||(0x01) Aa||0Rkin-|Aa|||(0x01)

K||N||enc8(|N|)||(0x01)||0b-Rkin-16||(0x02)(2) AD処理 A1||(0x01) A2||(0x01)(1) 初期値の設定

⊕

SC,2

SC,1

Mc||0Rkout-|Cc|||(0x01)

• Y ∈ {0, 1}384
Xoodoo[12] の手続きは以下の通りである．
1. ステート S の初期値として X を代入する．
2. i = 1, . . . , 12 に対して，S = Ri (S) を計算する．
3. Xoodoo[12] の出力を Y = S とする．
次に，384bit のステート S に対して，ラウンド関数 Ri の仕様を以下に示す．なお，各固定値 Ci は文献 [11] を参照されたい．

1. P ← S0 + S1 + S2
2. E ← P ≪ (1, 5) + P ≪ (1, 14)
3. y = 0, 1, 2 に対して，Sy ← Sy + E とする．
4. S1 ← S1 ≪ (1, 0) とする．
5. S2 ← S ≪ (0, 11) とする．
6. S0 ← S0 + Ci とする．
7. B0 ← S1 · S2 とする．
8. B1 ← S2 · S0 とする．
9. B2 ← S0 · S1 とする．
10. y = 0, 1, 2 に対して，Sy ← Sy + By とする．
11. S1 ← S1 ≪ (0, 1) とする．
12. S2 ← S2 ≪ (2, 8) とする．

6

Xoodyak の安全性に関する文献調査の結果
Xoodyak のハッシュ関数と認証暗号の安全性評価は，Xoodoo[12] をブラッ

クボックスとする場合の評価と，Xoodoo[12] の構造を入れた評価がある．以下，Xoodoo[12] の安全性，Xoodyak のハッシュ関数の Xoodoo[12] をブラッ
クボックスとする場合の安全性，Xoodoo[12] の構造を入れる場合の安全性，Xoodyak の認証暗号の Xoodoo[12] をブラックボックスとする場合の安全性，
Xoodoo[12] の構造を入れる場合の安全性に関する文献調査の結果を報告する．

6.1

Xoodoo[12] の安全性

文献 [16] は，Xoodoo[12] に対して，オフライン計算量が 233 の Zero-sum

Distinguisher を構成している．ただし，文献 [11] で設計者が述べているように，この攻撃が Xoodyak の安全性に直接影響を及ぼすものではないことに注意されたい．

6.2

Xoodyak のハッシュ関数の安全性

Xoodyak の安全性評価に関して，Xoodyak のプリミティブ Xoodoo[12] は単体で安全では無く，Xoodoo[12] がブラックボックスの場合の Xoodyak のハッシュ関数の安全性評価と，Xoodoo[12] の構造を含めた Xoodyak のハッシュ関数の安全性評価が必要である．以下，Xoodoo[12] と Xoodyak のハッシュ関数の Xoodoo[12] をブラックボックスとする場合とそうでない場合の安全性に関する文献調査の結果を報告する．

6.2.1

Xoodoo[12] がブラックボックスの場合の安全性

Xoodyak のハッシュ関数は，利用モードとして Sponge 構造 [6] を採用している．ここで，r = Rhash ，c = b−r とする．Sponge 構造は，置換ベースのハッシュ関数利用モードであり，置換 f がランダム置換の場合，Indiﬀerentiablityの安全性を持つことが証明されている．具体的には，以下の定理が文献 [6] で示されている．

Theorem 2 (Sponge の Indiﬀerentiability). 全クエリーのランダム置換の呼び出し回数が σ 回の Indiﬀerentiability の攻撃者 A に対し，以下が成り立つ．

Advindiﬀ
Sponge (A) ≤ 1 −

上記のバウンドはおよそ∏

1 − i+1
2c
.■
i
1
−
b
2
i∈(σ−1](1−2−r )σ 2 +(1+2−r )σであり，攻撃者の計算量が2c+1

σ = 2c/2 の場合にバウンドがコンスタントとなるため，Sponge 構造は，Indiﬀerentiability に関して，c/2 bit 安全である．
Indiﬀerentiability 以外の安全性に関して，Indiﬀerentiability 安全なハッシ
ュ関数は，c/2 とランダムオラクルの安全性レベルの最小の値が安全性レベルとなる．よって，Collision Resistance に関して min{ℓ/2, c/2} bit，Sec-

ond Preimage Resistance に関して min{ℓ, c/2} bit，Preimage Resistanceに関して min{ℓ, c/2} bit，m-target preimage resistance に関して min{ℓ −log2 m, c/2} bit の安全性を持つ．Rhash = 128，b = 384，ℓ = 256 なので，
Xoodyak のハッシュ関数は，Xoodoo[12] をブラックボックスとする場合，設計者が主張する安全性を持つ．

6.2.2

Xoodoo[12] の構造を入れる場合の安全性

Xoodoo[12] の構造を考慮に入れる場合の安全性は，今のところ解析論文は無く，設計者が主張する安全性を満たすと考えられる．

6.3

Xoodyak の認証暗号の安全性

Xoodyak の安全性評価に関して，Xoodyak のプリミティブ Xoodoo[12] は単体で安全では無く，Xoodoo[12] がブラックボックスの場合の Xoodyak の認証
暗号の安全性評価と，Xoodoo[12] の構造を含めた Xoodyak の認証暗号の安全性評価が必要である．以下，Xoodoo[12] と Xoodyak の認証暗号の Xoodoo[12]をブラックボックスとする場合とそうでない場合の安全性に関する文献調査の結果を報告する．

6.3.1

設計者が主張する Xoodoo[12] がブラックボックスの場合の安全性

Xoodyak の安全性に関して，設計者は AE 安全性に関して以下のバウンドが成り立つと主張している．以下の Claim は，文献 [11] の Claim 2 から導出されたものである．

Claim 3 (Xoodyak の AE 安全性). Xoodyak の置換 f をランダム関数とする．この時，ナンスリスペクトの Xoodyak の AE 安全性を破る任意の攻撃者

A に対し，以下の不等式が成り立つ．ここで，A のオンラインクエリの計算量を σ ，オフラインクエリ回数を p とする．

Advae
Xoodyak (A) ≤pσ2p+ 184 + 192+k . ■k2
22

Claim 3 から，Xoodyak の認証暗号の秘匿性に関して以下のバウンドが得られる．

Claim 4 (Xoodyak の秘匿性). Xoodyak の置換 f をランダム関数とする．この時，ナンスリスペクトの Xoodyak の秘匿性を破る任意の攻撃者 A に対し，以下の不等式が成り立つ．ここで，A のオンラインクエリの計算量を σe ，オ
フラインクエリ回数を p とする．

Advpriv
Xoodyak (A) ≤ppσe2+ 184 + 192+k
. ■
k
2
2
2

また，Claim 3 から，Xoodyak の認証暗号の偽造不可能性に関して以下のバウンドが得られる．

Claim 5 (Xoodyak の偽造不可能性). Xoodyak の置換 f をランダム関数とする．この時，ナンスリスペクトの Xoodyak の AE 安全性を破る任意の攻撃

者 A に対し，以下の不等式が成り立つ．ここで，A のオンラインクエリの計
算量を σ ，オフラインクエリ回数を p とする．

AdvauthXoodyak (A) ≤pσ2p+ 184 + 192+k . ■k2
22

Xoodyak は k = 128 なので，設計者が主張する，秘匿性と偽造不可能性について，オンライン計算量では 160bit，オフライン計算では 128bit の安全性が得られる．

6.3.2

Xoodoo[12] がブラックボックスの場合の安全性に関する考察

文献 [11] の Claim 2 では，Xoodyak の一般化アルゴリズム Cyclist がランダム関数と識別不可能性を示しており，このバウンドを Xoodyak に適用す
ると，Xoodyak の AE 安全性のバウンドは以下のようになる．
()(L + Ω)p + L+Ω+1pp
σ22+ 184 + 192+k +
.
2k
2
2
2192

(1)

ここで，L は攻撃者が選んだデータブロックが Xoodyak 内部で呼ばれる置換の Rkout bit 部分に直接入力される回数であり，Ω は Xoodyak への各クエリの置換の入力を先頭から結合した b bit ブロックの系列を見た場合，先頭から

1 ブロック以上同じブロックが現れる系列のペアの個数である．例えば，ナンスと鍵が同じで，次のデータブロックが違うクエリは 1 ペアと数える．

Xoodyak の設計者は，式 (1) のバウンドで，L = 0, Ω = 0 と設定して，Claim 3 のバウンドを導出している．Xoodyak の設計者は，復号オラクル
が Unveriﬁed Plaintext をタグの検証に合格しない時に出力しないならば，

L = 0, Ω = 0 であると主張している．ナンスリスペクトのセッティングで，暗号化オラクルへのクエリのみを考えるならば，L = 0, Ω = 0 は正しいが，暗号化オラクルと復号オラクルへのクエリを両方考える場合は正しくない．攻撃者
は復号オラクルへのクエリはナンスを含め自由に選択することができるため，ある暗号化クエリのナンスと同じナンスを全ての復号クエリで投げると Ω ≥ qdが成立する．qd は復号オラクルへのクエリ回数である．また，復号関数では，
暗号文ブロックが直接置換の入力値となることから，L ≥ σd が成立する．σdは復号クエリで呼び出される置換の呼び出し回数である．Ω = qd , L = σd の場合，式 (1) は以下のようになる．

pp
σ2(qd + σd )p + 0.5(qd + σd + 1)2
+
+
+
.
2k
2184
2192+k2192
このバウンドから，以下の秘匿性のバウンドが得られる．

p
σe2
p
+
+
.
2k
2184
2192+kそして，以下の偽造不可能性のバウンドが得られる．

pp
σ2(qd + σd )p + 0.5(qd + σd + 1)2+ 184 + 192+k +
.
k
2
2
2
2192
上記の秘匿性のバウンドは，設計者が主張する秘匿性の安全性レベルと矛盾しない．しかし，上記の偽造不可能性のバウンドは，オフライン計算で 128

bit 安全の時，オンライン計算で 64 bit の安全性までしか保証できないため，設計者が主張する偽造不可能性のオンライン計算に関する安全性レベル 160

bit は上記の考察と矛盾する．
今のところ，160 bit の偽造不可能性を破る攻撃は存在しないが，安全性証
明と設計者の主張に差があることに注意が必要である．

6.3.3

Xoodoo[12] の構造を入れる場合の安全性について

Xoodoo[12] の構造を入れる場合の Xoodyak の認証暗号に対する解析論文はいくつか発表されているが，7 ラウンド以上の攻撃は存在しない．以下，調査結果を記載する．

Conditional Cube 攻撃
文献 [24] で，Conditional Cube 攻撃で，Xoodoo[12] のラウンド数を 6 ラ
ウンドに削減した Xoodyak の認証暗号の鍵復元に成功している．鍵復元に必
要な時間は，244 である．

差分線形攻撃文献 [13] で，4 ラウンド Xoodoo[12] の差分線形の Distinguisher を構成し，この Distinguisher を用いて 4 ラウンド Xoodoo[12] を用いる認証暗号の鍵復元に成功している．鍵復元に必要なオフライン計算量は，223.34 である．5 ラ
ウンド Xoodoo[12] の差分線形の Distinguisher を構成し，この Distinguisherを用い 5 ラウンド Xoodoo[12] を用いる認証暗号の鍵復元に成功している．鍵復元に必要なオフラインの計算量は 222.04 である．

7

結論
本報告書では，GIFT-COFB [2, 3, 1] と Xoodyak [11, 10] の仕様を記載し，これらの方式の安全性に関する文献調査を報告した．

GIFT-COFB の安全性に関して，GIFT-COFB の利用モードである COFBの安全性は文献 [8, 4] で証明されており，調査時点で間違いは無いと考えられる．また，GIFT-COFB のプリミティブである GIFT-128 も調査時点で 40

ラウンド中 27 ラウンドまでしか攻撃されておらず，十分に安全性のマージンがあるため，GIFT-128 は安全であると考えられる．以上より，GIFT-COFB
は設計者が主張する安全性を満たすと考えられる．なお，文献 [9, 3] に COFBの安全性のバウンドが与えられているが，文献 [15, 14] でこれらのバウンドが間違いであることが示されている．

Xoodyak のハッシュ関数の安全性に関して，Xoodoo[12] をブラックボッ
クスとする場合，Sponge 構造の安全性証明 [6] からその安全性は保証され，

Xoodoo[12] の構造を入れる場合，調査時点で解析結果は報告されていない．
以上より，Xoodyak のハッシュ関数の安全性は設計者が主張する安全性を満たすと考えられる．

Xoodyak の認証暗号の安全性に関して，Xoodoo[12] をブラックボックスとする場合，設計者は Duplex 構造の安全性証明からその安全性を主張しているが，Duplex 構造の安全性バウンドと設計者が主張する安全性には差がある．なお，調査時点では，設計者が主張する安全性を破る攻撃法は見つかっていない．Xoodoo[12] の構造を入れる場合，調査時点で 12 ラウンド中 6 ラ
ウンドまでしか攻撃されておらず，十分に安全性のマージンがあるため，安全であると考えられる．以上より，Xoodyak の認証暗号は設計者が主張する安全性を満たすと考えられるが，Xoodoo[12] をブラックボックスとする場合の安全性の主張に矛盾点があるため注意が必要である．

参考文献[1] Subhadeep Banik, Avik Chakraborti, Akiko Inoue, Tetsu Iwata,Kazuhiko Minematsu, Mridul Nandi, Thomas Peyrin, Yu Sasaki,
Siang Meng Sim, and Yosuke Todo. GIFT-COFB Authenticated Encryption .
[2] Subhadeep Banik, Avik Chakraborti, Akiko Inoue, Tetsu Iwata,Kazuhiko Minematsu, Mridul Nandi, Thomas Peyrin, Yu Sasaki,
Siang Meng Sim, and Yosuke Todo. GIFT-COFB v1.2.
[3] Subhadeep Banik, Avik Chakraborti, Tetsu Iwata, Kazuhiko Minematsu, Mridul Nandi, Thomas Peyrin, Yu Sasaki, Siang Meng Sim,and Yosuke Todo. GIFT-COFB v1.1. A Submission to the NISTLightweight Cryptography Standardization Process (2021),.
[4] Subhadeep Banik, Avik Chakraborti, Tetsu Iwata, Kazuhiko Minematsu, Mridul Nandi, Thomas Peyrin, Yu Sasaki, Siang Meng Sim,and Yosuke Todo. GIFT-COFB. IACR Cryptol. ePrint Arch., page738, 2020.

[5] Subhadeep Banik, Sumit Kumar Pandey, Thomas Peyrin, Yu Sasaki,
Siang Meng Sim, and Yosuke Todo. GIFT: A small present - towards
reaching the limit of lightweight encryption. In Wieland Fischer andNaofumi Homma, editors, Cryptographic Hardware and Embedded Systems - CHES 2017 - 19th International Conference, Taipei, Taiwan,
September 25-28, 2017, Proceedings, volume 10529 of Lecture Notes in
Computer Science, pages 321–345. Springer, 2017.
[6] Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche.
On the indiﬀerentiability of the sponge construction. In Nigel P. Smart,
editor, Advances in Cryptology - EUROCRYPT 2008, 27th Annual
International Conference on the Theory and Applications of Cryptographic Techniques, Istanbul, Turkey, April 13-17, 2008. Proceedings,
volume 4965 of Lecture Notes in Computer Science, pages 181–197.
Springer, 2008.
[7] Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche.
Duplexing the sponge: Single-pass authenticated encryption and otherapplications. In Ali Miri and Serge Vaudenay, editors, Selected Areas in
Cryptography - 18th International Workshop, SAC 2011, Toronto, ON,
Canada, August 11-12, 2011, Revised Selected Papers, volume 7118 ofLecture Notes in Computer Science, pages 320–337. Springer, 2011.
[8] Avik Chakraborti, Tetsu Iwata, Kazuhiko Minematsu, and Mridul
Nandi. Blockcipher-based authenticated encryption: How small can
we go?

In Wieland Fischer and Naofumi Homma, editors, Cryp-

tographic Hardware and Embedded Systems - CHES 2017 - 19th International Conference, Taipei, Taiwan, September 25-28, 2017, Proceedings, volume 10529 of Lecture Notes in Computer Science, pages
277–298. Springer, 2017.
[9] Avik Chakraborti, Tetsu Iwata, Kazuhiko Minematsu, and Mridul
Nandi. Blockcipher-based authenticated encryption: How small can
we go? J. Cryptol., 33(3):703–741, 2020.
[10] Joan Daemen, Seth Hoﬀert, Silvia Mella, Michaël Peeters, Gilles Van
Assche, and Ronny Van Keer. Xoodyak.
[11] Joan Daemen, Seth Hoﬀert, Michaël Peeters, Gilles Van Assche,
Ronny Van Keer, and Silvia Mella. Xoodyak, a lightweight cryptographic scheme. A Submission to the NIST Lightweight CryptographyStandardization Process (2021),.

[12] Joan Daemen, Bart Mennink, and Gilles Van Assche. Full-state keyed
duplex with built-in multi-user support.

In Tsuyoshi Takagi andThomas Peyrin, editors, Advances in Cryptology - ASIACRYPT 2017 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7,
2017, Proceedings, Part II, volume 10625 of Lecture Notes in Computer Science, pages 606–637. Springer, 2017.
[13] Orr Dunkelman and Ariel Weizman. Diﬀerential-linear cryptanalysis
on xoodyak. In NIST LWC Workshop 2022, 2022.
[14] Akiko Inoue, Tetsu Iwata, and Kazuhiko Minematsu.

Analyzing

the provable security bounds of GIFT-COFB and photon-beetle. In
Giuseppe Ateniese and Daniele Venturi, editors, Applied Cryptography
and Network Security - 20th International Conference, ACNS 2022,
Rome, Italy, June 20-23, 2022, Proceedings, volume 13269 of Lecture
Notes in Computer Science, pages 67–84. Springer, 2022.
[15] Mustafa Khairallah. Security of COFB against chosen ciphertext attacks. IACR Trans. Symmetric Cryptol., 2022(1):138–157, 2022.
[16] Fukang Liu, Takanori Isobe, Willi Meier, and Zhonghao Yang. Algebraic attacks on round-reduced keccak/xoodoo. IACR Cryptol. ePrint
Arch., page 346, 2020.
[17] Ueli M. Maurer, Renato Renner, and Clemens Holenstein. Indiﬀerentiability, impossibility results on reductions, and applications to therandom oracle methodology. In Moni Naor, editor, Theory of Cryptography, First Theory of Cryptography Conference, TCC 2004, Cambridge, MA, USA, February 19-21, 2004, Proceedings, volume 2951 of
Lecture Notes in Computer Science, pages 21–39. Springer, 2004.
[18] Chanathip Namprempre, Phillip Rogaway, and Thomas Shrimpton.
Reconsidering generic composition. In Phong Q. Nguyen and Elisabeth
Oswald, editors, Advances in Cryptology - EUROCRYPT 2014 - 33rd
Annual International Conference on the Theory and Applications of
Cryptographic Techniques, Copenhagen, Denmark, May 11-15, 2014.
Proceedings, volume 8441 of Lecture Notes in Computer Science, pages
257–274. Springer, 2014.
[19] NIST.

Submission Requirements and Evaluation Criteria for theLightweight Cryptography Standardization Process, 2018.

[20] Thomas Ristenpart, Hovav Shacham, and Thomas Shrimpton. Carefulwith composition: Limitations of the indiﬀerentiability framework. In
Kenneth G. Paterson, editor, Advances in Cryptology - EUROCRYPT
2011 - 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, Estonia, May 15-19,
2011. Proceedings, volume 6632 of Lecture Notes in Computer Science,
pages 487–506. Springer, 2011.
[21] Phillip Rogaway and Thomas Shrimpton. Cryptographic hash-function
basics: Deﬁnitions, implications, and separations for preimage resistance, second-preimage resistance, and collision resistance. In Bimal K.
Roy and Willi Meier, editors, Fast Software Encryption, 11th International Workshop, FSE 2004, Delhi, India, February 5-7, 2004, Revised
Papers, volume 3017 of Lecture Notes in Computer Science, pages 371–
388. Springer, 2004.
[22] Ling Sun, Wei Wang, and Meiqin Wang. Linear cryptanalyses of threeaeads with GIFT-128 as underlying primitives. IACR Trans. Symmetric Cryptol., 2021(2):199–221, 2021.
[23] Ling Sun, Wei Wang, and Meiqin Wang. Addendum to linear cryptanalyses of three aeads with GIFT-128 as underlying primitives. IACR
Cryptol. ePrint Arch., page 151, 2022.
[24] Haibo Zhou, Zheng Li, Xiaoyang Dong, Keting Jia, and Willi Meier.
Practical key-recovery attacks on round-reduced ketje jr, xoodoo-ae
and xoodyak. Comput. J., 63(8):1231–1246, 2020.
[25] Rui Zong, Xiaoyang Dong, Huaifeng Chen, Yiyuan Luo, Si Wang, andZheng Li. Towards key-recovery-attack friendly distinguishers: Application to GIFT-128. IACR Trans. Symmetric Cryptol., 2021(1):156–
184, 2021.