GGHの1つ目。

アルファベット順に並んでいたので、最初は“Collision-Free Hashing from Lattice Problems”(入手先:Using Lattice Problem in Cryptography)から。
読んでみたらば、Ajtaiの“Generating Hard Instances of Lattice Problems”の拡張。いやー、ランダムなインスタンスが作れたら、ハッシュも作れるやん? という話だった。本当にそれだけなので9頁しかない。しかし議論の流れはAjtaiよりも数倍分かりやすい。いや、別にAjtaiを貶したい訳じゃないのよ。けど読みにくいのよ。ACMの書式が悪いだけだとは思うけど。
論文の書き方の参考にはなったな。

次は、“Eliminating Decryption Erros in the Ajtai-Dwork Cryptosystem”か。Ajtai-Dwork暗号の論文と並行して読むことにしよう。