UOVに付随する数学の問題
UOVの安全性解析において重要となる問題とその解法についてざっくり説明します.
$k$ を体, $x=(x_1, \cdots, x_n)$ を変数とし, $k[x]$ を多変数多項式環とします. $k$ は特に有限体 $\mathbb{F}_q$ について考えます.
$f(x) \in k[x]$ を二次形式, $\mathcal{O}$ を $k^n$ の線形部分空間とする. 任意の $a \in \mathcal{O}$ に対し, $f(a) = 0$ が成り立つとき, $\mathcal{O}$ は $f$ の完全等方部分空間であるという.
また, 二次形式の列 $F(x) \in k[x]^m$ の各要素が共通の完全等方部分空間 $\mathcal{O}$ を持つとき, $\mathcal{O}$ は $F$ の完全等方部分空間であるという.
有限体上の二次形式の列 $P \in \mathbb{F}_q[x_1, \cdots, x_n]^m$ が $o$次完全等方部分空間 $\mathcal{O}$ を持つとき, $P, \mathcal{O}$ をそれぞれ $\text{UOV}(q, n, m, o)$ の公開鍵, 秘密鍵という.
$P$ を $\text{UOV}(q, n, m, o)$ の公開鍵とし, $\mu \in \mathbb{F}_q^m$ とする. このとき, $P, \mu$ を入力とし,
$P(x) = \mu$
を満たす $x$ を出力せよ.
この問題はMQ(Multivariate Quadratic)問題として知られています. 主な解法として,
- Thomae-Wolf + Wiedemann XL
- Hilbert driven $F_4$
が知られています.
$P, \mathcal{O}$ をそれぞれ $\text{UOV}(q, n, m, o)$ の公開鍵, 秘密鍵とする. このとき $P$ を入力として $\mathcal{O}$ を出力せよ.
この問題について, 以下の定理が知られています.
$a \in \mathcal{O}$ となる $a$ が一つ(もしくはいくつか)得られたならば, $ \mathcal{O} $全体を復元できる.
このようなベクトル $a$ はsecret vectorと呼ばれています.
厳密には必要なsecret vectorの数はパラメータ $(q, n, m, o)$ に依存するのですが, 現在提案されているUOVのパラメータにおいてはその数は $1$ なので, そういう意味で鍵復元攻撃とはsecret vectorを$1$本計算する攻撃だと思って問題ないです.
鍵復元攻撃については以下が知られています.
- Kipnis-Shamir attack
- Reconciliation attack
- Intersection attack
- Rectangular MinRank attack
- Singular point attack
また, 鍵復元攻撃においては以下の問題が重要になることが知られています.
(同じサイズの)行列の配列 $M=(M_1, \cdots, M_k)$ と, 自然数 $r$ が入力されたとき,
$\rank{(a_1M_1 + \cdots + a_kM_k)} \leq r$
となる非自明な $a_1, \cdots, a_k$ を出力せよ.
この問題の解法としては
- Support minors method
が知られています.
以上, UOVの安全性解析において重要となる問題とその解法についての概観でした.
