Atribua aleatoriamente n elementos a n agentes, de modo que cada agente conheça apenas seu próprio elemento

Question

Problema

Estou trabalhando em um aplicativo que envolve embaralhar e distribuir cartas de baralho aos jogadores.Como desafio, tentei resolver este problema de uma forma que não exigisse um intermediário confiável.

Em outros termos, a tarefa é encontrar um algoritmo distribuído que

• atribui exclusivamente $n$ números de agentes $1..n$
• permite que cada agente não saiba nada sobre a tarefa além de sua própria
• ao revelar a tarefa, permite que outros jogadores verifiquem a tarefa

Assumimos também que conhecer a atribuição do outro é uma vantagem para cada agente, e revelar a sua prematuramente uma desvantagem.Supõe-se também que os agentes sejam capazes de conversar entre si de uma forma oculta de todos os outros agentes.

Solução parcial

A solução que encontrei funciona apenas sob a suposição de que os adversários não colaboram.

A ideia é criar um conjunto de $n$ nonces e atribua a cada agente exatamente um nonce.O conjunto é então passado de agente para agente em uma ordem acordada, oculto de todos os outros, até que cada agente receba o conjunto exatamente uma vez.Cada vez que um agente recebe o conjunto, ele troca seu nonce por um novo, memoriza o novo nonce e confirma o recebimento do conjunto para os demais.Todo esse procedimento é feito duas vezes, momento em que todos os agentes receberam o conjunto pelo menos uma vez após todos os outros agentes terem trocado seus nonces, impossibilitando o reconhecimento e, portanto, o mapeamento dos nonces para os outros agentes.

Quando o último agente recebe o conjunto pela segunda vez, ele o compartilha com todos, e todos os agentes confirmam aos demais que seu nonce está contido no conjunto.Os agentes então atribuem um número a cada nonce do conjunto com base em uma semente aleatória acordada, dando-nos a atribuição exclusiva necessária.

Para permitir a verificação de propriedade, em vez dos nonces, os agentes colocam o valor hash do seu nonce no conjunto, revelando o nonce real apenas quando a verificação é necessária.

---

O problema com esta solução é que se os adversários puderem colaborar, cada vez que um adversário receber o conjunto, eles poderão comparar suas versões, identificar alterações e potencialmente derivar qual nonce pertence a outros agentes, permitindo-lhes saber qual número foi atribuído a eles. .

Todas as ideias são apreciadas!

Answer 1

Este problema faz parte de um conjunto de problemas conhecido como Pôquer Mental.

Há um excelente e pequeno artigo por Shamir, Rivest e Adleman que descrevem uma forma prática de como implementar tal algoritmo.

O resumo é ouro:

Dois jogadores potencialmente desonestos podem jogar um jogo de pôquer justo sem usar cartas (por exemplo,por telefone)?

Este artigo fornece as seguintes respostas:

1. Não.(Rigorosa prova matemática fornecida.)
2. Sim. (Protocolo correto e completo fornecido.)

Basicamente, do ponto de vista da teoria da informação, jogar tal jogo é impossível sem um terceiro confiável, mas é viável projetar um protocolo usando funções criptográficas conhecidas e difíceis de reverter.

---

O algoritmo funcionará da seguinte forma:

Suponha que você tenha $n$ nonces (números de $1$ para $n$).Cada participante do protocolo tem acesso a funções secretas $e_i$ e $d_i$ que são usados ​​para criptografar e descriptografar dados.Estas funções devem satisfazer algumas propriedades, que analisaremos mais tarde.

O primeiro participante recebe o conjunto completo de nonces.Ele criptografa cada nonce com sua função secreta $e_1$, embaralha-os aleatoriamente e passa os dados resultantes para o segundo participante.

O segundo participante fará o mesmo, mas neste caso não possui nonces, mas sim uma permutação aleatória dos nonces criptografados.Também criptografará cada elemento com sua própria função secreta $e_2$ e embaralhe os dados novamente.

Depois, o terceiro participante e assim por diante, até que todos os participantes tenham embaralhado e criptografado os dados com sua função secreta.

No geral, o processo de configuração é:

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

Após esta configuração, cada elemento do data os nonces são criptografados com todas as funções secretas $e_i$ em uma ordem aleatória desconhecida para qualquer participante.

Observe que neste ponto é impossível para cada participante deduzir cada nonce sem a ajuda de outros participantes.E basta que um dos participantes embaralhe os dados de forma completamente aleatória para remover qualquer possível viés na ordem resultante, independentemente de algum participante mal-intencionado tentar distorcer a ordem.

Participante $i$-th recebe o nonce na posição $i$.Para recuperar tal nonce, o participante $i$ pergunta um ao outro participante $j eq i$ para descriptografar o valor com sua função secreta $d_j$ em turnos.No final participante $i$ terá seu nonce apenas criptografado com sua própria função secreta $e_i$ para que ele possa recuperá-lo usando $d_i$.

Recuperando no momento $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)

No final deste procedimento, cada participante conhece o seu próprio nonce, mas nenhum outro participante sabe nada sobre ele.

Depois de usar esses valores para o seu problema atual, um jogador pode afirmar que está realmente no controle de tal nonce, publicando as funções secretas $e_i$ e $d_i$, para que todos possam calcular localmente todos os valores ou descriptografar o valor data[i] após a primeira etapa, mas antes da segunda etapa, publicar e usar esse valor como entrada na segunda etapa para descriptografá-lo completamente.

As funções $e_i$ e $d_i$ deverá ter as seguintes propriedades:

1. $e_i(x)$ é a versão criptografada de uma mensagem $x$ sob chave $i$,
2. $d_i(e_i(x)) = x$ para todas as mensagens $x$ e chaves $i$,
3. $e_i(e_j(x)) = e_j(e_i(x))$ para todas as mensagens $x$ e chaves $i$ e $j$,
4. Dado $x$ e $e_i(x)$ é computacionalmente impossível para um criptoanalista derivar $i$, para todos $x$ e $i$,
5. Dada qualquer mensagem $x$ e $y$, é computacionalmente impossível encontrar chaves $i$ e $j$ de tal modo que $e_i(x) = e_j(y)$.

Conforme declarado no artigo, a maioria dessas suposições são de alguma forma comuns, exceto a propriedade 3), que informa que as funções de criptografia devem comutar.

Eles propõem um esquema de criptografia simples que satisfaça essas propriedades.Digamos que todos os participantes concordem com algum grande número primo $P$ (está tudo bem se for corrigido no protocolo).E cada participante escolhe secretamente um número aleatório $k_i$ de tal modo que $mdc(k_i, P - 1) = 1$.Digamos $q_i$ é esse valor que $k_i \cdot q_i \equiv 1 \mod(P -1)$.Então participante $i$ pode usar funções secretas:

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

Algumas advertências sobre este algoritmo:Os participantes não podem trapacear de tal forma que o conluio os beneficie no aprendizado do nonce sobre o outro colega (a menos, é claro, $n-1$ os participantes conspiram e resta apenas um nonce).No entanto, participantes mal-intencionados podem atacar o protocolo sem participar, paralisando efetivamente o processo de negociação, uma vez que muitas ações são exigidas de cada participante enquanto eles negociam os nonces.Eles também podem produzir jargões, mas isso pode ser mitigado estendendo o protocolo para detectar qual participante foi o culpado e penalizando esse participante em um nível superior.

---

Eu implementei esse algoritmo para um jogo de pôquer em PERTO da blockchain.Você pode ver o código enferrujado aqui.Observe que não há terceiros confiáveis ​​em um blockchain, mas há um ambiente de computação confiável que todos os participantes podem usar como mecanismo para executar este protocolo.