X-FeedAbuse: http://nntpfeed.proxad.net/abuse.pl feeded by 82.66.60.35
Path: ...!2.eu.feeder.erje.net!feeder.erje.net!proxad.net!feeder1-2.proxad.net!nntpfeed.proxad.net!pasdenom.info!from-devjntp
Message-ID: <FQynwbASehb_ZmZqlZB6KcAzSz4@jntp>
JNTP-Route: news2.nemoweb.net
JNTP-DataType: Article
Subject: Re: Preuve de transfert
References: <UIvzzOGDfoNraCnAKqSletaOHvA@jntp> <tapgo2$2u5t$1@cabale.usenet-fr.net>
Newsgroups: fr.sci.maths
JNTP-HashClient: lbbeKyEopQo71o-tSQrn5BdjUZA
JNTP-ThreadID: jQlT-kjzg3HhJzTgCDpHmS6MQ24
JNTP-Uri: http://news2.nemoweb.net/?DataID=FQynwbASehb_ZmZqlZB6KcAzSz4@jntp
User-Agent: Nemo/0.999a
JNTP-OriginServer: news2.nemoweb.net
Date: Fri, 15 Jul 22 19:49:36 +0000
Organization: Nemoweb
JNTP-Browser: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/103.0.0.0 Safari/537.36
Injection-Info: news2.nemoweb.net; posting-host="6f75b44715a75b7d88e7789aa4eb3bafe9d3eba6"; logging-data="2022-07-15T19:49:36Z/7076080"; posting-account="1@news2.nemoweb.net"; mail-complaints-to="newsmaster@news2.nemoweb.net"
JNTP-ProtocolVersion: 0.21.1
JNTP-Server: PhpNemoServer/0.94.5
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-JNTP-JsonNewsGateway: 0.96
From: Julien Arlandis <julien.arlandis@gmail.com>
Bytes: 4310
Lines: 69

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.