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.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Weighted LLL reductionPublic-key cryrtosystemPost-quantum cryptosystemDiophantine equation
Contact author(s)
m-kudo @ math kyushu-u ac jp
History
2016-04-07: last of 4 revisions
2015-12-23: received
See all versions
Short URL
https://ia.cr/2015/1229
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1229,
      author = {Jintai Ding and Momonari Kudo and Shinya Okumura and Tsuyoshi Takagi and Chengdong Tao},
      title = {Cryptanalysis of a public key cryptosystem based on Diophantine equations via weighted LLL reduction},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1229},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1229}},
      url = {https://eprint.iacr.org/2015/1229}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.