最近の格子ネタ

  • お久しぶりです.
  • C. Gentry. “Fully homomorphic encryption using ideal lattices.” (STOC 2009)
    • えーとね, あんまり細かく読む気が起きてないんだけど. 安全性に関してはぱっと見それNTRU以下だろうという感じ. どうなんだろうね.
    • うーん, mod qを取らないNTRUというかGGHというか. ちょっと真面目に考えよう.
    • KDM安全性を仮定すると回路をエミュレート出来るってのはいいですね. これは使えそう.
    • ただKDM安全性がきついなぁ.
  • D. Stehlé, R. Steinfeld, K. Tanaka, K. Xagawa “Efficient Public Key Encryption Based on Ideal Lattices.” (ePrint 2009/285)
    • これもあんまり読んでないけどね.
    • Gentry, Peikert, and Vaikuntanathan (STOC 2008) とPeikert (STOC 2009) のイデアル格子版.
      • 基底生成にはAlwen and Peikert (STACS 2009) ではなくて, Ajtai (ICALP 1999) を使っている.
      • Regevの量子帰着もPeikertの古典帰着もそのままでは使えないので, 一回SISに帰着するというテクニック.
      • あとIDベース認証と署名の話もついてる.
      • IND-CCA2もやってるみたい.

あとは, WEWoRCダルムシュタット系の人たちが2本分くらい話すようです.