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

Efficient delegated secure multiparty computation

Antoine Urban

Published Dec 18, 2024• 0 citations
Publisher

Abstract

Délégation efficace de calcul multipartite sécurisé Avec l’essor du cloud, il est devenu plus simple de déléguer la gestion et l’analyse des données à des infrastructures externes, favorisant la combinaison de données variées pour en tirer des informations utiles. Toutefois, garantir la confidentialité des données sensibles reste un obstacle majeur. Le calcul sécurisé multipartite (MPC) répond à ce défi en permettant à plusieurs participants de collaborer pour effectuer des calculs sur leurs données sans révéler celles-ci. Cette thèse explore une approche où les propriétaires des données délèguent ces calculs à des serveurs non fiables, tout en préservant sécurité et confidentialité. Pour cela, nous nous appuyons sur le chiffrement complètement homomorphe(FHE), qui permet de calculer directement sur des données chiffrées. Nos contributions incluent un protocole robuste de MPC basé sur le FHE et une méthode générique réduisant les besoins en communication. Ces avancées rendent les calculs sécurisés plus efficaces et accessibles, même pour des projets impliquant de nombreux participants.

DOI
10.70675/ab33e54ez239ez4a27z809ez61d5b23aea79

Related papers

Sublinear-communication secure multiparty computation

Pierre Meyer

Calcul multipartite sécurisé avec communication sous-linéaire Le calcul multipartite sécurisé (en anglais, MPC) [Yao82,GMW87a] permet à des agents d'un réseau de communication de calculer conjointement une fonction de leurs entrées sans avoir à n'en rien révéler de plus que le résultat du calcul lui-même. Une question primordiale est de savoir dans quelle mesure le coût en communication entre les agents dépend de la complexité calculatoire de la fonction en question. Un point de départ est l'étude d'une hypothétique barrière de la taille du circuit. L'existence d'une telle barrière est suggérée par le fait que tous les protocoles MPC fondateurs, des années 80 et 90, emploient une approche "porte-logique-par-porte-logique" au calcul sécurisé: la communication d'un tel protocole sera nécessairement au moins linéaire en le nombre de portes, c'est-à-dire en la taille du circuit. De plus ceux-ci représentent moralement l'état de l'art encore de nos jours en ce qui concerne la sécurité dite "par théorie de l'information". La barrière de la taille du circuit a été franchie pour le MPC avec sécurité calculatoire, mais sous des hypothèses structurées impliquant l'existence de chiffrement totalement homomorphe (en anglais, FHE) [Gen09] ou de partage de secret homomorphe (en anglais, HSS) [BGI16a]. De plus, il existe des protocoles avec sécurité par théorie de l'information dont la communication en-ligne (mais pas la communication totale) est sous-linéaire en la taille du circuit [IKM + 13, DNNR17, Cou19]. Notre méthodologie de recherche consiste à s'inspirer des techniques developpées dans le modèle de l'aléa corrélée dans lequel tout résultat pourra être considéré comme plus "fondamental" que le modèle calculatoire (de par le type de sécurité obtenue) mais qui est néanmoins un modèle inadapté à comprendre la complexité de communication du MPC (puisque que l'on s'autorise à ne pas compter toute quantité de communication qui peut être reléguée à une phase "hors-ligne", c'est-à-dire avant que les participants au calcul ne prennent connaissance de leurs entrées) pour développer de nouvelles méthodes dans le modèle calculatoire. Avec cette approche, nous obtenons des protocoles franchissant la barrière de la taille du circuit sous l'hypothèse de la sécurité quasipolynomiale de LPN [CM21] ou sous l'hypothèse QR+LPN [BCM22]. Ces hypothèses calculatoires n'étant pas précédement réputées impliquer l'existence de MPC sous-linéaire, la pertinence de notre méthodologie est, dans une certaine mesure, validée a posteriori. Plus fondamentalement cependant, nos travaux empruntent un nouveau paradigme pour construire du MPC sous-linéaire, sans utiliser les outils "avec de fortes propriétés homomorphiques" que sont le FHE ou du HSS. En combinant toutes nos techniques héritées de notre étude du modèle de l'aléa corrélé, nous parvenons à briser la barrière des deux joueurs pour le calcul sécurisé avec communication sous-linéaire, sans FHE [BCM23]. Spécifiquement, nous présentons le premier protocole à plus de deux participants dont la communication est sous-linéaire en la taille du circuit et qui ne soit pas fondé sur des hypothèses sous lesquelles on sait déjà faire du FHE. Parallèlement à ces travaux centrés sur la sécurité calculatoire, nous montrons [CMPR23] comment adapter les approches à deux joueurs utilisant du HSS, à la [BGI16a], pour gurantir une sécurité "théorie de l'information" à l'un des deux joueurs et une sécurité calculatoire à l'autre. Ceci est, de façon prouvable, la notion de sécurité la plus forte que l'on puisse espérer en présence de seulement deux joueurs (sans aléa corrélé). Nous obtenons le premier protocole de ce type avec communication sous-linéaire, qui ne soit pas fondé sur des hypothèses sous lesquelles on sait déjà faire du FHE.

•Sep 14, 2023•0 citations

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

Security and Efficiency of Delegated Quantum Computing

Dominik Leichtle

Sécurité et efficacité du calcul quantique délégué L'information quantique promet de révolutionner notre monde, de la façon dont nous communiquons à la façon dont nous calculons, en tirant sa puissance directement des lois qui régissent le comportement de la nature à des échelles extrêmement petites - la mécanique quantique. Dans un avenir proche, le matériel des ordinateurs quantiques éventuellement utiles devrait rester très coûteux et donc hors de portée de la plupart des utilisateurs finaux intéressés. Dans un tel monde, il est important de fournir des garanties de sécurité aux clients qui souhaitent donner des instructions à distance à des serveurs quantiques, en gardant leurs données privées (aveuglement) et en vérifiant l'exactitude des résultats (vérification). Cette fonctionnalité de l'informatique quantique déléguée sécurisée a reçu beaucoup d'attention au cours des dernières années, mais il reste encore beaucoup de questions ouvertes. Dans cette thèse, nous explorons l'(im)possibilité de sécuriser les calculs quantiques délégués dans différents contextes : quel est le matériel auquel le client doit avoir un accès sécurisé, quel est le matériel minimum requis par le serveur, et comment les parties doivent-elles communiquer ? Ce travail est motivé par la volonté de faire tomber les barrières qui nous empêchent de sécuriser et de vérifier les calculs quantiques dans la pratique, en identifiant et en supprimant les frais généraux inutiles. Nous commençons par nous interroger sur la nécessité d'une communication quantique entre le client et le serveur, et nous constatons que, si dans certaines situations la communication classique est tout à fait suffisante, le plus souvent la sécurité des protocoles de délégation repose de manière irremplaçable sur le caractère quantique de l'information échangée entre les parties. Cela prouve que la communication quantique est en effet un atout essentiel dans notre boîte à outils cryptographique. Nous nous concentrons ensuite sur le serveur qui souffrait de frais généraux irréalisables dans les tentatives précédentes de vérification quantique. Nous montrons que pour une large classe de calculs quantiques intéressants, il n'y a pas de besoin fondamental de réserver du matériel supplémentaire pour des techniques cryptographiques. En effet, nous donnons des constructions concrètes de protocoles sécurisés qui atteignent la cécité et la vérification sur du matériel de la même taille que celui qui serait nécessaire pour effectuer le calcul original non sécurisé, et nous fournissons un moyen systématique d'optimiser leur efficacité dans des contextes personnalisés. Notre voyage nous amène ensuite au problème du calcul multipartite sécurisé quantique, une généralisation de la fonctionnalité précédente à plus de deux parties participantes qui se méfient mutuellement. Nous explorons comment les améliorations que nous avons obtenues dans le cadre bipartite peuvent être transférées au cas multipartite, et nous terminons par la présentation de deux expériences réelles qui démontrent l'impact pratique et la faisabilité dans le monde réel des résultats obtenus au cours de cette thèse.

•Feb 23, 2024•0 citations

Efficient secure computation from correlated pseudorandomness

Thi Thuy Dung Bui

Calcul sécurisé efficace à partir de pseudo-aléa corrélé Dans cette thèse, nous explorons les avancées en calcul multipartite sécurisé (MPC), permettant à plusieurs parties de calculer conjointement des fonctions arbitraires tout en préservant la confidentialité de leurs entrées. Notre étude se concentre sur le MPC avec aléa corrélé, où l'efficacité est améliorée grâce à des corrélations générées en phase de prétraitement. Nous examinons deux paradigmes clés pour générer ces corrélations: les Générateurs de Corrélations Pseudoaléatoires (PCGs) et les Fonctions de Corrélations Pseudoaléatoires (PCFs). Tout d'abord, nous proposons de nouvelles constructions de PCG pour l'Intersection Privée d'Ensembles (PSI), offrant une sécurité renforcée ou de meilleures performances. Nous explorons ensuite les applications des PCGs et PCFs aux preuves à divulgation nulle de connaissance (ZKPs), en couvrant à la fois les cadres interactifs et non interactifs. Pour les ZKPs interactives, nous concevons un protocole vérifiable de manière privée pour la satisfaisabilité de circuits, avec une communication sous-linéaire et un calcul efficace. Dans le cadre non interactif, nous introduisons une nouvelle preuve à divulgation nulle de connaissance pour vérificateur désigné (DV-NIZK) exploitant les PCF avec une structure à clé publique (PK-PCF). Enfin, nous introduisons un nouveau cadre MPC pour les circuits binaires, basé sur un PCG optimisé pour les petits corps finis.

•Mar 18, 2025•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

Secure and efficient outsourced computation protocols for linear algebra

David Lucas

Protocoles de calculs externalisés efficaces et sécurisés pour l'algèbre linéaire L'algèbre linéaire exacte est un outil essentiel du calcul scientifique et trouve de nombreusesapplications en mathématiques expérimentales, en théorie des nombres, en cryptographie ou encorepour les preuves formelles. Les infrastructures de calcul à haute performance utilisées pour lecalcul scientifique ont connu de nombreuses évolutions au cours des 60 dernières années.Les calculs, initialement exécutés sur des machines locales possédées par les utilisateurs,sont désormais réalisés sur des machines externes, évolution permise par le rapide développementd'Internet au cours des années 1990. Ce phénomène a atteint son apogée avecl'arrivée récente du cloud computing.Désormais, un grand nombre de calculs sont effectués sur desmachines non plus possédées, mais louées par des clients.Ce nouveau modèle a donné naissance à denombreuses questions autour de la confiance à accorder à de tels calculs. Alors que les clients n'ontplus le contrôle des infrastructures qu'ils utilisent, comment peuvent-ils s'assurer de la confidentialité,la sécurité ou encore la validité de leurs calculs ?Dans cette thèse, nous considérons deux aspects fondamentaux de la sécurité des calculs externalisés enalgèbre linéaire exacte : la vérification de la justesse des résultats, et la confidentialité des donnéespour les calculs multipartites. Nous proposons de nouveaux protocoles permettant aux clients de vérifierefficacement les invariants liés au rang et nous les utilisons pour améliorer la vérification de propriétésclassiques de l'algèbre linéaire, le déterminant de matrices et la signature. Nous introduisons également lespremiers protocoles de vérification pour les propriétés classiques des modules de vecteurs de polynômes et leursmatrices associées.Enfin, nous proposons le premier protocole multipartite sécurisé récursif pour la multiplication de matrices basésur l'algorithme de Strassen-Winograd. Notre protocole permet à des utilisateurs possédant certains lignes des matricesd'entrée de calculer les mêmes lignes de la matrice de sortie. Ni les données initiales, ni les valeurs intermédiairesdu calcul ne sont révelées aux autres participants. Ce nouveau protocole nous permet d'améliorer l'état del'art pour le volume de données communiquées lors de l'exécution de tels protocoles.

•Jul 10, 2020•0 citations
Délégation efficace de calcul multipartite sécurisé Avec l’essor du cloud, il est devenu plus simple de déléguer la gestion et l’analyse des données à des infrastructures externes, favorisant la combinaison de données variées pour en tirer des informations utiles. Toutefois, garantir la confidentialité des données sensibles reste un obstacle majeur. Le calcul sécurisé multipartite (MPC) répond à ce défi en permettant à plusieurs participants de collaborer pour effectuer des calculs sur leurs données sans révéler celles-ci. Cette thèse explore une approche où les propriétaires des données délèguent ces calculs à des serveurs non fiables, tout en préservant sécurité et confidentialité. Pour cela, nous nous appuyons sur le chiffrement complètement homomorphe(FHE), qui permet de calculer directement sur des données chiffrées. Nos contributions incluent un protocole robuste de MPC basé sur le FHE et une méthode générique réduisant les besoins en communication. Ces avancées rendent les calculs sécurisés plus efficaces et accessibles, même pour des projets impliquant de nombreux participants.
Calcul multipartite sécurisé avec communication sous-linéaire Le calcul multipartite sécurisé (en anglais, MPC) [Yao82,GMW87a] permet à des agents d'un réseau de communication de calculer conjointement une fonction de leurs entrées sans avoir à n'en rien révéler de plus que le résultat du calcul lui-même. Une question primordiale est de savoir dans quelle mesure le coût en communication entre les agents dépend de la complexité calculatoire de la fonction en question. Un point de départ est l'étude d'une hypothétique barrière de la taille du circuit. L'existence d'une telle barrière est suggérée par le fait que tous les protocoles MPC fondateurs, des années 80 et 90, emploient une approche "porte-logique-par-porte-logique" au calcul sécurisé: la communication d'un tel protocole sera nécessairement au moins linéaire en le nombre de portes, c'est-à-dire en la taille du circuit. De plus ceux-ci représentent moralement l'état de l'art encore de nos jours en ce qui concerne la sécurité dite "par théorie de l'information". La barrière de la taille du circuit a été franchie pour le MPC avec sécurité calculatoire, mais sous des hypothèses structurées impliquant l'existence de chiffrement totalement homomorphe (en anglais, FHE) [Gen09] ou de partage de secret homomorphe (en anglais, HSS) [BGI16a]. De plus, il existe des protocoles avec sécurité par théorie de l'information dont la communication en-ligne (mais pas la communication totale) est sous-linéaire en la taille du circuit [IKM + 13, DNNR17, Cou19]. Notre méthodologie de recherche consiste à s'inspirer des techniques developpées dans le modèle de l'aléa corrélée dans lequel tout résultat pourra être considéré comme plus "fondamental" que le modèle calculatoire (de par le type de sécurité obtenue) mais qui est néanmoins un modèle inadapté à comprendre la complexité de communication du MPC (puisque que l'on s'autorise à ne pas compter toute quantité de communication qui peut être reléguée à une phase "hors-ligne", c'est-à-dire avant que les participants au calcul ne prennent connaissance de leurs entrées) pour développer de nouvelles méthodes dans le modèle calculatoire. Avec cette approche, nous obtenons des protocoles franchissant la barrière de la taille du circuit sous l'hypothèse de la sécurité quasipolynomiale de LPN [CM21] ou sous l'hypothèse QR+LPN [BCM22]. Ces hypothèses calculatoires n'étant pas précédement réputées impliquer l'existence de MPC sous-linéaire, la pertinence de notre méthodologie est, dans une certaine mesure, validée a posteriori. Plus fondamentalement cependant, nos travaux empruntent un nouveau paradigme pour construire du MPC sous-linéaire, sans utiliser les outils "avec de fortes propriétés homomorphiques" que sont le FHE ou du HSS. En combinant toutes nos techniques héritées de notre étude du modèle de l'aléa corrélé, nous parvenons à briser la barrière des deux joueurs pour le calcul sécurisé avec communication sous-linéaire, sans FHE [BCM23]. Spécifiquement, nous présentons le premier protocole à plus de deux participants dont la communication est sous-linéaire en la taille du circuit et qui ne soit pas fondé sur des hypothèses sous lesquelles on sait déjà faire du FHE. Parallèlement à ces travaux centrés sur la sécurité calculatoire, nous montrons [CMPR23] comment adapter les approches à deux joueurs utilisant du HSS, à la [BGI16a], pour gurantir une sécurité "théorie de l'information" à l'un des deux joueurs et une sécurité calculatoire à l'autre. Ceci est, de façon prouvable, la notion de sécurité la plus forte que l'on puisse espérer en présence de seulement deux joueurs (sans aléa corrélé). Nous obtenons le premier protocole de ce type avec communication sous-linéaire, qui ne soit pas fondé sur des hypothèses sous lesquelles on sait déjà faire du FHE.
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.
Sécurité et efficacité du calcul quantique délégué L'information quantique promet de révolutionner notre monde, de la façon dont nous communiquons à la façon dont nous calculons, en tirant sa puissance directement des lois qui régissent le comportement de la nature à des échelles extrêmement petites - la mécanique quantique. Dans un avenir proche, le matériel des ordinateurs quantiques éventuellement utiles devrait rester très coûteux et donc hors de portée de la plupart des utilisateurs finaux intéressés. Dans un tel monde, il est important de fournir des garanties de sécurité aux clients qui souhaitent donner des instructions à distance à des serveurs quantiques, en gardant leurs données privées (aveuglement) et en vérifiant l'exactitude des résultats (vérification). Cette fonctionnalité de l'informatique quantique déléguée sécurisée a reçu beaucoup d'attention au cours des dernières années, mais il reste encore beaucoup de questions ouvertes. Dans cette thèse, nous explorons l'(im)possibilité de sécuriser les calculs quantiques délégués dans différents contextes : quel est le matériel auquel le client doit avoir un accès sécurisé, quel est le matériel minimum requis par le serveur, et comment les parties doivent-elles communiquer ? Ce travail est motivé par la volonté de faire tomber les barrières qui nous empêchent de sécuriser et de vérifier les calculs quantiques dans la pratique, en identifiant et en supprimant les frais généraux inutiles. Nous commençons par nous interroger sur la nécessité d'une communication quantique entre le client et le serveur, et nous constatons que, si dans certaines situations la communication classique est tout à fait suffisante, le plus souvent la sécurité des protocoles de délégation repose de manière irremplaçable sur le caractère quantique de l'information échangée entre les parties. Cela prouve que la communication quantique est en effet un atout essentiel dans notre boîte à outils cryptographique. Nous nous concentrons ensuite sur le serveur qui souffrait de frais généraux irréalisables dans les tentatives précédentes de vérification quantique. Nous montrons que pour une large classe de calculs quantiques intéressants, il n'y a pas de besoin fondamental de réserver du matériel supplémentaire pour des techniques cryptographiques. En effet, nous donnons des constructions concrètes de protocoles sécurisés qui atteignent la cécité et la vérification sur du matériel de la même taille que celui qui serait nécessaire pour effectuer le calcul original non sécurisé, et nous fournissons un moyen systématique d'optimiser leur efficacité dans des contextes personnalisés. Notre voyage nous amène ensuite au problème du calcul multipartite sécurisé quantique, une généralisation de la fonctionnalité précédente à plus de deux parties participantes qui se méfient mutuellement. Nous explorons comment les améliorations que nous avons obtenues dans le cadre bipartite peuvent être transférées au cas multipartite, et nous terminons par la présentation de deux expériences réelles qui démontrent l'impact pratique et la faisabilité dans le monde réel des résultats obtenus au cours de cette thèse.
Calcul sécurisé efficace à partir de pseudo-aléa corrélé Dans cette thèse, nous explorons les avancées en calcul multipartite sécurisé (MPC), permettant à plusieurs parties de calculer conjointement des fonctions arbitraires tout en préservant la confidentialité de leurs entrées. Notre étude se concentre sur le MPC avec aléa corrélé, où l'efficacité est améliorée grâce à des corrélations générées en phase de prétraitement. Nous examinons deux paradigmes clés pour générer ces corrélations: les Générateurs de Corrélations Pseudoaléatoires (PCGs) et les Fonctions de Corrélations Pseudoaléatoires (PCFs). Tout d'abord, nous proposons de nouvelles constructions de PCG pour l'Intersection Privée d'Ensembles (PSI), offrant une sécurité renforcée ou de meilleures performances. Nous explorons ensuite les applications des PCGs et PCFs aux preuves à divulgation nulle de connaissance (ZKPs), en couvrant à la fois les cadres interactifs et non interactifs. Pour les ZKPs interactives, nous concevons un protocole vérifiable de manière privée pour la satisfaisabilité de circuits, avec une communication sous-linéaire et un calcul efficace. Dans le cadre non interactif, nous introduisons une nouvelle preuve à divulgation nulle de connaissance pour vérificateur désigné (DV-NIZK) exploitant les PCF avec une structure à clé publique (PK-PCF). Enfin, nous introduisons un nouveau cadre MPC pour les circuits binaires, basé sur un PCG optimisé pour les petits corps finis.
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.
Protocoles de calculs externalisés efficaces et sécurisés pour l'algèbre linéaire L'algèbre linéaire exacte est un outil essentiel du calcul scientifique et trouve de nombreusesapplications en mathématiques expérimentales, en théorie des nombres, en cryptographie ou encorepour les preuves formelles. Les infrastructures de calcul à haute performance utilisées pour lecalcul scientifique ont connu de nombreuses évolutions au cours des 60 dernières années.Les calculs, initialement exécutés sur des machines locales possédées par les utilisateurs,sont désormais réalisés sur des machines externes, évolution permise par le rapide développementd'Internet au cours des années 1990. Ce phénomène a atteint son apogée avecl'arrivée récente du cloud computing.Désormais, un grand nombre de calculs sont effectués sur desmachines non plus possédées, mais louées par des clients.Ce nouveau modèle a donné naissance à denombreuses questions autour de la confiance à accorder à de tels calculs. Alors que les clients n'ontplus le contrôle des infrastructures qu'ils utilisent, comment peuvent-ils s'assurer de la confidentialité,la sécurité ou encore la validité de leurs calculs ?Dans cette thèse, nous considérons deux aspects fondamentaux de la sécurité des calculs externalisés enalgèbre linéaire exacte : la vérification de la justesse des résultats, et la confidentialité des donnéespour les calculs multipartites. Nous proposons de nouveaux protocoles permettant aux clients de vérifierefficacement les invariants liés au rang et nous les utilisons pour améliorer la vérification de propriétésclassiques de l'algèbre linéaire, le déterminant de matrices et la signature. Nous introduisons également lespremiers protocoles de vérification pour les propriétés classiques des modules de vecteurs de polynômes et leursmatrices associées.Enfin, nous proposons le premier protocole multipartite sécurisé récursif pour la multiplication de matrices basésur l'algorithme de Strassen-Winograd. Notre protocole permet à des utilisateurs possédant certains lignes des matricesd'entrée de calculer les mêmes lignes de la matrice de sortie. Ni les données initiales, ni les valeurs intermédiairesdu calcul ne sont révelées aux autres participants. Ce nouveau protocole nous permet d'améliorer l'état del'art pour le volume de données communiquées lors de l'exécution de tels protocoles.