Loading
Notes d'étude
Study Reminders
Support
Text Version

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Foundations of Cryptography Dr. Ashish Choudhury Department of Computer Science Indian Institute of Science – Bengaluru Lecture-56 Secret Sharing (Référez-vous à la diapositive: 00:29) Bonjour tout le monde. Bienvenue à cette conférence. Ainsi, lors de cette conférence, nous discuterons des protocoles interactifs. Nous nous concentrons maintenant sur la résolution du problème de la communication sécurisée où nous avions deux entités, un émetteur et un récepteur, et nous avons longuement discuté de la façon de concevoir des algorithmes pour résoudre le problème de la communication sécurisée. Mais maintenant, ce que nous allons discuter est un scénario, un problème bien connu, où nous avons plusieurs entités. Et notre objectif est de concevoir un protocole cryptographique qui nécessite une interaction entre les entités. Ainsi, la feuille de route pour cette conférence est la suivante. Nous introduisons le problème du partage secret. Nous verrons des échanges secrets sur les additifs, des échanges secrets dupliqués, et ensuite nous verrons la construction classique d'un système de partage secret dû à Adi Shamir. (Voir Heure de la diapositive: 01:17)Voir donc la motivation du partage secret. Imaginez que nous ayons une application bancaire, par exemple, où le casier de la banque n'est accessible que par les gestionnaires de la façon suivante. Le mot de passe du locker est partagé entre les trois gestionnaires et il est partagé de manière à ce que si seulement deux des gestionnaires se réunissent et entrent leurs mots de passe respectifs, le locker est accessible. Mais si un seul gestionnaire tente d'entrer le mot de passe et d'accéder au casier, l'accès n'est pas possible. Ainsi, par exemple, si le second gestionnaire va et tente d'ouvrir le casier, il ne devrait pas le faire. De la même façon, si le troisième gestionnaire va seul, il devrait échouer. Mais si nous prenons un ensemble de deux ou plusieurs gestionnaires et qu'ils vont entrer leurs mots de passe respectifs, ils devraient pouvoir accéder au casier. C'est donc ce dont nous avons besoin ici. (Référez-vous à l'heure de la diapositive: 02:14)De la même façon, considérez-vous un autre scénario réel. Il s'agit d'un scénario réel, qui s'est réellement produit au cours des années 90. C'est donc à propos de la façon dont les armes nucléaires de la Russie sont accessibles aux plus hauts dirigeants des pays. On pense donc que le mot de passe pour lancer l'arme nucléaire de la Russie est partagé entre les trois principales entités du pays, à savoir le président, le Premier ministre et le ministre de la Défense de manière à ce que l'arme ne soit accessible ou lancée que si au moins 2 des 3 entités se réunissent et entrent leurs mots de passe, alors que si une seule entité tente de lancer ou d'accéder à l'arme, l'accès sera refusé. (Voir Heure de la diapositive: 02:55) Ces deux applications peuvent donc être extraites par le problème suivant, que nous appelons (Partage secret. Et ce problème a été formulé indépendamment par Shamir en 1979 et Blakley en 1979. Ce que nous avons ici, c'est que nous nous sommes donnés le cadre suivant. Nous avons un ensemble de parties 1, et elles sont reliées par un canal privé et authentique par paires. Ce que cela signifie est, si des informations veulent l'envoyer, nous supposons qu'il a un canal dédié avec lequel il est connecté. Et tout ce qui est envoyé par-dessus ce canal, il sera reçu correctement et en toute sécurité par. Si vous vous demandez comment exactement ces canaux sont disponibles dans le monde réel, eh bien, nous pouvons utiliser n'importe quel protocole de communication sécurisé bien connu que nous avons longuement discuté jusqu'à présent, pour s'assurer que de tels canaux sont disponibles entre chaque paire de parties. À l'exception de ces partis, nous avons une partie désignée parmi ces partis et tout le monde saura l'identité de cette partie et elle est appelée en tant que négociant. Et le croupier a une entrée privée, un secret d'un plus grand espace, qui est un ensemble de tous les secrets possibles. Maintenant, l'objectif de ce concessionnaire est de distribuer son secret parmi les parties en entrant ou en calculant une part pour chacune de ces parties et en distribuant les actions. Donc, le premier actionnaire obtient un titre 1, la deuxième partie devrait obtenir la deuxième action et le parti devrait obtenir la part. Et ces actions sont réparties sur le canal par paires avec lequel le concessionnaire est connecté aux actionnaires individuels. Nous avons maintenant besoin des propriétés suivantes de ces distributions d'actions. Nous avons besoin qu'il soit impossible pour tout groupe d'actionnaires ou moins d'échanger leurs actions et de reconstruire le secret. Et selon que l'ensemble des actionnaires qui essaient de reconstruire le secret, qu'ils soient délimités sur le plan informatique ou qu'ils soient sans limite de calcul, nous obtenions soit le secret parfait, soit le secret computationnel. C'est donc la première exigence de cette distribution d'actions. D'autre part, si un ensemble ou plus d'actionnaires tirent ensemble leurs actions, alors il devrait être possible de reconstruire le secret. Donc le paramètre ici agit comme un seuil pour vous. Cela signifie que nous avons besoin d'un mécanisme de partage tel que si un ensemble ou moins d'actionnaires se rassemblent, ils ne doivent pas avoir accès ou ne doivent pas reconstituer le secret. Les actions devraient être complètement indépendantes du secret sous-jacent. D'un autre côté, si un ensemble d'actionnaires ou plus s'assemblait, le secret devrait être reconstruit, il devrait être possible de reconstruire le secret. (Voir Heure de la diapositive: 05:39) Par conséquent, voyons une construction très simple de (additif de partage de secrets). Donc, en gros, mon seuil. Cela signifie que j'ai besoin d'un mécanisme de partage où tous les actionnaires devraient se réunir pour reconstruire le secret. Mais si un seul actionnaire est manquant, il ne devrait pas être possible de reconstruire le secret. Et pourquoi on l'appelle partage secret additive, il vous sera très bientôt clair. Alors voilà mon espace secret l. L'algorithme de partage est le suivant. Alors imaginez que le croupier a un secret. Pour le partager, il choisit des parts de façon aléatoire à partir de l'ensemble. Cela signifie que la première action 1 est une chaîne de l-bit aléatoire, la seconde part est une chaîne de l-bit aléatoire et de la même façon que la part est aussi une chaîne de l-bit aléatoire. Une fois que les premières actions sont fixées par le concessionnaire, la dernière action est définie comme étant = 1 euro, et une fois que les actions sont calculées, les concessionnaires envoient les actions respectives à leurs actionnaires respectifs. La part est donnée à la partie sur le canal sécurisé et authentique entre le concessionnaire et le parti. Donc la propriété de la correction ici est triviale pour ce partage secret, à savoir si tous les actionnaires se rassemblent et échangent leurs parts avec l'autre alors ils peuvent effectivement exécuter la xor de toutes les actions et ils revivideront de manière unique le secret sous-jacent qui a été partagé par le concessionnaire. W prouvera formellement la propriété de confidentialité ici. Donc, pour la protection de la vie privée, notre but est de montrer que, si parmi ces actionnaires, tous les actionnaires se rassemblent et tirent leurs actions, ils ne doivent pas apprendre quoi que ce soit sur le secret sous-jacent. Nous avons donc divisé la preuve en deux cas. Considérons le cas où l'ensemble des actionnaires corrompus et qui tentent de reconstruire le secret sont les premiers actionnaires. Il s'avère que si les premiers actionnaires sont corrompus, alors de leurs parts, ils n'apprennent absolument rien sur le secret sous-jacent. Parce que si vous voyez l'algorithme de partage, les premières actions qu'ils sont cueils indépendamment du secret réel du dealer. Cela signifie que si l'adversaire contrôle les premiers actionnaires et l'accès à leurs parts, l'adversaire n'apprend absolument rien sur le secret du croupier. C'est le cas. D'autre part, considérons le cas lorsque l'ensemble des actionnaires inclut définitivement le nème actionnaire, où la part est une fonction d'un secret et d'une action restante. Donc le deuxième cas est quand la coalition des actionnaires exclut une partie, où est nettement différente de la partie. Donc, pour la simplicité, vous pouvez imaginer que mon = 1, cela signifie que l'adversaire corrompu les derniers actionnaires ici. Il s'avère que la part manquante que l'ensemble des actionnaires est manquante, qui dans cet exemple est la part 1, qui est indépendante du secret. Parce que cela a été choisi au hasard par le concessionnaire et cela fait en sorte que même si l'adversaire apprend, c'est la part qui est aussi indépendante du secret. Parce que, par exemple, si nous examinons le cas où 1 est manquant dans la coalition, alors de la part de la vue de l'agresseur, l'attaquant sait que la valeur = 1 kamikaze présumé, où et 1ne sont pas connus de l'adversaire. Et où 1 est choisi de façon indépendante et aléatoire par le concessionnaire. Vous pouvez donc imaginer que ce n'est rien d'autre que le cryptage d'un clavier d'un message avec une clé, où la clé n'est rien d'autre que le xor des partages 2, lesquels sont connus de l'adversaire et de la valeur aléatoire 1, qui n'est pas connue de l'agresseur, ce qui signifie que même si l'adversaire est en train de voir, il ne peut pas déterminer s'il s'agit en fait d'une part correspondant au secret ou correspondant à un secret. Parce qu'il ne connaît pas la valeur de la part manquante 1, qui a été choisie au hasard et choisie indépendamment du secret réel du croupier. Cela garantit que même si l'adversaire contrôle le dernier actionnaire, il n'apprira absolument rien du secret sous-jacent. Et c'est pourquoi le partage secret répond aux exigences d'un (système de partage secret). (Voir Heure de la diapositive: 11:01) Il s'avère donc que le partage secret additif dont nous avons discuté, ne fonctionne que si mon seuil est. Mais en général je serais intéressé de concevoir un partage secret où mon seuil pourrait ne pas être, mon seuil pourrait être strictement inférieur à. Alors, voyons maintenant une solution, une solution naïve d'arriver à un système de partage secret pour n'importe quel seuil. Donc l'idée ici est que nous prenons tous les sous-ensembles appropriés de l'ensemble des parties, disons, où la taille d'est et de gérer une instance indépendante dédiée de partage des secrets d'additifs entre les parties en tant qu'actionnaires, avec le seuil d'être. Et l'idée ici est que si nous faisons cela pour chaque sous-ensemble de taille, alors quand il s'agit de la coalition réelle des actionnaires qui pourraient essayer d'en apprendre davantage sur le secret, cette coalition d'actionnaires manquera au moins une action pour reconstruire le secret partagé réel. Ce que j'essaie de dire est donc mieux démontré par cet exemple. Alors imaginez mon et je veux concevoir un schéma où mon seuil. Cela signifie que tout sous-ensemble de trois actionnaires devrait être en mesure de reconstruire le secret, mais n'importe quel groupe de deux actionnaires, s'ils tentent de tirer leurs parts, ils ne devraient pas reconstruire le secret. Donc l'idée ici est que le dealer divise cet ensemble de quatre parties en différents sous-ensembles 1,2, 3, 4 de taille trois parties. Maintenant, dans le premier sous-ensemble 1 = { 1, 2, 3 }, le courtier exécute une instance de partage de secret additif avec le seuil étant t = 2. Le distributeur à Namely choisit les actions aléatoires 11, 12, 13, telles que 11 euros 12 13, et ensuite les actions sont données à l'actionnaire respectif 1,2,3. De même, le concessionnaire exploite une instance indépendante de partage des additifs (3, 3) pour les sous-ensembles 2, 3 et 4. Maintenant, la part globale pour 1 sera toutes les actions qu'elle reçoit dans diverses instances du partage additif (3, 3), en fonction des différents sous-ensembles dans lesquels elle est présente. En effet, sa part sera de 11, 21 et 31. Maintenant il est facile de voir que quel que soit le fait que deux parties soient corrompues, parce que mon seuil dans tous les cas de partage des additifs, ces deux actionnaires n'apprennent absolument aucune information sur les secrets. Ainsi, par exemple si 1 et 2 sont corrompus, s'ils sont sous le contrôle de l'adversaire puis sur la base de leurs parts qu'ils apprennent, en raison de leur présence dans le sous-ensemble 1, les parties 1,2 ne parviennent pas à apprendre le secret, parce qu'elles manqueront le partage 13. De la même façon pour le sous-ensemble 2, ces deux parties manqueront le partage 23 et c'est pourquoi le secret ne leur sera pas connu, etc. Donc, peu importe le sous-ensemble des partis qui sont corrompus, sur la base de leurs parts, ils ne parviennent pas à apprendre le secret réel. Alors maintenant, vous vous demandez peut-être que nous avons maintenant un système de partage secret pour n'importe quel seuil par rapport à la valeur de. Mais il s'avère que ce schéma est inefficace parce que le nombre de sous-ensembles de taille est (1), qui devient une quantité exponentielle si c'est approximativement. Cela signifie que les concessionnaires doivent faire face à un nombre exponentiel de valeurs ici et il en va de même pour chaque actionnaire. Il s'agit donc d'une solution inefficace. (Référez-vous à l'heure de la diapositive: 15:53)Et nous allons discuter d'une solution très intelligente pour (Secret-Partage dû à Adi Shamir. Et c'est l'une des constructions cryptographiques les plus simples à laquelle vous pouvez penser. C'est mon préféré. Et ceci est basé sur des calculs simples que vous avez peut-être appris au cours de votre école secondaire. Donc l'idée est ici, si vous voulez partager un secret, puis pour le partager, vous choisissez un polynôme aléatoire de degré, de sorte que le terme constant du polynôme est le secret que vous voulez partager. Et que les actions soient les points ou les valeurs distincts gisant sur ce polynôme. Pour démontrer mon point de vue, imaginez mon seuil et j'ai un secret et je suis le dealer. Ce que je peux faire est, pour partager le secret, puisque mon seuil, je choisis une ligne droite aléatoire, il pourrait s'agir de n'importe quelle ligne droite dans l'avion avec la seule restriction a été que son terme constant devrait être le secret que je veux partager. Et ce que je fais maintenant c'est que je calcule la valeur de la ligne droite à certaines valeurs distinctes publiquement connues, disons à 1, à 2 et à 3. Il s'agit des actions du premier parti, du deuxième parti et du tiers respectivement. Chacun sait que la première partie obtient la valeur de la ligne droite que le concessionnaire a choisie à 1 et ainsi de suite. Donc ces valeurs, elles sont connues publiquement et tout le monde saura que c'est associé à la fête. Essons maintenant de prouver que, intuitivement, il satisfait aux exigences de (partage secret. Il est donc facile de voir que si les actionnaires se rassemblent, ils peuvent reconstruire de manière unique le polynôme de degré que le concessionnaire a choisi. Parce que des valeurs distinctes sur un polynôme de degré inconnu suffisent à reconstruire de manière unique ce polynôme. Par exemple, si, par exemple, les deux premiers actionnaires se retrouvent avec leurs actions 1 et 2, ils peuvent trouver la ligne droite passant par les points (1, 1) et (2, 2) en ajustant une ligne droite. Une fois qu'ils ont obtenu la ligne droite, ils peuvent prendre le terme constant de la ligne droite pour être le secret récupéré. D'autre part, le deuxième fait que nous pouvons utiliser pour les polynômes de degré est que, si vous prenez des actionnaires qui sont les méchants et qu'ils essaient de reconstruire le secret du dealer, ils ne le feront pas. Parce que des valeurs distinctes ne suffisent pas à récupérer de manière unique le polynôme de degré inconnu qui a été choisi par le concessionnaire. Plus précisément, dans cet exemple, le premier actionnaire est corrompu. Puis de son point de vue, il pourrait y avoir un nombre infini de lignes droies possibles dans le plan passant par le point (1, 1) et donc un nombre infini de secrets possibles. C'est-à-dire juste à partir d'actions, l'adversaire ne pourra absolument pas reconstruire de façon unique le polynôme original du dealer et donc le secret original du dealer. C'est l'idée intuitive. Il s'avère que nous devons exécuter tous les calculs ci-dessus sur un champ fini pour atteindre la sécurité et éviter de travailler sur un domaine infini. (Référez-vous à l'heure de la diapositive: 20:01) Alors essayons de comprendre d'abord quelques faits de base sur les polynômes sur un champ fini. Alors imaginez que j'ai un champ fini (. Un polynôme de degré est de la forme 0 + 1 ∙ ∙, où 0, …, ∈. Une valeur est appelée racine de (), si () = 0I souligne ici que toutes les opérations ici sont les opérations + et ∙ sur le champ. Maintenant un autre fait bien connu de l'algèbre de l'abstrait que nous pouvons utiliser ici est le suivant. Si on vous donne un polynôme de degré au-dessus d'un champ, alors il peut avoir la plupart des racines. Par exemple, si, une droite sur un champ rencontre l'axe des y au plus un point. Et c'est vrai pour n'importe quel polynôme de degré sur un champ. Et sur la base de ce résultat, nous pouvons dire que deux polynômes distincts (), () over peuvent avoir à la plupart des valeurs communes. Ainsi, par exemple, si vous avez 2 lignes droitelles distinctes, elles peuvent se croiser au plus un point. Ils ne peuvent pas se croiser à 2 points parce que s'ils se croisent à deux points communs, alors les 2 lignes droitaux sont fondamentalement la même ligne droite et en général, cette généralisation pour n'importe quelle valeur de. Encore une fois, je ne prouve pas ce théorème. Ce sont des résultats bien connus de l'algèbre de l'abstrait. Et le résultat final que je vais utiliser pour donner la description du partage de Shamir est la formule d'interpolation Lagrange. Donc ce que ce théorème dit fondamentalement c'est que si on vous donne des paires de valeurs t + 1 (1, 1), …, (,) De la zone, où 1, …, sont distincts. Il existe ensuite un polynôme de degré unique, tel que) =, pour 1 ≤ Pour voir comment exactement nous pouvons calculer ce polynôme, permettez-moi de définir une séquence de polynômes, où le polynôme ((− 1) (− 2) est défini (− − 1) (− 1) (− + 1) (− 1) (− 2) (− − 1) (− 1) (− 1) (− 1), qui possède un degré. Et la façon dont j'ai défini ce polynôme (il suit que () = 1, while (1) = (2) = ≥ () = () = 0. Cela signifie que ces (polynômes) sont tels qu'ils survivent à =, alors qu'ils disparaissent à toutes les autres valeurs. Maintenant mon polynôme inconnu passant à travers les t + 1 paires de valeurs (xi, yi). Et je peux représenter ce polynôme inconnu 1 (1 + + + (. (voir Heure de la diapositive: 24:43)Et il est facile de voir qu'en effet 1) = 1, parce que pour 1, mon 1 (polynôme survivra et donnera la valeur 1 et 1 multiplié par 1 sera 1, alors que tous les autres (les polynômes vont disparaître. De la même façon pour 2, tous mes polynômes delta disparaîteront sauf le 2 (polynôme, qui donnera la valeur 1 et 1 multiplié par 2 me donnera 2, ce qui satisfait à mon état. C'est donc le polynôme de degré unique, que vous pouvez découvrir en passant par les points donnés (1, 1), …, (,), où 1, …, sont distincts. Maintenant vous vous demandez peut-être pourquoi 1, …, est distinct doit être distinct? Ils doivent être distincts pour s'assurer que chacun des (polynômes) a un dénominateur qui est différent de zéro. Et si le dénominateur est différent de zéro, alors fondamentalement ce numérateur divisé par le dénominateur doit être interprété comme si ce numérateur est multiplié par l'inverse multiplicatif de mon dénominateur, parce que je fais la division ici. Et cette division doit être interprétée comme multipliant le numérateur par l'inverse multiplicatif du dénominateur. Et l'inverse multiplicatif du dénominateur n'existera que si mon dénominateur est différent de zéro. (Référez-vous à l'heure de la diapositive: 26:08)Allons maintenant à la description de Shamir ’ s Secret Sharing. Dans le cadre de la configuration publique, on nous donnera un champ fini où la taille du champ sera au moins, le nombre d'actionnaires. Et associé avec les actionnaires sera publiquement connu des valeurs distinctes non nulles, à savoir 1, …,, qui sont les valeurs du champ fini. L'algorithme de partage du partage secret Shamir est le suivant. Si le croupier a une valeur secrète, qu'il veut partager, alors il choisit un polynôme aléatoire sur le terrain en choisissant des éléments aléatoires comme les coefficients du champ, de sorte que le terme constant du polynôme est le secret que le dealer veut partager. Et maintenant, l'actionnaire, c'est-à-dire le parti, obtient la part, où n'est rien d'autre que la valeur de ce polynôme choisi par le concessionnaire. L'exactitude de ce partage secret est triviale. Autrement dit, imaginez ces actionnaires, n'importe quel sous-ensemble d'actionnaires se rassemblent en échangant leurs parts, puis ils peuvent interpoler de manière unique le polynôme de degré à l'aide de la formule d'interpolation de Lagrange ’ dont nous avons discuté précédemment. Et pour prouver la vie privée, nous allons prouver que si nous prenons un ensemble d'actionnaires parmi ces actionnaires, alors leurs parts sont indépendantes du secret de partage sous-jacent, parce que intuitivement cela vient du fait que les coefficients de polynôme qui sont choisis par le concessionnaire pour partager le secret, sont choisis uniformément au hasard dans le champ sous-jacent. (Référez-vous à l'heure de la diapositive: 27:55)La rendre plus rigoureuse. Permettez-moi de définir un ensemble Fto dénote l'ensemble des polynômes de tous les degrés sélectionnés dans le champ fini dont le terme constant est le secret. Il s'avère donc que le nombre d'un tel polynôme dont le terme constant est le secret n'est rien, mais |. C'est parce que dans chaque polynôme de ce genre, à part le terme constant qui est, il y a d'autres coefficients 1, choisis dans le champ et pour chacun de ces coefficients, il y a |candidats. Par conséquent | F | = |. Pour la simplicité et sans perte de la genialité, supposons que les premiers actionnaires sont corrompus, ce qui signifie qu'ils ont vu les partages 1, …,. Et ils savent que ces actions ne sont rien d'autre que la valeur d'un polynôme de degré inconnu, évalué à 1, …,. Nous montrerons que la distribution de probabilité de ces actions est indépendante du secret choisi par le concessionnaire. Pour cela, nous notons d'abord qu'étant donné n'importe quelle action arbitraire 1, …,, il existe un polynôme unique, avec =), pour. Cela découle du fait que les points distincts (0,), (1, 1), …, (,) Ne peut résider que sur un seul polynôme de degré. Maintenant basé sur toutes ces choses, je demande que les actions 1, …, soient indépendantes du secret réel partagé par le croupier. Et pour prouver cette affirmation, considérons une paire de secrets arbitraires (′) De, comme ça. Nous montrerons que du point de vue de l'adversaire, 1, …, pourrait être les parts d'aussi bien qu'avec une probabilité égale. Soit un polynôme unique de l'ensemble Fwhich aurait produit les actions 1, …, pour le secret. De même, laissez ′ (être les polynômes uniques de l'ensemble F ′, qui aurait produit les partages 1, …, pour le secret. Maintenant la probabilité que l'adversaire ait vu les partages 1, …,, marchand ’ s secret est le même que le dealer a utilisé le polynôme (pour le partage. Et cet événement se produit avec la probabilité 1/ |, en tant que marchand ’ s polynomial est choisi au hasard, où tous les coefficients sauf le terme constant sont choisis au hasard à partir de. En utilisant exactement le même argument, nous concluons que la probabilité que l'adversaire ait vu les partages 1, …,, dealer ’ s secret est le même que le dealer a utilisé le ′ polynomial (pour le partage. Cet événement se produit avec la probabilité 1/ |. Cela prouve que la distribution de probabilité de 1, …, est indépendante du secret sous-jacent et donc de voir ces actions, l'adversaire sera sans clume si le dealer a partagé le secret ou le secret. Cela m'amène à la fin de cette conférence. Juste pour résumer. Dans cette conférence, nous avons introduit le problème de (le partage secret et nous avons vu trois constructions. Nous avons vu la construction d'un partage secret d'additif où le seuil est. Et ensuite à l'aide de ce (partage secret