Analyse et conception d'algorithmes de cryptographie post-quantique : Schéma de signature basé sur PKP et signatures ultra-courtes de type multivariée

The construction of large quantum computers would endanger most of the public-key cryptographic schemes in use today. Therefore, there is currently a large research effort to develop new post-quantum secure schemes. In particular, we are interested in post-quantum cryptographic schemes whose security relies on the hardness of solving some mathematical problems such as thePermuted Kernel Problem (PKP) and the Hidden Field Equations (HFE). This work investigates first the complexity of PKP. And after a thorough analysis of the State-of-theart attacks of PKP, we have been able to update some results that were not accurate, and to provide an explicit complexity formula which allows us to identify hard instances and secure sets of parameters of this problem. PKP was used in 1989 to develop the first Zero-Knowledge Identification Scheme (ZK-IDS) that has an efficient implementation on low-cost smart cards. In a second step, we optimize the PKP-based ZK-IDS and then we introduce PKP-DSS:a Digital Signature Scheme based on PKP. We construct PKP-DSS from the ZK-IDS based on PKP by using the traditional Fiat-Shamir (FS) transform that converts Identification schemes into Signature schemes. We develop a constant time implementation of PKP-DSS. It appears that our scheme is very competitive with other post-quantum FS signature schemes. Since that PKP is an NP-Complete problem and since there are no known quantum attacks for solving PKP significantly better than classical attacks, we believe that our scheme is post-quantum secure. On the other hand, we study multivariate public-key signature schemes that provide“ultra”-short signatures. We first analyze the most known attacks against multivariate signatures, and then define the minimal parameters that allow ultra-short signature. We also design some specific newmodes of operations in order to avoid particular attacks.Second, we provide various explicit examples of ultra-short signature schemes that are based on variants of HFE. We present parameters for several level of classical security: 80, 90, 100 bits in addition to 128, 192, and 256 bits; foreach level, we propose different choices of finite fields.La construction d’un ordinateur quantique remettrait en cause la plupart des schémas à clef publique utilisés aujourd’hui. Par conséquent, il existe actuellement un effort de recherche important pour développer de nouveauxschémas cryptographiques post-quantique. En particulier, nous nous intéressons aux schémas post-quantiques dont la sécurité repose sur la dureté de la résolution de certains problèmes mathématiques tels que le problème PKP et leproblème HFE. Ce travail étudie d’abord la complexité de PKP. Et après une analyse approfondie des attaques connus sur PKP, nous avons pu mettre à jour certains résultats qui n’étaient pas précis, et fournir une formule de complexité explicite qui nous permet d’identifier les instances difficilesde ce problème et de donner des ensembles de paramètres sécurisés. PKP a été utilisé en 1989 pour développer le premier schéma d’identification à divulgation nulle de connaissance (ZK-IDS) qui a une implémentation efficace sur les cartes à puce. Dans un deuxième temps, nous optimisons le ZK-IDS basé sur PKP, puis nous introduisons PKP-DSS: un schéma de signature digitale basé sur PKP.Nous construisons PKP-DSS à partir du ZK-IDS basé sur PKP en utilisant la transformation Fiat-Shamir (FS) traditionnelle qui convertit les schémas d’identification en schémas de signature. Nous développons une implémentation àtemps constant de PKP-DSS. Il semble que notre schéma soit très compétitif par rapport aux autres schémas de signature FS post-quantiques. Étant donné que PKP est un problème NP-Complet et qu’il n’y a pas d’attaques quantiquesconnues pour résoudre PKP nettement mieux que les attaques classiques, nous pensons que notre schéma est post-quantique.D’autre part, nous étudions les schémas de signature à clé publique de type multivariés qui fournissent des signatures ultra-courtes. Nous analysons d’abord les attaques les plus connues contre les signatures multivariées, puis nous définissons les paramètres minimaux permettant une signatureultra-courte. Nous présentons également de nouveaux modes d’opérations spécifiques afin d’éviter des attaques particulières. Deuxièmement, nous fournissons divers exemples explicites de schémas de signature ultra-courts,pour plusieurs niveaux de sécurité classique, qui sont basés sur des variantes de HFE sur différents corps finis