前回からの続きです．
QR-UOV 理解ログ 1/7
QR-UOV 理解ログ 2/7
QR-UOV 理解ログ 3/7
全７回通しでの目次
第１回
- 本論文全体の流れ
- MQ問題
- 多変数多項式暗号署名方式
- UOV署名方式
第２回
- 巡回行列と逆巡回行列
- BAC-UOV 署名方式
- BAC-UOV への Structual Attack
第３回
第４回
第５回
第６回
第７回
突貫で書いてしまった部分もあるので，大いに誤りを含む可能性があります．誤字・脱字レベルでも構いませんので，ご指摘ください．
また，予告なしに内容の加筆や構成の変更を行うことがありますが，読みやすくするためのものですので，ご容赦ください
前回の主定理の例
前回の主定理はこのようなものでした．
\underline{\mathrm{Thm(多項式行列)}}
任意の \Phi_g^f \in A_f に対して，W \Phi_g^f が対称行列なる可逆な W \in \mathbb{F}_q^{\ell \times \ell} が存在する．
実際にこのような行列が存在することを構成して上記の証明を行いました．
詳しいことは，前回の記事QR-UOV 理解ログ 3/7「今回の主定理」 を参照してください．
今回は上記の具体例から始めます．
a, \in \mathbb{F}_q, 1 \leq k \leq \ell - 1 として，f = x^{\ell} - a x^k - 1 とします．
\phi : \mathbb{F}_q[x] / (f) \ni a_0 + a_1 x + \cdots + a_{\ell - 1} \mapsto a_{k - 1} \in \mathbb{F}_q として（前回は向かう先が a_{\ell - 1} だったことに注意），\ell \times \ell 行列 W の (i, j) 成分は \phi(x^{i + j - 2}) と等しい，と定義していました．つまり，i + j - 2 \equiv k - 1 \ \mathrm{mod} \ \ell i.e. i + j \equiv k + 1 \ \mathrm{mod} \ \ell のとき，W[i][j] = 1 で，それ以外のときは W[i][j] = 0 です．
例えば，i = 1 のとき，j = k のとき，W[i][j] = 1 となります．これを一般化すると，1 \leq i \leq k のとき，j = k - i とすると，W[i][j] = 1 です．
次に，i =k + 1 のとき，j = \ell とすると，i + j \equiv k + 1 \ \mathrm{mod} \ \ell より，W[i][j] = 1 です．これを一般化すると，k + 1 \leq i \leq \ell のとき，j = k + \ell - i とすると，W[i][j] = 1 です．
以上をまとめると，論文に記載の J_k と J_{\ell - k} を用いた形で表せます．
f の既約性
まず，R を環としたとき，f \in R[X] が既約であるとは，次数が \mathrm{def}f(X) 未満の R 係数の多項式で割り切れないことです．
＊詳しいことは，プログラマブルブートストラップの原著論文を理解する回 1/4 を参照してください
2.4 では，Structual Attack を扱いました．そこでは，ブロック逆巡回行列 Y を変形することで，成分に0が多く現れるようにして，計算量を削減する攻撃でした．
実は，f が既約の場合，そこから構成される X = W \Phi_g^f では，同じような変形をしても，0が現れない（任意の成分が非零）であることが知られています．その事実を次の定理で示します:
\underline{\mathrm{Thm}}
f \in \mathbb{F}_q[X] が次数 \ell の既約多項式であり，g \in \mathbb{F}_q[X] / (f) を取る．(1, x, \cdots, x^{\ell - 1}) \Phi_g^f = (g, xg, \cdots, x^{\ell - 1} g) なる \ell \times \ell 行列 \Phi_g^f 全体の集合を A_f とする．A_f の任意の要素 \Phi_g^f に対して，W \Phi_g^f が対称行列なる可逆な行列 W を取る．
このとき，X = W \Phi_g^f に対して，L^t X L のある成分が0になるような可逆行列 L は存在しない．
＊３行目のそのような行列 W が存在することは，前回の QR-UOV 理解ログ 3/7「今回の主定理」 を参照してください
f が既約のため，\mathbb{F}_q[X] / (f) なる剰余環は体になります（既約多項式で生成されるイデアルで割った剰余環は体になるため）．
証明
ある可逆な \ell \times \ell 行列 L とを取って，L^t X L の (i, j) 成分が0になるような 1 \leq i, j \leq \ell が存在したと仮定します．
L^t X L = (L^t W) \psi_g^f L = (W^t L)^t \psi_g^f L です．上の i, j に対して，W^t L の i 番目の列ベクトルを {w \ell}_i として，L の j 番目の列ベクトルを \ell_j とします．すると，((W^t L)^t \Phi_g^f L)[i][j] = L^t X L[i][j] = 0 なので，({w \ell}_i)^t \Phi_g^f \ell_j = 0 です．
ここで，V_1 : \mathbb{F}_q[x] / (f) \ni a_0 + a_1 x + \cdots a_{\ell - 1} x^{\ell - 1} \mapsto (a_0, a_1, \cdots, a_{\ell - 1})^t \in \mathbb{F}^{\ell} とすると，V_1 は同型写像（群準同型かつ全単射）です．よって，V_1(g) は \Phi_g^f の1番目の列ベクトルに等しくなります（このことは，\Psi_g^f の行列表示から明らか）．
また，V_2 : \mathbb{F}_q[x] / (f) \ni a_0 + a_1 x + \cdots a_{\ell - 1} x^{\ell - 1} \mapsto (a_{\ell - 1}, a_{\ell - 2}, \cdots, a_0)^t \mathbb{F}_q^{\ell} とすると，V_2 は同型写像（群準同型かつ全単射）です．よって，V_2(g) は (\Phi_g^f)^t の1番目の列ベクトルに等しくなります（このことは，\Psi_g^f の行列表示から明らか）．
V_1 の補足
V_1 は要するに，多項式とベクトルの対応づけを表しています．
V_1 が同型であることを念のため確認します．ちなみに環準同型ではなく，群準同型です．つまり，\mathbb{F}_q[x] / (f) と \mathbb{F}_q^{\ell} はどちらも環（だし，前者は体）なのですが，掛け算を忘れて，足し算だけに注目した群として見ることで，準同型性が成り立っています．
V_1 が全単射であることは明らかです．要素が1対1対応するように作っています．
群準同型であることは，多項式の足し算がベクトルの足し算に対応するので，準同型になっています．ただし，多項式の掛け算がベクトルの内積には対応しない（掛け算の回数が異なる）ので，掛け算に対しては準同型性が成り立たないため，環準同型ではなく，群準同型です．
V_2 の補足
論文だと，V_2 の単射性が自明でないと考えて，V_2(g) = 0 \Rightarrow g = 0 を示していますが，V_1 の議論と同じようにして，V_2 が同型であることを示せます（V_2 で元の行き先を明示したから，一気に全単射性が言えるため，そのような議論が不要，ということです）．
ここで，g_i = V_2^{-1}({w \ell}_i), g_j = V_1^{-1}(\ell_j) とします（どちらも全単射なので，逆写像が存在）．つまり，V_2(g_i) は {w \ell}_i に等しく，また，V_2(g) は (\Phi_{g}^f)^t の1番目の列ベクトルに等しい，という条件から，\Phi_{g_i}^f の1番目の列ベクトルは ({w \ell}_i)^t であることが分かります．同様にして，\Phi_{g_j}^f の1番目の列ベクトルは \ell_j です．
よって，任意の g に対して，({w \ell}_i)^t \Phi_g^f \ell_j = 0 だったことから，\Phi_{g_i}^f \Phi_g^f \Phi_{g_j}^f の (1, 1) 成分は0です．ここで，g = (g_i g_j)^{-1} とします．
逆元の存在性
g = (g_i g_j)^{-1} としたとき，g_i g_j が逆元を持つかは確認すべきことなのです．
これは，g_i, g_j \in \mathbb{F}_q[x] / (f) であり，\mathbb{F}_q[x] / (f) は体だったことと g_i g_j が0でないことから，g_i g_j が逆元を持つことが分かります．
すると，\Phi_{g_i}^f \Phi_{(g_i g_j)^{-1}}^f \Phi_{g_j}^f の (1, 1) 成分は，\ell \times \ell 単位行列 I_{\ell} の (1, 1) 成分と等しくなり，それは1ですが，\Phi_{g_i}^f \Phi_g^f \Phi_{g_j}^f の (1, 1) 成分は0，という条件に矛盾します．
上記の補足
\Phi_{g_i}^f \Phi_{(g_i g_j)^{-1}}^f \Phi_{g_j}^f の (1, 1) 成分は，\ell \times \ell 単位行列 I_{\ell} の (1, 1) 成分と等しくなり，の部分についてです．つまり，\Phi_{g_i}^f \Phi_{(g_i g_j)^{-1}}^f \Phi_{g_j}^f = I_{\ell} です．
ここで，前回のQR-UOV 理解ログ 3/7「多項式行列」 の補題を思い出すと，\Psi_{g_1}^f \Psi_{g_2}^f = \Psi_{g_1 g_2}^f でした．すると，\Phi_{g_i}^f \Phi_{(g_i g_j)^{-1}}^f \Phi_{g_j}^f = \Phi_{g_i (g_i g_j)^{-1} g_j}^f が成り立ちます．このとき，(g_i g_j)^{-1} = g_j^{-1} g_i^{-1} ですが，\mathbb{F}_q[x] / (f) は可換（\mathbb{F}_q が可換かつ多項式のかける順番は入れ替えられるため）なので，g_j^{-1} g_i^{-1} = g_i^{-1} g_j^{-1} です．よって，g_i (g_i g_j)^{-1} g_j = g_i g_i^{-1} g_j^{-1} g_j = 1 ですから，\Phi_{g_i}^f \Phi_{(g_i g_j)^{-1}}^f \Phi_{g_j}^f = \Phi_1^f = I_{\ell} を得ます．
本当にここの議論は明らかなのか・・・？
よって，示されました．
つまり，暗号化方式に用いる f は既約であることが望ましい，ということになります．
次回から，やっと，QR-UOV 方式の定義に入っていきます．
今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！
Discussion