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 の係数が小さい部分集合とする。

1. f を L_f からランダムに選ぶ。
   1. f が f ⊗ F_q ≡ 1 (mod q) となるR中の要素 F_q を持たない場合 f を選び直す。
   2. 同様に f が f ⊗ F_p ≡ 1 (mod p) となるR中の要素 F_q を持たない場合 f を選び直す。
2. g を L_g からランダムに選ぶ。
3. h ≡ F_q ⊗ p ⊗ g (mod q) とする。

公開鍵は 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' を出力する。

完全性について

a ≡ f ⊗ c ≡ p ⊗ g ⊗ r + f ⊗ m (mod q)

である。 上手くパラメータを調節すると、Z上で

a' = p ⊗ g ⊗ r + f ⊗ m

が高い確率で成立する。 この等式が成立している場合、

F_p ⊗ a' ≡ F_p ⊗ f ⊗ m ≡ m (mod p)

となる。

実装

Tで係数が1, 0, -1のN-1次以下の多項式の集合を表す。 T(d)で、係数が1, 0, -1かつ、1と-1の個数がdのN-1次以下の多項式の集合を表す。 IEEE P1361.1/D10では例えば以下のようにパラメータ集合が定められている。

ees449ep1

(N, q, p, L_f, L_g, L_r, L_m) = (449, 2048, 3, T(134), T(149), T(134), T)

ees853ep1

(N, q, p, L_f, L_g, L_r, L_m) = (853, 2048, 3, T(268), T(284), T(268), T)

応用

実用の際にはRSA暗号と同様にパディングを行うことが推奨されている。

参考文献

原論文

• NTRU: A Ring-Based Public Key Cryptosystem; Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman; Algorithmic Number Theory (ANTS III), Portland, OR, June 1998, J.P. Buhler (ed.), Lecture Notes in Computer Science 1423, Springer-Verlag, Berlin, 1998, 267-288.
• http://sourceforge.net/projects/ntru/ NTRUのオープンソース実装

関連項目

• 暗号
• 暗号理論
• 格子暗号
• NTRU署名