Practical Cryptanalysis of a Public-Key Encryption Scheme Based on New Multivariate Quadratic Assumptions

Abstract : In this paper, we investigate the security of a public-key encryption scheme introduced by Huang, Liu and Yang (HLY) at PKC'12. This new scheme can be provably reduced to the hardness of solving a set of quadratic equations whose coefficients of highest degree are chosen according to a discrete Gaussian distributions. The other terms being chosen uniformly at random. Such a problem is a variant of the classical problem of solving a system of non-linear equations (PoSSo), which is known to be hard for random systems. The main hypothesis of Huang, Liu and Yang is that their variant is not easier than solving PoSSo for random instances. In this paper, we disprove this hypothesis. To this end, we exploit the fact that the new problem proposed by Huang, Liu and Yang reduces to an easy instance of the Learning With Errors (LWE) problem. The main contribution of this paper is to show that security and efficiency are essentially incompatible for the HLY proposal. That is, one cannot find parameters which yield a secure and a practical scheme. For instance, we estimate that a public-key of at least $1.03~\textnormal{GB}$ is required to achieve $80$-bit security against the simplest of our attacks. As a proof of concept, we present $3$ practical attacks against all the parameters proposed by Huang, Liu and Yang. With the most efficient attack, we have been able to recover the private-key in roughly $5$ minutes for the first challenge \big(i.e.\ Case~1\big) proposed by HLY and less than $30$ minutes for the second challenge \big(i.e.\ Case~2\big).
Type de document :
Communication dans un congrès
PKC 2014 - 17th International Conference on Practice and Theory in Public-Key Cryptography, Mar 2014, Buenos Aires, Argentina. Springer, 2014
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00932382
Contributeur : Ludovic Perret <>
Soumis le : jeudi 16 janvier 2014 - 20:13:24
Dernière modification le : lundi 29 mai 2017 - 14:25:50
Document(s) archivé(s) le : jeudi 17 avril 2014 - 09:51:30

Fichier

mqpkc-lattice.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00932382, version 1

Collections

Citation

Martin Albrecht, Jean-Charles Faugère, Robert Fitzpatrick, Ludovic Perret, Yosuke Todo, et al.. Practical Cryptanalysis of a Public-Key Encryption Scheme Based on New Multivariate Quadratic Assumptions. PKC 2014 - 17th International Conference on Practice and Theory in Public-Key Cryptography, Mar 2014, Buenos Aires, Argentina. Springer, 2014. 〈hal-00932382〉

Partager

Métriques

Consultations de la notice

937

Téléchargements de fichiers

577