Uma loteria que você pode estar convencido de que é justo

(Desculpe, se isso é bem conhecido.) Gostaria de dar algum item a um dos agentes , para que o agente obtenha o item com probabilidade . Existe uma ferramenta criptográfica (ou outra) para que todo agente (e até todo observador) possa se convencer de que o desenho aleatório foi realmente justo?$k$p $j$$p_i$

Se estou entendendo o problema corretamente, parece que o público lança uma moeda do lado . Parece haver muitas maneiras de fazer isso se você assumir um pouco de compromisso. Um exemplo seria fazer com que cada parte gere um número inteiro aleatório entre 0 e , usando o comprometimento de bits para confirmar publicamente essa sequência de bits. Então, após a confirmação de cada agente, todos eles revelam publicamente seu número inteiro secreto. O agente vencedor é então o indexado pela soma dos números inteiros módulo . Se pelo menos um agente for honesto, o flip deve ser aleatório.k - 1 $k$$k-1$$k$

Obviamente, um problema disso é que exige pouco comprometimento. Esquemas teóricos da informação para comprometimento de bits são impossíveis para a computação clássica e quântica (embora Adrian Kent tenha proposto recentemente um esquema que explora a relatividade). No entanto, o comprometimento seguro de bits pode ser alcançado com suposições computacionais.

Como outros usuários sugeriram, esse é um problema bem estudado em criptografia. É chamado de "lançamento de moeda" e é um caso especial de computação multipartidária.

Qual protocolo o trabalho realmente depende bastante do contexto.

• Na configuração "autônoma", o protocolo será executado isoladamente, sem que os jogadores estejam envolvidos em outros protocolos (ou mesmo em qualquer interação com o mundo externo) ao mesmo tempo. Há um tratamento maravilhosamente completo disso no livro de Oded Goldreich, "Foundations of Cryptography" (volume 2, eu acho).

Só para se ter uma idéia de como é sutil, o protocolo "todo mundo se compromete com valores aleatórios" sugerido por outro respondedor é inseguro se o esquema de compromisso usado for maleável. Os esquemas de comprometimento não-pequenos fornecem um protocolo seguro, mas são um pouco complicados de projetar.

• Nas configurações em que os participantes estão envolvidos em outros protocolos simultâneos, você deseja um protocolo que possa ser composto . Existem várias noções de composibilidade, mas a mais forte, chamada composibilidade universal , requer algumas suposições de configuração adicionais (por exemplo, uma PKI ou uma sequência aleatória comum visível a todas as partes, mas controlável por nenhuma delas). Infelizmente, não conheço um tratamento acessível sobre esse tópico. Mas analisar um artigo recente sobre composição universal ou compromisso não-pequeno seria um bom ponto de partida.

Nota: leia os comentários abaixo. Este protocolo parece ter problemas.

$p_j$

$\{0,1\}^b$$b$

Qualquer agente pode ter certeza de que o número aleatório escolhido veio uniformemente aleatoriamente, escolhendo seu próprio vetor uniformemente aleatoriamente. Para qualquer observador se convencer, precisa confiar que pelo menos um agente seguiu o protocolo, mas, se nenhum, seguiu, acho que ninguém realmente queria uma loteria justa para começar.

Observadores passivos não podem verificar se o desenho não foi encenado. Entradas no processo pseudo-aleatório podem ser escolhidas para dar o resultado desejado.

No entanto, se o observador puder fornecer um número aleatório que ele sabe ser aleatório E garantir que outros agentes não alterem suas entradas posteriormente (porque eles poderiam compensar seu efeito com as entradas), então ele pode ter certeza de que o resultado foi realmente aleatório .

Isso requer um esquema de compromisso que não conhecemos matematicamente comprovadamente seguro, mas na prática pode ser realizado usando hash seguro (como o SHA3).

Considere este exemplo:

Eu fiz um exemplo de implementação. Você pode vê-lo ao vivo aqui: https://mrogalski.eu/cl/ ou verificar fontes no GitHub .