NTRU暗号
N をセキュリティパラメータとする。 Z[X]で整数係数の多項式環を表す。(X-1)をX-1が生成するイデアルとする。 環Rを Z[X]/(X-1) とする。以下、⊗で R の要素の積を表す。 q を O(N) の整数とし、p を環R中の小さい要素とする。(2, 3, 2+X等が用いられる。) また, Lf, Lgを R の係数が小さい部分集合とする。
f を Lf からランダムに選ぶ。 f が f ⊗ Fq ≡ 1 (mod q) となるR中の要素 Fq を持たない場合 f を選び直す。 同様に f が f ⊗ Fp ≡ 1 (mod p) となるR中の要素 Fq を持たない場合 f を選び直す。
g を Lg からランダムに選ぶ。
h ≡ Fq ⊗ p ⊗ g (mod q) とする。
公開鍵は h、秘密鍵はfである。