Il protocollo di dividi e scegli o, dall'inglese, divide and choose è un algoritmo utilizzato per assolvere alcune problematiche di divisione equa di beni o risorse. In italiano è spesso riferito col detto "chi taglia non sceglie".
Esempio
Nella sua versione più semplice si possono immaginare due persone che devono dividere un bene tra di loro e necessitano di farlo in maniera equa.
Per un esempio pratico possiamo immaginare Alice e Bob che devono dividere tra loro un panino.
L'algoritmo è costituito da tre semplici passi:
- Alice taglia a metà il panino.
- Bob sceglie la sua metà.
- Alice prende la metà rimanente.
Considerazioni
Almeno in via teorica, con questo approccio si risolve il problema della divisione in parti eque.
Ricollegandoci all'esempio, questo avviene perché:
- Alice ha tutto l'interesse nel dividere le risorse nella maniera più equa possibile perché sa che poi non potrà scegliere tra le parti che ha diviso.
- Bob ha tutto l'interesse nello scegliere la parte migliore lasciando ad Alice l'altra parte (che dualmente sarà quella peggiore).
La concomitanza di queste due situazioni portano Alice a voler suddividere il bene nella maniera più equa possibile, in modo che per Bob sia indifferente scegliere una parte piuttosto che un'altra e in modo in cui lei possa avere la metà che le spetta.
Varie
In crittografia è utilizzata una tecnica derivata e molto simile al dividi e scegli. Teorizzata per la prima volta nel 1978 da Michael O. Rabin[1] è chiamata taglia e scegli. L'approccio taglia e scegli e quindi, indirettamente, anche l'approccio dividi e scegli, sono alla base dei protocolli interattivi e delle dimostrazioni a conoscenza zero[2].
Note
- ^ M. O. Rabin, "Digital Signatures", Foundations of secure communication, New York Academic Press, 1978. Pag.155-168
- ^ "Applied Cryptography, Bruce Schneier, Wiley, 2nd edition". Pag.103
Voci correlate