Attribuez aléatoirement n éléments à n agents de telle sorte que chaque agent ne connaisse que son propre élément

Question

Problème

Je travaille sur une application qui consiste à mélanger et à distribuer des cartes à jouer aux joueurs.En guise de défi, j'ai essayé de résoudre ce problème d'une manière qui ne nécessite pas d'intermédiaire de confiance.

En d’autres termes, la tâche consiste à trouver un algorithme distribué qui

• attribue de manière unique $n$ numéros d'agents $1..n$
• permet à chaque agent de ne rien savoir de la mission sauf la sienne
• lors de la révélation de la mission, permet aux autres joueurs de vérifier la mission

Nous supposons également que connaître la mission d'autrui est un avantage pour chaque agent, et révéler prématurément la sienne est un inconvénient.Les agents sont également supposés être capables de communiquer entre eux d’une manière cachée à tous les autres agents.

Solution partielle

La solution que j’ai proposée ne fonctionne que dans l’hypothèse où les adversaires ne collaborent pas.

L'idée est de créer un ensemble de $n$ occasionnels et attribuez à chaque agent exactement un occasionnel.L'ensemble est ensuite transmis d'agent à agent dans un ordre convenu, caché à tous les autres, jusqu'à ce que chaque agent reçoive l'ensemble exactement une fois.Chaque fois qu'un agent reçoit l'ensemble, il échange son nom occasionnel avec un nouveau, mémorise le nouveau nom occasionnel et confirme la réception de l'ensemble aux autres.Toute cette procédure est effectuée deux fois, auquel cas tous les agents ont reçu l'ensemble au moins une fois après que tous les autres agents ont échangé leurs noms occasionnels, ce qui rend impossible la reconnaissance et donc le mappage des noms occasionnels aux autres agents.

Lorsque le dernier agent reçoit l'ensemble une deuxième fois, il le partage avec tout le monde et tous les agents confirment aux autres que leur nom occasionnel est contenu dans l'ensemble.Les agents attribuent ensuite un numéro à chaque occasionnel de l'ensemble sur la base d'une graine aléatoire convenue, nous donnant l'affectation unique requise.

Pour permettre la vérification de la propriété, au lieu des noms occasionnels, les agents mettent la valeur de hachage de leur nom occasionnel sur l'ensemble, révélant le nom occasionnel réel uniquement lorsque la vérification est requise.

---

Le problème avec cette solution est que si les adversaires sont autorisés à collaborer, chaque fois qu'un adversaire reçoit l'ensemble, ils peuvent comparer leurs versions, identifier les modifications et potentiellement en déduire laquelle n'appartient pas à d'autres agents, ce qui leur permet de savoir quel numéro leur a été attribué. .

Toutes les idées sont appréciées !

Answer 1

Ce problème fait partie d'un ensemble de problèmes appelés Poker mental.

Il y a un excellent et petit article par Shamir, Rivest et Adleman qui décrivent une manière pratique de mettre en œuvre un tel algorithme.

Le résumé est d’or :

Deux joueurs potentiellement malhonnêtes peuvent-ils jouer une partie de poker équitable sans utiliser de cartes (par ex.par téléphone) ?

Cet article apporte les réponses suivantes :

1. Non.(Preuve mathématique rigoureuse fournie.)
2. Oui. (Protocole correct et complet donné.)

Fondamentalement, d’un point de vue de la théorie de l’information, jouer à un tel jeu est impossible sans un tiers de confiance, mais il est possible de concevoir un protocole utilisant des fonctions cryptographiques difficiles à inverser bien connues.

---

L'algorithme fonctionnera comme suit :

Supposons que vous ayez $n$ occasionnels (numéros de $1$ à $n$).Chaque participant au protocole a accès à des fonctions secrètes $e_i$ et $d_i$ qui sont utilisés pour crypter et décrypter les données.Ces fonctions doivent satisfaire quelques propriétés, que nous analyserons plus tard.

Le premier participant reçoit l'ensemble complet des noms occasionnels.Il crypte chaque occasionnel avec sa fonction secrète $e_1$, les mélange de manière aléatoire et transmet les données résultantes au deuxième participant.

Le deuxième participant fera de même, mais dans ce cas, il n'a pas de noms occasionnels, mais une permutation aléatoire des noms occasionnels cryptés.Il chiffrera également chaque élément avec sa propre fonction secrète $e_2$ et mélangez à nouveau les données.

Puis un troisième participant, et ainsi de suite, jusqu'à ce que tous les participants aient mélangé et chiffré les données grâce à sa fonction secrète.

Dans l'ensemble, le processus de configuration est :

data = [1..n]
for i in [1..n]:
    data = [e_i(nonce) for nonce in data]
    shuffle(data)

Après cette configuration, chaque élément de data les noms occasionnels sont-ils chiffrés avec toutes les fonctions secrètes $e_i$ dans un ordre aléatoire inconnu de tous les participants.

Notez qu'à ce stade, il est impossible pour chaque participant de déduire chaque nonce sans l'aide des autres participants.Et il suffit que l'un des participants mélange les données de manière complètement aléatoire pour supprimer tout biais possible dans l'ordre résultant, indépendamment si un participant malveillant tente de biaiser l'ordre.

Participant $i$-th se voit attribuer le nom occasionnel à la position $i$.Pour récupérer ce nonce, le participant $i$ demande à chaque autre participant $j eq je$ pour décrypter la valeur avec sa fonction secrète $d_j$ à leur tour.À la fin des participants $i$ aura son nom chiffré avec sa propre fonction secrète $e_i$ afin qu'il puisse le récupérer en utilisant $d_i$.

Récupération occasionnelle $i$:

nonce_i_encrypted = data[i]
for j in [1..n]:
    if j == i:
        continue
    nonce_i_encrypted = d_j(nonce_i_encrypted)

nonce_i = d_i(nonce_i_encrypted)

A la fin de cette procédure, chaque participant connaît son propre nonce, mais aucun autre participant n'en sait rien.

Après avoir utilisé ces valeurs pour votre problème actuel, un joueur peut prétendre qu'il contrôle réellement ce type de cas, soit en publiant les fonctions secrètes. $e_i$ et $d_i$, afin que chacun puisse calculer localement toutes les valeurs, ou décrypter la valeur data[i] après la première étape mais avant la deuxième étape, publier puis utiliser cette valeur comme entrée dans la deuxième étape pour la déchiffrer complètement.

Les fonctions $e_i$ et $d_i$ doit avoir les propriétés suivantes :

1. $e_i(x)$ est la version cryptée d'un message $x$ sous la clé $i$,
2. $d_i(e_i(x)) = x$ pour tous les messages $x$ et les clés $i$,
3. $e_i(e_j(x)) = e_j(e_i(x))$ pour tous les messages $x$ et les clés $i$ et $j$,
4. Donné $x$ et $e_i(x)$ il est informatiquement impossible pour un cryptanalyste de dériver $i$, pour tous $x$ et $i$,
5. Compte tenu des messages $x$ et $y$, il est informatiquement impossible de trouver les clés $i$ et $j$ tel que $e_i(x) = e_j(y)$.

Comme indiqué dans l'article, la plupart de ces hypothèses sont courantes, à l'exception de la propriété 3), qui indique que les fonctions de chiffrement doivent commuter.

Ils proposent un schéma de chiffrement simple qui satisfait ces propriétés.Disons que tous les participants sont d'accord sur un grand nombre premier $P$ (ce n'est pas grave si c'est corrigé dans le protocole).Et chaque participant choisit secrètement un numéro aléatoire $k_i$ tel que $gcd(k_i, P - 1) = 1$.Disons $q_i$ est une telle valeur que $k_i \cdot q_i \equiv 1 \mod(P -1)$.Puis participant $i$ peut utiliser des fonctions secrètes :

$$e_i(x) = x^{k_i} \mod(P)$$ $$d_i(y) = y^{q_i} \mod(P)$$

Quelques mises en garde concernant cet algorithme :Les participants ne peuvent pas tricher de telle manière que la collusion leur permette d'apprendre de temps en temps l'autre pair (à moins bien sûr $n-1$ les participants s'entendent et il ne reste qu'une seule occasion).Cependant, des participants malveillants peuvent attaquer le protocole en ne participant pas, bloquant ainsi le processus de négociation, car de nombreuses actions sont requises de la part de chaque participant pendant qu'il traite les informations occasionnelles.Ils peuvent également produire du charabia, mais cela peut être atténué en étendant le protocole pour détecter quel participant était le coupable et en pénalisant ce participant à un niveau plus élevé.

---

J'ai implémenté cet algorithme pour un jeu de poker dans PROCHE blockchain.Vous pouvez voir le code en rouille ici.Notez qu'il n'y a pas de tiers de confiance dans une blockchain, mais il existe un environnement informatique de confiance que tous les participants peuvent utiliser comme mécanisme pour exécuter ce protocole.