前回からの続きです．きっちりやろうとすると，めんどくさい議論が多いです・・・．
QR-UOV 理解ログ 1/7
全７回通しでの目次
第１回
- 本論文全体の流れ
- MQ問題
- 多変数多項式暗号署名方式
- UOV署名方式
第２回
- 巡回行列と逆巡回行列
- BAC-UOV 署名方式
- BAC-UOV への Structual Attack
第３回
第４回
第５回
第６回
第７回
突貫で書いてしまった部分もあるので，大いに誤りを含む可能性があります．誤字・脱字レベルでも構いませんので，ご指摘ください．
また，予告なしに内容の加筆や構成の変更を行うことがありますが，読みやすくするためのものですので，ご容赦ください
巡回行列と逆巡回行列
BAC-UOV 署名方式の準備として，巡回行列と逆巡回行列を導入します．早速定義を見て見ましょう．
\underline{\mathrm{Def(巡回行列と逆巡回行列)}}
長さが \ell のベクトル a = (a_0, \cdots, a_{\ell - 1}) \in \mathbb{F}_q^{\ell} について，
\begin{align*}
X = \begin{pmatrix}
a_0 & a_1 & \cdots & a_{\ell - 2} & a_{\ell - 1} \\
a_{\ell - 1} & a_0 & \cdots & a_{\ell - 3} & a_{\ell - 2} \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
a_2 & a_3 & \cdots & a_0 & a_1 \\
a_1 & a_2 & \cdots & a_{\ell - 1} & a_0 \\
\end{pmatrix}, \
Y = \begin{pmatrix}
a_0 & a_1 & \cdots & a_{\ell - 2} & a_{\ell - 1} \\
a_1 & a_2 & \cdots & a_{\ell - 1} & a_0 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
a_{\ell - 2} & a_{\ell - 1} & \cdots & a_{\ell - 4} & a_{\ell - 3} \\
a_{\ell - 1} & a_0 & \cdots & a_{\ell - 3} & a_{\ell - 2} \\
\end{pmatrix}
\end{align*}
なる行列 X, Y を与えたとき，X を a の巡回行列，Y を a の逆巡回行列という．
例えば，a = (2, 1, 0, 0, 2) \in \mathbb{F}_3^5 に対して，
\begin{align*}
X = \begin{pmatrix}
2 & 1 & 0 & 0 & 2 \\
2 & 2 & 1 & 0 & 0 \\
0 & 2 & 2 & 1 & 0 \\
0 & 0 & 2 & 2 & 1 \\
1 & 0 & 0 & 2 & 2 \\
\end{pmatrix}, \
Y = \begin{pmatrix}
2 & 1 & 0 & 0 & 2 \\
1 & 0 & 0 & 2 & 2 \\
0 & 0 & 2 & 2 & 1 \\
0 & 2 & 2 & 1 & 0 \\
2 & 2 & 1 & 0 & 0 \\
\end{pmatrix}
\end{align*}
です．そして，巡回行列を部分行列として持つのが，ブロック巡回行列とブロック逆巡回行列です．
\underline{\mathrm{Def(ブロック巡回行列とブロック逆巡回行列)}}
1 \leq i, j \leq N で，X_{i j} が \ell \times \ell の巡回行列のとき，
\begin{align*}
X = \begin{pmatrix}
X_{1 1} & \cdots & X_{1 N} \\
\vdots & \ddots & \vdots \\
X_{N 1} & \cdots & X_{N N}
\end{pmatrix}
\end{align*}
なる \ell N \times \ell N 行列 X をブロック巡回行列という．
また，1 \leq i, j \leq N で，Y_{i j} が \ell \times \ell の逆巡回行列のとき，
\begin{align*}
Y = \begin{pmatrix}
Y_{1 1} & \cdots & Y_{1 N} \\
\vdots & \ddots & \vdots \\
Y_{N 1} & \cdots & Y_{N N}
\end{pmatrix}
\end{align*}
なる \ell N \times \ell N 行列 Y をブロック逆巡回行列という．
X そのものが巡回行列とは限りません．同様に Y そのものが逆巡回行列とは限りません．
そのことは次の具体例からもわかると思います．
a_{11} = (2, 1, 1), \ a_{1 2} = (0, 1, 0), \ a_{21} = (1, 1, 2), \ a_{22} = (2, 2, 0) として，
\begin{align*}
X_{11} = \begin{pmatrix}
2 & 1 & 1 \\
1 & 2 & 1 \\
1 & 1 & 2
\end{pmatrix}, \
Y_{11} = \begin{pmatrix}
2 & 1 & 1 \\
1 & 1 & 2 \\
1 & 2 & 1
\end{pmatrix}
\end{align*}
\begin{align*}
X_{12} = \begin{pmatrix}
0 & 1 & 0 \\
0 & 0 & 1 \\
1 & 0 & 0
\end{pmatrix}, \
Y_{12} = \begin{pmatrix}
0 & 1 & 0 \\
1 & 0 & 0 \\
0 & 0 & 1
\end{pmatrix}
\end{align*}
\begin{align*}
X_{21} = \begin{pmatrix}
1 & 1 & 2 \\
2 & 1 & 1 \\
1 & 2 & 1
\end{pmatrix}, \
Y_{21} = \begin{pmatrix}
1 & 1 & 2 \\
1 & 2 & 1 \\
2 & 1 & 1
\end{pmatrix}
\end{align*}
\begin{align*}
X_{22} = \begin{pmatrix}
2 & 2 & 0 \\
0 & 2 & 2 \\
2 & 0 & 2
\end{pmatrix}, \
Y_{22} = \begin{pmatrix}
2 & 2 & 0 \\
2 & 0 & 2 \\
0 & 2 & 2
\end{pmatrix}
\end{align*}
ですから，
\begin{align*}
X & = \begin{pmatrix}
X_{1 1} & X_{1 2} \\
X_{2 1} & X_{2 2}
\end{pmatrix} = \begin{pmatrix}
2 & 1 & 1 & 0 & 1 & 0 \\
1 & 2 & 1 & 0 & 0 & 1 \\
1 & 1 & 2 & 1 & 0 & 0 \\
1 & 1 & 2 & 2 & 2 & 0 \\
2 & 1 & 1 & 0 & 2 & 2 \\
1 & 2 & 1 & 2 & 0 & 2
\end{pmatrix} \\
Y & = \begin{pmatrix}
Y_{1 1} & Y_{1 2} \\
Y_{2 1} & Y_{2 2}
\end{pmatrix} = \begin{pmatrix}
2 & 1 & 1 & 0 & 1 & 0 \\
1 & 1 & 2 & 1 & 0 & 0 \\
1 & 2 & 1 & 0 & 0 & 1 \\
1 & 1 & 2 & 2 & 2 & 0 \\
1 & 2 & 1 & 2 & 0 & 2 \\
2 & 1 & 1 & 0 & 2 & 2 \\
\end{pmatrix}
\end{align*}
となります．明らかに X は巡回行列ではないですし，Y も逆巡回行列ではありません．
しかし，次の命題が成り立ちます:
\underline{\mathrm{Prop}}
\ell N \times \ell N 行列 X をブロック巡回行列，\ell N \times \ell N 行列 Y をブロック逆巡回行列，とするとき，XY , YX 共にブロック逆巡回行列である．
証明の方針としては，1 \leq s, t \leq N としたとき，X Y の左から s番目・上から t 番目のブロックが逆巡回行列になっていることを示せばOKです．
証明
行列 A の ij 成分を A[i][j] と表すことにします．
XY の ij 成分は \displaystyle \sum_{k = 1}^{\ell N} X[i][k] \cdot Y[k][j] で表せます．このとき，X Y の上から s番目・左から t 番目のブロックが逆巡回行列になっていることを示します．つまり，(s \ell + 1, t \ell + 1) から (s \ell + (\ell - 1), t \ell + (\ell - 1)) までのブロックを確認します．
ここのブロックがブロック逆巡回行列であることを示すには，1 \leq \forall i \leq \ell に対して，次を示せば必要十分です．
\begin{align*}
\begin{cases}
XY[s \ell + 1][t \ell + i] = XY[s \ell + 2][t \ell + (i - 1)] = \cdots = XY[s \ell + i][t \ell + 1] \\
XY[s \ell + i][t \ell + 1] = XY[s \ell + (i + 1)][t \ell + (\ell - 1)] \\
XY[s \ell + (i + 1)][t \ell + (\ell - 1)] = XY[s \ell + (i + 2)][t \ell + (\ell - 2)] = \cdots = XY[s \ell + (\ell - 1)][t \ell + (i + 1)]
\end{cases}
\end{align*}
また，1つ目と3つ目で示すことは本質的に同じなので，1つ目と2つ目を示せばOKです．
ここで，XY[s \ell + 1][t \ell + i] がどう表せるかを考えます．普通に考えたら，
\begin{align*}
\displaystyle
XY[s \ell + 1][t \ell + i] = \sum_{k = 1}^{\ell N} X[s \ell + 1][k] \cdot Y[k][t \ell + i]
\end{align*}
なのですが，X, Y 共にブロック行列なので，ブロック行列の要素に分解しようとします．よって，k の部分を分解すると，
\begin{align*}
\displaystyle
XY[s \ell + 1][t \ell + i] = \sum_{j^{\prime} = 1}^{N} \sum_{j = 1}^{\ell} X_{s + 1, j^{\prime}}[s \ell + 1][j] \cdot Y_{j^{\prime}, t + 1} [j][t \ell + i]
\end{align*}
で表せます．ここで，X_{s + 1, j^{\prime}} は X の上から s + 1 番目・左から j^{\prime} 番目のブロックを表し，Y_{j^{\prime}, t + 1} は Y の上から j^{\prime}番目・左から t + 1 番目のブロックを表します．
ここで，X_{s + 1, j^{\prime}} はブロック巡回行列であり，Y_{j^{\prime}, t + 1} はブロック逆巡回行列なので，
\begin{align*}
\displaystyle
X_{s + 1, j^{\prime}} = \begin{pmatrix}
a_1 & a_2 & \cdots & a_{\ell - 1} & a_{\ell} \\
a_{\ell} & a_1 & \cdots & a_{\ell - 2} & a_{\ell - 1} \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
a_3 & a_4 & \cdots & a_1 & a_2 \\
a_2 & a_3 & \cdots & a_{\ell} & a_1 \\
\end{pmatrix}, \
Y_{j^{\prime}, t + 1} = \begin{pmatrix}
b_1 & b_2 & \cdots & b_{\ell - 1} & b_{\ell} \\
b_2 & b_3 & \cdots & b_{\ell} & b_1 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
b_{\ell - 1} & b_{\ell} & \cdots & b_{\ell - 3} & b_{\ell - 2} \\
b_{\ell} & b_1 & \cdots & b_{\ell - 2} & b_{\ell - 1} \\
\end{pmatrix}
\end{align*}
と表せます（議論のみやすさのために，インデックスを変更していることに注意してください）．
ここで，\displaystyle \sum_{j^{\prime} = 1}^{N} \sum_{j = 1}^{\ell} X_{s + 1, j^{\prime}}[s \ell + 1][j] \cdot Y_{j^{\prime}, t + 1} [j][t \ell + i] の部分をベクトルの内積で考えると，
\begin{align*}
\displaystyle
\sum_{j = 1}^{\ell} X_{s + 1, j^{\prime}}[s \ell + 1][j] \cdot Y_{j^{\prime}, t + 1} [j][t \ell + i] = (a_1, a_2, \cdots, a_{\ell}) \cdot (b_i, b_{i + 1}, \cdots, b_{\ell}, b_1, \cdots, b_{i - 1})
\end{align*}
と表せます．このとき，(a_1, a_2, \cdots, a_{\ell}) \cdot (b_i, b_{i + 1}, \cdots, b_{\ell}, b_1, \cdots, b_{i - 1}) = (a_2, \cdots, a_{\ell}, a_1) \cdot (b_{i + 1}, \cdots, b_{\ell}, b_1, \cdots, b_{i - 1}, b_i) です．これは，２つのベクトルのインデックスを同時に1だけ左に動かしただけだからです．
実際に
\begin{align*}
\displaystyle
(a_1, \cdots, a_{\ell - 1}, a_{\ell}) \cdot (b_i, \cdots, b_{\ell}, b_1, \cdots, b_{i - 2}, b_{i - 1}) & = a_1 b_i + \cdots + a_{\ell - i + 1} b_{\ell} + a_{\ell - i + 2} b_1 + \cdots + a_{\ell - 1} b_{i - 2} + a_{\ell} b_{i - 1} \\
(a_{\ell}, a_1, \cdots, a_{\ell - 1}) \cdot (b_{i - 1}, b_i, \cdots, b_{\ell}, b_1, \cdots, b_{i - 2}) & = a_{\ell} b_{i - 1} + a_1 b_i + \cdots + a_{\ell - i + 1} b_{\ell} + a_{\ell - i + 2} b_1 + \cdots + a_{\ell - 1} b_{i - 2} \\
& = a_1 b_i + \cdots + a_{\ell - i + 1} b_{\ell} + a_{\ell - i + 2} b_1 + \cdots + a_{\ell - 1} b_{i - 2} + a_{\ell} b_{i - 1}
\end{align*}
です．ここで，(a_1, a_2, \cdots, a_{\ell}) \cdot (b_i, b_{i + 1}, \cdots, b_{\ell}, b_1, \cdots, b_{i - 1}) = \sum_{j = 1}^{\ell} X_{s + 1, j^{\prime}}[s \ell + 1][j] \cdot Y_{j^{\prime}, t + 1} [j][t \ell + i] を考えると，(a_{\ell}, a_1, \cdots, a_{\ell - 1}) \cdot (b_{i - 1}, b_i, \cdots, b_{\ell}, b_1, \cdots, b_{i - 2}) = \sum_{j = 1}^{\ell} X_{s + 1, j^{\prime}}[s \ell + 2][j] \cdot Y_{j^{\prime}, t + 1} [j][t \ell + i - 1] が成り立ちます．
ここで，\displaystyle \sum_{j = 1}^{\ell} X_{s + 1, j^{\prime}}[s \ell + 1][j] \cdot Y_{j^{\prime}, t + 1} [j][t \ell + i] = XY[s \ell + 1][t \ell + i] だったことを思い出すと，\displaystyle \sum_{j = 1}^{\ell} X_{s + 1, j^{\prime}}[s \ell + 2][j] \cdot Y_{j^{\prime}, t + 1} [j][t \ell + (i - 1)] = XY[s \ell + 2][t \ell + (i - 1)] です．
同様にインデックスを同じだけずらすことを考えると，
\begin{align*}
XY[s \ell + 1][t \ell + i] = XY[s \ell + 2][t \ell + (i - 1)] = \cdots = XY[s \ell + i][t \ell + 1]
\end{align*}
まで成り立ちます．また，そこから更にインデックスを1ずらすと
\begin{align*}
XY[s \ell + i][t \ell + 1] = XY[s \ell + (i + 1)][t \ell + (\ell - 1)]
\end{align*}
を得ます．
以上より示されました．
BAC-UOV 署名方式
BAC-UOV 署名方式は，UOV署名方式の変種です．BAC は Block-Anti-Circulant つまり，ブロック逆巡回の略称です．
大雑把には，v 個の vineger 変数と m 個の oil 変数があって，v, m は共に \ell で割り切れるとします．\mathcal{F} = \{ f_1, f_2, \cdots, f_m \} の任意の f_i を2次形式で表した F_i がサイズ \ell のブロック逆巡回行列であり，\mathcal{S} がサイズ \ell のブロック巡回行列であることを言います．
定式化すると，次のようになります:
\underline{\mathrm{Def(BAC-UOV署名方式)}}
n, m, v, q を正整数として，\mathbb{F}_q なる有限体を考える．ただし，v < n であり，n = v + m を満たすものとする．
x = (x_1, \cdots, x_v, x_{v + 1}, \cdots, x_n) \in \mathbb{F}_q^n をとったとき，x_1, \cdots, x_v を vinegar 変数，x_{v + 1}, \cdots, x_n を oil 変数，という．
鍵生成アルゴリズム KeyGen(1^n) \mapsto (sk, pk)
セキュリティパラメタ n を引数として，秘密鍵 SK = (\mathcal{F} : \mathbb{F}_q^n \rightarrow \mathbb{F}_q^m, \mathcal{S} : \mathbb{F}_q^n \rightarrow \mathbb{F}_q^n) とそれに対応する公開鍵 pk = \mathcal{P} : \mathbb{F}_q^n \rightarrow \mathbb{F}_q^m を返す関数
具体的には，\mathcal{F} = (f_1, \cdots, f_m) : \mathbb{F}_q^n \rightarrow \mathbb{F}_q^m を取る．ここで，1 \leq \forall k \leq n に対して，
\begin{align*}
\displaystyle
f_k(x_1, \cdots, x_n) = \sum_{i = 1}^n \sum_{j = 1}^v \alpha_{i, j}^{(k)} x_i x_j
\end{align*}
を満たすものとする．\alpha_{i, j}^{(k)} \in \mathbb{F}_q である．
また，f_k(x_1, \cdots, x_n) = x F_k x^t を満たす対称行列 F_i はサイズ \ell のブロック逆巡回行列とする．
\mathcal{S} : \mathbb{F}_q^n \rightarrow \mathbb{F}_q^n はそのような可逆写像をランダムに取る．つまり，\mathbb{F}_q 上の n \times n 正則行列全体から \mathcal{S} を一様分布に従って取る．
また，\mathcal{S} はサイズ \ell のブロック巡回行列とする．
\mathcal{P} : \mathbb{F}_q^n \rightarrow \mathbb{F}_q^m は \mathcal{P} = \mathcal{F} \circ \mathcal{S} として，計算する．
署名アルゴリズム Sign (sk, M) \mapsto \sigma
秘密鍵 sk とメッセージ M \in \mathbb{F}_q^n を引数として，署名値 \sigma = \mathcal{S}^{-1}(x) \in \mathbb{F}_q^m を出力する．ここで，x は \mathcal{F}(x) = M の解である．
具体的には，次の手続きで x を得る:
-
a_1, \cdots, a_v \in \mathbb{F}_q をランダムに取る
-
x_{v + 1}, \cdots, x_n についての方程式 F(a_1, \cdots, a_v, x_{v + 1}, \cdots, x_n) = M を解く
- 2の方程式に解が存在すれば，その１つを x とし，解が存在しなければ，1に戻る
検証アルゴリズム Ver (pk, \sigma, M) \mapsto b
公開鍵 pk と署名値 \sigma，メッセージ M を引数として，P(\sigma) = M が成り立つなら b = 1，そうでないなら b = 0 を出力する．
\mathcal{F} = (f_1, \cdots, f_m) に対応して，\mathcal{P} = (p_1, \cdots, p_m) と置くと，\mathcal{P} = \mathcal{F} \circ S ですから，p_i = S^T f_i S でした．
参照：QR-UOV 理解ログ 1/7 「UOV署名方式」
S はブロック巡回行列で，そのとき，S^t もブロック巡回行列です．f_i はブロック逆巡回行列なので，S^t f_i はブロック逆巡回行列です（前節の命題から，ブロック巡回行列とブロック逆巡回行列の積はブロック逆巡回行列）．
すると，(S^t f_i) S はブロック逆巡回行列です（前節の命題から，ブロック逆巡回行列とブロック巡回行列の積はブロック逆巡回行列）．
よって，p_i はブロック逆巡回行列です．
BAC-UOV への Structual Attack
ここでは，BAC-UOV 方式への攻撃を紹介します．
まず，L_{\ell} という \ell \times \ell 行列を
- 1行目と1列目は全て1
-
(2, 2), (3, 3), \cdots , (\ell, \ell) なる対角成分は全て-1
- それ以外は全て0
とします．つまり，次のような形です:
\begin{align*}
L_{\ell} = \begin{pmatrix}
1 & 1 & \cdots & 1 \\
1 & -1 & & \\
\vdots & & \ddots & \text{\huge{0}} \\
1 & \text{\huge{0}} & -1
\end{pmatrix}
\end{align*}
ここで，Y を 長さが \ell のベクトル a = (a_0, \cdots, a_{\ell - 1}) \in \mathbb{F}_q^{\ell} に関する逆巡回行列，つまり，
\begin{align*}
Y = \begin{pmatrix}
a_0 & a_1 & \cdots & a_{\ell - 2} & a_{\ell - 1} \\
a_1 & a_2 & \cdots & a_{\ell - 1} & a_0 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
a_{\ell - 2} & a_{\ell - 1} & \cdots & a_{\ell - 4} & a_{\ell - 3} \\
a_{\ell - 1} & a_0 & \cdots & a_{\ell - 3} & a_{\ell - 2} \\
\end{pmatrix}
\end{align*}
とすると，
\begin{align*}
L_{\ell}^t Y L_{\ell} & =
\begin{pmatrix}
1 & 1 & \cdots & 1 \\
1 & -1 & & \\
\vdots & & \ddots & \text{\huge{0}} \\
1 & \text{\huge{0}} & & -1
\end{pmatrix}
\begin{pmatrix}
a_0 & a_1 & \cdots & a_{\ell - 2} & a_{\ell - 1} \\
a_1 & a_2 & \cdots & a_{\ell - 1} & a_0 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
a_{\ell - 2} & a_{\ell - 1} & \cdots & a_{\ell - 4} & a_{\ell - 3} \\
a_{\ell - 1} & a_0 & \cdots & a_{\ell - 3} & a_{\ell - 2} \\
\end{pmatrix}
\begin{pmatrix}
1 & 1 & \cdots & 1 \\
1 & -1 & & \\
\vdots & & \ddots & \text{\huge{0}} \\
1 & \text{\huge{0}} & & -1
\end{pmatrix} \\
& = \begin{pmatrix}
\sum_{i = 0}^{\ell - 1} a_i & \sum_{i = 0}^{\ell - 1} a_i & \cdots & \sum_{i = 0}^{\ell - 1} a_i \\
a_0 - a_1 & a_1 - a_2 & \cdots & a_{\ell - 1} - a_0 \\
\vdots & \vdots & \ddots & \vdots \\
a_0 - a_{\ell - 1} & a_1 - a_0 & \cdots & a_{\ell - 1} - a_{\ell - 2}
\end{pmatrix}
\begin{pmatrix}
1 & 1 & \cdots & 1 \\
1 & -1 & & \\
\vdots & & \ddots & \text{\huge{0}} \\
1 & \text{\huge{0}} & & -1
\end{pmatrix} \\
& = \begin{pmatrix}
\ell \sum_{i = 0}^{\ell - 1} a_i & 0 & \cdots & 0 \\
0 & (a_0 - a_1) - (a_1 - a_2) & \cdots & (a_0 - a_1) - (a_{\ell - 1} - a_0) \\
\vdots & \vdots & \ddots & \vdots \\
0 & (a_0 - a_{\ell - 1}) - (a_1 - a_0) & \cdots & (a_0 - a_{\ell - 1}) - (a_{\ell - 1} - a_{\ell - 2})
\end{pmatrix}
\end{align*}
で表せます．
上記の逆巡回行列での議論を，ブロック逆巡回行列へと拡張します．このとき，L_{\ell} を N 個対角に並べた行列 L_{\ell}^{(N)} を考えます．つまり，
\begin{align*}
L_{\ell}^{(N)} =
\begin{pmatrix}
L_{\ell} & & \\
& \ddots & \text{\huge{0}} \\
\text{\huge{0}} & & L_{\ell} \\
\end{pmatrix}
\end{align*}
とします．n = N \ell として，サイズ \ell の n \times n のブロック逆巡回行列 B を考えます．(L_{\ell}^{(N)})^t B L_{\ell}^{(N)} = L_{\ell}^{(N)} B L_{\ell}^{(N)} については，
\begin{align*}
\displaystyle
L_{\ell}^{(N)} B L_{\ell}^{(N)} &=
\begin{pmatrix}
\begin{pmatrix}
\ell \sum_{i = 0}^{\ell - 1} a_{i, 0} & 0 & \cdots & 0 \\
0 & (a_{0, 0} - a_{1, 0}) - (a_{1, 0} - a_{2, 0}) & \cdots & (a_{0, 0} - a_{1, 0}) - (a_{\ell - 1, 0} - a_{0, 0}) \\
\vdots & \vdots & \ddots & \vdots \\
0 & (a_{0, 0} - a_{\ell - 1, 0}) - (a_{1, 0} - a_{0, 0}) & \cdots & (a_{0, 0} - a_{\ell - 1, 0}) - (a_{\ell - 1, 0} - a_{\ell - 2, 0})
\end{pmatrix}
& \text{\huge{0}} & \cdots & \text{\huge{0}} \\
\text{\huge{0}} & \begin{pmatrix}
\ell \sum_{i = 0}^{\ell - 1} a_{i, 1} & 0 & \cdots & 0 \\
0 & (a_{0, 1} - a_{1, 1}) - (a_{1, 1} - a_{2, 1}) & \cdots & (a_{0, 1} - a_{1, 1}) - (a_{\ell - 1, 1} - a_{0, 1}) \\
\vdots & \vdots & \ddots & \vdots \\
0 & (a_{0, 1} - a_{\ell - 1, 1}) - (a_{1, 1} - a_{0, 1}) & \cdots & (a_{0, 1} - a_{\ell - 1, 1}) - (a_{\ell - 1, 1} - a_{\ell - 2, 1})
\end{pmatrix}
& \cdots & \text{\huge{0}} \\
\vdots & \vdots & \ddots & \vdots \\
\text{\huge{0}} & \text{\huge{0}} & \cdots &
\begin{pmatrix}
\ell \sum_{i = 0}^{\ell - 1} a_{i, \ell - 1} & 0 & \cdots & 0 \\
0 & (a_{0, \ell - 1} - a_{1, \ell - 1}) - (a_{1, \ell - 1} - a_{2, \ell - 1}) & \cdots & (a_{0, \ell - 1} - a_{1, \ell - 1}) - (a_{\ell - 1, \ell - 1} - a_{0, \ell - 1}) \\
\vdots & \vdots & \ddots & \vdots \\
0 & (a_{0, \ell - 1} - a_{\ell - 1, \ell - 1}) - (a_{1, \ell - 1} - a_{0, \ell - 1}) & \cdots & (a_{0, \ell - 1} - a_{\ell - 1, \ell - 1}) - (a_{\ell - 1, \ell - 1} - a_{\ell - 2, \ell - 1})
\end{pmatrix}
\end{pmatrix}
\end{align*}
なる形になります（各ブロックは全て \ell \times \ell 行列です）．
すると，ある置換行列 L^{\prime} を使って，\ell \sum_{i = 0}^{\ell - 1} a_{j, \ell - 1} 成分を左上の N \times N ブロックに配置することができます．よって，(L_{\ell}^{(N)} L^{\prime})^t B (L_{\ell}^{(N)} L^{\prime}) は左上が N \times N の部分行列，右下が (\ell - 1) N \times (\ell - 1) N の部分行列，それ以外は N \times (\ell - 1) N の零行列（またはその転置）で表せます．
BAC-UOV 署名方式において，\mathcal{P} = (p_1, \cdots, p_m) の各 p_i はブロック逆巡回行列だったので，L_{\ell}^{(N)} とある置換行列 L^{\prime} を使って上記の形に直すことができます．
Structual Attack とは，上記の形にして，\mathcal{P}(x) = m なる方程式を解くことです．この攻撃法は，変更前と比べて計算量が20%削減できることが知られています．
今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！
Discussion