NTRU暗号

NTRU暗号とは、公開鍵暗号の一つである。
1996年にJeffrey Hoffstein, Jill Pipher, Joseph H. SilvermanがCRYPTO'96のRump Sessionで発表した。2000年にNTRU Cryptosystems社が米国で特許を取得している。
多項式環を用いて定義された格子の最短ベクトル問題が困難と予想されることを基にしているが、実際に帰着出来るか否かは未解決問題である。
暗号方式.
鍵生成.
"N" をセキュリティパラメータとする。
Z["X"]で整数係数の多項式環を表す。("X""N"-1)を"X""N"-1が生成するイデアルとする。
環"R"を Z["X"]/("X""N"-1) とする。以下、⊗で "R" の要素の積を表す。
"q" を "O"("N") の整数とし、"p" を環"R"中の小さい要素とする。（2, 3, 2+"X"等が用いられる。）
また, "L""f", "L""g"を "R" の係数が小さい部分集合とする。
公開鍵は "h"、秘密鍵は"f"である。
暗号化.
平文空間"L""m"、乱数空間"L""r"を "R" の係数が小さい部分集合とする。
"L""m"中の平文"m"と"L""r"中の乱数"r"を用いて、"c" = "h" ⊗ "r" + "m" mod "q" を計算し、"c"を出力する。
復号.
"c"を暗号文とする。
まず"a" = "f" ⊗ "c" mod "q" を計算する。次に、"a"の係数を[-q/2,q/2]の範囲に収め、それを"a' "とする。最後に、"m' " = "F""p" ⊗ "a' " mod p を計算し、"m' "を出力する。
完全性について.
である。
上手くパラメータを調節すると、Z上で
が高い確率で成立する。
この等式が成立している場合、
となる。
実装.
"T"で係数が1, 0, -1の"N"-1次以下の多項式の集合を表す。
"T"("d")で、係数が1, 0, -1かつ、1と-1の個数が"d"の"N"-1次以下の多項式の集合を表す。
IEEE P1361.1/D10では例えば以下のようにパラメータ集合が定められている。
応用.
実用の際にはRSA暗号と同様にパディングを行うことが推奨されている。