Show simple item record

dc.contributor.advisorRonald Cramer
dc.contributor.advisorGilles Zémor
dc.contributor.advisorSerge Fehr
hal.structure.identifierInstitut de Mathématiques de Bordeaux [IMB]
dc.contributor.authorSPINI, Gabriele
dc.contributor.otherAnne Canteaut [Président]
dc.contributor.otherYuval Ishai [Rapporteur]
dc.contributor.otherBerry Schoenmakers [Rapporteur]
dc.contributor.otherBart De smit
dc.date.accessioned2024-04-04T03:06:43Z
dc.date.available2024-04-04T03:06:43Z
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/193362
dc.identifier.nnt2017BORD0817
dc.description.abstractLe sujet de cette thèse est la cryptographie et son interconnexions avec la théorie des codes. En particulier, on utilise des techniques issues de la théorie des codes pour construire et analyser des protocoles cryptographiques avec des propriétés nouvelles ou plus avancées. On se concentre d'abord sur le partage de secret ou secret sharing, un sujet important avec de nombreuses applications pour la Cryptographie actuelle. Dans la variante à laquelle on s'intéresse, un schéma de partage de secret reçoit en entrée un élément secret, et renvoie en sortie n parts de telle façon que chaque ensemble de parts de taille suffisamment petite ne donne aucune information sur le secret (confidentialité), tandis que chaque ensemble de taille suffisamment grande permet de reconstituer le secret (reconstruction). Un schéma de partage de secret peut donc être vu comme une solution à un problème de communication où un émetteur Alice est connectée avec un destinataire Bob par n canaux distincts, dont certains sont contrôlés par un adversaire Ève. Alice peut utiliser un schéma de partage de secret pour communiquer un message secret a Bob de telle façon qu'Ève n'apprenne aucune information sur le secret en lisant les données transmises sur les canaux qu'elle contrôle, tandis que Bob peut recevoir le message même si Ève bloque ces dits canaux. Notre contributions au partage de secret concernent ses liens avec la théorie des codes ; comme les deux domaines partagent un même but (récupérer des données à partir d'informations partielles), ce n'est pas surprenant qu'ils aient connu une interaction longue et fertile. Plus précisément, Massey commença une analyse fructueuse à propos de la construction et de l'étude d'un schéma de partage de secret à partir d'un code correcteur. L'inconvénient de cette analyse est que la confidentialité d'un schéma de partage de secret est estimé grâce au dual du code sous-jacent ; cela peut être problématique vu qu'il pourrait ne pas être possible d'obtenir des codes avec des propriétés souhaitables qui aient aussi un bon code dual. On contourne ce problème en établissant une connexion nouvelle entre les deux domaines, telle que la confidentialité d'un schéma de partage de secrets n'est plus contrôlée par le dual du code sous-jacent. Cela nous permet d'exploiter complètement le potentiel de certaines constructions récentes de codes pour obtenir des meilleurs schémas; on illustre ceci avec deux applications. Premièrement, en utilisant des codes avec codage et décodage en temps linéaire on obtient une famille de schémas de partage de secret où le partage (calcul des parts issues du secret) tout comme la reconstruction peuvent s'effectuer en temps linéaire ; pour des seuils de confidentialité et de reconstruction croissants, ceci restait jusqu'à présent un problème ouvert. Deuxièmement, on utilise des codes avec décodage en liste pour construire des schémas de partage de secret robustes, c'est-à-dire des schémas qui peuvent reconstituer le secret même si certaines parts sont incorrectes, sauf avec une petite probabilité d'erreur. etc...
dc.description.abstractEnThe topic of this dissertation is Cryptography, and its connections with Coding Theory. Concretely, we make use of techniques from Coding Theory to construct and analyze cryptographic protocols with new and/or enhanced properties. We first focus on Secret Sharing, an important topic with many applications to modern Cryptography, which also forms the common ground for most of the concepts discussed in this thesis. In the flavor we are interested in, a secret-sharing scheme takes as input a secret value, and produces as output n shares in such a way that small enough sets of shares yield no information at all on the secret (privacy), while large enough sets of shares allow to recover the secret (reconstruction). A secret-sharing scheme can thus be seen as a solution to a secure communication problem where a sender Alice is connected to a receiver Bob via n distinct channels, some of which are controlled by an adversary Eve. Alice can use a secret-sharing scheme to communicate a secret message to Bob in such a way that Eve learns no information on the message by eavesdropping on the channels she controls, while Bob can receive the message even if Eve blocks the channels under her control. Our contributions to Secret Sharing concern its connection with Coding Theory; since the two fields share the goal of recovering data from incomplete information, it is not surprising that Secret Sharing and Coding Theory have known a long and fruitful interplay. In particular, Massey initiated a very successful analysis on how to construct and study secret-sharing schemes from error-correcting codes. The downside of this analysis is that the privacy of secret-sharing schemes is estimated in terms of the dual of the underlying code; this can be problematic as it might not be possible to obtain codes with desirable properties that have good duals as well. We circumvent this problem by establishing a new connection between the two fields, where the privacy of secret-sharing schemes is no longer controlled by the dual of the underlying code. This allows us to fully harness the potential of recent code constructions to obtain improved schemes; we exemplify this by means of two applications. First, by making use of linear-time encodable and decodable codes we obtain a family of secret-sharing schemes where both the sharing (computation of the shares from the secret) and the reconstruction can be performed in linear time; for growing privacy and reconstruction thresholds, this was an hitherto open problem. Second, we make use of list-decodable codes to construct robust secret-sharing schemes, i.e., schemes that can recover the secret even if some of the shares are incorrect, except with a small error probability. The family we present optimizes the trade-off between the extra data that needs to be appended to the share to achieve robustness and the error probability in the reconstruction, reaching the best possible value. etc...
dc.language.isoen
dc.subjectCryptographie
dc.subjectThéorie des Codes
dc.subjectSécurité Inconditionnelle
dc.subject.enCryptography
dc.subject.enCoding Theory
dc.subject.enUnconditional Security
dc.titleProtocoles avec Sécurité Inconditionnelle issus de Techniques de la Théorie des Codes
dc.title.enUnconditionally Secure Cryptographic Protocols from Coding-Theoretic Primitives
dc.typeThèses de doctorat
dc.subject.halMathématiques [math]/Mathématiques générales [math.GM]
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.type.institutionUniversité de Bordeaux
bordeaux.type.institutionUniversiteit Leiden (Leyde, Pays-Bas)
bordeaux.ecole.doctoraleÉcole doctorale de mathématiques et informatique (Talence, Gironde ; 1991-....)
hal.identifiertel-01715247
hal.version1
hal.origin.linkhttps://hal.archives-ouvertes.fr//tel-01715247v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.title=Protocoles%20avec%20S%C3%A9curit%C3%A9%20Inconditionnelle%20issus%20de%20Techniques%20de%20la%20Th%C3%A9orie%20des%20Codes&rft.atitle=Protocoles%20avec%20S%C3%A9curit%C3%A9%20Inconditionnelle%20issus%20de%20Techniques%20de%20la%20Th%C3%A9orie%20des%20Codes&rft.au=SPINI,%20Gabriele&rft.genre=unknown


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record