Paper 2008/451

Algebraic Cryptanalysis of MQQ Public Key Cryptosystem by MutantXL

Mohamed Saied Emam Mohamed, Jintai Ding, and Johannes Buchmann

Abstract

In this paper, we present an efficient attack to the multivariate Quadratic Quasigroups (MQQ) cryptosystem. Our cryptanalysis breaks MQQ cryptosystems by solving systems of multivariate quadratic polynomial equations using a modified version of the MutantXL algorithm. We present experimental results comparing the behavior of our implementation of MutantXL to Magma's implementation of $F_4$ on MQQ systems ($\geq$ 135 bit). Based on our results we show that the MutantXL implementation solves with much less memory than Magma's implementation of $F_4$ algorithm.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Algebraic CryptanalysisMutantXLF4MQQ Block Cipher
Contact author(s)
mohamed @ cdc informatik tu-darmstadt de
History
2008-10-27: received
Short URL
https://ia.cr/2008/451
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/451,
      author = {Mohamed Saied Emam Mohamed and Jintai Ding and Johannes Buchmann},
      title = {Algebraic Cryptanalysis of MQQ Public Key Cryptosystem by MutantXL},
      howpublished = {Cryptology ePrint Archive, Paper 2008/451},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/451}},
      url = {https://eprint.iacr.org/2008/451}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.