Algorithme quantique rapide pour la résolution d'équations quadratiques multivariées.

Résumé En août 2015, le monde de la cryptographie a été secoué par une annonce soudaine et surprenante de l'Agence nationale de sécurité américaine NSA concernant des plans de transition vers des algorithmes post-quantiques. Depuis cette annonce, la cryptographie post-quantique est devenue un sujet de premier intérêt pour plusieurs organismes de normalisation. La transition des algorithmes à clé publique actuellement déployés vers des algorithmes post-quantiques s'est avérée être un défi à de nombreux égards. En particulier, le problème de l'évaluation de la sécurité quantique de ces cryptosystèmes post-quantiques reste largement ouvert. Bien sûr, cette question est d'une importance capitale dans le processus de normalisation des cryptosystèmes post-quantiques. Dans cet article, nous examinons la sécurité quantique du problème de la résolution d'un système d'équations quadratiques multivariées booléennes de $m$ dans $n$ variables} (\MQb), un problème central de la cryptographie post-quantique. Lorsque $n=m$, sous une hypothèse algébrique naturelle, nous présentons un algorithme quantique de Las-Vegas résolvant \MQb{} qui nécessite l'évaluation, en moyenne, de $O(2^{0.462n})$ portes quantiques. À notre connaissance, il s'agit de l'algorithme le plus rapide pour résoudre \MQb{}.