Paper 2015/1229

Cryptanalysis of a public key cryptosystem based on Diophantine equations via weighted LLL reduction

Jintai Ding, Momonari Kudo, Shinya Okumura, Tsuyoshi Takagi, and Chengdong Tao

Abstract

Post-quantum cryptography now plays a central role in cryptography. Many candidates of post-quantum cryptosystems (PQC) have been already proposed but require public keys of large sizes. Constructing PQC with public keys of small sizes is strongly desired. In [Oku15], Okumura proposed a public key cryptosystem based on the difficulty of solving Diophantine equations of degree increasing type (DEC for short). DEC is proposed as an analogue of the Algebraic Surface Cryptosystem [AGM09]. DEC has been expected to avoid the analogues of all attacks against ASC (and the previous versions of ASC). Moreover, DEC has been expected to be a candidate of PQC and to achieve the high security with public keys of small sizes, e.g., about 1;200 bits with 128 bit security. In this paper, we propose a polynomial time attack against DEC. 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 with respect to well-known norms such as the $p$-norms ($1 \leq p \leq 1$) does not seem to work well for finding such vectors. The most technical point of our method is to heuristically find a special norm, which we call a weighted norm, such that the most important target vector becomes a (nearly) shortest vector in a lattice of low rank. We call the LLL algorithm with respect to a weighted norm the ``weighted LLL algorithm" in this paper. Our experimental results by a standard PC with Magma suggest that our attack via the weighted LLL algorithm can break the one-wayness of DEC for 128 bit security proposed in [Oku15] with sufficiently high probability.