Etude de protocoles de consensus pour les technologies blockchain et cryptanalyse quantique des schémas de Misty

Ces dernières années, deux domaines de recherche en cryptologie ont reçu une attention considérable : les protocoles de consensus pour les technologies blockchain dus à l'émergence des cryptomonnaies, et la cryptanalyse quantique due à la menace des ordinateurs quantiques. Naturellement, nos sujets de recherche se sont orientés vers ces deux domaines que nous avons étudiés séparément dans cette thèse.Dans la première partie, nous analysons la sécurité de certains protocoles de consensus pour les technologies blockchain qui sont un des principaux défis dans ces technologies. En particulier, nous nous focalisons sur l'élection de leader qui intervient au sein d'un protocole de consensus. Après une étude de l'état de l'art des protocoles de consensus avant et après l'introduction des technologies blockchain, nous étudions la sécurité de deux approches prometteuses pour construire des protocoles de consensus, appelées Algorand et Single Secret Leader Election. Ainsi, nous définissons un modèle de sécurité d'élection de leader avec cinq propriétés de sécurité qui empêchent les problèmes et attaques bien connus des protocoles de consensus. Ensuite, nous décrivons un nouveau protocole d'élection de leader appelé LEP-TSP destiné à être utilisé dans des systèmes privés et prouvons que LEP-TSP satisfait les propriétés de sécurité attendues tant que plus de deux tiers des participants sont honnêtes. Comme travail additionnel, nous présentons une description à haut niveau d'un nouveau protocole de consensus appelé Useful Work, qui utilise la puissance de calcul pour résoudre n'importe quel problème concret.Dans la seconde partie de cette thèse, nous passons en revue les meilleurs résultats de cryptanalyse connus sur les schémas de Misty et nous présentons de nouveaux résultats de cryptanalyse quantique. Tout d'abord, nous décrivons des attaques quantiques non adaptatives à clairs choisis (QCPA) contre les schémas de Misty L à 4 tours, Misty LKF à 4 tours, Misty R à 3 tours et Misty RKF 3 à tours. Nous étendons l'attaque QCPA contre les schémas de Misty RKF à 3 tours pour obtenir une attaque quantique permettant de retrouver la clé secrète des schémas de Misty RKF à d tours. Comme travail supplémentaire, nous montrons que la meilleure attaque non quantique connue contre les schémas de Misty R à 3 tours est optimale.In recent years, two research domains in cryptography have received considerable attention: consensus protocols for blockchain technologies due to the emergence of cryptocurrencies, and quantum cryptanalysis due to the threat of quantum computers. Naturally, our research topics are geared towards these two research domains that are studied separately in this thesis.In the first part, we analyze the security of consensus protocols which are one of main challenges in these technologies. We focus more specifically on the leader election of consensus protocols. After a study of the state of the art on consensus protocols before and after the emergence of blockchain technologies, we study the security of two promising approaches to construct these protocols, called Algorand and Single Secret Leader Election. As a result, we define a security model of leader election with five security properties that address well-known issues and attacks against consensus protocols. Then, we provide a new leader election protocol called LEP-TSP intended to be used in private setting and prove that LEP-TSP meets the expected security properties while more than two third of participants are honest. As additional work, we provide a high level description of a new consensus protocol called Useful Work that uses the computing power to solve any real world problem.In the second part of this thesis, we review the best known cryptanalysis results on Misty schemes and we provide new quantum cryptanalysis results. First, we describe non-adaptive quantum chosen plaintext attacks (QCPA) against 4-round Misty L, 4-round Misty LKF, 3-round Misty R and 3-round Misty RKF schemes. We extend the QCPA attack against 3-round Misty RKF schemes to recover the keys of d-round Misty RKF schemes. As additional work, we show that the best known non-quantum attack against 3-round Misty R schemes is optimal