Essaie encore. Echoue encore. Echoue mieux : Nouvelles notions de sécurité, d'hypothèses brisées et d'efficacité accrue de la cryptographie

This thesis presents new results addressing three fundamental areas of cryptography: security notions, assumptions, and efficiency. The first part encompasses the security of symmetric primitives. We give a new security notion that provides the strongest security for symmetric primitives proven in the random oracle model (ROM). Key-correlated attacks (KCA) model the scenario where all inputs (keys, messages, and possibly nonces and headers) are correlated with the secret key. Under mild assumptions, we prove KCA security of blockciphers, and show that 3-rounds of Even-Mansour are necessary to achieve this. Then, we define a KCA-security notion for nonce-based authenticated encryption (AE), and provide a black-box transformation that turns a multiuser-secure AE into an AE scheme that is provably KCA secure in the ROM. We show relations and separations with older notions (related-key and key-dependent message security) to show that security under KCA is strictly stronger, and implies the others. The next part turns to public-key cryptography, and analyses the assumptions underlying the new public-key cryptosystem of AJPS17. Cryptanalysis of their assumption, based on arithmetic modulo a Mersenne prime, allowed us to reconstruct the secret key, given only the public key. Based on a modified version of the assumption, we propose a variant post-quantum secure public-key cryptosystem. The last part turns to efficiency, and studies the Schnorr Signature scheme. Exploiting the group structure we can generate multiple nonces (instead of just one) with which we can then generate a batch of signatures. This, together with some preprocessing tricks, allow us to increase efficiency of Schnorr signature generation. Security is maintained under a new assumption shown intractable in the Generic Group Model.Cette thèse présente des résultats nouveaux portant sur trois domaines fondamentaux de la cryptographie : les propriétés de sécurité, les hypothèses cryptographiques, et l’efficacité algorithmique. La première partie s’intéresse à la sécurité des primitives symétriques. Nous introduisons une nouvelle propriété de sécurité correspondant à la plus forte sécurité pour les primitives symétriques prouvées sûres dans le modèle de l’oracle aléatoire. Les attaques par clé corrélées capturent les scénarios dans lesquels toutes les entrées (clés, messages, et éventuellement nonces et en-têtes) sont corrélées avec la clé secrète. Sous des hypothèses relativement faibles nous prouvons la sécurité contre les attaques par clé corrélées pour les algorithmes de chiffrement par bloc, et montrons que trois tours d’Even-Mansour sont nécessaires pour cela. Nous étendons ensuite les attaques par clés corrélées au chiffrement authentifié basé sur les nonces, et fournissons une transformation en boîte noire qui, partant d’un chiffrement authentifié à utilisateurs multiples, donne un chiffrement authentifié démontré résistant aux attaques par clés corrélées dans le modèle de l’oracle aléatoire. Nous établissons les relations et séparations avec les notions déjà existantes (sécurité contre les attaques par clés apparentées et par message dépendant de la clé) pour montrer que la sécurité contre les attaques par clé corrélées est strictement plus forte, et implique les autres. La partie suivante porte sur la cryptographie à clé publique, et analyse les hypothèses sous-jacentes au nouveau cryptosystème introduit dans AJPS17. La cryptanalyse de cette hypothèse, reposant sur l’arithmétique modulo un premier de Mersenne, nous permet de reconstruire la clé secrète à partir de la clé publique uniquement. Nous proposons alors une variante de ce système à clé publique, fondée sur une modification de l’hypothèse précédente, résistant aux attaques connues (classiques et quantiques). La dernière partie aborde l’efficacité algorithmique du schéma de signature de Schnorr. En mettant à profit la structure de groupe nous pouvons tirer parti du nonce pour produire un lot de signatures. Combinant ceci avec des méthodes de pré-calcul nous permet de rendre plus efficace l’algorithme de signature de Schnorr. La sécurité est préservée sous une hypothèse nouvelle, dont on montre qu’elle est vraie dans le modèle du groupe générique