FN-DSA（Falcon）とNTRU格子署名

なぜもう一つの格子署名が要るのか

NISTのポスト量子署名として最初に標準化されたのは 格子暗号とLWE／RLWE を土台とする ML-DSA（Dilithium）でした。ではなぜ二つ目の格子署名 Falcon（2024年に FIPS 206 のドラフト名 FN-DSA＝FFT over NTRU lattices Digital Signature Algorithm として標準化進行中）が必要なのか。答えは一点、サイズです。ML-DSA は Fiat-Shamir with Aborts 型で堅牢な反面、署名が数キロバイトに達します。証明書チェーンや DNSSEC レコード、ブロックチェーンのように「署名を大量に載せる／狭い帯域を通す」用途では、この肥大が効いてきます。Falcon は同じ安全水準で 署名を数分の一 に抑えます。

横にスクロール

NTRU格子とハッシュ＆サインの枠組み

Falcon の署名は ハッシュ＆サイン、正確には GPV（Gentry-Peikert-Vaikuntanathan）フレームワーク に従います。発想は素朴です。メッセージ m をハッシュして格子の外の点 c に写し、秘密鍵として持つ「良い基底」を使って c に十分近い格子点 v を求め、そのずれ s = c - v（短いベクトル）を署名とする。検証者は公開鍵（悪い基底）で s が本当に格子の要素で、かつ十分短いことだけを確かめます。良い基底が無ければ近い格子点を見つけられない――この非対称性が 署名スキームの内部 で見た EUF-CMA 安全性を支えます。

鍵の土台が NTRU格子 です。二つの短い多項式 f, g（環 Zq[x]/(x^n + 1)、Falcon-512 は n=512, q=12289）を秘密に選び、公開鍵を h = g · f^(-1) mod q とします。(f, g) から (F, G) を NTRU方程式 f·G - g·F = q を満たすよう補完すると、[[g, -f], [G, -F]] が短いベクトルからなる良い基底になります。攻撃者に見えるのは h だけで、そこから短い (f, g) を復元するのは NTRU 探索問題として困難です。

高速フーリエサンプリング：漏れない丸め方

この漏洩を封じる GPV の核心が 離散ガウスサンプリング です。c に最も近い格子点へ決定的に丸めるのではなく、c を中心とする 離散ガウス分布 に厳密に従って格子点を確率的に選びます。ガウス分布は回転対称なので、どの基底を使ってサンプリングしても 出力分布が基底の形に依存しない。結果として署名の分布は秘密鍵の情報を一切含まず（正確には統計的にゼロ知識に近く）、いくら署名を集めても良い基底を復元できません。

問題は速度です。格子上の離散ガウスサンプリングは一般に重い。Falcon の名の由来である 高速フーリエサンプリング（Fast Fourier sampling） は、NTRU格子の再帰構造を突いてこれを O(n log n) に落とします。鍵生成時に良い基底を LDL 分解 し、その結果を Falcon tree（FFT の分割統治に対応する二分木）に格納しておく。署名時はこの木を葉から根へたどりながら、各ノードで1次元の離散ガウスサンプリングを行います。分割統治は高速フーリエ変換そのものの構造で、ここが「FFT over NTRU」という命名の実体です。

署名（概念フロー）:
  c   = HashToPoint(salt || m)        # メッセージを環の点へ
  t   = c を FFT 領域へ変換
  z   = ffSampling(t, FalconTree)     # 木を辿り離散ガウスで格子点へ丸め
  s   = (c - z·B) を短ベクトルとして取得   # B は良い基底
  # ノルム ‖s‖ が上限 β を超えたら salt を引き直してやり直す
  署名 = (salt, Compress(s))          # s をエントロピー符号化して圧縮
検証:
  c   = HashToPoint(salt || m)
  s0  = c - s1·h                      # 公開鍵 h で相方成分を復元
  有効 ⇔ ‖(s0, s1)‖ ≤ β              # 短さの検証だけ

浮動小数点実装という地雷

Falcon の理論的な美しさは、そのまま実装の難しさに跳ね返ります。離散ガウスサンプリングと FFT は 実数演算を要し、参照実装は IEEE 754 の64ビット倍精度浮動小数点 を使います。ここに二つの深刻な落とし穴があります。

第一に 再現性。浮動小数点演算は丸めモードや FMA（積和融合）の有無、コンパイラの最適化、CPU アーキテクチャによって最終ビットがずれ得ます。鍵生成と署名で計算がわずかに食い違えば、正しい署名が出せなかったり、最悪サンプリングが歪んで安全性が崩れたりします。Falcon 実装は浮動小数点の挙動を厳密に固定する必要があり、環境非依存の実装は容易ではありません。

第二に サイドチャネル。浮動小数点命令の実行時間はオペランド依存になり得ます（非正規化数の処理など）。ガウスサンプリングの内部でデータ依存の分岐やメモリアクセス、可変時間命令が残ると、サイドチャネル攻撃 で秘密鍵が漏れます。定数時間プログラミング を浮動小数点で徹底するのは、整数だけの ML-DSA よりはるかに難しい。

ML-DSA との使い分け

Falcon と ML-DSA はどちらも ポスト量子暗号 の格子署名ですが、設計思想が対照的で、優劣ではなく トレードオフ です。

指針は明快です。署名や公開鍵のサイズが支配的な制約（証明書チェーン、TLS ハンドシェイクの往復量、DNSSEC、狭帯域 IoT、大量署名を載せる台帳）で、かつ 検証済みの堅牢な実装を利用できる なら Falcon が効きます。逆に、多様なプラットフォームへ移植する／自前実装を避けきれない／サイドチャネル対策の余力が乏しい なら、整数演算だけで完結し実装が読みやすい ML-DSA を既定にします。実務では PQC 移行戦略 で述べるように、まず ML-DSA を基本線に置き、サイズが本当に問題になる箇所へ Falcon を差す、という二段構えが現実的です。

まとめ

Falcon（FN-DSA） は NTRU格子上のハッシュ＆サイン署名で、GPV フレームワークに従います。メッセージのハッシュを格子点へ丸める際、決定的な丸めではなく 離散ガウスサンプリング を用いることで、署名分布から秘密の良い基底が漏れる GGH／NTRUSign 型の破綻を封じます。この丸めを O(n log n) で実現するのが、NTRU格子の再帰構造と Falcon tree を使う 高速フーリエサンプリング です。得られる利点は 署名・公開鍵の小ささで、ML-DSA の数分の一に収まります。

代償は実装の難しさです。64ビット浮動小数点の再現性確保と、定数時間プログラミング による サイドチャネル攻撃 対策が必須で、整数演算だけの ML-DSA より格段に神経を使います。したがって選定は、サイズ制約が支配的で堅牢な実装が使える場面で Falcon、移植性と実装堅牢性を優先する場面で ML-DSA、という 署名スキームの内部 と同じ「困難性は近くても失敗モードで選ぶ」判断に帰着します。