<a href="http://eprint.iacr.org/2006/460">Cryptology ePrint Archive: Report 2006/460 - Donghoon Chang "Preimage Attacks On Provably Secure FFT Hashing proposed at Second Hash Workshop in 2006"</a>

ePrintにあったので読んだ.
Lyubashevsky, Micciancio, Peikert, and Rosenのsecure FFT hashingを格子の言葉で言い直すと,

  • n次元縦ベクトルをm本用意して, それぞれにcirculant matrixを作り横につなげAという(n*m)×nの行列を作る.
  • 入力値はZ_q^{n*m}中のベクトル m (ただし 各要素は{0,1,...,d-1}に入っている)
  • 出力はZ_q^n中のベクトル Am

となっている.
で, このアタックを格子の言葉で言い直すと, 出力を見て, n*(m-1)個の要素を総当たりすれば残りのn個の要素は決まるという至極当然のことを言っている. mやnが小さい (即ち次元が低い) 場合にこのアタックが利いてくることには同意するが, これをPreimageを求めるアタックと言っていいのかどうか非常に悩む. 当たり前やんとしか言いようがない.