🤖

離散フーリエ変換からNTTまで

に公開
離散フーリエ変換
pqc
mlkem
数論変換
多項式演算
idea

はじめに

現在広く利用されている暗号技術は、量子コンピュータの登場によって安全性が揺らぐ可能性があると指摘されています。この問題への解決策として二つのアプローチが注目を集めています。一つは、量子コンピュータでも解けない計算問題に基づいた「耐量子計算機暗号（PQC）」 です。もう一つは、量子力学の原理を利用する「量子暗号（QKDなど）」 です。

私はこれらの最先端の暗号技術に強い関心があり、独学で得た知識を体系的に整理するために、記事シリーズとしてまとめています。

本記事では、NIST標準のML-KEMが採用しているModule-LWE問題における多項式演算を高速化する技術、数論変換(Number Theorem Transform、以下 NTT) について整理します。NTTは、離散フーリエ変換(DFT)の考え方を整数環に応用したものであるため、まず離散フーリエ変換と離散逆フーリエ変換に触れ、その後にNTTがどのように多項式演算を高速化しているかを整理していきます。

離散フーリエ変換、離散逆フーリエ変換

離散フーリエ変換は、多項式同士の複雑な乗算を単純な掛け算に置き換えることができる数学的な手法です。これにより、多項式の乗算を高速化できます。

多項式の掛け算の課題

n次の多項式A(x)=A_0+A_1x+A_2x^2+...+A_nx^nと、n次の多項式B(x)=B_0+B_1x+B_2x^2+...+B_nx^nを掛け合わせると、その結果は2n次の多項式C(x)となります。係数を直接計算しようとすると、計算量はO(n^2)となり、大きなnでは非常に時間がかかります。

多項式の性質を利用する

多項式の次数が m のとき、m+1 個の異なる点での値がわかれば係数は一意に決まる という性質があります。この性質を使えば、多項式の掛け算を「係数計算」ではなく「点での掛け算」に置き換えられます。

例えば、C(x)=C_0+C_1x+C_2x^2+C_3x^3+C_4x^4という4次の多項式を考えます。この多項式の係数がわからなくても、もし5つの異なる点、例えばx=0,1,2,3,4におけるC(x)の値がそれぞれ2,-1,3,-4,1だとわかっていれば、多項式の係数を効率的に求めることができます。

1のN乗根

離散フーリエ変換を理解するために必要な概念が**「1のN乗根」**です。
1のN乗根とは、N乗すると1になる数 ωを指します。複素数の世界では全部N個であり、円周上の点として幾何学的に表現できます。

ω^N=1
ω_k​=e^{2πki​/N} (k=0,1,…,N−1)

例えば、N=4の場合、1の4乗根は{1,i,−1,−i}です。

そして、ζ_N​:=e^{2πi/N}​としたとき、1のN乗根は(ζ_N)^0,(ζ_N)^1,...,(ζ_N)^{N-1}という形で表すことができます。

  • 1のN乗根には次の性質があります。

    • (ζ_N)^N=1
    • (ζ_N)^0,(ζ_N)^1,...,(ζ_N)^{N-1}は全て異なる
    • ∑_{k=0}^{N-1}(ζ_N)^{kl}は、l≡0 (mod N)の時N、そうでないとき0

離散フーリエ変換（DFT）の手順

n次多項式 A(x)=A_0+A_1x+A_2x^2+...+A_nx^n , B(x)=B_0+B_1x+B_2x^2+...+B_nx^nを乗算した多項式C(x)は、次数が2nになるため、その係数を求めるためには 2n+1 個の点での値が必要です。ここでは、計算を簡単にするため、

  • A(x)とB(x)の次数の和2nよりも大きく、
  • かつ2のべき乗である最小の数 N を選びます（N=2^k）。

このN個の1のN乗根を評価点として利用し、A(x)とB(x)をそれぞれ評価します。
求めたい多項式は、C(x)=C_0+C_1x+C_2x^2+...+C_{2n}x^{2n}とします。

手順：

  1. 評価点の選定
    乗算後の多項式の次数2nに対して、2のべき乗で最小のNを選びます。
    評価点は1のN乗根：

    x_i=(ζ_N)^i (0 \le i \le N-1)

  2. 評価値の計算

    これらの評価点を多項式に代入します。例えば、多項式f(x)に代入すると次のようになります。

    f((ζ_N)^0)=f_0((ζ_N)^0)^0+f_1((ζ_N)^0)^1+f_2((ζ_N)^0)^2+...+f_{N-1}((ζ_N)^0)^{N-1}
    f((ζ_N)^1)=f_0((ζ_N)^1)^0+f_1((ζ_N)^1)^1+f_2((ζ_N)^1)^2+...+f_{N-1}((ζ_N)^1)^{N-1}
    ・
    ・
    ・
    f((ζ_N)^{N-1})=f_0((ζ_N)^{N-1})^0+f_1((ζ_N)^{N-1})^1+f_2((ζ_N)^{N-1})^2+...+f_{N-1}((ζ_N)^{N-1})^{N-1}

    同様に、A(x),B(x)についても計算すると、計算結果は、次の式で表すことができます。

    A(x_i)=A((ζ_N)^i)=Σ^{N-1}_{j=0}A_j(ζ_N)^{ij} (0 \le i \le N-1)
    B(x_i)=B((ζ_N)^i)=Σ^{N-1}_{j=0}B_j(ζ_N)^{ij} (0 \le i \le N-1)

  • ここで、(ζ_N)^{ij}は、「正の指数」で回転させるイメージです。
    これをi=0,1,...,N-1すべてについて計算すると、次のような配列が得られます。

    \hat A = [ A((ζ_N)^0),A((ζ_N)^1),...,A((ζ_N)^{N-1}) ]
    \hat B = [ B((ζ_N)^0),B((ζ_N)^1),...,B((ζ_N)^{N-1}) ]

これは、「多項式を1のN乗根で評価した結果のリスト」、すなわち評価点での値の配列です。

  1. 要素ごとの掛け算
    評価値同士を対応する要素ごとに掛けます。

    \hat C = \hat A・\hat B

    この計算は、単なるn個の数値の掛け算なので、非常に高速に計算できます。

すなわち、離散フーリエ変換は、「係数の配列」から「評価点の値の配列」への変換する処理です。係数から評価値への変換は、幾何学的には「順方向の回転」に対応しています。

離散逆フーリエ変換の手順

離散逆フーリエ変換(Inverse DFT)は、離散フーリエ変換(DFT)の逆の操作です。つまり、「評価点の値の配列」から元の「係数の配列」に戻すための処理です。

\hat C = [C'_0,C'_1,...,C'_{N-1}]
↓
C(x)=C_0+C_1x+C_2x^2+...+C_{N-1}x^{N-1}

逆変換の計算式

逆変換は以下の式で定義されます：

C_j=N^{-1}Σ^{N-1}_{i=0}C'_k(ζ_N)^{-ji} (mod q) (0 \le j \le N-1)

ここで、N^{-1} はNの逆元\pmod qを表します。

  • 負の指数の役割：DFTでは「順方向の回転」で評価値を求めましたが、IDFTでは、その値を逆方向（負の指数）に回転させて元に戻します。
  • N^{-1} を掛ける理由：DFTの計算過程で、N回の加算が行われることで値がスケーリング（拡大）されています。元の大きさに戻すために、N^{-1}を掛けて平均化する必要があります。

この計算により、各 C_j はすべての C'_k を合成して求められます。

C(x)=C_0+C_1x+C_2x^2+...+C_{N-1}x^{N-1}

この計算によって、各係数 C_j は、すべての評価値 C'_i を合成することで求められます。このようにして、二つの多項式を乗算した結果の係数配列を取り戻すことができます。

NTT

NTT(数論変換) は、離散フーリエ変換の考え方を応用し、多項式の乗算を整数環\pmod q上で高速に行う手法です。言い換えると、離散フーリエ変換が複素数を扱うのに対して、NTTは 法qの世界(Z_q) で計算を行います。

実際に、NTTはNIST（アメリカ国立標準技術研究所）で標準化されたPQCアルゴリズム、ML-KEMにおいて、多項式演算の高速化に使用されています。ここでは、ML-KEMが採用する Module-LWE問題を例に、NTTの仕組みを整理します。

NTTを可能にする「魔法の数」

NTTを使うには、離散フーリエ変換でいう1のN乗根に相当する、整数版の特殊な値が必要です。

ML-KEMが採用するるModule-LWE問題は、多項式を要素とするベクトルや行列を扱い、各多項式の次数はn次未満、係数は整数[0,q-1]の範囲です。多項式の乗算にNTTを適用するためには、次の条件が必要です。

  1. 多項式の次数 nと評価点の数 N

    Module-LWE で使われる多項式の係数の数 n と、NTT で使う評価点の数 N は同じです。
    ML-KEM の全てのパラメータセット（ML-KEM-512, 768, 1024）では n = 256 に固定されています。

  2. 法 q

    法qは、q-1が多項式の次数nで割り切れる必要があります。これは、NTTで使う「n次の原始根」r_Nを作るための条件です。

原始根とn次の原始根

  • mod q の原始根 r
    1. rとqは互いに素
    2. {r^1,r^2,⋯,r ^{q−1}} \pmod qが全て異なる
      →最小のkでr^k ≡ 1 (mod q)となるkはq-1
  • n次の原子根r_N （=整数版の特殊な値）
    1. mod qの原始根rを一つ選ぶ
    2. r_N = r^{(q-1)/n} \pmod qと定義します。

特性：

  • r_N^n ≡ r^{q-1} ≡ 1 (mod q)

  • 0 < k < nのとき、r^k \not\equiv 1 (mod q)

フーリエ変換の1のN乗根 NTTの「魔法の数」
(\zeta_N)^N = 1 (r_N)^n \equiv 1 \pmod q
(\zeta_N)^0, (\zeta_N)^1, \dots, (\zeta_N)^{N-1} は全て異なる r_N^0, r_N^1, \dots, r_N^{n-1} \pmod q は全て異なる
\sum_{k=0}^{N-1} (\zeta_N)^{kl} は、l \equiv 0 \pmod N の時 N、そうでないとき 0 \sum_{k=0}^{n-1} (r_N)^{kl} \pmod q は、l \equiv 0 \pmod n の時 N、そうでないとき 0

離散フーリエ変換と同じ手順で、NTTではN個のn次の原始根r_N^k (0 \le k \le n-1)を多項式の評価点として用い、N個の値のリスト「評価点の値の配列」を得ることができます。そして逆NTTで、「評価点の値の配列」から元の「係数の配列」に戻すことができます。

NTTの手順（簡単な例）

多項式 a(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 を考えます(N=n=4）。

  1. NTT（順方向変換）
    評価点として、n次の原始根r_N^k (0 \le k \le n-1)を使います。

    \hat a[k] = a(r_N^k) = \sum_{j=0}^{3} a_j r_N^{jk} \pmod q \quad (k=0,1,2,3)
    \hat{a} = [a(r_N^0),a(r_N^1),a(r_N^2),a(r_N^3)]

  2. 逆NTT（逆方向変換）

    a_j = \frac{1}{4} \sum_{k=0}^{3} \hat{a}[j] r_N^{-kj} \pmod q (j=0,1,2,3)

このように、「係数の配列」↔「評価点の値の配列」の変換により、多項式演算を高速に計算できます。

離散フーリエ変換やNTTは、複雑な計算を効率的に行うための重要な技術です。今回は、ML-KEMを例に、、NTTの仕組みやその役割を整理しました。NTTを使用して高速多項式演算を実現しているPQCアルゴリズム、ML-KEMについて詳しく知りたい方は、以下の記事をご覧ください。

Discussion