4 Maximal exceptional graphs
5.3 持駒方式の安全性解析
任意の多変数公開鍵暗号系の安全性を強化する概念として，持駒概念 [Tsu03] が提案 されている．この概念を具現化したものである，持駒方式と呼ばれる安全性強化手法が，
これまでに，いくつか提案されている．持駒方式の具体的な構成方法については，文献 [TTF07a, TTF08, FTT08c] などを参照されたい．
以下では，これらの持駒方式の安全性について，グレブナ基底計算を用いた代数攻撃に 対する安全性に関する結果について述べる．下記の計算機実験においては，計算機実験環 境 A（1.2 節）を使用した．なお，HFE の解読に使われた HFE オプションなどのよう な，グレブナ基底計算に関する Magma のオプションについては一切使用していない．
5.3.1 線形持駒行列方式[TTF07a]
HFE（3.2.1 節）に乱数変数を付加した線形持駒行列方式を適用することにより，グレ
ブナ基底攻撃に対する安全性が強化されることが，計算機実験により示されている（表 4）．特に平文変数の数を一定（10）とした場合，原方式である HFE と比較して，持駒方 式において，乱数変数を導入することにより，変数の総数 z = 39 とした方が，計算時間 が約 106 倍になることが計算機実験から明らかとなった．また，復号時間が一定となる ように，n を一定（20）とした場合，原方式である HFE と比較して，持駒方式において 変数の総数z = 39の方が，計算時間が 740 倍以上になることが計算機実験から明らかと なった．
表4 グレブナ基底攻撃のための計算時間の比較（線形持駒行列方式）
パラメータ 計算時間
方式 p n z g (sec.)
10 <10−3
HFE（q= 2, 20 8
128< d <513） 25 184
28 959
パラメータ 計算時間
方式 p n z g (sec.)
10 20 35 25 1000 線形持駒行列方式 10 20 37 25 2424
（原方式： 10 20 38 25 5288 HFE（q= 2, 10 20 32 28 665 128< d <513）） 10 20 36 28 2290
10 20 38 28 4460 10 20 39 28 5963 p:持駒方式における平文変数の数，n:原方式における平文変数の数
z:持駒方式における変数（平文変数，乱数変数）の総数，g:持駒方式における公開鍵多項式の数
33
5.3.2 非線形持駒行列方式 [TTF08]
MI（3.2.1 節），RSE（3.2.2節）に，非線形持駒行列方式を適用することにより，線形 持駒行列方式よりもグレブナ基底攻撃に対する安全性が強化されることが，計算機実験に より示されている（表 5）．表 5 から，非線形持駒行列方式の方が，線形持駒行列方式と 比較して，計算時間が約10 倍から 100倍大きくなっていることがわかる．また，平文変 数の数を一定（25）とした場合，原方式である MI，RSE と比較して持駒方式において 変数の総数z = 52 の方が，計算時間が約 104 倍になることが計算機実験から明らかと なった．
表5 グレブナ基底攻撃のための計算時間の比較（持駒行列方式）
パラメータ 計算時間
方式 p n z g (sec.)
15 <10−2
MI 20 0.01
（q= 2） 25 0.03
30 0.07
35 0.2
40 0.4
45 0.7
50 1
55 2
60 4
パラメータ 計算時間 (sec.) 方式 p n z g 線形 非線形
25 35 50 47 3 52
持駒行列方式 25 35 51 47 6 260
（原方式： 25 35 52 47 22 1307 MI（q= 2）） 25 35 54 47 58 n/a
25 35 56 47 829 n/a
30 40 54 50 3 59
30 40 55 50 5 263
30 40 56 50 7 1281
30 40 58 50 47 n/a
30 40 60 50 1016 n/a
パラメータ 計算時間
方式 p n z g (sec.)
15 0.01
RSE 20 0.03
（q= 2） 25 0.08
30 0.2
35 0.5
40 1
45 2
50 5
55 9
60 16
パラメータ 計算時間(sec.) 方式 p n z g 線形 非線形
25 35 50 47 6 50
持駒行列方式 25 35 51 47 13 250
（原方式： 25 35 52 47 19 1309 RSE（q= 2）） 25 35 54 47 131 n/a
25 35 56 47 1622 n/a
30 40 54 50 8 58
30 40 55 50 11 264
30 40 56 50 28 1285
30 40 58 50 158 n/a
30 40 60 50 1770 n/a p:持駒方式における平文変数の数，n:原方式における平文変数の数
z:持駒方式における変数（平文変数，乱数変数）の総数，g:持駒方式における公開鍵多項式の数 n/aは計算不可を示す．
34
5.3.3 非線形持駒摂動ベクトル方式[FTT08c]
MI に非線形持駒摂動ベクトル方式を適用することにより，グレブナ基底攻撃に対する 安全性がInternal Perturbation（3.3 節）と同等に強化されることが計算機実験により示 されている（表 6，表 7）．
乱数変数を付加しない非線形持駒摂動ベクトル方式について，特に，平文変数の数を一
定 (n= 30) とした場合，原方式である MI と比較して，持駒方式は PMI+ と同様に計
算時間が約 104 倍になることが計算機実験から明らかとなった．
一方，乱数変数を付加した非線形持駒摂動ベクトル方式について，平文変数の数を一定
（15）とした場合，原方式である MI，RSE と比較して，持駒方式において変数の総数z と公開鍵多項式の数 g がそれぞれz = 47, g = 35（原方式：MI）z = 44, g = 35（原方 式：RSE）の方が，計算時間が約105 倍になることが計算機実験から明らかとなった（表 8）．
表6 PMI+（q = 2）に対するグレブ ナ基底攻撃のための計算時間
パラメータ 計算時間
n k h (sec.)
28 6 0 845
28 6 5 733
28 6 10 563
28 6 15 436
29 6 15 747
30 6 15 1305
n: 平文変数の数
k: perturbation dimension h: Plus 多項式の数
表7 非線形持駒摂動ベクトル方式を 適用した MI（q = 2）に対するグレブ ナ基底攻撃のための計算時間
パラメータ 計算時間
n l h (sec.)
28 17 3 290
28 17 4 289
28 17 5 263
29 17 3 537
29 17 8 402
29 17 10 349
30 17 3 936
30 17 8 701
30 17 13 513
n: 平文変数の数
l: 補助方式における変数の数 h: ランダム項ベクトルの次元
なお，非線形持駒摂動ベクトル方式の計算機実験において，補助方式として，HFE の 公開鍵多項式による非線形変換を用いたが，補助方式として，どのような方式が最適であ るかについては未解決問題である．
35
表8 グレブナ基底攻撃のための計算時間の比較（非線形持駒摂動ベクトル方式）
パラメータ 計算時間
方式 p n z g (sec.)
15 <10−2
MI 20 0.01
（q= 2） 25 0.03
30 0.07
35 0.2
40 0.4
45 0.7
50 1
55 2
60 4
パラメータ 計算時間
方式 p n z g (sec.)
15 20 40 35 75
非線形持駒 15 20 43 35 129 摂動ベクトル方式 15 20 45 35 260
（原方式： 15 20 46 35 320 MI（q= 2）） 15 20 47 35 1029
15 20 40 40 97
15 20 43 40 161
15 20 47 40 284
15 20 48 40 495
15 20 49 40 1077
パラメータ 計算時間
方式 p n z g (sec.)
15 0.01
RSE 20 0.03
（q= 2） 25 0.08
30 0.2
35 0.5
40 1
45 2
50 5
55 9
60 16
パラメータ 計算時間
方式 p n z g (sec.)
15 20 40 35 40
非線形持駒 15 20 41 35 71 摂動ベクトル方式 15 20 42 35 179
（原方式： 15 20 43 35 713 RSE（q= 2）） 15 20 44 35 2791
15 20 40 40 51
15 20 42 40 82
15 20 44 40 231
15 20 45 40 877
15 20 46 40 2327
p:持駒方式における平文変数の数，n:原方式における平文変数の数
z:持駒方式における変数（平文変数，乱数変数）の総数，g:持駒方式における公開鍵多項式の数