格子ベースのデジタル署名スキームFALCON

PQデジタル署名スキームとして、これまでSQISign、SPHINCS+、HPPK DSと見てきたので、今回は格子ベースの署名スキームFALCONについて。

格子暗号

FALCONのベースになっているのは格子暗号。格子は空間内の規則的な点の集まりを表す数学的構造で、2次元だと方眼紙の交点だったり蜂の巣のような構造だったりも格子構造を持つ。たとえば、一番単純な2次元の格子の例は↓

このような格子は、基底ベクトルの整数倍の組み合わせで構成される点の集合になる。例えば基底ベクトルを ${b_1 = (1, 1), b_2 = (2, 1)}$ とした場合、その基底ベクトルを整数倍することで以下のような2次元の格子を構成できる。

n次元の格子は ${L= \lbrace \sum_{i=1}^{n} (a_i \cdot b_i) | a_i \in \mathbb Z \rbrace}$ と基底ベクトルの整数線形結合として定義される。

また、基底 ${b'_1 = (0, 1), b'_2 = (1, 0)}$ のように異なる基底で同じ格子を表現することができるという重要な特徴がある。

格子暗号は、主に以下の格子の計算困難性の問題に基づいて構成されている。

最短ベクトル問題（Shortest Vector Problem = SVP）：
格子の原点から最も近い格子点を見つける問題。
最近ベクトル問題（Closest Vector Problem = CVP）：
ある点に最も近い格子点を見つける問題。起点が格子の原点ではなく、かつ格子点とも限らないので、SVPをより一般化した問題と言える。

前述したように同じ格子でも無数の基底表現がある。たとえば基底 ${b'_1 = (0, 1), b'_2 = (1, 0)}$ が提供されれば、最短ベクトルは目視で分かるレベルで自明だけど（計算する場合も探索範囲も[-1, 1]でとても小さい）、別の基底 ${b''_1 = (1000, 999), b''_2 = (999, 998)}$ から最短ベクトルを求めるとそのハードルは上がる（探索する範囲が[-1000, 1000]の約400万とおり）。これが高次元になるほど急激に問題を解くのが難しくなり、量子コンピューターでも効率的に解く方法が見つかっていないため、ポスト量子暗号として期待されている。

このような特性から、短いベクトルで構成され互いが直交に近い良い基底を秘密鍵とし、長く歪んだベクトルで構成される悪い基底を公開鍵として用いて暗号スキームを構成する。

FALCON

FALCONは、Fast-Fourier Lattice-based Compact Signatures over NTRUという名前に記載されているように、NTRU格子上に構築された署名スキームになる。

NTRU格子

↑の2次元の格子の例は直線的な点の広がりを持つとてもシンプルなものだったけど、NTRU格子というのは円環的な構造を持ち、多項式環 ${R = \mathbb Z \lbrack x \rbrack / (x^{n} + 1)}$ 上で定義される。

たとえば8次元の格子を構成する場合、基底ベクトルは8個の要素を持つ8個のベクトルで構成され、合計8 × 8 = 64 個の数値が必要になり、それらをすべて保存する必要がある。

NTRU格子の場合は、多項式から基底ベクトルを生成する。具体的には8次元の格子を構成する場合、まず ${f(x) = 2 + x + 3x^{3}}$ のような3次の多項式を用意する。続いて、多項式から負巡回行列（Negacyclic Matrix）を作る。これは、任意の ${g(x) = g_0 + g_1x + g_2x^{2} + g_3x^{3}}$ に対して ${f \times g}$ を計算した結果の各項の係数で構成される行列。多項式環により ${x^{4} = -1}$ となり高次の項は負の符号で巻き戻るため、この場合、

定数項： ${2g_0 - 3g_1 + 0g_2 - 1g_3}$
x¹の項： ${1g_0 + 2g_1 - 3g_2 + 0g_3}$
x²の項： ${0g_0 + 1g_1 + 2g_2 - 3g_3}$
x³の項： ${3g_0 + 0g_1 + 1g_2 - 2g_3}$

となり、結果以下の行列が得られる。

対角線上より上の要素が負になる。

8次元の格子を構成する場合、2つの3次の多項式f(x)とg(x)の係数（合計8個）だけ保持すれば済む。

FALCONでは、先程の多項式f(x)とg(x)が秘密鍵の一部となる。これらの多項式はとても短い係数を持つように選択され、公開鍵は以下のように計算される。

h(x) = g(x) / f(x) mod q

ここでqは大きな素数。これにより、h(x)の係数は0〜q-1の間のランダム値に見える。

このh(x)からf, gを復元しようとすると、以下の条件を満たす短い多項式のペアを見つける必要がある。

f(x) × h(x) ≡ g(x) (mod q)かつ、
||f||、||g||が十分小さい*1,

h(x)から作られる基底行列（公開基底）によって構成される格子と、f(x)およびg(x)から作られる秘密基底はどちらも同じ格子を構成するが、前者の基底ベクトルはとても長く、後者は短い。これは、NTRU格子上の最短ベクトル問題（SVP）の一種であり解くのが難しく、FALCON-512であれば約 ${2^{130}}$ の計算（量子コンピューターを使っても約 ${2^{65}}$ の計算）が必要とされている。

公開パラメーター

セキュリティパラメーターn（512 または 1024）。nは2の冪乗。
円分多項式 ${\phi = x^{n} + 1}$ とする
素数の法 q
離散ガウス分布の標準偏差σ
有効な署名のノルムの上限β

各パラーメータにおける公開鍵と署名のサイズは↓

安全性レベル	n	q	σ	${\lfloor β^{2}\rfloor}$	公開鍵	署名
NIST-I	512	12289	165.736617183	34034726	897 B	666 B
NIST-V	1024	12289	168.388571447	70265242	1,793 B	1,280 B

鍵生成

FALCONの秘密鍵skは、短い整数係数の4つの多項式 ${f, g, F, G \in \mathbb \lbrack x \rbrack / \phi}$ で構成される。具体的な鍵生成プロセスは↓

多項式f、gの係数を小さな離散ガウス分布から選択
fが可逆かチェック
fの逆元を計算
NTRU方程式 ${f \cdot G - g \cdot F = q (\mod x^{n} + 1)}$ を満たす、FとGを計算する
4つの短い多項式(f, g, F, G)が秘密鍵となる
fとgを使って公開鍵 ${h = g / f (\mod q)}$ を計算（悪い基底に対応）し、公開鍵とする
5の多項式から行列B（後述）を計算し、BのFFT表現FFT(B)（後述）を計算する
高速な署名計算を可能にするためFFT(B)からFALCONツリーを計算する
- FFT(B)からグラム行列Gを計算し、
- GをLDL分解しLDLツリーを構成する
- ツリー内のリーフの値を正規化してFALCONツリーを完成させる
- これにより多項式演算をO(n²)からO(n log n)に高速化し、効率的な最近接点探索を可能にする

デジタル署名スキーム

FALCONはHash-and-Sign型の署名方式で、署名スキームの大まかな流れは↓

HashToPoint関数を使って、署名対象のメッセージmとランダムなソルトr*2のSHAKE-256ハッシュを計算し、多項式c*3を導出する。cはn個の整数の点であり、これはn次元空間の点と見なすことができる。
1の点と近い格子上の点 ${v = (s_1, s_2)}$ を秘密鍵とFALCONツリーを使って見つける。ここで、 ${s_1 + s_2 h \equiv c (\mod q)}$
${(r, s_2)}$ が署名データとなる（ ${s_1}$ は計算で導出できるため）。

続いて署名データ ${(r, s_2)}$ とメッセージmおよび公開鍵hが与えられると、署名は以下のように検証される↓

HashToPoint関数を使って、署名対象のメッセージmとランダムなソルトrのSHAKE-256ハッシュを計算し、多項式cを導出する。
${s_1 = c - s_2 h (\mod q)}$ を計算し、
${|| (s_1, s_2 ) ||^{2} \lt \lfloor \beta^{2} \rfloor}$ かどうかチェックする。満たしていれば成功、そうでなければ失敗。正当な署名者だけが秘密鍵を使って短いベクトルを生成できるため、ノルムの小ささが署名の正当性を保証する。

*1:||・||はノルムを表す記号で、この場合、多項式をその係数のベクトルとして見たときの長さを示す

*2:ランダムソルトを使うことで、同じメッセージに対して毎回異なる署名が生成される。これは格子暗号を使用する場合の考慮事項で、決定論的な署名を用いた場合、攻撃者がメッセージのパターンを細工して、秘密の基底に関する統計情報が漏洩するリスクなどがある。

*3:正確にはcは多項式の係数のリスト

Develop with pleasure!

福岡でCloudとかBlockchainとか。