多変数 2 次公開鍵暗号の分類

対し，検証鍵 E を用いて c=E(p) かどうか検査することとなる．

なお，図 1 に示した暗号系は秘密鍵 G について 1 段構成であるが，このような構 成を拡張したものとして，非線形変換 G₁, G₂, 線形変換 L₁, L₂, L₃ について，公開鍵 E = L1◦G1◦L2◦G2 ◦L3 といった 2 段構成をなし，公開鍵多項式の次数が 4 以上と なる暗号系がいくつか提案されている[TFH89, PG97a, PG97b]．以下では，図1に示さ れるような，1 段構成の暗号系のみを取り上げる．

■MI (Matsumoto-Imai; MIA, C^∗) [MIHM83, IM85, MI88a, MI88b] 中間変数ベクトル v, w のそれぞれの次元 n, m について n =m とする．V = φ⁻¹(v) ∈F_qⁿ に関する単 項式写像 F をF(V) =V^qθ+1 = V^ι とする．ただし g.c.d.(q^θ+ 1, qⁿ−1) = 1 とする．

この条件は，F が全単射であることと同値である．

MI における G は以下のように表される：

G(v) = (φ◦F ◦φ⁻¹)(v).

法 qⁿ−1における ι の乗法の逆元を ι⁰ とすると，W =φ⁻¹(w)∈Fqⁿ に対するF の 逆変換 F⁻¹ は以下のように表される：

F⁻¹(W) =W^ι0.

F⁻¹ を用いて，G の逆変換 G⁻¹ は以下のように表される：

G⁻¹(w) = (φ◦F⁻¹◦φ⁻¹)(w).

■HFE (Hidden Field Equations) [Pat96a] ^{中間変数ベクトル} v, w ^{のそれぞれの次元}n, m について n=m とする．V =φ⁻¹(v)∈F_qⁿ に関するd 次多項式写像 F が以下のよ うな形をなすものとする：

F(V) = X

0≤i,j≤d qⁱ+q^j≤d

β_i,jV^qi+qj + X

0≤l≤d q^l≤d

α_lV^ql +µ₀.

ここで，β_i,j, α_l, µ₀ ∈U F_qⁿ である．

HFE における G は以下のように表される：

G(v) = (φ◦F ◦φ⁻¹)(v).

HFE における G⁻¹ は下記のように計算される：

1. W =φ⁻¹(w).

2. 1 において得られた W と未知変数 V に関する方程式 F(V) =W を V について 解く．

3. 2 において得られた V それぞれについてv =φ(V)を得る．

3.2.2 順序解法型

順序解法型とは，G⁻¹ を計算する際に，中間変数 v₁, . . . , v_n のうち，1 変数，あるい はいくつかの変数について順序的に解いてゆくものである．

21

■順序解法 [Tsu85, TKIFM86, Sha93] 順序解法における G = (g1, . . . , gn) は以下のよ うに表される：

w₁ =g₁(v₁, . . . , v_n) =v₁

w₂ =g₂(v₁, . . . , v_n) =v₂·l₂(v₁) +q₂(v₁) w₃ =g₃(v₁, . . . , v_n) =v₃·l₃(v₁, v₂) +q₃(v₁, v₂)

...

wn =gn(v1, . . . , vn) =vn·ln(v1, . . . , vn−1) +qn(v1, . . . , vn−1)

ここに l_i は v₁, . . . , v_i−1 に関する線形変換，q_i は v₁, . . . , v_i−1 に関する非線形変換で ある．

順序解法 における G の逆変換 G⁻¹ は以下のように計算される：

1. v1 =w1.

2. v2 = w2−q2(v1)

l2(v1) , v3 = w3−q3(v1, v2)

l3(v1, v2) , . . . , vn= wn−qn(v1, . . . , vn−1) ln(v1, . . . , vn−1) .

■R(S)SE (Random (Singular) Simultaneous Equations) [KS04, KS05a] 中間変数ベク トル v, w のそれぞれの次元 n, m について n = m とする．また，整数 t ≥ 2, N ≥ 2 に対し，n=N t ^{をみたすものとする．}

v, w をそれぞれ N 個の t 次元ベクトルに分割したものを，それぞれ v_i, w_i と 表す．すなわち vi = (v_(i−1)t+1, . . . , vit)^T, wi = (w_(i−1)t+1, . . . , wit)^T である．また 1≤i < j ≤N ^に対しvi,...,j = (v_(i−1)t+1, . . . , vjt)^T, wi,...,j = (w_(i−1)t+1, . . . , wjt)^{T と} する．

Fi を逆変換が一意な（非特異な）非線形変換とし，Ψi を（必ずしも逆変換が一意とは 限らない）非線形変換とする．

RSE における G= (G₁, . . . , G_N) :v7→w は以下のように表される：

w1 =G1(v1, . . . , vn) =F1(v1)

w2 =G2(v1, . . . , vn) =F2(v2) + Ψ2(v1) w3 =G3(v1, . . . , vn) =F3(v3) + Ψ3(v1,2)

...

w_N =G_N(v₁, . . . , v_n) =F_N(v_N) + Ψ_N(v_1,...,N−1)

22

RSSE における G= (G1, . . . , GN) は以下のように表される：

w₁ =G₁(v₁, . . . , v_n) = Ψ₁(v₁) w₂ =G₂(v₁, . . . , v_n) = Ψ₂(v₂) w₃ =G₃(v₁, . . . , v_n) = Ψ₃(v₃)

...

wN =GN(v1, . . . , vn) = ΨN(vN) RSE における G⁻¹ は以下のように計算される：

1. v1 =F₁⁻¹(w1).

2. v₂ =F₂⁻¹(w₂−Ψ₂(v₁)), . . . ,v_N =F_N⁻¹(w_N −Ψ_N(v_1,...,N−1)).

RSSE ^における G^{−1 の計算は，各} i ^についてwi = Ψi(vi) ^{となるような}vi の候補を それぞれ求めることにより行う．

3.2.3 UOV ^型

UOV 型とは，oil 変数とvinegar 変数による双線形形式を非線形変換 G として用いる

ものである．

■UOV (Unbalanced Oil and Vinegar) [KPG99] 中間変数ベクトル v, w のそれぞれの 次元 n, m^{について，任意の整数} k ≥1 ^に対し n=m+k ^{であるものとする．}

UOV における G= (g₁, . . . , g_m) :v7→w は以下のように表される：

gi = X

1≤j≤m m+1≤l≤m+k

γi,j,lvjvl+ X

m+1≤j,l≤m+k

λi,j,lvjvl+ X

1≤j≤m

ξi,jvj+ X

m+1≤j≤m+k

ηi,jvj+δi.

これらの 方程式 の係 数 に つ い て ，γi,j,l, λi,j,l, ξi,j, ηi,j, δi ∈U Fq で ある．こ こで v₁, . . . , v_m を oil 変数，v_m+1, . . . , v_m+k を vinegar 変数と呼ぶ．g_i には oil 変数同 士の積，すなわち1≤j, l≤m に対する vjvl の項が含まれていない.

UOV における G の逆変換 G⁻¹ を計算するためには，gi における vinegar 変数 v_m+1, . . . , v_m+k に値を与えたもの g_i(v₁, . . . , v_m) について以下の線形連立方程式を v1, . . . , vm について解く：







g₁(v1, . . . , vm) = w1

... g_m(v1, . . . , vm) = wm

23

UOV において，非線形変換 Gはランダムに生成される．このため，秘密鍵 L1 は非線形 変換 G に吸収される．それゆえ，UOV において L₁ を考えないのが一般的である．

UOV のパラメータとしては，以下が提案されている：

• q= 2, n= 192, m= 64, k = 128.

• q= 16, n= 48, m= 16, k = 32.