Disegno "sicuro" dei lotti [chiuso]

Naviga le tue risposte
1

Voglio scegliere a caso un gioco nei 50 giochi che ho, per giocare con uno dei miei amici. Ma questo amico non si fida di me, e nemmeno io: ogni volta che uno di noi prende una partita, l'altro si lamenta che la scelta non è stata davvero casuale.

Una prima soluzione potrebbe essere quella di mettere tutti i nomi in un cappello e dopo raccogliere un nome; ma siamo entrambi paranoici: il cappello potrebbe contenere solo un nome ripetuto 50 volte, quindi dobbiamo verificare che tutti i nomi siano presenti solo una volta per garantire una scelta casuale. Questo è troppo lungo.

Seconda soluzione: entrambi selezioniamo a caso un numero intero in [1,50], lo scriviamo su un foglio e sommiamo il risultato modulo 50. Questa è una buona soluzione quando ci troviamo di fronte l'un l'altro.

Ma cosa succede se vogliamo scegliere un gioco online, io a Parigi e il mio amico che gioca a New York? Ho provato a emulare il protocollo di cui sopra: ogni giocatore sceglie casualmente un numero in un intervallo enorme come [1,1e30] e in una prima volta invia un hash del suo numero (simulando il fatto di nascondere il numero su un pezzo di carta) . Quando ogni giocatore ha ricevuto l'hash dell'altro, i due giocatori pubblicano i loro numeri e aggiungono loro il modulo 50.

Questo protocollo è corretto? C'è un protocollo migliore (forse più veloce) per questo scopo?

    
posta Sebastien 05.01.2015 - 22:13
fonte

2 risposte

1

Quello che vuoi è una variante di uno schema per lanciare le monete. Il modo standard per farlo è, come hai identificato, che entrambe le persone abbiano un valore e quindi uniscono quei valori in modo tale che nessuna delle due parti abbia il controllo sul risultato da solo. Hai deciso di utilizzare l'aggiunta modulare; questo è davvero un modo standard. Hai anche identificato il problema con questo, ovvero chi ha deciso per secondo di poter controllare il risultato (poiché sa che cosa ha scelto la prima persona), quindi hai bisogno che le persone si impegnino a rispettare i loro valori prima che conoscano il valore dell'altra persona. p>

Questo tipo di cose è chiamato schema di impegno . In questi sistemi, Alice ha un certo valore a cui vuole impegnarsi. Nello specifico, dovrebbe inviare qualcosa a Bob che codifica il suo valore, ma da cui Bob non può recuperare il valore. Alice può quindi inviare a Bob un'informazione quando è il momento di rivelare il suo segreto; l'idea è che lei possa solo rivelare il valore a cui si era inizialmente impegnata.

Per essere più concreto, supponiamo che Alice voglia impegnarsi un po '. Vuole produrre un "blob" da inviare a Bob; questo blob codifica 1 o 0. Quindi, quando è il momento di rivelare il bit, Alice e Bob possono aprire questo blob, utilizzando alcune informazioni aggiuntive fornite da Alice. Le due proprietà chiave del BLOB sono che Bob non può scoprire quale bit codifica e possono solo aprire il BLOB su uno dei due bit (Alice non può produrre una codifica BLOB 1 e quindi imbrogliare aprendolo a 0 ).

Con l'impegno bit, puoi usare un hash resistente alle collisioni, calcolare il BLOB come H(s||b) con% casuale lungos (hai hash s concatenato con b ) e rivela s per aprirlo (beh, s e b , ma rivelando s è facile ottenere b ). Questo equivale ad avere un numero lungo e ad assumere il modulo 2 per ottenere il bit commesso. Il tuo schema ha un effetto simile e dovrebbe funzionare fornito non puoi trovare collisioni.

Sfortunatamente, solo facendo ciò significa che qualcuno che trova una collisione può usarlo ripetutamente. È meglio che Bob fornisca un po 'di bitstring b casuale ad Alice e che Alice calcoli un secondo (segreto) bitstring% a , abbia Alice codifichi un numero da 0 a 50 come 6 bit n (lunghezza fissa, quindi non può pretendere che la linea di demarcazione sia diversa da quella che è in realtà) e calcola il BLOB come H(b||a||n) . Ciò significa che anche se Alice trova una collisione in H , non aiuta; ha bisogno di una coppia in collisione che inizi con b .

    
risposta data 05.01.2015 - 22:53
fonte
0

Is there a better (maybe faster) protocol for this purpose?

Dai un'occhiata a "Schemi di impegno" .

Ecco una semplice: pensa a un segreto casuale e al tuo impegno. Esegui entrambi attraverso HMAC-SHA256. Usando la parte casuale come chiave (o sale se vuoi.)

Pubblica il risultato. Quando entrambi i partner hanno ricevuto l'hash, quindi pubblica le chiavi / sale. Ora ogni partner può calcolare l'hash per se stesso e verificare che l'operazione sia corretta.

Ora non può esserci mercanteggiamento dopo il fatto.

    
risposta data 05.01.2015 - 22:56
fonte

Leggi altre domande sui tag

Metodo di memorizzazione delle password facile da usare, semplice e sicuro? [chiuso] Ci sono delle risorse per il forensystem del file system in memoria?