2009-06-30期待されているようなので, Gentryの暗号 (STOC 2009) については簡単な解説を後日書きます. 今のところフルヴァージョンは公開されていないので, 詳しいテクニックはぼかして書く方向で. 乗法的準同型性, 加法的準同型性, 制限付き加法的準同型性, 制限付き環準同型性, 制限無し環準同型性辺りといった歴史を押さえて書いた方が良いか. 30年来の未解決問題でもあったことだし. ものすごい大雑把に言うとNTRUとGGHの拡張みたいなもんです. アイデアはそっちに近い. ただこれだけだとANDやORの素子を評価するたびにエラーが溜まっていくので, 一旦内部で復号してエラーをキャンセルします. そのために最近流行のKDM安全性を仮定して, 秘密鍵を暗号化してそれを公開鍵に含めておく. すると, 復号回路をエミュレート出来るというアイデアです. あと取り急ぎ指摘しておくと, Apple
