Peikert (ECCC TR06-148)
Peikert “Limits on the Hardness of Lattice Problems in l_p Norms” (ECCC TR06-148)
Alon Rosenと格子の話してた人.
格子上に離散化されたガウシアンl_pノルムで解析しているBanaszczykの論文があったらしい (Banaszczyk Discrete and Computational Geometry, 1995). その辺の結果を使ってl_pノルムでの様々な格子問題を解析する話. Micciancio and Regev (FOCS 2004) やAharonov and Regev (JACM 2005) なんかの結果と組み合わせて使って色々なことを証明している. Regev and Rosen (STOC 2006) の格子を異なるノルム空間への埋め込みむ話は使わなくてもいいようで.
なんかこんな話を前にしたような気がする.
Peikert and Rosen "Lattices that Admit Logarithmic Worst-Case to Average-Case Connection Factors" (ECCC TR06-147)も読むかぁ. こっちはIdeal Lattice絡みらしい. Micciancio (FOCS 2002), Lybashevsky and Micciancio (ICALP 2006), Peikert and Rosen (TCC 2006)の流れ. こっからNTRUと絡められると面白いんだけどなぁ.