Sujet : Re: Preuve de transfert
De : julien.arlandis (at) *nospam* gmail.com (Julien Arlandis)
Groupes : fr.sci.mathsDate : 15. Jul 2022, 21:49:36
Autres entêtes
Organisation : Nemoweb
Message-ID : <FQynwbASehb_ZmZqlZB6KcAzSz4@jntp>
References : 1 2
User-Agent : Nemo/0.999a
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.
- la taille N2 est-elle la somme totale des bits échangés entre Charlie
et Alice ou Bob ? Ou bien est-ce que c'est le nombre de bits transmis
par Charlie à Alice, et celui transmis en réponse d'Alice à Charlie,
et même chose avec Bob ?
On considère tous les bits qui s'échangent depuis ou vers Charlie :
bits[A > C] + bits[C > A] + bits[B > C] + bits[C > B] < N2
- lorsque l'un des trois compères envoie quelque chose sur le canal
d'information, est-ce que c'est accessible par les deux autres, ou
bien chaque conversation est-elle privée à deux personnes seulement ?
C'est une communication point à point, j'aurais dû le préciser.
- peut-il y avoir une longue série de questions-réponses (jusqu'à N2
questions et/ou réponses) ou est-ce que c'est une question suivie
d'une réponse, ou alors encore autre chose ?
Aucune contrainte directionnelle dans les bits échangés.
- peut-il y avoir une information commune aux protagonistes, de taille
N2 ou davantage, avant que ne commence la phase de vérification − par
exemple un dictionnaire, ou peut-être les décimales de pi ?
Oui aucun problème. Tu auras compris que si Alice veut transférer à Bob les 10^12 premières décimales de pi, il aura la plus grande difficulté à prouver à Charlie qu'il ne s'est pas contenté de lui envoyer la consigne.
- peut-on faire appel à des éléments physiques à la fois aléatoires et
contrôlés, par exemple avec des paires de particules intriquées ?
Oui pourquoi pas.
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.