Breaking and Improving a Lattice-Code-Based Cryptosystem by Li, Ling, Xing, and Yeo

Li, Ling, Xing, and Yeo (LLXY) have proposed a code-based encryption scheme based on factoring in finite fields. The security of the scheme relies on both the decoding problem for (q – 1)-ary codes, and the Bounded Distance Decoding problem for the ℓ-norm in a family of lattices. On the negative side, we describe a Chosen Ciphertext Attack that breaks the claimed CCA protection proposed by LLXY. We also extend a previous cryptanalysis by Lapiha using decoding attacks, and argue that the May-Ozerov information set decoding attack is the most powerful decoding attack on the scheme. On the positive side, we streamline the description of the scheme and give simple algorithms to generate the public keys. We also give a Niederreiter version of the scheme that has smaller ciphertexts, and show how to correctly obtain a CCA secure Key Encapsulation Mechanism by using standard techniques.