NTRU暗号

NTRU暗号とは

NTRU暗号は、1996年にJeffrey Hoffstein、Jill Pipher、Joseph H. Silvermanによって発表された公開鍵[[暗号]]方式です。多項式環上で定義された格子問題の困難性を利用しており、効率的な暗号化と復号が可能な点が特徴です。

暗号方式の概要

NTRU暗号の安全性は、多項式環上で定義される格子の最短ベクトル問題を解くことが困難であるという仮定に基づいています。ただし、この困難性が数学的に厳密に証明されているわけではありません。NTRU暗号は、比較的シンプルな代数構造を利用しているため、処理速度が速く、リソースの限られた環境でも利用しやすいという利点があります。

鍵生成

NTRU暗号の鍵生成は以下の手順で行われます。

1. パラメータ設定: セキュリティパラメータ `N`、整数 `q` (O(N)のオーダー)、小さな要素 `p` (2, 3, 2+Xなど) を選択します。また、多項式環の係数が小さい部分集合 `Lf`、`Lg` を定義します。
2. 秘密鍵の生成: `Lf` からランダムに要素 `f` を選択します。`f` が `f ⊗ Fq ≡ 1 (mod q)` および `f ⊗ Fp ≡ 1 (mod p)` となるような逆元 `Fq` と `Fp` を持つまで選び直します。
3. 公開鍵の生成: `Lg` からランダムに要素 `g` を選択し、`h ≡ Fq ⊗ p ⊗ g (mod q)` を計算します。ここで、`h` が公開鍵、`f` が秘密鍵となります。

暗号化

平文 `m` を暗号化する手順は以下の通りです。

1. 平文と乱数の準備: 平文空間 `Lm` から平文 `m` を、乱数空間 `Lr` から乱数 `r` を選択します。`Lm` と `Lr` は、係数が小さい部分集合です。
2. 暗号化: 暗号文 `c = h ⊗ r + m (mod q)` を計算します。

復号

暗号文 `c` を復号する手順は以下の通りです。

1. 計算: `a = f ⊗ c (mod q)` を計算します。
2. 係数の調整: `a` の係数を `[-q/2, q/2]` の範囲に収め、`a'` とします。
3. 復号: `m' = Fp ⊗ a' (mod p)` を計算し、平文 `m'` を得ます。

完全性について

暗号化と復号が正しく行われるための条件は、以下の通りです。

`a ≡ f ⊗ c ≡ p ⊗ g ⊗ r + f ⊗ m (mod q)`
パラメータを適切に調整することで、`a' = p ⊗ g ⊗ r + f ⊗ m` が高い確率で成立します。
この場合、`Fp ⊗ a' ≡ Fp ⊗ f ⊗ m ≡ m (mod p)` となり、正しく復号できます。

実装

NTRU暗号の実装では、多項式の係数が1, 0, -1である多項式の集合 `T` や、1と-1の個数が指定された集合 `T(d)` などが用いられます。IEEE P1361.1/D10では、以下のようなパラメータセットが定義されています。

ees449ep1: (N, q, p, Lf, Lg, Lr, Lm) = (449, 2048, 3, T(134), T(149), T(134), T)
ees853ep1: (N, q, p, Lf, Lg, Lr, Lm) = (853, 2048, 3, T(268), T(284), T(268), T)

性能

NTRU暗号は、他の公開鍵[[暗号]]方式と比較して、高速な暗号化と復号が可能です。特に、組み込みシステムなどのリソースが限られた環境での利用に適しています。

安全性

NTRU暗号の安全性は、格子問題の困難性に基づいています。適切なパラメータを選択することで、十分な安全性を確保できます。実用上は、RSA[[暗号]]と同様にパディングを施すことが推奨されています。

応用

NTRU暗号は、電子メールの暗号化、デジタル署名、鍵交換など、様々な暗号化アプリケーションに利用できます。

参考文献

原論文: NTRU: A Ring-Based Public Key Cryptosystem; Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman; Algorithmic Number Theory (ANTS III), Portland, OR, June 1998
NTRUのオープンソース実装: http://sourceforge.net/projects/ntru/

関連項目

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

もう一度検索