Cryptographie

[sorenoa]

Bonjour,
J'ai un exposé à présenter sur le partage de secret de Shamir, et je suis tombée sur le problème suivant:
"Eleven scientists are working on a secret project. They wish to lock up the documents in a cabinet so that the cabinet can be opened if and only if six or more of the scientists are present. What is the smallest number of locks needed? What is the smallest number of keys to the locks each scientist must carry? "

J'ai donc cherché une démonstration et je suis arrivée sur ce site:
https://math.stackexchange.com/question ... and-a-safe
Ce n'est pas exactement le même problème mais il est analogue.
La deuxième réponse (celle de Calvin Lin) m'a l'air plutôt intéressante par rapport à ce que je recherche mais je ne comprends pas vraiment le cheminement de sa pensée. Comment a-t-on .
Et pour le sens réciproque, est-ce que cette démonstration est assez "mathématique" pour être présentée comme une "vraie" preuve (je crois que je bloque parce qu'elle est assez concrète)?

Merci!

[Ben314]

Salut,
Soit le nombre de cadenas, le nombre de personnes et le nombre de personnes nécessaires (et toujours suffisantes) pour ouvrir le coffre.
Si un groupe est constitué de personnes alors il y a au moins une clef qui n'est possédée par aucun des membres du groupe vu que le groupe n'est pas sensé pouvoir ouvrir le coffre.
Mais par contre toute personne qui n'est pas dans ce groupe doit posséder la clef vu qu'en ajoutant cette personne au groupe, cela fait un groupe de personne qui est sensé pouvoir ouvrir le coffre.
Ensuite, si et sont deux groupes distincts de personnes, alors il y a au moins une personne qui est dans , mais pas dans donc qui ne possède pas la clef , mais qui possède la clef .
Cela prouve bien évidement que ce qui signifie qu'il y a forcément plus de clef différentes que de groupes différents constitué de personnes (coefficient binomial).

Réciproquement, s'il plus de clef que de groupes de personnes, c'est qu'il existe une application qui à tout groupe de personnes associe une clef de façon à ce que lorsque .
Donnons alors à chaque personne toutes les clefs existantes sauf les clefs correspondant aux groupes de personnes dont elle fait partie.
- Un groupe de personnes ne peut évidement pas ouvrir le coffre vu que personne n'a la clef .
- Si un groupe ne peut pas ouvrir le coffre, c'est qu'il y a une clef que personne ne possède qui est forcément une clef du type pour un certain groupe de personnes.
Or, comme cette clef et du type pour ce groupe et lui seul, cela signifie que seules les personne du groupe ne possèdent pas la clef et donc que le groupe est contenu dans le groupe et qu'il a donc au plus éléments

[sorenoa]

Salut Ben314, merci pour la réponse! C'est très bien expliqué, je n'y aurais jamais pensé