概要
格子暗号のバックエンドでなぜフーリエ変換を使うNTLなどのライブラリが使われているかを初歩的ながら考えてみた。備忘録的な要素あり。
内容
- 格子暗号
- 離散フーリエ変換(DFT)
- 高速フーリエ変換 (FFT)
- バタフライ演算
格子暗号
量子コンピュータ耐性があり、さらに加算と乗算に関しての完全準同型性があるとされ注目されている次世代の暗号スキームのこと。
ひどく簡単にまとめると、多項式環を公開鍵である多項式でイデアル化することによって暗号空間へとマッピングし、その空間での準同型性を用いることで、暗号空間での演算を可能にしている。
大きい多項式を用い、それらの演算をする際に、畳み込み演算が必要となる。この際に、離散フーリエ変換が高速化のために必要となる。
離散フーリエ変換
正直言って、wikipediaの離散フーリエ変換の記事で説明は事足りる。
ひどく簡単にまとめると、有限体の標本点を用いて離散化されたフーリエ変換を行う。いろいろな応用先があるが、その１つとして多項式の乗算（本質的には畳み込み）を簡単に行えるため、格子暗号のライブラリでは離散フーリエ変換を裏で用いている。
このproject nayukiのページに多項式の乗算を、DFTを用いて高速化するやり方がわかりやすくまとめられていたので参考にしたい。
高速フーリエ変換
これに関してもwikipediaの高速フーリエ変換の記事がわかりやすい。
簡単にまとめると、高速フーリエ変換は上の離散フーリエ変換を高速に行うための手法である。例えば、 N次元の多項式同士の乗算を考える時に、お互いを離散フーリエ変換したもの同士を乗算し、結果を離散フーリエ逆変換すると畳み込み結果が得られるが、これを正直にやるとO(N^2)の計算量が必要である。しかし、高速フーリエ変換を用いると、これがO(NlogN)で済む。これは、Nが因数分解できるとき、例えばN=PQとできるときは、N次元のベクトルに対する離散フーリエ変換が、P組のQ次元離散フーリエ変換に変換できるからである。この際、Nが２の乗数で書かれているとすると、この落とし込みを繰り返すことで最終的に２次の離散フーリエ変換（２次と４次はより早く求めることができるため、区別される）にできる。このため、格子暗号では多項式の剰余環のモジュラスとして、２のN次のオーダーの多項式を使うことが一般的である。（多分他にもこれを使う理由はある。）
バタフライ演算
上の高速フーリエ変換において、低次の２次もしくは４次の離散フーリエ変換を行うことを、バタフライ演算と呼ぶ。
これからも格子暗号などを中心に簡単に論文などをまとめていければいいと思うので、もし興味ある人いましたら「いいね」、「コメント」お待ちしております。
おわり