UOVに付随する数学の問題

UOVの安全性解析において重要となる問題とその解法についてざっくり説明します.

$k$ を体, $x = (x_{1}, \dots, x_{n})$ を変数とし, $k [x]$ を多変数多項式環とします. $k$ は特に有限体 $F_{q}$ について考えます.

完全等方部分空間

$f (x) \in k [x]$ を二次形式, $O$ を $k^{n}$ の線形部分空間とする. 任意の $a \in O$ に対し, $f (a) = 0$ が成り立つとき, $O$ は $f$ の完全等方部分空間であるという.
また, 二次形式の列 $F (x) \in k [x]^{m}$ の各要素が共通の完全等方部分空間 $O$ を持つとき, $O$ は $F$ の完全等方部分空間であるという.

UOVの鍵ペア

有限体上の二次形式の列 $P \in F_{q} [x_{1}, \dots, x_{n}]^{m}$ が $o$ 次完全等方部分空間 $O$ を持つとき, $P, O$ をそれぞれ $UOV (q, n, m, o)$ の公開鍵, 秘密鍵という.

UOVに対する直接攻撃

$P$ を $UOV (q, n, m, o)$ の公開鍵とし, $μ \in F_{q}^{m}$ とする. このとき, $P, μ$ を入力とし,

$P (x) = μ$

を満たす $x$ を出力せよ.

この問題はMQ(Multivariate Quadratic)問題として知られています. 主な解法として,

Thomae-Wolf + Wiedemann XL
Hilbert driven $F_{4}$

が知られています.

UOVに対する鍵復元攻撃

$P, O$ をそれぞれ $UOV (q, n, m, o)$ の公開鍵, 秘密鍵とする. このとき $P$ を入力として $O$ を出力せよ.

この問題について, 以下の定理が知られています.

One vector method

$a \in O$ となる $a$ が一つ(もしくはいくつか)得られたならば, $O$ 全体を復元できる.

このようなベクトル $a$ はsecret vectorと呼ばれています.
厳密には必要なsecret vectorの数はパラメータ $(q, n, m, o)$ に依存するのですが, 現在提案されているUOVのパラメータにおいてはその数は $1$ なので, そういう意味で鍵復元攻撃とはsecret vectorを $1$ 本計算する攻撃だと思って問題ないです.