Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Post-Quantum Signatures from Secure Multiparty Computation

Thibauld Feneuil

Published Oct 23, 2023• 0 citations
Publisher

Abstract

Signatures post-quantiques à partir de techniques de calcul multipartite Le développement actuel des ordinateurs quantiques pousse la communauté cryptographique à mettre au point de nouveaux cryptosystèmes dont la sécurité se fonde sur la difficulté à résoudre des problèmes cryptographiques résistant au calcul quantique. Dans le cadre de cette thèse, nous nous sommes focalisés sur la conception de schémas de signatures électroniques construits à partir de preuves à divulgation nulle de connaissance (zero-knowledge proofs of knowledge). Plus précisément, nous nous sommes intéressés au paradigme “MPC-in-the-Head” (littéralement, “calcul-multipartite-dans-la-tête”) qui fournit une méthode générique de construire de telles preuves en utilisant des techniques de calcul multipartite sécurisé. Nous proposons plusieurs nouveaux schémas de signatures utilisant le paradigme “MPC-in-the-Head”. La plupart d’entre eux sont compétitifs avec les schémas existants dans l’état de l’art post-quantique. Ils produisent des signatures ayant des tailles entre 5 et 20 kylo-octets (pour un niveau de sécurité de 128 bits) et possèdent de très petites clés (de moins de 200 octets). Les problèmes difficiles sur lesquels la sécurité de ces schémas se fonde sont très variés. Certains schémas s’appuient sur des hypothèses de sécurité issues de la théorie des codes correcteurs d’erreurs, telle que celle sur la difficulté à résoudre le problème de décodage par syndrome pour des codes linéaires aléatoires. Les autres schémas s’appuient sur la difficultés à résoudre un système d’équations quadratiques, le problème de la somme de sous-ensembles ou le problème MinRank. Nous avons également mis au point deux nouvelles techniques de MPC-in-the-Head. La première vise à gérer efficacement les situations où le secret est de petite taille avec un grand modulus. La seconde consiste en une nouvelle méthode pour transformer un protocole de calcul multipartite en preuve de divulgation nulle de connaissance. Cette nouvelle transformation offre des nouveaux compromis entre coût de communication et temps de calcul. En particulier, elle permet de produire des algorithmes de vérification très rapides. Plusieurs soumissions à l’appel du NIST pour des schémas de signatures post-quantiques supplémentaires s'appuient (parfois partiellement) sur des idées développées dans le cadre de cette thèse.

DOI
10.70675/7ecd6017z289fz4e38zbc93zb85d7c33aefc

Related papers

Privacy preserving post-quantum cryptography

Guillaume Kaim

Cryptographie post-quantique pour la protection de la vie privée Ces dernières années la cryptographie a été chamboulée par l'arrivée des ordinateurs quantiques. En effet ceux-ci possèdent un très fort avantage pour casser les schémas cryptographique utilisés actuellement dans la quasi-totalité des communications sécurisées. Nous proposons dans cette thèse plusieurs constructions cryptographiques basées sur des outils mathématiques résistants à ces ordinateurs quantique, que sont les réseaux euclidiens. Tout d'abord nous construisons une signature de groupe, permettant à chaque membre composant un groupe donné de signer au nom du groupe tout en conservant son anonymat. Nous rajoutons une propriété supplémentaire qui est la "forward secrecy" qui sépare le temps en périodes durant lesquelles les clés secrètes des utilisateurs sont mises à jour. Nous proposons également un schéma de signature aveugle qui permet à un utilisateur de générer une signature sur un message de son choix de manière interactive avec un signeur qui possède la clé de signature. Nous améliorons l'état-de-l'art en proposant un schéma sans abandon et avec une sécurité plus efficace. Enfin, comme cas d'usage de la signature aveugle nous construisons un schéma de vote électronique à partir de cette primitive.

•Dec 16, 2020•0 citations

Zero-knowledge arguments from secure multiparty computation

Jules Maire

Arguments à divulgation nulle de connaissance via du calcul réparti sécurisé Cette thèse a pour but d'étudier les arguments à divulgation nulle de connaissance, une primitive cryptographique qui permet de prouver un énoncé tout en ne révélant rien d'autre que sa vérité (nous pouvons l'appeler preuve au lieu d'argument en fonction du modèle de sécurité). Plus précisément, nous nous concentrons sur une famille d'arguments dont la construction est basée sur le calcul multipartite sécurisé. Il est bien connu que, pour toute fonctionnalité, il existe un protocole multipartite sécurisé pour la calculer. Prenons une fonction générique à sens unique f, et un protocole multipartite sécurisé calculant f, il a été montré assez récemment que nous pouvons construire un argument à divulgation nulle de connaissance pour le problème NP de trouver une pré-image de f. Cette construction n'était considérée que comme théorique jusqu'à il y a quelques années, et notre travail contribue à l'émergence de nouvelles techniques ainsi que d'applications efficaces dans ce paradigme. En guise d'amuse-gueule, nous développons des protocoles simples qui améliorent de manière significative la complexité en communication pour certains problèmes bien connus. Notre première contribution substantielle, avec un désir de partager des petits éléments, est l'introduction d'un partage sur les entiers qui est intégré de manière sûre dans nos protocoles avec un rejet artificiel. Les applications sont multiples, y compris dans le monde post-quantique. Dans la lignée de notre partage sur les entiers, nous proposons un schéma cryptographique de mise en gage basé sur des problèmes de sac-à-dos modulaire. En particulier, il permet des arguments efficaces pour la satisfiabilité de circuits génériques. Ensuite, nous présentons une construction de preuve utilisant la conversion entre les partages de secrets additifs et multiplicatifs, conduisant à des preuves efficaces de relations linéaires et multiplicatives. Les applications sont encore une fois multiples lors de la conception d'arguments et de signatures numériques. Enfin, laissant de côté la conception de protocoles, nous explorons les fondements de la cryptographie avec des preuves à divulgation nulle de connaissance avec prouveurs multiple, un cadre pour distribuer le travail du prouveur. Pour saisir tout l'intérêt de cette répartition, nous ajoutons à la littérature un résultat fondamental sur les preuves à seuil pour un langage NP générique.

•Oct 11, 2024•0 citations

Security of cryptographic protocols based on coding theory

Hervé Talé Kalachi

Sécurité des protocoles cryptographiques fondés sur la théorie des codes correcteurs d'erreurs Contrairement aux protocoles cryptographiques fondés sur la théorie des nombres, les systèmes de chiffrement basés sur les codes correcteurs d’erreurs semblent résister à l’émergence des ordinateurs quantiques. Un autre avantage de ces systèmes est que le chiffrement et le déchiffrement sont très rapides, environ cinq fois plus rapide pour le chiffrement, et 10 à 100 fois plus rapide pour le déchiffrement par rapport à RSA. De nos jours, l’intérêt de la communauté scientifique pour la cryptographie basée sur les codes est fortement motivé par la dernière annonce de la “National Institute of Standards and Technology" (NIST), qui a récemment initié le projet intitulé “Post-Quantum cryptography Project". Ce projet vise à définir de nouveaux standards pour les cryptosystèmes résistants aux attaques quantiques et la date limite pour la soumission des cryptosystèmes à clé publique est fixée pour novembre 2017. Une telle annonce motive certainement à proposer de nouveaux protocoles cryptographiques basés sur les codes, mais aussi à étudier profondément la sécurité des protocoles existants afin d’écarter toute surprise en matière de sécurité. Cette thèse suit cet ordre d’idée en étudiant la sécurité de plusieurs protocoles cryptographiques fondés sur la théorie des codes correcteurs d’erreurs. Nous avons commencé par l’étude de la sécurité d’une version modifiée du cryptosystème de Sidelnikov, proposée par Gueye et Mboup [GM13] et basée sur les codes de Reed-Muller. Cette modification consiste à insérer des colonnes aléatoires dans la matrice génératrice (ou de parité) secrète. La cryptanalyse repose sur le calcul de carrés du code public. La nature particulière des codes de Reed-Muller qui sont définis au moyen de polynômes multivariés binaires, permet de prédire les valeurs des dimensions des codes carrés calculés, puis permet de récupérer complètement en temps polynomial les positions secrètes des colonnes aléatoires. Notre travail montre que l’insertion de colonnes aléatoires dans le schéma de Sidelnikov n’apporte aucune amélioration en matière de sécurité. Le résultat suivant est une cryptanalyse améliorée de plusieurs variantes du cryptosystème GPT qui est un schéma de chiffrement en métrique rang utilisant les codes de Gabidulin. Nous montrons qu’en utilisant le Frobenius de façon appropriée sur le code public, il est possible d’en extraire un code de Gabidulin ayant la même dimension que le code de Gabidulin secret mais avec une longueur inférieure. Le code obtenu corrige ainsi moins d’erreurs que le code secret, mais sa capacité de correction d’erreurs dépasse le nombre d’erreurs ajoutées par l’expéditeur et par conséquent, un attaquant est capable de déchiffrer tout texte chiffré, à l’aide de ce code de Gabidulin dégradé. Nos résultats montrent qu’en fin de compte, toutes les techniques existantes visant à cacher la structure algébrique des codes de Gabidulin ont échoué. Enfin, nous avons étudié la sécurité du système de chiffrement de Faure-Loidreau [FL05] qui est également basé sur les codes de Gabidulin. Inspiré par les travaux précédents et, bien que la structure de ce schéma diffère considérablement du cadre classique du cryptosystème GPT, nous avons pu montrer que ce schéma est également vulnérable à une attaque polynomiale qui récupère la clé privée en appliquant l’attaque d’Overbeck sur un code public approprié. Comme exemple, nous arrivons en quelques secondes à casser les paramètres qui ont été proposés comme ayant un niveau de sécurité de 80 bits.

•Jul 5, 2017•0 citations

Designing Efficient, Practical and Secure Post-quantum Cryptosystems

Anaëlle Le Dévéhat

Concevoir des systèmes cryptographiques post-quantiques efficaces, pratiques et sûrs Cette thèse explore des stratégies d’optimisation pour la cryptographie post-quantique. Par systèmes cryptographiques post-quantiques, nous entendons des schémas classiques (non quantiques) dont la sécurité est destinée à résister à des attaques provenant d’ordinateurs quantiques.Premièrement, nous étudions des systèmes cryptographiques dans le cadre GPV avec des réseaux ou des codes non structurés qui souffrent généralement de clés de grande taille. Nous traitons ce problème avec une méthode permettant de remplacer les grandes clés publiques dans les signatures de type GPV par de plus petites clés de vérification privées. Cela réduit significativement le stockage et le temps d’exécution du vérificateur tout en préservant la sécurité. Appliquée aux schémas à signatures courtes Wave et Squirrels, notre méthode compresse les clés de Squirrels-I de 665 kB à 20{,}7 kB et les clés de Wave822 de 3{,}5 MB à 207{,}97 kB. Cela est particulièrement utile lorsque de nombreuses vérifications sont effectuées avec la même clé (par exemple, les mises à jour logicielles, les certificats racine). Deuxièmement, nous présentons quelques accélérations pour le calcul d’isogénies. L’une réorganise l’évaluation des formules de Vélu pour accélérer l’évaluation des ell-isogénies pour de nombreux nombres premiers ell, ce qui constitue un calcul de base dans de nombreux systèmes cryptographiques à base d’isogénies. Une autre vise les isogénies rationnelles dont les noyaux sont engendrés par des éléments irrationnels. Nos techniques accélèrent les schémas à base d’isogénies tels que CSIDH, CSI-FiSh et CRS.Enfin, nous proposons des algorithmes classiques de recherche parallèle de collisions pour les logarithmes discrets restreints multidimensionnels. La cryptographie basée sur les actions de groupes, et plus spécifiquement les emph{Restricted Effective Group Actions} (REGA), est profondément liée à ces problèmes. Une méthode existante pour résoudre les logarithmes discrets restreints multidimensionnels est l’algorithme de Gaudry--Schost. Cependant, il ne s’applique qu’à de faibles dimensions, ce qui ne correspond pas aux actions de groupes à base d’isogénies actuelles. Nous étendons l’algorithme de Gaudry--Schost à des dimensions plus élevées, offrant une vision plus approfondie des menaces classiques pour les échanges de clés REGA.

•Dec 16, 2025•0 citations

Lattice-based cryptography in a quantum setting : security proofs and attacks

Pouria Fallahpour

Cryptographie fondée sur les réseaux euclidiens dans une contexte quantique : preuves de sécurité et attaques L'émergence des machines quantiques crée des défis et des opportunités pour la cryptographie. En particulier, les preuves de sécurité doivent être révisées en raison des capacités quantiques des adversaires. Cette thèse propose deux contributions à cet égard : un résultat positif et un résultat négatif. La transformation de Fiat-Shamir avec des rejets est l’un des principaux paradigmes pour concevoir des schémas de signature post-quantiques. Une partie de cette thèse consiste en une analyse détaillée de cette transformation dans le modèle de l’oracle aléatoire quantique. Tous les travaux précédents proposant une analyse de sécurité de cette transformation ont négligé des détails subtils, compromettant la correction des preuves. Par conséquent, notre preuve de sécurité est la première de son genre à être correcte. De plus, nous analysons le temps d'exécution et la correction des signatures obtenues à partir de cette transformation. Le problème learning with errors (LWE) a été largement utilisé pour construire des schémas cryptographiques sécurisés contre les adversaires quantiques. Une hypothèse liée à LWE stipule que la génération d'une instance LWE sans connaître son secret est difficile pour tous les algorithmes polynomiaux. On peut utiliser cette hypothèse pour prouver la sécurité de certains arguments de connaissance succints. Bien que cela semble être une tâche difficile pour les algorithmes classiques, nous présentons un algorithme quantique polynomial qui génère des instances LWE sans connaître le secret. Notre algorithme invalide ainsi les analyses de sécurité de ces arguments de connaissance succints dans le contexte quantique.

•Jul 5, 2024•1 citation

Calcul multipartite basé sur la difficulté calculatoire de la théorie des codes

Clément Ducros

Depuis l'apparition de la cryptographie moderne, le calcul sécurisé (MPC) a longuement été étudié. Le MPC permet à un groupe de parties (ou joueurs) d'effectuer ensemble un ou plusieurs calculs sur des données secrètes, tout en garantissant que les joueurs n'obtiennent rien de plus que le résultat et ce qui peut en être déduit. Le développement massif de notre utilisation quotidienne d'Internet rend le besoin de méthodes de calcul sécurisé plus urgent que jamais : les calculs sur des données privées sont omniprésents, des algorithmes de recommandation aux enchères électroniques. Les algorithmes de MPC modernes bénéficient grandement de l'apport d'aléa corrélé, afin d'obtenir des protocoles rapides. Cet aléa corrélé doit être généré massivement au préalable pour que les protocoles de MPC puissent être efficaces. Toutefois, réaliser cette génération d'aléa corrélé efficacement reste encore un défi. Dans cette thèse, nous étudions les Générateurs de Corrélations Pseudo-aléatoires (PCGs). Cette primitive cryptographique transforme une petite quantité d'aléa corrélé en une large quantité de pseudo-aléa corrélé, tout en étant efficace en ce qui concerne le temps de calcul et la communication. Nous présentons différentes constructions de PCG dont la sécurité repose sur des variantes de l'hypothèse de Décodage de Syndrome (SD), une hypothèse classique en théorie des codes. L'intuition derrière les constructions proposées est de mélanger l'hypothèse SD avec certaines techniques de MPC qui permettent de partager de manière additive des vecteurs creux. Nos résultats obtenus battent l'état de l'art en ce qui concerne les protocoles de calcul sécurisé nécessitant plus de deux joueurs lorsque le calcul est effectué sur un corps fini de taille > 2. Nous montrons également comment supprimer cette contrainte au prix d'un léger surcoût en communication. Nous considérons également la construction de Fonctions Pseudo-aléatoires Corrélées (PCFs). Les PCFs produisent des corrélations à la volée : les joueurs détiennent chacun des fonctions corrélées de sorte que les sorties des fonctions, lorsqu'elles sont évaluées sur la même entrée, soient corrélées. Ces objets offrent plus de flexibilité que les PCGs, mais sont aussi plus difficiles à construire. Nous nous appuyons à nouveau sur des variantes de SD pour construire des PCFs. Nous nous basons sur une construction de PCF déjà établie, montrant que la preuve de sécurité associée était incorrecte, et proposons une correction. De plus, nous présentons des optimisations de la construction, provenant d'une meilleure analyse et d'un calcul précis des paramètres nécessaires via des simulations. Nous obtenons des paramètres utilisables en pratique. Cette thèse repose majoritairement sur l'hypothèse SD. La recherche d'une bonne complexité implique des efforts pour trouver les codes les plus efficaces tout en garantissant que la sécurité ne soit pas compromise. Nous considérons un modèle permettant l'étude de l'efficacité des attaques prometteuses contre SD et ses variantes. Pour chaque construction mentionnée précédemment, nous menons une analyse de sécurité approfondie de la variante associée de SD et tentons d'attaquer notre propre schéma pour calculer des paramètres concrets.

•Nov 12, 2024•0 citations
Signatures post-quantiques à partir de techniques de calcul multipartite Le développement actuel des ordinateurs quantiques pousse la communauté cryptographique à mettre au point de nouveaux cryptosystèmes dont la sécurité se fonde sur la difficulté à résoudre des problèmes cryptographiques résistant au calcul quantique. Dans le cadre de cette thèse, nous nous sommes focalisés sur la conception de schémas de signatures électroniques construits à partir de preuves à divulgation nulle de connaissance (zero-knowledge proofs of knowledge). Plus précisément, nous nous sommes intéressés au paradigme “MPC-in-the-Head” (littéralement, “calcul-multipartite-dans-la-tête”) qui fournit une méthode générique de construire de telles preuves en utilisant des techniques de calcul multipartite sécurisé. Nous proposons plusieurs nouveaux schémas de signatures utilisant le paradigme “MPC-in-the-Head”. La plupart d’entre eux sont compétitifs avec les schémas existants dans l’état de l’art post-quantique. Ils produisent des signatures ayant des tailles entre 5 et 20 kylo-octets (pour un niveau de sécurité de 128 bits) et possèdent de très petites clés (de moins de 200 octets). Les problèmes difficiles sur lesquels la sécurité de ces schémas se fonde sont très variés. Certains schémas s’appuient sur des hypothèses de sécurité issues de la théorie des codes correcteurs d’erreurs, telle que celle sur la difficulté à résoudre le problème de décodage par syndrome pour des codes linéaires aléatoires. Les autres schémas s’appuient sur la difficultés à résoudre un système d’équations quadratiques, le problème de la somme de sous-ensembles ou le problème MinRank. Nous avons également mis au point deux nouvelles techniques de MPC-in-the-Head. La première vise à gérer efficacement les situations où le secret est de petite taille avec un grand modulus. La seconde consiste en une nouvelle méthode pour transformer un protocole de calcul multipartite en preuve de divulgation nulle de connaissance. Cette nouvelle transformation offre des nouveaux compromis entre coût de communication et temps de calcul. En particulier, elle permet de produire des algorithmes de vérification très rapides. Plusieurs soumissions à l’appel du NIST pour des schémas de signatures post-quantiques supplémentaires s'appuient (parfois partiellement) sur des idées développées dans le cadre de cette thèse.
Cryptographie post-quantique pour la protection de la vie privée Ces dernières années la cryptographie a été chamboulée par l'arrivée des ordinateurs quantiques. En effet ceux-ci possèdent un très fort avantage pour casser les schémas cryptographique utilisés actuellement dans la quasi-totalité des communications sécurisées. Nous proposons dans cette thèse plusieurs constructions cryptographiques basées sur des outils mathématiques résistants à ces ordinateurs quantique, que sont les réseaux euclidiens. Tout d'abord nous construisons une signature de groupe, permettant à chaque membre composant un groupe donné de signer au nom du groupe tout en conservant son anonymat. Nous rajoutons une propriété supplémentaire qui est la "forward secrecy" qui sépare le temps en périodes durant lesquelles les clés secrètes des utilisateurs sont mises à jour. Nous proposons également un schéma de signature aveugle qui permet à un utilisateur de générer une signature sur un message de son choix de manière interactive avec un signeur qui possède la clé de signature. Nous améliorons l'état-de-l'art en proposant un schéma sans abandon et avec une sécurité plus efficace. Enfin, comme cas d'usage de la signature aveugle nous construisons un schéma de vote électronique à partir de cette primitive.
Arguments à divulgation nulle de connaissance via du calcul réparti sécurisé Cette thèse a pour but d'étudier les arguments à divulgation nulle de connaissance, une primitive cryptographique qui permet de prouver un énoncé tout en ne révélant rien d'autre que sa vérité (nous pouvons l'appeler preuve au lieu d'argument en fonction du modèle de sécurité). Plus précisément, nous nous concentrons sur une famille d'arguments dont la construction est basée sur le calcul multipartite sécurisé. Il est bien connu que, pour toute fonctionnalité, il existe un protocole multipartite sécurisé pour la calculer. Prenons une fonction générique à sens unique f, et un protocole multipartite sécurisé calculant f, il a été montré assez récemment que nous pouvons construire un argument à divulgation nulle de connaissance pour le problème NP de trouver une pré-image de f. Cette construction n'était considérée que comme théorique jusqu'à il y a quelques années, et notre travail contribue à l'émergence de nouvelles techniques ainsi que d'applications efficaces dans ce paradigme. En guise d'amuse-gueule, nous développons des protocoles simples qui améliorent de manière significative la complexité en communication pour certains problèmes bien connus. Notre première contribution substantielle, avec un désir de partager des petits éléments, est l'introduction d'un partage sur les entiers qui est intégré de manière sûre dans nos protocoles avec un rejet artificiel. Les applications sont multiples, y compris dans le monde post-quantique. Dans la lignée de notre partage sur les entiers, nous proposons un schéma cryptographique de mise en gage basé sur des problèmes de sac-à-dos modulaire. En particulier, il permet des arguments efficaces pour la satisfiabilité de circuits génériques. Ensuite, nous présentons une construction de preuve utilisant la conversion entre les partages de secrets additifs et multiplicatifs, conduisant à des preuves efficaces de relations linéaires et multiplicatives. Les applications sont encore une fois multiples lors de la conception d'arguments et de signatures numériques. Enfin, laissant de côté la conception de protocoles, nous explorons les fondements de la cryptographie avec des preuves à divulgation nulle de connaissance avec prouveurs multiple, un cadre pour distribuer le travail du prouveur. Pour saisir tout l'intérêt de cette répartition, nous ajoutons à la littérature un résultat fondamental sur les preuves à seuil pour un langage NP générique.
Sécurité des protocoles cryptographiques fondés sur la théorie des codes correcteurs d'erreurs Contrairement aux protocoles cryptographiques fondés sur la théorie des nombres, les systèmes de chiffrement basés sur les codes correcteurs d’erreurs semblent résister à l’émergence des ordinateurs quantiques. Un autre avantage de ces systèmes est que le chiffrement et le déchiffrement sont très rapides, environ cinq fois plus rapide pour le chiffrement, et 10 à 100 fois plus rapide pour le déchiffrement par rapport à RSA. De nos jours, l’intérêt de la communauté scientifique pour la cryptographie basée sur les codes est fortement motivé par la dernière annonce de la “National Institute of Standards and Technology" (NIST), qui a récemment initié le projet intitulé “Post-Quantum cryptography Project". Ce projet vise à définir de nouveaux standards pour les cryptosystèmes résistants aux attaques quantiques et la date limite pour la soumission des cryptosystèmes à clé publique est fixée pour novembre 2017. Une telle annonce motive certainement à proposer de nouveaux protocoles cryptographiques basés sur les codes, mais aussi à étudier profondément la sécurité des protocoles existants afin d’écarter toute surprise en matière de sécurité. Cette thèse suit cet ordre d’idée en étudiant la sécurité de plusieurs protocoles cryptographiques fondés sur la théorie des codes correcteurs d’erreurs. Nous avons commencé par l’étude de la sécurité d’une version modifiée du cryptosystème de Sidelnikov, proposée par Gueye et Mboup [GM13] et basée sur les codes de Reed-Muller. Cette modification consiste à insérer des colonnes aléatoires dans la matrice génératrice (ou de parité) secrète. La cryptanalyse repose sur le calcul de carrés du code public. La nature particulière des codes de Reed-Muller qui sont définis au moyen de polynômes multivariés binaires, permet de prédire les valeurs des dimensions des codes carrés calculés, puis permet de récupérer complètement en temps polynomial les positions secrètes des colonnes aléatoires. Notre travail montre que l’insertion de colonnes aléatoires dans le schéma de Sidelnikov n’apporte aucune amélioration en matière de sécurité. Le résultat suivant est une cryptanalyse améliorée de plusieurs variantes du cryptosystème GPT qui est un schéma de chiffrement en métrique rang utilisant les codes de Gabidulin. Nous montrons qu’en utilisant le Frobenius de façon appropriée sur le code public, il est possible d’en extraire un code de Gabidulin ayant la même dimension que le code de Gabidulin secret mais avec une longueur inférieure. Le code obtenu corrige ainsi moins d’erreurs que le code secret, mais sa capacité de correction d’erreurs dépasse le nombre d’erreurs ajoutées par l’expéditeur et par conséquent, un attaquant est capable de déchiffrer tout texte chiffré, à l’aide de ce code de Gabidulin dégradé. Nos résultats montrent qu’en fin de compte, toutes les techniques existantes visant à cacher la structure algébrique des codes de Gabidulin ont échoué. Enfin, nous avons étudié la sécurité du système de chiffrement de Faure-Loidreau [FL05] qui est également basé sur les codes de Gabidulin. Inspiré par les travaux précédents et, bien que la structure de ce schéma diffère considérablement du cadre classique du cryptosystème GPT, nous avons pu montrer que ce schéma est également vulnérable à une attaque polynomiale qui récupère la clé privée en appliquant l’attaque d’Overbeck sur un code public approprié. Comme exemple, nous arrivons en quelques secondes à casser les paramètres qui ont été proposés comme ayant un niveau de sécurité de 80 bits.
Concevoir des systèmes cryptographiques post-quantiques efficaces, pratiques et sûrs Cette thèse explore des stratégies d’optimisation pour la cryptographie post-quantique. Par systèmes cryptographiques post-quantiques, nous entendons des schémas classiques (non quantiques) dont la sécurité est destinée à résister à des attaques provenant d’ordinateurs quantiques.Premièrement, nous étudions des systèmes cryptographiques dans le cadre GPV avec des réseaux ou des codes non structurés qui souffrent généralement de clés de grande taille. Nous traitons ce problème avec une méthode permettant de remplacer les grandes clés publiques dans les signatures de type GPV par de plus petites clés de vérification privées. Cela réduit significativement le stockage et le temps d’exécution du vérificateur tout en préservant la sécurité. Appliquée aux schémas à signatures courtes Wave et Squirrels, notre méthode compresse les clés de Squirrels-I de 665 kB à 20{,}7 kB et les clés de Wave822 de 3{,}5 MB à 207{,}97 kB. Cela est particulièrement utile lorsque de nombreuses vérifications sont effectuées avec la même clé (par exemple, les mises à jour logicielles, les certificats racine). Deuxièmement, nous présentons quelques accélérations pour le calcul d’isogénies. L’une réorganise l’évaluation des formules de Vélu pour accélérer l’évaluation des ell-isogénies pour de nombreux nombres premiers ell, ce qui constitue un calcul de base dans de nombreux systèmes cryptographiques à base d’isogénies. Une autre vise les isogénies rationnelles dont les noyaux sont engendrés par des éléments irrationnels. Nos techniques accélèrent les schémas à base d’isogénies tels que CSIDH, CSI-FiSh et CRS.Enfin, nous proposons des algorithmes classiques de recherche parallèle de collisions pour les logarithmes discrets restreints multidimensionnels. La cryptographie basée sur les actions de groupes, et plus spécifiquement les emph{Restricted Effective Group Actions} (REGA), est profondément liée à ces problèmes. Une méthode existante pour résoudre les logarithmes discrets restreints multidimensionnels est l’algorithme de Gaudry--Schost. Cependant, il ne s’applique qu’à de faibles dimensions, ce qui ne correspond pas aux actions de groupes à base d’isogénies actuelles. Nous étendons l’algorithme de Gaudry--Schost à des dimensions plus élevées, offrant une vision plus approfondie des menaces classiques pour les échanges de clés REGA.
Cryptographie fondée sur les réseaux euclidiens dans une contexte quantique : preuves de sécurité et attaques L'émergence des machines quantiques crée des défis et des opportunités pour la cryptographie. En particulier, les preuves de sécurité doivent être révisées en raison des capacités quantiques des adversaires. Cette thèse propose deux contributions à cet égard : un résultat positif et un résultat négatif. La transformation de Fiat-Shamir avec des rejets est l’un des principaux paradigmes pour concevoir des schémas de signature post-quantiques. Une partie de cette thèse consiste en une analyse détaillée de cette transformation dans le modèle de l’oracle aléatoire quantique. Tous les travaux précédents proposant une analyse de sécurité de cette transformation ont négligé des détails subtils, compromettant la correction des preuves. Par conséquent, notre preuve de sécurité est la première de son genre à être correcte. De plus, nous analysons le temps d'exécution et la correction des signatures obtenues à partir de cette transformation. Le problème learning with errors (LWE) a été largement utilisé pour construire des schémas cryptographiques sécurisés contre les adversaires quantiques. Une hypothèse liée à LWE stipule que la génération d'une instance LWE sans connaître son secret est difficile pour tous les algorithmes polynomiaux. On peut utiliser cette hypothèse pour prouver la sécurité de certains arguments de connaissance succints. Bien que cela semble être une tâche difficile pour les algorithmes classiques, nous présentons un algorithme quantique polynomial qui génère des instances LWE sans connaître le secret. Notre algorithme invalide ainsi les analyses de sécurité de ces arguments de connaissance succints dans le contexte quantique.
Depuis l'apparition de la cryptographie moderne, le calcul sécurisé (MPC) a longuement été étudié. Le MPC permet à un groupe de parties (ou joueurs) d'effectuer ensemble un ou plusieurs calculs sur des données secrètes, tout en garantissant que les joueurs n'obtiennent rien de plus que le résultat et ce qui peut en être déduit. Le développement massif de notre utilisation quotidienne d'Internet rend le besoin de méthodes de calcul sécurisé plus urgent que jamais : les calculs sur des données privées sont omniprésents, des algorithmes de recommandation aux enchères électroniques. Les algorithmes de MPC modernes bénéficient grandement de l'apport d'aléa corrélé, afin d'obtenir des protocoles rapides. Cet aléa corrélé doit être généré massivement au préalable pour que les protocoles de MPC puissent être efficaces. Toutefois, réaliser cette génération d'aléa corrélé efficacement reste encore un défi. Dans cette thèse, nous étudions les Générateurs de Corrélations Pseudo-aléatoires (PCGs). Cette primitive cryptographique transforme une petite quantité d'aléa corrélé en une large quantité de pseudo-aléa corrélé, tout en étant efficace en ce qui concerne le temps de calcul et la communication. Nous présentons différentes constructions de PCG dont la sécurité repose sur des variantes de l'hypothèse de Décodage de Syndrome (SD), une hypothèse classique en théorie des codes. L'intuition derrière les constructions proposées est de mélanger l'hypothèse SD avec certaines techniques de MPC qui permettent de partager de manière additive des vecteurs creux. Nos résultats obtenus battent l'état de l'art en ce qui concerne les protocoles de calcul sécurisé nécessitant plus de deux joueurs lorsque le calcul est effectué sur un corps fini de taille > 2. Nous montrons également comment supprimer cette contrainte au prix d'un léger surcoût en communication. Nous considérons également la construction de Fonctions Pseudo-aléatoires Corrélées (PCFs). Les PCFs produisent des corrélations à la volée : les joueurs détiennent chacun des fonctions corrélées de sorte que les sorties des fonctions, lorsqu'elles sont évaluées sur la même entrée, soient corrélées. Ces objets offrent plus de flexibilité que les PCGs, mais sont aussi plus difficiles à construire. Nous nous appuyons à nouveau sur des variantes de SD pour construire des PCFs. Nous nous basons sur une construction de PCF déjà établie, montrant que la preuve de sécurité associée était incorrecte, et proposons une correction. De plus, nous présentons des optimisations de la construction, provenant d'une meilleure analyse et d'un calcul précis des paramètres nécessaires via des simulations. Nous obtenons des paramètres utilisables en pratique. Cette thèse repose majoritairement sur l'hypothèse SD. La recherche d'une bonne complexité implique des efforts pour trouver les codes les plus efficaces tout en garantissant que la sécurité ne soit pas compromise. Nous considérons un modèle permettant l'étude de l'efficacité des attaques prometteuses contre SD et ses variantes. Pour chaque construction mentionnée précédemment, nous menons une analyse de sécurité approfondie de la variante associée de SD et tentons d'attaquer notre propre schéma pour calculer des paramètres concrets.