前回からの続きです．今回で QR-UOV の原論文の解説ログは終わりです．
QR-UOV 理解ログ 1/7
QR-UOV 理解ログ 2/7
QR-UOV 理解ログ 3/7
QR-UOV 理解ログ 4/7
QR-UOV 理解ログ 5/7
全７回通しでの目次
第１回
- 本論文全体の流れ
- MQ問題
- 多変数多項式暗号署名方式
- UOV署名方式
第２回
- 巡回行列と逆巡回行列
- BAC-UOV 署名方式
- BAC-UOV への Structual Attack
第３回
第４回
第５回
第６回
第７回
突貫で書いてしまった部分もあるので，大いに誤りを含む可能性があります．誤字・脱字レベルでも構いませんので，ご指摘ください．
また，予告なしに内容の加筆や構成の変更を行うことがありますが，読みやすくするためのものですので，ご容赦ください
Improved QR-UOV
NIST PQC 標準化第３ラウンドに残っているRainbowを改善する方法を２つ与えて，それらでデフォルトのQR-UOVを改善していきます
＊この記事を書いている2022/12/31現在は，第４ラウンドでそこには残念ながらRainbowは残っていません
１つ目の方法が，Czypekらによる方法で，秘密鍵に特定の構造を持たせるものです．
２つ目の方法が，公開鍵の一部（大部分？）を擬似乱数によって置き換えるものです．
以下で２つ目を詳しく見ていきます（１つ目はたぶん論文を読んだ方が早いし，どう改善されるかもよく分からないので）．
実際に提案されたRainbowでもこの2つ目の方法を使っているらしく，Petzoldt らの compression technique を使った Rainbow を compressed Rainbow というらしいです
具体的には，公開鍵 \mathcal{P} = (p_1, \cdots, p_m) で 1 \leq i \leq m としたとき p_i に対応する表現行列を P_i とおくとき，P_i は
\begin{align*}
P_i = \begin{pmatrix}
P_{i, 1} & P_{i, 2} \\
P_{i, 2}^t & P_{i, 3}
\end{pmatrix}
\end{align*}
のように表されるとします（P_{i, 1}, P_{i, 2}, P_{i, 3} はそれぞれ v \times v, v \times m, m \times m 行列で P_{i, 1}, P_{i, 3} は対称行列）
また，\mathcal{P} = (p_1, \cdots, p_m) に対応して \mathcal{F} = (f_1, \cdots, f_m) が定まるのですから，f_i に対応する表現行列を F_i とおくとき，F_i は
\begin{align*}
F_i = \begin{pmatrix}
F_{i, 1} & F_{i, 2} \\
F_{i, 2}^t & 0
\end{pmatrix}
\end{align*}
のように表されるとします（P_{i, 1}, P_{i, 2}, 0 はそれぞれ v \times v, v \times m, m \times m 行列で P_{i, 1} は対称行列，0は零行列）
このとき，P_i = S^t F_i S ゆえ，S は
\begin{align*}
S^{-1} = \begin{pmatrix}
I_v & - S^{\prime} \\
0 & I_m
\end{pmatrix}
\end{align*}
のように表されます（I_v, I_m はそれぞれ v \times v, m \times m の単位行列で，0は m \times v の零行列，- S^{\prime} は v \times m 行列）
P_i = S^t F_i S を F_i = (S^{-1})^t F_i S^{-1} とみると
\begin{align*}
\begin{pmatrix}
F_{i, 1} & F_{i, 2} \\
F_{i, 2}^t & 0
\end{pmatrix} =
\begin{pmatrix}
I_v & 0 \\
- (S^{\prime})^t & I_m
\end{pmatrix}
\begin{pmatrix}
P_{i, 1} & P_{i, 2} \\
P_{i, 2}^t & P_{i, 3}
\end{pmatrix}
\begin{pmatrix}
I_v & - S^{\prime} \\
0 & I_m
\end{pmatrix}
\end{align*}
が成り立ち，それぞれの成分を見比べると，
\begin{align*}
F_{i, 1} & = P_{i, 1} \\
F_{i, 2} & = - P_{i, 1} S^{\prime} + P_{i, 2} \\
0 & = (S^{\prime})^t P_{i, 1} S^{\prime} - P_{i, 2}^t S^{\prime} - S^{\prime} P_{i, 2} + P_{i, 3}
\end{align*}
を得ます．3番目の式から，P_{i, 1}, P_{i, 2}, S^{\prime} が与えられたら P_{i, 3} を計算できます．
以上の操作で公開鍵のサイズを圧縮することができます．
今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！
今回は分かっていない部分が多いため，論文中で記載されていた↓の論文を後で見てみようと思います．
P. Czypek, S. Heyse, E. Thomae: ``Efficient implementations of MQPKS on constrained devices'', In: International Workshop on Cryptographic Hardware and Embedded Systems. Springer, Berlin, Heidelberg, pp.374-389, 2012.
J. Ding, M.S. Chen: ``Rainbow Signature'', In Third round submission to the NIST post-quantum cryptography call, 2020.
初めに書いたとおりで，５章は飛ばします．
次回は QR-UOV の初等的な構成論文の解説をします．
Discussion