2008-05-14 <a href="http://eprint.iacr.org/2008/204">Cryptology ePrint Archive: Report 2008/204 - Yanbin Pan and Yingpu Deng “Cryptanalysis of the Cai-Cusick Lattice-based Public-key Cryptosystem”</a> crypt Cai-Cusick暗号とはAjtai-Dworkの構造を利用したナップサック暗号の一つ. ナップサック系の常として安全性の帰着が無い*1. 論文によればCPAの状況で1に近い確率でO(n^3)で解読可能 (ここは読んだ. 合っている.). また, CCAの状況では秘密鍵を取り出すことが出来る (こっちは流し読み. 多分あってる). *1:ナップサック系で帰着があるのって, R.Impagliazzo and M.Naor “Efficient Cryptographic Schemes Provably as Secure as Subset Sum”くらい. しかもこれは公開鍵暗号ではなく, PRGやビットコミットメントを作る話.
