Assegna a caso n elementi a agenti N tali che ogni agente conosce solo il proprio elemento

Question

Problema

Sto lavorando a un'app che implica mescolare e distribuire carte da gioco ai giocatori. Come una sfida, ho provato a risolvere questo problema in un modo che non richiede un intermediario attendibile.

In altri termini, il compito è trovare un algoritmo distribuito che

.
• assegna in modo univoco $ N $ numeri agenti $ 1..n $
• consente ad ogni agente di non sapere nulla sull'assegnazione ma è proprio
• Quando si rivela l'assegnazione, consente ad altri giocatori di verificare l'assegnazione

Assumiamo anche che conoscere l'altro incarico sia un vantaggio per ciascun agente e rivelando il proprio prematuramente uno svantaggio. Si suppone anche che gli agenti siano in grado di parlare tra loro in un modo nascosto da tutti gli altri agenti.

soluzione parziale

La soluzione che ho trovato con opere solo sotto l'ipotesi che gli avversari non collaborano.

L'idea è quella di creare un set di $ N $ non perces e assegna ad ogni agente esattamente un nonce. Il set viene quindi passato dall'agente all'agente in un ordine concordato, nascosto da tutti gli altri, fino a quando ogni agente ha ricevuto il set esattamente una volta. Ogni volta che un agente riceve il set, scambia il suo nonce con uno nuovo, memorizza il nuovo nonce e conferma il ricevitore del set agli altri. Questa intera procedura viene eseguita due volte, a quel punto, tutti gli agenti hanno ricevuto il set almeno una volta dopo tutti gli altri agenti scambiati i loro canoni, rendendo impossibile riconoscere e quindi mappare i non perceti agli altri agenti.

Quando l'ultimo agente riceve il set la seconda volta, lo condivide con tutti e tutti gli agenti confermano agli altri che il loro nonce è contenuto nel set. Gli agenti assegnano quindi un numero a ciascun nonce nel set basato su un seme casuale concordato, dandoci l'assegnazione unica richiesta.

Per consentire la verifica della proprietà, invece dei non perces, gli agenti hanno messo il valore di hash del loro nonceo sul set, rivelando il nonce effettivo solo quando è richiesta la verifica.

---

.

Il problema con questa soluzione è che se gli avversari sono autorizzati a collaborare, ogni volta che un avversario riceve il set, possono confrontare le loro versioni, identificare le modifiche e potenzialmente derivare da non appartenere ad altri agenti, consentendo loro di sapere quale numero ha ottenuto il numero assegnato a loro.

Tutte le idee sono apprezzate!

Answer 1

Questo problema fa parte di un insieme di problemi noti come poker mentale . c'è un articolo eccellente e piccolo di Shamir , Rivest e Adleman che descrivono un modo pratico su come implementare tale algoritmo.

L'abstract è oro:

.

Due giocatori potenzialmente disonesti giocano un gioco equo del poker senza usare nessuna carta (ad esempio un telefono)?

Questo documento fornisce le seguenti risposte:

.
1. no. (Provata matematica rigorosa fornita.)
2. Sì. (Protocollo corretto e completo dato.)

Fondamentalmente, da un punto di vista teorico informativo, giocare a tale gioco è impossibile senza una terza parte fidata, ma è possibile progettare un protocollo utilizzando le funzioni crittografiche difficili da invertire.

<

---

.

L'algoritmo funzionerà come segue:

Supponiamo di avere $ N $ non perces (numeri da $ 1 $ a $ N $ ). Ogni partecipante nel protocollo ha accesso a funzioni segrete $ E_i $ e $ d_i $ che vengono utilizzati per crittografare e decifrare i dati. Queste funzioni dovrebbero soddisfare poche proprietà, che analizzeremo più tardi.

Il primo partecipante viene assegnato l'intero set di canoni. Critta ogni nonce con la sua funzione segreta $ E_1 $ , mescolarli in modo casuale e passa i dati risultanti al secondo partecipante.

Secondo partecipante farà lo stesso, ma in questo caso non ha non percesimi, ma una permuta casuale dei nonici crittografati. Incritterà anche ciascun elemento con la sua funzione segreta $ E_2 $ e mescolare nuovamente i dati.

Allora terzo partecipante, e così via, fino a quando tutti i partecipanti hanno mescolato e crittografato i dati con la sua funzione segreta.

Complessivamente il processo di configurazione è:

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

.

Dopo questa configurazione, ciascun elemento di data sono i nonnici crittografati con tutte le funzioni segrete $ E_i $ in un ordine casuale sconosciuto a qualsiasi partecipante.

Si noti che a questo punto è impossibile per ogni partecipante dedurre ogni nonce senza l'aiuto di altri partecipanti. Ed è sufficiente che uno dei partecipanti di mischiare i dati completamente casuali per rimuovere qualsiasi possibile pregiudizio nell'ordine risultante, indipendentemente se alcuni partecipanti dannosi tentano di bias l'ordine.

Partecipante $ i $ -th è assegnato il nonce in posizione $ i $ . Per recuperare tale nonce, partecipante $ i $ chiede a ogni altro partecipante $ j \ neq I $ per decrittografare il Valore con la sua funzione segreta $ d_j $ a turno. Al partecipante alla fine $ i $ avrà il suo nonce solo crittografato con la propria funzione segreta $ e_i $ così Può recuperarlo usando $ d_i $ .

Recupero nonce $ 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)

.

Alla fine di questa procedura ogni partecipante conosce il proprio nonce, ma nessun altro partecipante sappia nulla al riguardo.

Dopo aver utilizzato questi valori per il tuo problema corrente, un giocatore può rivendicare che sono davvero in controllo di tale nonce, pubblicando i segreti funzioni $ e_i $ e $ D_I $ , quindi tutti possono calcolare localmente tutti i valori o decrittografia del valore data[i] dopo il primo passo ma prima del secondo passaggio, pubblicazione e quindi utilizzare questo valore come input in il secondo passo per decrittografarlo completamente.

le funzioni $ E_i $ e $ d_i $ dovrebbe avere le seguenti proprietà:

.
1. $ e_i (x) $ è la versione crittografata di un messaggio $ x $ sotto il tasto < Span Class="Math-Container"> $ i $ ,
2. $ d_i (e_i (x))= x $ per tutti i messaggi $ x $ e tasti $ i $ ,
3. $ e_i (e_j (x))= E_J (E_i (x)) $ per tutti i messaggi $ x $ e tasti $ i $ e $ j $ ,
4. Dato $ x $ e $ E_i (x) $ è computazionale impossibile per un criptanaleyst Deriva $ i $ , per tutti $ x $ e $ $ , <

/ Li >.

Dato qualsiasi messaggio $ x $ e $ y $ , è impossibile trovare tasti computazionalmente impossibili Class Class="Math-Container"> $ i $ e $ j $ tale che $ e_i (x )= E_J (Y) $ .

Come indicato nel documento, la maggior parte di queste ipotesi è in qualche modo comune eccetto per la proprietà 3), che indica le funzioni di crittografia devono commutare.

Propongono uno schema di crittografia semplice che soddisfi queste proprietà. Diciamo che tutti i partecipanti concordano su un grande numero di primo piano $ P $ (va bene se risolto nel protocollo). E ogni partecipante sceglie segretamente un numero casuale $ k_i $ tale che $ GCD (K_i, P - 1)= 1 $ < / span>. Diciamo $ Q_i $ è tale valore che $ k_i \ clot q_i \ equiv 1 \ mod (P -1) $ < / span>. Quindi partecipante $ i $ può usare le funzioni segrete:

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

Alcuni avvertimenti su questo algoritmo: i partecipanti non possono imbrogliare in modo tale che la collusione che li avvantaggi nell'apprendimento del nonce sull'altro peer (a meno che, a meno che, naturalmente) / SPAN> I partecipanti colludono e rimangono solo un nonce). Tuttavia, i partecipanti dannosi possono attaccare il protocollo senza partecipare, in modo efficace, in modo efficace il processo di negoziazione, poiché sono necessarie molte azioni da ciascun partecipanti, mentre stanno affrontando i nonnici. Possono anche produrre gibberish, ma ciò può essere mitigato che estende il protocollo per rilevare quale partecipante fosse il colpevole e penalizzando tale partecipante ad un livello più alto.

---

.

Ho implementato questo algoritmo per un gioco di poker in vicino a Blockchain . Puoi vedere il codice in Rust qui . Avviso Non esiste una terza parte fidata in un Blockchain, ma c'è un ambiente di calcolo affidabile che tutti i partecipanti possono utilizzare come meccanismo per eseguire questo protocollo.