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

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

Researching post-quantum cryptography is now an important task in cryptography. Although various candidates of post-quantum cryptosystems (PQC) have been constructed, sizes of their public keys are large. Okumura constructed a candidate of PQC whose security is expected to be based on certain Diophantine equations (DEC). Okumura analysis suggests that DEC achieves the high security with small public key sizes. This paper proposes a polynomial time-attack on the one-way property of DEC. We reduce the security of DEC to finding special short lattice points of some low-rank lattices derived from public data. The usual LLL algorithm could not find the most important lattice point in our experiments because of certain properties of the lattice point. Our heuristic analysis leads us to using a variant of the LLL algorithm, called a weighted LLL algorithm by us. Our experiments suggest that DEC with 128 bit security becomes insecure by our attack.

Original languageEnglish
Pages (from-to)1123-1152
Number of pages30
JournalJapan Journal of Industrial and Applied Mathematics
Volume35
Issue number3
DOIs
Publication statusPublished - 1 Nov 2018
Externally publishedYes

Keywords

  • Diophantine equation
  • Post-quantum cryptosystem
  • Public-key cryptosystem
  • Weighted LLL reduction

Fingerprint

Dive into the research topics of 'Cryptanalysis of a public key cryptosystem based on Diophantine equations via weighted LLL reduction'. Together they form a unique fingerprint.

Cite this