前回からの続きです．
QR-UOV 理解ログ 1/7
QR-UOV 理解ログ 2/7
QR-UOV 理解ログ 3/7
QR-UOV 理解ログ 4/7
全７回通しでの目次
第１回
- 本論文全体の流れ
- MQ問題
- 多変数多項式暗号署名方式
- UOV署名方式
第２回
- 巡回行列と逆巡回行列
- BAC-UOV 署名方式
- BAC-UOV への Structual Attack
第３回
第４回
第５回
第６回
第７回
突貫で書いてしまった部分もあるので，大いに誤りを含む可能性があります．誤字・脱字レベルでも構いませんので，ご指摘ください．
また，予告なしに内容の加筆や構成の変更を行うことがありますが，読みやすくするためのものですので，ご容赦ください
Description
\ell, v, m を正整数として，v, m は \ell で割り切れ，v > m とします．また，n := v + m, N = \frac{n}{\ell} と置きます．
f \in \mathbb{F}_q[x] を \ell 次の既約多項式として，W を可逆行列として，W A_f の任意の行列が対称行列とします．
1 \leq i, j \leq N で X_{i, j} \in A_f \subset \mathbb{F}_q^{\ell \times \ell} とします．\begin{pmatrix} X_{11} & \cdots & X_{1N} \\ \vdots & \ddots & \vdots \\ X_{N1} & \cdots & X_{NN} \end{pmatrix} を任意の元とする \mathbb{F}_q^{n \times n} の部分空間 A_f^{(N)} を考えます．
また，n \times n 行列 W^{(N)} = \begin{pmatrix} W & & \\ & \ddots & \\ & & W \end{pmatrix} とします．
ここで，次の命題が成り立ちます．
\underline{\mathrm{Prop}}
任意の X \in A_f^{(N)}, \ Y \in W^{(N)} A_f^{(N)} として，X^{T} Y X \in W^{(N)} A_f^{(N)} である．
証明
\mathbb{F}_q[x] / (f) の任意の元 g を取ると，A_f の元は，\Phi_g^f と表せることを思い出します．
参考:QR-UOV 理解ログ 3/7「多項式行列」
N = 1 のとき，\mathbb{F}_q[x] / (f) の任意の元 g_X, g_Y を取ると，X = \Phi_{g_X}^f, \ Y = W \Phi_{g_Y}^f と表せます．よって，
\begin{align*}
X^T Y X
& = (\Phi_{g_X}^f)^T (W \Phi_{g_Y}^f) \Phi_{g_X}^f \\
& = (\Phi_{g_X}^f)^T W^T \Phi_{g_Y}^f \Phi_{g_X}^f \\
& = (W \Phi_{g_X}^f)^T \Phi_{g_Y}^f \Phi_{g_X}^f \\
& = W \Phi_{g_X}^f \Phi_{g_Y}^f \Phi_{g_X}^f \\
& = W \Phi_{g_X g_Y g_X}^f
\end{align*}
となり，示されました．ただし，１行目から２行目の変形では，W が対称（A_f の元として単位行列を取って，W A_f の任意の元が対称であることから分かる）なので W = W^T を使っています．また，２行目から３行目の変形では、行列について A^T B^T = (B A)^T を使って，３行目から４行目では，W A_f が対称であること，最後では \Phi_{g_1}^f \Phi_{g_2}^f = \Phi_{g_1 g_2}^f を使っています．
参考:QR-UOV 理解ログ 3/7「多項式行列」
N \leq 2 として，X^T Y X の i, j 成分を考えます．これは，X^T Y X[i][j] \in W A_f を示せばOKだからです．
\begin{align*}
\displaystyle
X^T Y X[i][j]
& = \sum_{k = 1}^{N} X^T Y[i][k] X[k][j] \\
& = \sum_{k = 1}^{N} \left( \sum_{\ell = 1}^{N} X^T[i][\ell] Y[\ell][k] \right) X[k][j] \\
& = \sum_{k = 1}^{N} \sum_{\ell = 1}^{N} \left( X^T[i][\ell] Y[\ell][k] X[k][j] \right)
\end{align*}
すると，X^T[i][\ell] は，ある \mathbb{F}_q[x] / (f) の元 g_{X, i, \ell} を用いて，\Phi_{g_{X, i, \ell}}^f と表せます．同様に，Y[\ell][k] = \Phi_{g_{Y, \ell, k}}^f, \ X[k][j] = \Phi_{g_{X, k, j}}^f と表すことができて，N = 1 の議論から，\Phi_{g_{X, i, \ell}}^f \Phi_{g_{Y, \ell, k}}^f \Phi_{g_{X, k, j}}^f \in W A_f を満たします．よって，X^T[i][\ell] Y[\ell][k] X[k][j] \in W A_f です．
ここで，A_f の任意の元 \Phi_{g_1}^f, \ \Phi_{g_2}^f について，\Phi_{g_1}^f + \Phi_{g_2}^f = \Phi_{g_1 + g_2}^f なので，A_f は行列の足し算に関して群になります．
よって，W A_f も行列の足し算に関して群なので，\sum_{k = 1}^{N} \sum_{\ell = 1}^{N} \left( X^T[i][\ell] Y[\ell][k] X[k][j] \right) \in W A_f を得ます．
以上より示されました．
鍵生成アルゴリズム
-
f \in \mathbb{F}_q[x] を \ell 次の既約多項式として，W を可逆行列として，W A_f の任意の行列が対称行列とする
- 左下の m \times m 部分行列が零行列なる F_i を W^{(N)} A_f^{(N)} から選ぶ
-
A_f^{(N)} からランダムに可逆行列 S を選ぶ
-
P_i = S^T F_i S を計算する
このアルゴリズムを使って，QR-UOV を構成します（Rainbow にも応用できるそうです）．
今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！
次回で QR-UOV の原論文の解説ログは終わりです．
Discussion