NTRU暗号
NTRU暗号とは、公開鍵暗号の一つである。 1996年にJeffrey Hoffstein, Jill Pipher, Joseph H. SilvermanがCRYPTO'96のRump Sessionで発表した。2000年にNTRU Cryptosystems社が米国で特許を取得している。 多項式環を用いて定義された格子の最短ベクトル問題が困難と予想されることを基にしているが、実際に帰着出来るか否かは未解決問題である。
暗号化
平文空間Lₘ、乱数空間Lᵣを R の係数が小さい部分集合とする。 Lₘ中の平文mとLᵣ中の乱数rを用いて、c = h ⊗ r + m mod q を計算し、cを出力する。
復号
cを暗号文とする。 まずa = f ⊗ c mod q を計算する。次に、aの係数を[-q/2,q/2]の範囲に収め、それをa' とする。最後に、m' = Fₚ ⊗ a' mod p を計算し、m' を出力する。
応用
実用の際にはRSA暗号と同様にパディングを行うことが推奨されている。