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

Jintai Ding; Momonari Kudo; Shinya Okumura; Tsuyoshi Takagi; Chengdong Tao

doi:10.1007/978-3-319-44524-3_18

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: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

1 Citation (Scopus)

Abstract

Okumura proposed a candidate of post-quantum cryptosystem based on Diophantine equations of degree increasing type (DEC). Sizes of public keys in DEC are small, e.g., 1,200 bits for 128 bit security, and it is a strongly desired property in post-quantum erea. In this paper, we propose a polynomial time attack against DEC. We show that the one-wayness of DEC is reduced to finding special (relatively) short vectors in some lattices. The usual LLL algorithm does not work well for finding the most important target vector in our attack. The most technical point of our method is to heuristically find a special norm called a weighted norm to find the most important target vector. We call this method "weighted LLL algorithm" in this paper. Our experimental results suggest that our attack can break the one-wayness of DEC for 128 bit security with sufficiently high probability.

Original language	English
Title of host publication	Advances in Information and Computer Security - 11th International Workshop on Security, IWSEC 2016, Proceedings
Editors	Katsunari Yoshioka, Kazuto Ogawa
Publisher	Springer Verlag
Pages	305-315
Number of pages	11
ISBN (Print)	9783319445236
DOIs	https://doi.org/10.1007/978-3-319-44524-3_18
Publication status	Published - 2016
Externally published	Yes
Event	11th International Workshop on Security on Advances in Information and Computer Security, IWSEC 2016 - Tokyo, Japan Duration: 12 Sept 2016 → 14 Sept 2016

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9836 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	11th International Workshop on Security on Advances in Information and Computer Security, IWSEC 2016
Country/Territory	Japan
City	Tokyo
Period	12/09/16 → 14/09/16

Keywords

Diophantine equation
Post-quantum cryptosystem
Weighted LLL reduction

Access to Document

10.1007/978-3-319-44524-3_18

Cite this

Ding, J., Kudo, M., Okumura, S., Takagi, T., & Tao, C. (2016). Cryptanalysis of a public key cryptosystem based on diophantine equations via weighted LLL reduction. In K. Yoshioka, & K. Ogawa (Eds.), Advances in Information and Computer Security - 11th International Workshop on Security, IWSEC 2016, Proceedings (pp. 305-315). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9836 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-44524-3_18

Ding, Jintai ; Kudo, Momonari ; Okumura, Shinya et al. / Cryptanalysis of a public key cryptosystem based on diophantine equations via weighted LLL reduction. Advances in Information and Computer Security - 11th International Workshop on Security, IWSEC 2016, Proceedings. editor / Katsunari Yoshioka ; Kazuto Ogawa. Springer Verlag, 2016. pp. 305-315 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{d0e383b8aed449f483840f97586bf833,

title = "Cryptanalysis of a public key cryptosystem based on diophantine equations via weighted LLL reduction",

abstract = "Okumura proposed a candidate of post-quantum cryptosystem based on Diophantine equations of degree increasing type (DEC). Sizes of public keys in DEC are small, e.g., 1,200 bits for 128 bit security, and it is a strongly desired property in post-quantum erea. In this paper, we propose a polynomial time attack against DEC. We show that the one-wayness of DEC is reduced to finding special (relatively) short vectors in some lattices. The usual LLL algorithm does not work well for finding the most important target vector in our attack. The most technical point of our method is to heuristically find a special norm called a weighted norm to find the most important target vector. We call this method {"}weighted LLL algorithm{"} in this paper. Our experimental results suggest that our attack can break the one-wayness of DEC for 128 bit security with sufficiently high probability.",

keywords = "Diophantine equation, Post-quantum cryptosystem, Weighted LLL reduction",

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

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 11th International Workshop on Security on Advances in Information and Computer Security, IWSEC 2016 ; Conference date: 12-09-2016 Through 14-09-2016",

year = "2016",

doi = "10.1007/978-3-319-44524-3_18",

language = "English",

isbn = "9783319445236",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "305--315",

editor = "Katsunari Yoshioka and Kazuto Ogawa",

booktitle = "Advances in Information and Computer Security - 11th International Workshop on Security, IWSEC 2016, Proceedings",

}

Ding, J, Kudo, M, Okumura, S, Takagi, T & Tao, C 2016, Cryptanalysis of a public key cryptosystem based on diophantine equations via weighted LLL reduction. in K Yoshioka & K Ogawa (eds), Advances in Information and Computer Security - 11th International Workshop on Security, IWSEC 2016, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9836 LNCS, Springer Verlag, pp. 305-315, 11th International Workshop on Security on Advances in Information and Computer Security, IWSEC 2016, Tokyo, Japan, 12/09/16. https://doi.org/10.1007/978-3-319-44524-3_18

Cryptanalysis of a public key cryptosystem based on diophantine equations via weighted LLL reduction. / Ding, Jintai; Kudo, Momonari; Okumura, Shinya et al.
Advances in Information and Computer Security - 11th International Workshop on Security, IWSEC 2016, Proceedings. ed. / Katsunari Yoshioka; Kazuto Ogawa. Springer Verlag, 2016. p. 305-315 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9836 LNCS).

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

TY - GEN

T1 - Cryptanalysis of a public key cryptosystem based on diophantine equations via weighted LLL reduction

AU - Ding, Jintai

AU - Kudo, Momonari

AU - Okumura, Shinya

AU - Takagi, Tsuyoshi

AU - Tao, Chengdong

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2016.

PY - 2016

Y1 - 2016

N2 - Okumura proposed a candidate of post-quantum cryptosystem based on Diophantine equations of degree increasing type (DEC). Sizes of public keys in DEC are small, e.g., 1,200 bits for 128 bit security, and it is a strongly desired property in post-quantum erea. In this paper, we propose a polynomial time attack against DEC. We show that the one-wayness of DEC is reduced to finding special (relatively) short vectors in some lattices. The usual LLL algorithm does not work well for finding the most important target vector in our attack. The most technical point of our method is to heuristically find a special norm called a weighted norm to find the most important target vector. We call this method "weighted LLL algorithm" in this paper. Our experimental results suggest that our attack can break the one-wayness of DEC for 128 bit security with sufficiently high probability.

AB - Okumura proposed a candidate of post-quantum cryptosystem based on Diophantine equations of degree increasing type (DEC). Sizes of public keys in DEC are small, e.g., 1,200 bits for 128 bit security, and it is a strongly desired property in post-quantum erea. In this paper, we propose a polynomial time attack against DEC. We show that the one-wayness of DEC is reduced to finding special (relatively) short vectors in some lattices. The usual LLL algorithm does not work well for finding the most important target vector in our attack. The most technical point of our method is to heuristically find a special norm called a weighted norm to find the most important target vector. We call this method "weighted LLL algorithm" in this paper. Our experimental results suggest that our attack can break the one-wayness of DEC for 128 bit security with sufficiently high probability.

KW - Diophantine equation

KW - Post-quantum cryptosystem

KW - Weighted LLL reduction

UR - http://www.scopus.com/inward/record.url?scp=84987933707&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-44524-3_18

DO - 10.1007/978-3-319-44524-3_18

M3 - Conference Proceeding

AN - SCOPUS:84987933707

SN - 9783319445236

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 305

EP - 315

BT - Advances in Information and Computer Security - 11th International Workshop on Security, IWSEC 2016, Proceedings

A2 - Yoshioka, Katsunari

A2 - Ogawa, Kazuto

PB - Springer Verlag

T2 - 11th International Workshop on Security on Advances in Information and Computer Security, IWSEC 2016

Y2 - 12 September 2016 through 14 September 2016

ER -

Ding J, Kudo M, Okumura S, Takagi T, Tao C. Cryptanalysis of a public key cryptosystem based on diophantine equations via weighted LLL reduction. In Yoshioka K, Ogawa K, editors, Advances in Information and Computer Security - 11th International Workshop on Security, IWSEC 2016, Proceedings. Springer Verlag. 2016. p. 305-315. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-44524-3_18

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

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this