Sujet : Re: Preuve de transfert
De : julien.arlandis (at) *nospam* gmail.com (Julien Arlandis)
Groupes : fr.sci.mathsDate : 16. Jul 2022, 10:27:54
Autres entêtes
Organisation : Nemoweb
Message-ID : <a0tGykFCac3EYgMNQ2rma1gMUPg@jntp>
References : 1 2 3
User-Agent : Nemo/0.999a
Le 15/07/2022 à 21:49, Julien Arlandis a écrit :
Le 14/07/2022 à 18:37, Olivier Miakinen a écrit :
Bonjour,
Le 14/07/2022 17:11, Julien Arlandis a écrit :
Alice, Bob et Charlie disposent d'un canal de communication pour transférer des informations.
Le but de l'exercice est de trouver un protocole qui permet à Alice et Bob de prouver à Charlie que Alice a bien transféré une information de taille N1 à Bob (N1 étant le nombre de bits) et pour cela Bob et Alice ne peuvent transférer à Charlie qu'une information de taille inférieure à N2.
On considère que N1 = 10^12, et N2 = 10^6.
Quel protocole Charlie va t-il imposer à Bob et Alice ?
J'ai l'impression qu'il manque plein d'informations dans l'énoncé du
problème.
Par exemple :
- est-ce que Charlie connaît l'information qu'Alice est censée avoir
transféré à Bob ?
Pas forcément, il veut juste avoir la garantie que N1 bits ont bien été échangé entre Alice et Bob.
- s'il ne la connaît pas au départ, est-ce un problème s'il en découvre
une partie lors de sa vérification ?
Non aucun problème.
Voilà pour commencer. ;-)
Note que je n'ai pas la réponse à cette énigme et je ne sais même pas si c'est possible. Si c'est impossible j'aimerais bien pouvoir le prouver.
Notons que dans le cas N1 = N2, il existe un protocole trivial : Charlie crée une information aléatoire de taille N1 qu'il transmet à Alice, que Alice transmet à Bob, que Bob transmet à Charlie. Si l'information n'a pas été altérée, preuve est faite que le transfert d'information a bien eu lieu entre Alice et Bob. Dans ce cas, on peut dire que la preuve de transfert est de même volumétrie que le transfert à prouver.
L'intérêt de l'exercice c'est de savoir jusqu'où on peut abaisser N2 relativement par rapport à N1.