Practical algebraic cryptanalysis for dragon-based cryptosystems

Johannes Buchmann; Stanislav Bulygin; Jintai Ding; Wael Said Abd Elmageed Mohamed; Fabian Werner

doi:10.1007/978-3-642-17619-7_11

Practical algebraic cryptanalysis for dragon-based cryptosystems

Johannes Buchmann^*, Stanislav Bulygin, Jintai Ding, Wael Said Abd Elmageed Mohamed, Fabian Werner

^*Corresponding author for this work

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

2 Citations (Scopus)

Abstract

Recently, the Little Dragon Two and Poly-Dragon multivariate based public-key cryptosystems were proposed as efficient and secure schemes. In particular, the inventors of the two schemes claim that Little Dragon Two and Poly-Dragon resist algebraic cryptanalysis. In this paper, we show that MXL2, an algebraic attack method based on the XL algorithm and Ding's concept of Mutants, is able to break Little Dragon Two with keys of length up to 229 bits and Poly-Dragon with keys of length up to 299. This contradicts the security claim for the proposed schemes and demonstrates the strength of MXL2 and the Mutant concept. This strength is further supported by experiments that show that in attacks on both schemes the MXL2 algorithm outperforms the Magma's implementation of F4.

Original language	English
Title of host publication	Cryptology and Network Security - 9th International Conference, CANS 2010, Proceedings
Pages	140-155
Number of pages	16
DOIs	https://doi.org/10.1007/978-3-642-17619-7_11
Publication status	Published - 2010
Externally published	Yes
Event	9th International Conference on Cryptology and Network Security, CANS 2010 - Kuala Lumpur, Malaysia Duration: 12 Dec 2010 → 14 Dec 2010

Publication series

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

Conference

Conference	9th International Conference on Cryptology and Network Security, CANS 2010
Country/Territory	Malaysia
City	Kuala Lumpur
Period	12/12/10 → 14/12/10

Access to Document

10.1007/978-3-642-17619-7_11

Cite this

Buchmann, J., Bulygin, S., Ding, J., Mohamed, W. S. A. E., & Werner, F. (2010). Practical algebraic cryptanalysis for dragon-based cryptosystems. In Cryptology and Network Security - 9th International Conference, CANS 2010, Proceedings (pp. 140-155). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6467 LNCS). https://doi.org/10.1007/978-3-642-17619-7_11

Buchmann, Johannes ; Bulygin, Stanislav ; Ding, Jintai et al. / Practical algebraic cryptanalysis for dragon-based cryptosystems. Cryptology and Network Security - 9th International Conference, CANS 2010, Proceedings. 2010. pp. 140-155 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{13793fcecbae4c28b4e52eb8522a2415,

title = "Practical algebraic cryptanalysis for dragon-based cryptosystems",

abstract = "Recently, the Little Dragon Two and Poly-Dragon multivariate based public-key cryptosystems were proposed as efficient and secure schemes. In particular, the inventors of the two schemes claim that Little Dragon Two and Poly-Dragon resist algebraic cryptanalysis. In this paper, we show that MXL2, an algebraic attack method based on the XL algorithm and Ding's concept of Mutants, is able to break Little Dragon Two with keys of length up to 229 bits and Poly-Dragon with keys of length up to 299. This contradicts the security claim for the proposed schemes and demonstrates the strength of MXL2 and the Mutant concept. This strength is further supported by experiments that show that in attacks on both schemes the MXL2 algorithm outperforms the Magma's implementation of F4.",

author = "Johannes Buchmann and Stanislav Bulygin and Jintai Ding and Mohamed, {Wael Said Abd Elmageed} and Fabian Werner",

year = "2010",

doi = "10.1007/978-3-642-17619-7_11",

language = "English",

isbn = "3642176186",

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

pages = "140--155",

booktitle = "Cryptology and Network Security - 9th International Conference, CANS 2010, Proceedings",

note = "9th International Conference on Cryptology and Network Security, CANS 2010 ; Conference date: 12-12-2010 Through 14-12-2010",

}

Buchmann, J, Bulygin, S, Ding, J, Mohamed, WSAE & Werner, F 2010, Practical algebraic cryptanalysis for dragon-based cryptosystems. in Cryptology and Network Security - 9th International Conference, CANS 2010, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6467 LNCS, pp. 140-155, 9th International Conference on Cryptology and Network Security, CANS 2010, Kuala Lumpur, Malaysia, 12/12/10. https://doi.org/10.1007/978-3-642-17619-7_11

Practical algebraic cryptanalysis for dragon-based cryptosystems. / Buchmann, Johannes; Bulygin, Stanislav; Ding, Jintai et al.
Cryptology and Network Security - 9th International Conference, CANS 2010, Proceedings. 2010. p. 140-155 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6467 LNCS).

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

TY - GEN

T1 - Practical algebraic cryptanalysis for dragon-based cryptosystems

AU - Buchmann, Johannes

AU - Bulygin, Stanislav

AU - Ding, Jintai

AU - Mohamed, Wael Said Abd Elmageed

AU - Werner, Fabian

PY - 2010

Y1 - 2010

N2 - Recently, the Little Dragon Two and Poly-Dragon multivariate based public-key cryptosystems were proposed as efficient and secure schemes. In particular, the inventors of the two schemes claim that Little Dragon Two and Poly-Dragon resist algebraic cryptanalysis. In this paper, we show that MXL2, an algebraic attack method based on the XL algorithm and Ding's concept of Mutants, is able to break Little Dragon Two with keys of length up to 229 bits and Poly-Dragon with keys of length up to 299. This contradicts the security claim for the proposed schemes and demonstrates the strength of MXL2 and the Mutant concept. This strength is further supported by experiments that show that in attacks on both schemes the MXL2 algorithm outperforms the Magma's implementation of F4.

AB - Recently, the Little Dragon Two and Poly-Dragon multivariate based public-key cryptosystems were proposed as efficient and secure schemes. In particular, the inventors of the two schemes claim that Little Dragon Two and Poly-Dragon resist algebraic cryptanalysis. In this paper, we show that MXL2, an algebraic attack method based on the XL algorithm and Ding's concept of Mutants, is able to break Little Dragon Two with keys of length up to 229 bits and Poly-Dragon with keys of length up to 299. This contradicts the security claim for the proposed schemes and demonstrates the strength of MXL2 and the Mutant concept. This strength is further supported by experiments that show that in attacks on both schemes the MXL2 algorithm outperforms the Magma's implementation of F4.

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

U2 - 10.1007/978-3-642-17619-7_11

DO - 10.1007/978-3-642-17619-7_11

M3 - Conference Proceeding

AN - SCOPUS:78651084285

SN - 3642176186

SN - 9783642176180

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

SP - 140

EP - 155

BT - Cryptology and Network Security - 9th International Conference, CANS 2010, Proceedings

T2 - 9th International Conference on Cryptology and Network Security, CANS 2010

Y2 - 12 December 2010 through 14 December 2010

ER -

Buchmann J, Bulygin S, Ding J, Mohamed WSAE, Werner F. Practical algebraic cryptanalysis for dragon-based cryptosystems. In Cryptology and Network Security - 9th International Conference, CANS 2010, Proceedings. 2010. p. 140-155. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-17619-7_11

Practical algebraic cryptanalysis for dragon-based cryptosystems

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this