QR-UOV 理解ログ　3/7

前回からの続きです．前回までは「QR-UOV」の「UOV」を見ていましたが，今回から「QR」を見ます．

QR-UOV 理解ログ　1/7
QR-UOV 理解ログ　2/7

全７回通しでの目次

第１回

• 本論文全体の流れ
• MQ問題
• 多変数多項式暗号署名方式
• UOV署名方式

第２回

• 巡回行列と逆巡回行列
• BAC-UOV 署名方式
• BAC-UOV への Structual Attack

第３回

• 多項式行列
• 今回の主定理

第４回

第５回

第６回

第７回

突貫で書いてしまった部分もあるので，大いに誤りを含む可能性があります．誤字・脱字レベルでも構いませんので，ご指摘ください．
また，予告なしに内容の加筆や構成の変更を行うことがありますが，読みやすくするためのものですので，ご容赦ください

多項式行列

$\ell$ を正整数として，$f$ を $\mathbb{F}_q$ 上の多項式であって，次数が $\ell$ とします．
剰余環 $\mathbb{F}_q[x] / (f)$ の任意の元 $g$ を取ると，次が成り立ちます:

$$\begin{align*} (1, x, \cdots, x^{\ell - 1}) \begin{pmatrix} g & & & \\ & g & \text{\huge{0}} \\ \text{\huge{0}} & & \ddots & \\ & & & g \end{pmatrix} = (g, xg, \cdots, x^{\ell - 1}g) \end{align*}$$

＊$f$ の次数が $\ell$ だからと言って，$g$ の次数が $\ell - 1$ とは限らないのですが，一々言及するとめんどくさいので，今後は $g$ の次数が $\ell - 1$ と仮定します

ここで，$g$ は単項式とは限りません．つまり，上記に出てくる $\ell \times \ell$ 行列の $g$ には一般には多項式が入ります．
また，上記の $\ell \times \ell$ 行列は，$f, g$ に依存するので，$\Phi_g^f$ と置きます．

例えば，$\ell = 3, q = 5, f = x^3 - 1$ とすると，$a_0 + a_1 x + a_2 x^2 \in \mathbb{F}_q[x] / (f)$ です．そこで，$g = 3 + 4 x + x^2$ とすると，

$$\begin{align*} (1, x, x^2) \begin{pmatrix} 3 + 4 x + x^2 & 0 & 0 \\ 0 & 3 + 4 x + x^2 & 0 \\ 0 & 0 & 3 + 4 x + x^2 \end{pmatrix} = (g, xg, x^2 g) \end{align*}$$

です．しかし，この行列は，$g$ を単項式の形に分解した，次のように見ることもできます．

$$\begin{align*} (1, x, x^2) \begin{pmatrix} 3 & 1 & 4 \\ 4 & 3 & 1 \\ 1 & 4 & 3 \end{pmatrix} = (g, xg, x^2 g) \end{align*}$$

つまり，サイズが3の巡回行列です．
ここで，

$$\begin{align*} (g, xg, x^2 g) & = (3 + 4 x + x^2, x(3 + 4 x + x^2), x^2(3 + 4 x + x^2)) \\ & = (3 + 4 x + x^2, 1 + 3 x + 4 x^2, 4 + x + 3 x^2) \end{align*}$$

です（今は $x^3 = 1$ とみなしています）から，確かに上の式は整合性が取れています．

＊$\Phi_g^f$ は $f, g$ の取り方に依存し，一般には巡回行列とは限りません（上はたまたま巡回行列となった例です）

一般論に戻ると，$0 \leq j \leq \ell - 1$ に対して，$\displaystyle x^j g = \sum_{i = 0}^{\ell - 1} (\Phi_g^f)_{ij} \cdot x^i$ です（インデックスはずらしています）.
$(\Phi_g^f)_{ij}$ は上記のように，$g$ を単項式に分解したときの $\Psi_g^f$ の $(i + 1, j + 1)$ 成分と見ることができます．

次の補題が成り立ちます．

---

$\underline{\mathrm{Lem(多項式行列)}}$
任意の $g_1, g_2 \in \mathbb{F}_q[x] / (f)$ に対して，次が成り立つ:

$$\begin{align*} \Phi_{g_1}^f + \Phi_{g_2}^f & = \Phi_{g_1 + g_2}^f \\ \Phi_{g_1}^f \Phi_{g_2}^f & = \Phi_{g_1 g_2}^f \end{align*}$$

---

証明

$$\begin{align*} \Phi_{g_1}^f = \begin{pmatrix} g_1 & & & \\ & g_1 & \text{\huge{0}} \\ \text{\huge{0}} & & \ddots & \\ & & & g_1 \end{pmatrix}, \Phi_{g_2}^f = \begin{pmatrix} g_2 & & & \\ & g_2 & \text{\huge{0}} \\ \text{\huge{0}} & & \ddots & \\ & & & g_2 \end{pmatrix} \end{align*}$$

ですから，

$$\begin{align*} \Phi_{g_1}^f + \Phi_{g_2}^f & = \begin{pmatrix} g_1 + g_2 & & & \\ & g_1 + g_2 & \text{\huge{0}} \\ \text{\huge{0}} & & \ddots & \\ & & & g_1 + g_2 \end{pmatrix} = \Phi_{g_1 + g_2}^f \\ \Phi_{g_1}^f \Phi_{g_2}^f & = \begin{pmatrix} g_1 g_2 & & & \\ & g_1 g_2 & \text{\huge{0}} \\ \text{\huge{0}} & & \ddots & \\ & & & g_1 g_2 \end{pmatrix} = \Phi_{g_1 g_2}^f \end{align*}$$

ゆえ，示されました．

---

ここで，$A_f = \{ \Psi_g^f \in \mathbb{F}_q^{\ell \times \ell} \ | \ g \in \mathbb{F}_q[x] / (f) \}$ とします．つまり，$A_f$ は $g$ を動かしたときの $\Phi_g^f$ 全体です．この行列の集合は，上記の補題から，和と積で閉じています．

今回の主定理

初めに主張を確認します．

---

$\underline{\mathrm{Thm(多項式行列)}}$
任意の $\Phi_g^f \in A_f$ に対して，$W \Phi_g^f$ が対称行列なる可逆な $W \in \mathbb{F}_q^{\ell \times \ell}$ が存在する．

---

実際に，$W \Phi_g^f$ が対称行列なる可逆な $W \in \mathbb{F}_q^{\ell \times \ell}$ を構成すればOKです．
論文だと前半が一般の場合の議論で，後半で構成した $W$ を使って議論しています．ここでは，前半の証明の際に，一般の場合と構成した $W$ を使って実際に確かめる場合の2つを紹介します．

証明
$g = a_0 + a_1 x + \cdots + a_{\ell - 1} x^{\ell - 1} \in \mathbb{F}_q[x] / (f)$ を取って，$\phi_g : \mathbb{F}_q[x] / (f) \ni g \mapsto a_{\ell - 1} \in \mathbb{F}_q$ とします．このとき，$\phi_g$ は線型です．
そして，$1 \leq i, j \leq \ell$ としたとき，$W$ の $(i, j)$ 成分は $\phi_g(x^{i + j - 2})$ であるように $W$ を構成します．つまり，$i + j - 2 \equiv \ell - 1 \ \mathrm{mod} \ \ell$ i.e. $i + j \equiv 1 \ \mathrm{mod} \ \ell$ のとき $W[i][j] = 1$ で，それ以外のときは $W[i][j] = 0$ です．
まとめると，$W$ は $(\ell, 1)$-$(1, \ell)$ にかけての右肩上がりの対角成分が1でそれ以外は0の $\ell \times \ell$ 行列です．

まず，示すべきことは $W \Phi_g^f$ の $(i, j)$ 成分と $(j, i)$ 成分が等しいことです．
これは

$$\begin{align*} \displaystyle (W \Psi_g^f)_{ij} & = \sum_{k = 1}^{\ell - 1} W[i][k] \Psi_g^f[k][j] \\ & = \sum_{k = 1}^{\ell - 1} \phi_g(x^{i + k - 2}) (\Psi_g^f)_{kj} \\ & = \phi_g \left( \sum_{k = 1}^{\ell - 1} x^{i + k - 2} (\Psi_g^f)_{kj} \right) \hspace{10pt} \because) \ \phi_g \text{は線型} \\ & = \phi_g \left( x^{i - 1} \left( \sum_{k = 1}^{\ell - 1} x^{k - 1} (\Psi_g^f)_{kj} \right) \right) \\ & = \phi_g \left( x^{i - 1} x^{j - 1} g \right) \hspace{10pt} \because) \ x^j g = \sum_{i = 0}^{\ell - 1} (\Phi_g^f)_{ij} \cdot x^i \\ & = \phi_g (x^{i + j - 2} g ) \end{align*}$$

ですから，同様の議論から $(W \Psi_g^f)_{ji} = \phi_g (x^{j + i - 2} g )$ を得ることができるので，$(W \Psi_g^f)_{ij} = (W \Psi_g^f)_{ji}$ です．

＊ちなみに実際に $W \Phi_g^f$ を計算すると，$(\ell, 1)$-$(1, \ell)$ にかけての右肩上がりの対角成分が $g$ でそれ以外は0の $\ell \times \ell$ 行列となります．$W \Phi_g^f$ の $(i, \ell + 1 - i)$ 成分が $a_0$ なので，$(i, j)$ 成分は，$a_{i + j - 1}$ です．また，$W \Phi_g^f$ の $(j, \ell + 1 - j)$ 成分が $a_0$ なので，$(j, i)$ 成分は，$a_{j + i - 1}$ です．このことからも $W \Phi_g^f$ が対称行列であることが分かります．

続いて $W$ の可逆性を示しますが，これはすぐに可逆だと分かります（$W W = I_n$ のため）．

以上より示されました．

---

この定理が後にUOV方式に応用されます．
次回はこの定理の具体例から見ていきます．

---

今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！