読者です 読者をやめる 読者になる 読者になる

<a href="http://eprint.iacr.org/2008/204">Cryptology ePrint Archive: Report 2008/204 - Yanbin Pan and Yingpu Deng &ldquo;Cryptanalysis of the Cai-Cusick Lattice-based Public-key Cryptosystem&rdquo;</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やビットコミットメントを作る話.