A Polynomial-Time Key-Recovery Attack on MQQ Cryptosystems

Abstract : We investigate the security of the family of MQQ public key cryptosystems using multivariate quadratic quasigroups (MQQ). These cryptosystems show especially good performance properties. In particular, the MQQ-SIG signature scheme is the fastest scheme in the ECRYPT benchmarking of cryptographic systems (eBACS). We show that both the signature scheme MQQ-SIG and the encryption scheme MQQ-ENC, although using different types of MQQs, share a common algebraic structure that introduces a weakness in both schemes. We use this weakness to mount a successful polynomial time key-recovery attack. Our key-recovery attack finds an equivalent key using the idea of so-called {\it good keys} that reveals the structure gradually. In the process we need to solve a MinRank problem that, because of the structure, can be solved in polynomial-time assuming some mild algebraic assumptions. We highlight that our theoretical results work in characteristic $2$ which is known to be the most difficult case to address in theory for MinRank attacks. Also, we emphasize that our attack works without any restriction on the number of polynomials removed from the public-key, that is, using the minus modifier. This was not the case for previous MinRank like-attacks against \MQ\ schemes. From a practical point of view, we are able to break an MQQ-SIG instance of $80$ bits security in less than $2$ days, and one of the more conservative MQQ-ENC instances of $128$ bits security in little bit over $9$ days. Altogether, our attack shows that it is very hard to design a secure public key scheme based on an easily invertible MQQ structure.
Type de document :
Communication dans un congrès
IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC'15), Mar 2015, Maryland, United States
Liste complète des métadonnées

Littérature citée [39 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01074194
Contributeur : Ludovic Perret <>
Soumis le : mardi 23 décembre 2014 - 12:39:04
Dernière modification le : jeudi 19 novembre 2015 - 01:20:52
Document(s) archivé(s) le : mardi 24 mars 2015 - 10:05:34

Fichier

811.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01074194, version 1

Collections

Citation

Jean-Charles Faugère, Danilo Gligoroski, Ludovic Perret, Samardjiska Simona, Enrico Thomae. A Polynomial-Time Key-Recovery Attack on MQQ Cryptosystems. IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC'15), Mar 2015, Maryland, United States. 〈hal-01074194〉

Partager

Métriques

Consultations de
la notice

347

Téléchargements du document

158