新しいAjtai-Dwork暗号
Miklos Ajtai, Cynthia Dwork "The First and Fourth Public-Key Cryptosystems with Worst-Case/Average-Case Equivalence." (ECCC TR07-097)
96年以降話題となったAjtai-Dwork暗号*1が生まれ変わりましたという論文. TR96-065の方のAjtai-Dwork暗号IIIを元にパラメータを変更して解析を良くしたり, 1ビット暗号だったのをlビット暗号に変更している. MicciancioやRegevが導入したガウス分布の格子上のフーリエ解析から得られる結果を武器に解析を行い, 仮定をO~(n^2)-uSVPの最悪時の困難性にまで下げている*2.
次元をnのままにするのではなくn+lに変えているらしい. 解析が良くなったので, 公開鍵のサイズはO~(n^5)からO(n^4)に減らされている.
あとで詳しく読むかー. 前の論文よりは可読性が上がっているので読みやすそうだし.
追記:復号が上手くいかない．ちょっと弄れば直るので証明は大丈夫だと思うが，証明を書き直す必要があると思う．
