SWIFFT読んだ

crypt

Peikertのサイトに草稿があったので読んだ.
f(\alpha)=\alpha^n+1とおく. nが2の冪のとき, \alpha^n+1はZ上既約. a_0,...,a_{m-1}をR=\mathbb{Z}_q[\alpha]/(f(\alpha))の要素とする.
Hを圧縮関数とし, 入力をmnビット列xとする.

  1. 入力xをm個のnビット列に分割 (x_0,...,x_{m-1}をRの要素と見る)
  2. z=\sum_{i=0}^{m-1} a_i x_iを出力とする
    1. 正確には違う. 各a_i x_iを計算する際に, DFTを使う
      1. a_i'=DFT(a_i), x_i'=DFT(x_i)としておいて, a_i' x_i'を計算
    2. で, そのまま足して, 逆DFTを経由せずに出力する (筈).

がH. R上の積の計算にFFT (正確にはNTT) が使えるので相当速い.
適切にn, m, qを選ぶと, 安全性は\mathbb{Z}[\alpha]/(f(\alpha))中のイデアルと同型な格子の最短ベクトル問題の最悪時に帰着される.
SWIFFTでは, n=64, m=16, q=257として高速化を狙っているようだ (このパラメータでは帰着付かないんじゃないか?). 圧縮関数HはH:\{0,1\}^{1024}\to\mathbb{Z}_q^{64}. 1024ビットを約356ビットへ圧縮する関数になっている. そこそこのアルゴリズム的な最適化でPen4 3GHzのマシンを使って処理速度が40MB/sらしい. SHA1は48MB/sだったからほぼ互角. 並列化が可能な場合には, より高速化される点が魅力的という話.
5章に攻撃に対する考察があるのだが, LASHに対する攻撃が余りにも簡単で笑った. 後で提案パラメータに対して攻撃できるかどうか考えてみよう.