Algebraic attack on the MQQ public key cryptosystem

Mohamed Saied Emam Mohamed; Jintai Ding; Johannes Buchmann; Fabian Werner

doi:10.1007/978-3-642-10433-6_26

Algebraic attack on the MQQ public key cryptosystem

Mohamed Saied Emam Mohamed, Jintai Ding, Johannes Buchmann, Fabian Werner

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

22 Citations (Scopus)

Abstract

In this paper, we present an efficient attack on the multivariate Quadratic Quasigroups (MQQ) public key cryptosystem. Our cryptanalysis breaks the MQQ cryptosystem by solving a system of multivariate quadratic polynomial equations using both the MutantXL algorithm and the F₄ algorithm. We present the experimental results that show that MQQ systems is broken up to size n equal to 300. Based on these results we show also that MutantXL solves MQQ systems with much less memory than the F₄ algorithm implemented in Magma.

Original language	English
Title of host publication	Cryptology and Network Security - 8th International Conference, CANS 2009, Proceedings
Pages	392-401
Number of pages	10
DOIs	https://doi.org/10.1007/978-3-642-10433-6_26
Publication status	Published - 2009
Externally published	Yes
Event	8th International Conference on Cryptology and Network Security, CANS 2009 - Kanazawa, Japan Duration: 12 Dec 2009 → 14 Dec 2009

Publication series

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

Conference

Conference	8th International Conference on Cryptology and Network Security, CANS 2009
Country/Territory	Japan
City	Kanazawa
Period	12/12/09 → 14/12/09

Keywords

Algebraic Cryptanalysis
F algorithm
MQQ public key cryptosystem
MutantXL algorithm

Access to Document

10.1007/978-3-642-10433-6_26

Cite this

Mohamed, M. S. E., Ding, J., Buchmann, J., & Werner, F. (2009). Algebraic attack on the MQQ public key cryptosystem. In Cryptology and Network Security - 8th International Conference, CANS 2009, Proceedings (pp. 392-401). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5888 LNCS). https://doi.org/10.1007/978-3-642-10433-6_26

@inproceedings{67e9179b86c94238b4f3b0e99157f92c,

title = "Algebraic attack on the MQQ public key cryptosystem",

abstract = "In this paper, we present an efficient attack on the multivariate Quadratic Quasigroups (MQQ) public key cryptosystem. Our cryptanalysis breaks the MQQ cryptosystem by solving a system of multivariate quadratic polynomial equations using both the MutantXL algorithm and the F4 algorithm. We present the experimental results that show that MQQ systems is broken up to size n equal to 300. Based on these results we show also that MutantXL solves MQQ systems with much less memory than the F4 algorithm implemented in Magma.",

keywords = "Algebraic Cryptanalysis, F algorithm, MQQ public key cryptosystem, MutantXL algorithm",

author = "Mohamed, {Mohamed Saied Emam} and Jintai Ding and Johannes Buchmann and Fabian Werner",

year = "2009",

doi = "10.1007/978-3-642-10433-6_26",

language = "English",

isbn = "3642104320",

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

pages = "392--401",

booktitle = "Cryptology and Network Security - 8th International Conference, CANS 2009, Proceedings",

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

}

Mohamed, MSE, Ding, J, Buchmann, J & Werner, F 2009, Algebraic attack on the MQQ public key cryptosystem. in Cryptology and Network Security - 8th International Conference, CANS 2009, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5888 LNCS, pp. 392-401, 8th International Conference on Cryptology and Network Security, CANS 2009, Kanazawa, Japan, 12/12/09. https://doi.org/10.1007/978-3-642-10433-6_26

Algebraic attack on the MQQ public key cryptosystem. / Mohamed, Mohamed Saied Emam; Ding, Jintai; Buchmann, Johannes et al.
Cryptology and Network Security - 8th International Conference, CANS 2009, Proceedings. 2009. p. 392-401 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5888 LNCS).

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

TY - GEN

T1 - Algebraic attack on the MQQ public key cryptosystem

AU - Mohamed, Mohamed Saied Emam

AU - Ding, Jintai

AU - Buchmann, Johannes

AU - Werner, Fabian

PY - 2009

Y1 - 2009

N2 - In this paper, we present an efficient attack on the multivariate Quadratic Quasigroups (MQQ) public key cryptosystem. Our cryptanalysis breaks the MQQ cryptosystem by solving a system of multivariate quadratic polynomial equations using both the MutantXL algorithm and the F4 algorithm. We present the experimental results that show that MQQ systems is broken up to size n equal to 300. Based on these results we show also that MutantXL solves MQQ systems with much less memory than the F4 algorithm implemented in Magma.

AB - In this paper, we present an efficient attack on the multivariate Quadratic Quasigroups (MQQ) public key cryptosystem. Our cryptanalysis breaks the MQQ cryptosystem by solving a system of multivariate quadratic polynomial equations using both the MutantXL algorithm and the F4 algorithm. We present the experimental results that show that MQQ systems is broken up to size n equal to 300. Based on these results we show also that MutantXL solves MQQ systems with much less memory than the F4 algorithm implemented in Magma.

KW - Algebraic Cryptanalysis

KW - F algorithm

KW - MQQ public key cryptosystem

KW - MutantXL algorithm

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

U2 - 10.1007/978-3-642-10433-6_26

DO - 10.1007/978-3-642-10433-6_26

M3 - Conference Proceeding

AN - SCOPUS:71549124018

SN - 3642104320

SN - 9783642104329

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

SP - 392

EP - 401

BT - Cryptology and Network Security - 8th International Conference, CANS 2009, Proceedings

T2 - 8th International Conference on Cryptology and Network Security, CANS 2009

Y2 - 12 December 2009 through 14 December 2009

ER -

Mohamed MSE, Ding J, Buchmann J, Werner F. Algebraic attack on the MQQ public key cryptosystem. In Cryptology and Network Security - 8th International Conference, CANS 2009, Proceedings. 2009. p. 392-401. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-10433-6_26

Algebraic attack on the MQQ public key cryptosystem

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this