NTRU

convolution

https://xz.aliyun.com/t/7163#toc-3

https://latticehacks.cr.yp.to/ntru.html

パラメータ

p：素数

q： q > 6(d + 1)pであるような素数

\gcd(p, q) = 1

n：生成する多項式 fの最大次数。なぜか素数であることが要求されている

d：生成する多項式 fの0でない項の数

今後

R = \Z\lbrack x\rbrack /(x^n - 1)

R_p = \Z_p\lbrack x\rbrack /(x^n - 1)

R_q = \Z_q\lbrack x\rbrack /(x^n - 1)

鍵生成

  • 多項式 f,g を生成する。 f,g は最大で n 次で、係数が \pm 1 の項が d 個あって、係数が 0 の項が n - d 個ある

  • F_q \equiv f \mod q, F_p \equiv f \mod p を計算する

  • public key h \equiv F_q \ast g \mod q を計算する。ここで \ast は多項式の乗算（一部では Convolution などと呼ばれていますが）

  • private keyは f, g

暗号化

  • 平文 m \in R_p

  • ランダムな r を f,g と同様に選ぶ

  • 暗号文 e \equiv pr \ast h + m \mod q

復号

  • a \equiv f \ast e \equiv pg \ast r + f \ast m \mod q を計算する

  • F_p \ast a \mod p \equiv F_ppg \ast r + F_pf \ast m \equiv 0 + 1*m \equiv m を計算する

なんかCenterLiftをする、みたいなのもある