STOC 2009

STOC 2009 - Accepted Papers (with Abstracts)
格子暗号は2件. Peikertだけかと思ったら, Gentryが凄いの出してきた.
イデアル格子ベースの暗号でNC1の回路をシミュレートできるらしい. エラーが足されるせいで, O(log n)までなのかな. エラーを外せれば任意の深さになるだろうけど, 格子ベースだとエラーが本質なのでそれは無理そう.

他だと,

  • Yevgeniy Dodis, Yael Tauman Kalai and Shachar Lovett “On Cryptography with Auxiliary Input.”
    • LPN系の仮定を使うらしい.
  • Huijia Lin and Rafael Pass “Non-Malleability Amplification.”
  • Yevgeniy Dodis and Daniel Wichs “One-Round Authenticated Key Agreement from Weak Secrets”

とかも気になる.