メモと論文紹介
前に予告されていたPeikert and VaikuntanathanはGentryも入っていた. IBEで参加したぽい.
C. Gentry, C. Peikert, V. Vaikuntanathan. "Trapdoors for Hard Lattices and New Cryptographic Constructions." (Cryptology ePrint Archive 2007/432)
書き直し
格子上に離散化されたガウス分布は解析に使われていたが, 最短ベクトルを知っていると実はサンプリング出来る. しかもBabaiのnearest-planeをランダマイズしただけ. (Kelinも同じようなことをやっている.) MicciancioとRegevが導入したsmoothing parameterでこの解析が上手くいく. これが基本.
で, Ajtaiが99年にSBPの最悪時/平均時を作っているので, 公開鍵を格子の基底にして, 秘密鍵をその短い基底にする. Micciancio-GGH暗号のよう, 歪んだ基底の方の基本領域上で関数の評価を行えば良い. {x|Ax=0 mod q}を格子とする. 関数を評価する際はeをZ^m上に離散化されたガウス分布としてf_A(e)=Ae mod qを出力. 関数を逆算するときは, (1) At=u mod qとなるtを求め (2) トラップドアを用いてAv=0 mod qとなるv (ガウス分布に従う) を求め (3) e=t+vを出力する.
応用として格子問題ベースの署名, LWEベースのUCOT, LWEベースの匿名IBE (in ROM)を作っている.
署名はランダムオラクルモデルの下でsEUF-CMA安全. 使っている関数が特殊な強衝突耐性ハッシュ関数でもあるので帰着は相当タイト. 署名偽造成功確率がεとすると衝突を発見する確率はε-negl(n).
暗号の方はRegev05を基にDual Cryptosystemを構成して作っている. 丁度Regev暗号と双対の処で話が進む. 先程のf_A(e)=uとするとeが秘密鍵, uが公開鍵になるんだな. で, uが一様分布だとeはAの秘密情報を知っている人だと求められる. なのでuをH(ID)にするとID暗号も出来るという寸法. 何だこりゃ.
8章のIncIVDからSISへの帰着の解析が良くなっている点はこっちでも使えるかな.
あと関数を紹介するときに結構符号の用語を使っている. ポジティブな応用方面ではRegev05と自分の以外では始めて見た気がする. ISIS=SDPということもちゃんと書いてある.
S. Contini, K. Matusiewicz, J. Pieprzyk, R. Steinfeld, J. Guo, S. Ling, H. Wang. "Cryptanalysis of LASH." (Cryptology ePrint Archive 2007/430)
NTRU系の人が出していた格子ベースのハッシュを解析したという話. collision一歩手前まで計算した様子. 初期値がオール0だったので解析が楽だったそうな.
