Cryptology ePrint Archive: Report 2008/451

Algebraic Cryptanalysis of MQQ Public Key Cryptosystem by MutantXL

Mohamed Saied Emam Mohamed and 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.

Category / Keywords: public-key cryptography / Algebraic Cryptanalysis, MutantXL, F4, MQQ Block Cipher

Date: received 26 Oct 2008

Contact author: mohamed at cdc informatik tu-darmstadt de

Available formats: PDF | BibTeX Citation

Version: 20081027:200214 (All versions of this report)

Discussion forum: Show discussion | Start new discussion