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 modifica

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:

  1. Alice taglia a metà il panino.
  2. Bob sceglie la sua metà.
  3. Alice prende la metà rimanente.

Considerazioni modifica

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 modifica

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 modifica

  1. ^ M. O. Rabin, "Digital Signatures", Foundations of secure communication, New York Academic Press, 1978. Pag.155-168
  2. ^ "Applied Cryptography, Bruce Schneier, Wiley, 2nd edition". Pag.103

Voci correlate modifica

  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica