International Association
for Cryptologic Research

In this paper, we give an attack against a public key cryptosystem based on Diophantine equations of degree increasing type (DEC) proposed by the third author ([Oku15]). We show that the security of DEC depends on the difficulty of finding special (relatively) short vectors in some lattices obtained from a public key and a ciphertext. The most important target vector in our attack is not necessarily a shortest vector in a lattice of low rank but only some entries are relatively small. In our attack, the LLL algorithm does not work well for finding such vectors. The technical point of our method is to change a norm dealt with in the usual LLL algorithm from the Euclidean norm to a special norm called a weighted norm. We call the LLL algorithm with respect to a weighted norm the ``weighted LLL algorithm'' in this paper. Our heuristic analysis suggests that the most important target vector in our attack becomes a shorter vector with respect to a weighted norm for an appropriate weight among the vectors in the lattice of low rank. Our experimental results by a standard PC with Magma suggest that our attack with the weighted LLL algorithm can recover a plaintext without finding a secret key for 128 bit security proposed in [Oku15] with sufficiently high probability.