NTRUSign - crypto-writeup-public

NTRUの仕組みから署名をやるやつ

$n$ ：多項式の次数の最大値

$d$ ：

$q$ ：素数

多項式 $f,g$ を生成する。 $f,g$ は最大で $n$ 次で、係数が $\pm 1$ の項が $d$ 個あって、係数が $0$ の項が $n - d$ 個ある
$f \ast G - g \ast F = q$ が成り立つような $F, G$ を選択する
- ユークリッドの互除法などを使った選び方はあるけど後で書きます。まだ理解してないので
- $\det{\begin{bmatrix} f & g \ a & b \end{bmatrix}} = 1$ となるような $a, b$ を選んで
- $\det{\begin{bmatrix} f & g \ qa & qb \end{bmatrix}} = q$
- - $F = qa, G = qb$ （ただし小さい係数である必要がある？）
public key $h \equiv F \ast f_q \equiv G \ast g_q \mod q$
private key（ $2n \times 2n$ 行列
$R = \begin{bmatrix} f_0 & \dots & f_{n-1} & g_0 & \dots & g_{n_1} \ f_{n-1} & \dots & f_{1} & g_{n-1} & \dots & g_{1} \ \vdots \ f_{1} & \dots & f_{0} & g_{1} & \dots & g_{0} \ F_{0} & \dots & F_{n-1} & G_{0} & & G_{N-1} \ \vdots \ F_{1} & \dots & F_{0} & G_{1} & \dots & G_{0} \end{bmatrix}$