個人的に気になっている QR-UOV について理解したことをまとめていきます．
H. Furue, Y. Ikematsu, Y. Kiyomura and T. Takagi: "A New Variant of Unbalanced Oil and Vinegar Using Quotient Ring: QR-UOV", Asiacrypt’21, LNCS 13093 (2021), 187–217.
Chapter4の構成までを目標とします．
また，上記の初等的な構成として
H. Yasufumi: "An elementary construction of QR-UOV", Cryptology ePrint Archive, 2022.
も余裕があれば，解説します．
以下では，初めの論文を「QR-UOV 原著論文」・後の論文を「QR-UOV 初等的構成論文」と呼ぶことにします．
大雑把な流れは以下のとおりです:
第１回：QR-UOV 原著論文 2.1 2.2
第２回：QR-UOV 原著論文 2.3 2.4
第３回：QR-UOV 原著論文 3.1
第４回：QR-UOV 原著論文 3.1 3.2
第５回：QR-UOV 原著論文 4.1
第６回：QR-UOV 原著論文 4.2
第７回：QR-UOV 初等的構成論文
突貫で書いてしまった部分もあるので，大いに誤りを含む可能性があります．誤字・脱字レベルでも構いませんので，ご指摘ください．
また，予告なしに内容の加筆や構成の変更を行うことがありますが，読みやすくするためのものですので，ご容赦ください
全７回通しでの目次
第１回
- 本論文全体の流れ
- MQ問題
- 多変数多項式暗号署名方式
- UOV署名方式
第２回
第３回
第４回
第５回
第６回
第７回
本論文全体の流れ
- どういう背景や課題・モチベーションがあって，
- どのようなアイディアのもとで，
- どのような結果が得られたのか
を整理します．
背景・課題
耐量子計算機暗号（と考えられている）多変数多項式暗号の署名方式でUOV方式というものがあります．初めて提案されたのは1999年でもう20年以上前のことなのですが，公開鍵のサイズが大きいという課題があります．
アイディア
剰余環の要素を成分とするブロック行列によって，公開鍵のサイズを削減
結果
NIST PQC標準化プロジェクトでの security level3 での公開鍵のサイズが 85.8KB であり，第3Roundに残っている Rainbow と比較しても，1/3程度のサイズになりました
それらを元に各章を整理すると，次のようになります:
1章：イントロ
2章：前提知識
3章：剰余環の多項式行列
4章：QR-UOV 方式の提案
5章：Security Analysis
6章：提案パラメタ
7章：まとめ
つまり，2章と3章までが「準備段階」で，４章が一番言いたいことになります．
５章以降は扱わないので，４章の提案方式までを確認することになります．
MQ問題
何かしらの公開鍵暗号方式・電子署名方式を構成したいなら，NP困難な問題が必要になります．そこで，今回はMQ問題というものを使います．MQとは Multivariate Quadratic の略称で，つまり多変数の連立２次方程式系を考えます．
\underline{\mathrm{Def(MQ問題)}}
n, m, q を正整数として，\mathbb{F}_q なる有限体を考える．
\mathbb{F}_q 上の m 個の n 変数２次多項式系 \mathcal{P} = (p_1(x_1, \cdots, x_n), \cdots, p_m(x_1, \cdots, x_n)) と y \in \mathbb{F}_q^m が与えられたとき，P(x) = y なる x \in \mathbb{F}_q^n を求めよ．
MQ問題は n \sim m の際にNP困難であることが知られています（どのぐらいの近似を指すのかは要確認）．
後で出てきますが，\mathcal{P} とは，\mathcal{P} : \mathbb{F}_q^n \rightarrow \mathbb{F}_q^m なる写像と見ることができます．
これは，P(x) = y を見ると納得しやすいかと思います．より詳しく，もし，1次方程式系であれば，1 \leq \forall i \leq m に対して，
\begin{align*}
p_i(x_1, \cdots, x_n) = p_{i1} x_1 + p_{i2} x_2 + \cdots + p_{in} x_n \hspace{10pt} p_{i1}, p_{i2}, \cdots , p_{in} \in \mathbb{F}_q
\end{align*}
なる多項式を考えて，
\begin{align*}
p_{i1} x_1 + p_{i2} x_2 + \cdots + p_{in} x_n = y_i \hspace{10pt} y_i \in \mathbb{F}_q
\end{align*}
なる方程式を並べることで，
\begin{align*}
\begin{cases}
p_{11} x_1 + p_{12} x_2 + \cdots + p_{1n} x_n = y_1 \\
p_{21} x_1 + p_{22} x_2 + \cdots + p_{2n} x_n = y_2 \\
\vdots \\
p_{m1} x_1 + p_{m2} x_2 + \cdots + p_{mn} x_n = y_m \\
\end{cases}
\end{align*}
を得ます．すると，
\begin{align*}
\begin{pmatrix}
p_{11} & p_{12} & \cdots & p_{1n} \\
p_{21} & p_{22} & \cdots & p_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
p_{m1} & p_{m2} & \cdots & p_{mn} \\
\end{pmatrix}
\begin{pmatrix}
x_1 \\
x_2 \\
\vdots \\
x_n \\
\end{pmatrix}
=
\begin{pmatrix}
y_1 \\
y_2 \\
\vdots \\
y_m \\
\end{pmatrix}
\end{align*}
という表示を得ます．よって，
\begin{align*}
\mathcal{P}
\begin{pmatrix}
x_1 \\
x_2 \\
\vdots \\
x_n \\
\end{pmatrix}
=
\begin{pmatrix}
y_1 \\
y_2 \\
\vdots \\
y_m \\
\end{pmatrix}
\end{align*}
と考えることで，\mathcal{P} : \mathbb{F}_q^n \rightarrow \mathbb{F}_q^m とみなすことができます．
以上の議論は2次方程式系でも同じです．
多変数多項式暗号署名方式
初めに電子署名方式の定義を紹介します．
メッセージとは，気持ちとしては暗号文のことです．
メッセージ，なので m という記号を使いたいのですが，\mathcal{F} : \mathbb{F}_q^n \rightarrow \mathbb{F}_q^m での次数 m と記号がバッティングするので，メッセージは M で表します．
\underline{\mathrm{Def(電子署名方式)}}
電子署名方式とは，次の3つ組のアルゴリズム(KeyGen, Sign, Ver)のこと:
-
鍵生成アルゴリズム KeyGen (1^n) \mapsto (pk, sk)
セキュリティパラメタ n を引数にとって，公開鍵 pk とそれに対応する秘密鍵 sk の組を出力する．
-
署名アルゴリズム Sign (sk, M) \mapsto \sigma
秘密鍵 sk とメッセージ M を受け取って，署名値 \sigma を出力する．
-
検証アルゴリズム Ver (pk, \sigma, M) \mapsto b
公開鍵 pk と署名値 \sigma，メッセージ M を受け取って，b \in \{ 0, 1 \} を返す．b = 1 なら有効な署名であり，b = 0 なら無効な署名とする．
Ver は verify の略です．
また，暗号化のときと同じく，（鍵が適切な定義域であれば）\mathrm{Ver}(pk, \mathrm{Sign}(sk, M), M) = 1 が成り立ちます．これが，電子署名方式が正当であることの定義です（暗号化のときと同じ）．
さて，MQ問題に対して，次の写像の３つ組 (\mathcal{F}, \mathcal{S}, \mathcal{T}) を取ります．
\mathcal{F} : \mathbb{F}_q^n \rightarrow \mathbb{F}_q^m
\mathcal{S} : \mathbb{F}_q^n \rightarrow \mathbb{F}_q^n で可逆かつ線型
\mathcal{T} : \mathbb{F}_q^m \rightarrow \mathbb{F}_q^m で可逆かつ線型
そして，これらはMQ問題の \mathcal{P} に対して，\mathcal{P} = \mathcal{T} \circ \mathcal{F} \circ \mathcal{S} とします．
＊\mathcal{S}, \mathcal{T} が可逆とは，それぞれ n \times n 行列，m \times m 行列として逆行列を持つ，ということです
イメージとしては，\mathcal{P} が公開鍵用の多変数多項式系で，\mathcal{F} が秘密鍵用の多変数多項式系であり，\mathcal{S}, \mathcal{T} でこれらを行き来できる，という感じです．
F の可逆性について
論文では，\mathcal{F} が可逆という条件がついています．n \times m 行列 \mathcal{F} が可逆とは，「ある m \times n 行列 A があって，\mathcal{F} A =I_n かつ A \mathcal{F} =I_m が成り立つ」こと，と考えられます．なんですが，n, m の選び方によっては，このような \mathcal{F} が存在しないこともあります．
なので，以降では，\mathcal{F} の可逆性は仮定せずに議論を進めます．より一般的な形，ということで．
線型性について
\mathcal{S}, \mathcal{T} の線型性はどこに効いてくるかについてです．\mathcal{P} として，
\begin{align*}
\begin{pmatrix}
p_{11} & p_{12} & \cdots & p_{1n} \\
p_{21} & p_{22} & \cdots & p_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
p_{m1} & p_{m2} & \cdots & p_{mn} \\
\end{pmatrix}
\begin{pmatrix}
x_1 \\
x_2 \\
\vdots \\
x_n \\
\end{pmatrix}
=
\begin{pmatrix}
y_1 \\
y_2 \\
\vdots \\
y_m \\
\end{pmatrix}
\end{align*}
のように取るとします．また，\mathcal{F} として，
\begin{align*}
\begin{pmatrix}
f_{11} & f_{12} & \cdots & f_{1n} \\
f_{21} & f_{22} & \cdots & f_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
f_{m1} & f_{m2} & \cdots & f_{mn} \\
\end{pmatrix}
\begin{pmatrix}
x^{\prime}_1 \\
x^{\prime}_2 \\
\vdots \\
x^{\prime}_n \\
\end{pmatrix}
=
\begin{pmatrix}
y^{\prime}_1 \\
y^{\prime}_2 \\
\vdots \\
y^{\prime}_m \\
\end{pmatrix}
\end{align*}
のように取ります．もちろん，\mathcal{F} は \mathbb{F}_q 上の m \times n 行列で，(x^{\prime}_1, x^{\prime}_2, \cdots, x^{\prime}_n) と (y^{\prime}_1, y^{\prime}_2, \cdots, y^{\prime}_m) も共に \mathbb{F}_q 上のベクトルです．
すると，
\begin{align*}
\mathcal{S}
\begin{pmatrix}
x_1 \\
x_2 \\
\vdots \\
x_n \\
\end{pmatrix}
=
\begin{pmatrix}
x^{\prime}_1 \\
x^{\prime}_2 \\
\vdots \\
x^{\prime}_n \\
\end{pmatrix}
\end{align*}
と
\begin{align*}
\mathcal{T}
\begin{pmatrix}
y^{\prime}_1 \\
y^{\prime}_2 \\
\vdots \\
y^{\prime}_m \\
\end{pmatrix}
=
\begin{pmatrix}
y_1 \\
y_2 \\
\vdots \\
y_m \\
\end{pmatrix}
\end{align*}
に注意すると，\mathcal{P}, \mathcal{F} では方程式系が成り立っていないといけないので，線型性が必要となります．
ここで，抽象的に多変数多項式暗号の暗号化方式・署名方式をまとめます．
平文で m という記号を使いたいのですが，\mathcal{F} : \mathbb{F}_q^n \rightarrow \mathbb{F}_q^m での次数 m と記号がバッティングするので，平文は \mu で表します．
\underline{\mathrm{Def(多変数多項式暗号の暗号化方式)}}
-
鍵生成アルゴリズム KeyGen (1^n) \mapsto(pk, sk)
セキュリティパラメタ n を引数として，公開鍵 pk = \mathcal{P} : \mathbb{F}_q^n \rightarrow \mathbb{F}_q^m と 秘密鍵 sk = (\mathcal{F} : \mathbb{F}_q^n \rightarrow \mathbb{F}_q^m, \mathcal{S} : \mathbb{F}_q^n \rightarrow \mathbb{F}_q^n, \mathcal{T} : \mathbb{F}_q^m \rightarrow \mathbb{F}_q^m) を出力する．
-
暗号化アルゴリズム Enc (pk, \mu) \mapsto c
公開鍵 pk と平文 \mu \in \mathbb{F}_q^n を引数として，暗号文 c = \mathcal{P} \mu \in \mathbb{F}_q^m を出力する．
-
復号化アルゴリズム Dec (sk, c) \mapsto \mu
秘密鍵 sk と暗号文 c \in \mathbb{F}_q^m を引数として，平文 \mu \in \mathbb{F}_q^m を出力する．
具体的には，\mathcal{F}(x) = \mathcal{T}^{-1}(c) の解 x \in \mathbb{F}_q^n をとって，\mu = \mathcal{S}^{-1}(x) とする．
＊復号化アルゴリズムが必ず成功するとは限らない（必ず \mu を出力するとは限らない，失敗値 \perp を出力することもある）のですが，今回は細かいことは抜きにします．
\mathcal{F}(x) = \mathcal{T}^{-1}(c) の解 x \in \mathbb{F}_q^n が一意に存在すれば，暗号化の正当性が示されます．
解の一意性
異なる x^{\prime}, y^{\prime} \in \mathbb{F}_q^n であって，S(x^{\prime}) = x, S(y^{\prime}) = y \in \mathbb{F}_q^n と置いたとき，\mathcal{F}(x) = \mathcal{F}(y) = \mathcal{T}^{-1}(c) とします．つまり，\mathcal{F}(z) = \mathcal{T}^{-1}(c) なる解 z \in \mathbb{F}_q^n として，x, y の両方がありうるとすると，\mathcal{T} \circ \mathcal{F} \circ \mathcal{S}(x^{\prime}) = c にもかかわらず，復号する際に y に戻ってきて，復号失敗，ということが起こり得ます．よって，\mathcal{F}(x) = \mathcal{T}^{-1}(c) の解 x \in \mathbb{F}_q^n は一意であることが必要条件です．
続いて署名方式です．
\underline{\mathrm{Def(多変数多項式暗号の署名方式)}}
-
鍵生成アルゴリズム KeyGen (1^n) \mapsto(pk, sk)
セキュリティパラメタ n を引数として，公開鍵 pk = \mathcal{P} : \mathbb{F}_q^n \rightarrow \mathbb{F}_q^m と 秘密鍵 sk = \mathcal{F} : \mathbb{F}_q^n \rightarrow \mathbb{F}_q^m を出力する．
-
署名アルゴリズム Sign (sk, M) \mapsto \sigma
秘密鍵 sk とメッセージ M \in \mathbb{F}_q^n を引数として，署名値 \sigma \in \mathbb{F}_q^m を出力する．
具体的には，\mathcal{F}(y) = \mathcal{T}^{-1}(M) の解 y \in \mathbb{F}_q^n をとって，\sigma = \mathcal{S}^{-1}(y) とする．
-
検証アルゴリズム Ver (pk, \sigma, M) \mapsto b
公開鍵 pk と署名値 \sigma，メッセージ M を引数として，P(\sigma) = M が成り立つなら b = 1，そうでないなら b = 0 を出力する．
大雑把に見ると，署名方式は暗号化方式の「逆」をやっていることが分かりますね．
具体例を見ていきましょう．ここでは，q = 3, n = 3, m = 2 とします．
そして，\mathcal{S} = \begin{pmatrix} 0 & 0 & 1 \\ 2 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}, \ \mathcal{F} = \begin{pmatrix} 0 & 2 & 1 \\ 1 & 1 & 1 \end{pmatrix}, \ \mathcal{T} = \begin{pmatrix} 2 & 1 \\ 0 & 1 \end{pmatrix} とします．このとき，\mathcal{S}^{-1} = \begin{pmatrix} 0 & 2 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix} ですし，\displaystyle \mathcal{T}^{-1} = \frac{1}{2} \begin{pmatrix} 1 & 2 \\ 0 & 2 \end{pmatrix} = \begin{pmatrix} 2 & 1 \\ 0 & 1 \end{pmatrix} です（\mathbb{F}_q = \mathbb{F}_3 上の演算であることに注意してください）．
よって，
\begin{align*}
\mathcal{P} & = \mathcal{T} \circ \mathcal{F} \circ \mathcal{S} \\
& = \begin{pmatrix} 2 & 1 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 0 & 2 & 1 \\ 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} 0 & 0 & 1 \\ 2 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix} \\
& = \begin{pmatrix} 1 & 2 & 0 \\ 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} 0 & 0 & 1 \\ 2 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix} \\
& = \begin{pmatrix} 1 & 0 & 1 \\ 2 & 1 & 1 \end{pmatrix}
\end{align*}
が公開鍵です．
x = (2, 0, 1) \in \mathbb{F}_3 を平文とすると，c = \mathcal{P}(x) = (0, 2) です．
ここから復号を考えると，\mathcal{F}(z) = \mathcal{T}^{-1}(c) = (2, 2)^t を解けばよく，つまり，
\begin{align*}
\begin{pmatrix} 0 & 2 & 1 \\ 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} z_1 \\ z_2 \\ z_3 \end{pmatrix} = \begin{pmatrix} 2 \\ 2 \end{pmatrix}
\end{align*}
の解 z = (z_1, z_2, z_3) を考えます．(0, 0, 2), (1, 1, 0), (2, 2, 1) が解になります（計算機で回せばOK）．このとき何らかの付加情報（トラップドア的な）があって，z= (1, 1, 0) に一意に定まったとします．
すると，\mathcal{S}^{-1}(z) = (2, 0, 1) で，無事に復号できました．
署名についても同様です．
UOV署名方式
さて，ここから具体的なセッティングに入って行きます．
\underline{\mathrm{Def(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 である．
\mathcal{S} : \mathbb{F}_q^n \rightarrow \mathbb{F}_q^n はそのような可逆写像をランダムに取る．つまり，\mathbb{F}_q 上の n \times n 正則行列全体から \mathcal{S} を一様分布に従って取る．
\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 を出力する．
鍵生成アルゴリズムでの f_k の条件は，2次方程式系を表すけど，全体ではないことを表しています．つまり，2つある変数のうち，前者は x_1, \cdots, x_n 全体を走るけど，後者は vinegar 変数のみ x_1, \cdots, x_v までを走ることを条件としています．
上記でなぜ vinegar 変数のみまでに制限しているのかというと，署名アルゴリズムで F(a_1, \cdots, a_v, x_{v + 1}, \cdots, x_n) とした際に，どちらかの変数は必ず既知になるように調整しているからです．そうすると，実質1変数の方程式になるので，解きやすいからです（たぶん）．
ここで，2次形式 \displaystyle f_k(x_1, \cdots, x_n) = \sum_{i = 1}^n \sum_{j = 1}^v \alpha_{i, j}^{(k)} x_i x_j を行列表示します．x = (x_1, \cdots, x_n) とすると，
\begin{align*}
\displaystyle f_k(x) & = \sum_{i = 1}^n \sum_{j = 1}^v \alpha_{i, j}^{(k)} x_i x_j \\
& = \begin{pmatrix} x_1 & x_2 & \cdots & x_n \end{pmatrix} \begin{pmatrix} \alpha_{1, 1}^{(k)} & \frac{1}{2} \alpha_{1, 2}^{(k)} & \cdots & \frac{1}{2} \alpha_{1, v}^{(k)} & \frac{1}{2} \alpha_{1, v + 1}^{(k)} & \cdots & \frac{1}{2} \alpha_{1, n}^{(k)} \\ \frac{1}{2} \alpha_{2, 1}^{(k)} & \alpha_{2, 2}^{(k)} & \cdots & \frac{1}{2} \alpha_{2, v}^{(k)} & \frac{1}{2} \alpha_{2, v + 1}^{(k)} & \cdots & \frac{1}{2} \alpha_{2, n}^{(k)} \\ \vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ \frac{1}{2} \alpha_{v, 1}^{(k)} & \frac{1}{2} \alpha_{v, 2}^{(k)} & \cdots & \alpha_{v, v}^{(k)} & \frac{1}{2} \alpha_{v, v + 1}^{(k)} & \cdots & \frac{1}{2} \alpha_{v, n}^{(k)} \\ \frac{1}{2} \alpha_{v + 1, 1}^{(k)} & \frac{1}{2} \alpha_{v + 1, 2}^{(k)} & \cdots & \frac{1}{2} \alpha_{v + 1, v}^{(k)} & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ \frac{1}{2} \alpha_{n, 1}^{(k)} & \frac{1}{2} \alpha_{n, 2}^{(k)} & \cdots & \frac{1}{2} \alpha_{n, v}^{(k)} & 0 & \cdots & 0 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix}
\end{align*}
です．上記の n \times n 対称行列 F_k について解説すると，まず，2つ目の変数については，vinegar 変数のみで制限されているので，右下の m \times m ブロック行列は零行列となります（n = v + m に注意してください）．
それ以外の成分については，i \neq j としたときの x_i x_j の係数は F_k[i][j] + F_k[j][i] であり，F_k[i][j] + F_k[j][i] = \alpha_{i, j}^{(k)} が成り立ちます．F_k を対称行列で書こうと思うと，F_k[i][j] = F_k[j][i] なので，F_k[i][j] = F_k[j][i] = \frac{1}{2} \alpha_{i, j}^{(k)} です．
対角成分は，F_k[i][i] = \alpha_{i, i}^{(k)} なので，そのまま入ってきます．
よって，f_i を F_i という行列で書くことができました．同様に \mathcal{P} = (p_1(x_1, \cdots, x_n), \cdots, p_m(x_1, \cdots, x_n)) について，p_i(x) = x P_i x^t という対称行列 P_i を使って表すことができます．
polarization
今まで二次形式を考えていましたが，ここでは，双一次形式，つまり，2つの1変数多項式 \sigma_{i, j = 1}^{n} x_i a_{i, j} y_j について考えます．
上記と同様の議論で，対称行列 A を使って，\sigma_{i, j} x_i a_{i, j} y_j = x A y^t と表せます．右辺を内積の形と見ると，x A y^t = (x, A y) = (A x, y) となって，転置を消すことができます．
ここでは，双一次形式と二次形式を結ぶことを考えます．双一次形式から二次形式は簡単で，単に y = x とすればOKです．逆に二次形式 \sigma_{i, j} x_i a_{i, j} x_j = x A x^t = (x, A x) = (A x, x) が与えられたとき，A[x] = (x, A x) = (A x, x) と置くと，双一次形式 \frac{1}{2} (A[x + y] - A[x] - A[y]) = x A y^t を得ます．
（実際，A[x + y] - A[x] - A[y] = (x + y, A (x + y)) - (x, A x) - (y, A y) = (x, A y) + (y, A x) = 2(x, Ay) = 2 x A y^t です）
つまり，ある意味で双一次形式と二次形式は同値になります．上記の操作で，二次形式から双一次形式を得ることを A[x] の polarization と言います．
\mathcal{P} = \mathcal{F} \circ \mathcal{F} で定義しているので，f_i(x) = x F_i x^t， \mathcal{S}(x) = S x^t なので，p_i(x) = f_i \circ S(x) = f_i(S x^t) = (S x^t) F_i (S x^t)^t = x S^t F_i S^t x を得ます．
p_i(x) = x P_i x^t から P_i = S F_i S^t となります．
今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！
参考文献
縫田 光司 : "耐量子計算機暗号"，森北出版，2020.
D. J. Bernstein, J. Buchmann, and E. Dahmen, editors: "Post-Quantum Cryptography", Springer-Verlag, 2009.
A. Kipnix, J. Patarin, L. Goubin: "Unbalanced oil and vinegar signature schemes", In: International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 1999. p. 206-222.
A. Kipnis, A. Shamir: "Cryptanalysis of the oil and vinegar signature scheme", In: Annual international cryptology conference. Springer, Berlin, Heidelberg, 1998. p. 257-266.
佐竹 一郎 : "線型代数学"，裳華房，1958.
Discussion