Segretezza Perfetta

Claude Shannon

(musica)

Immaginate: Bob va in una stanza vuota,
ha lucchetti, carte ed una scatola vuota

Bob sceglie una carta dal mazzo
e la nasconde.

Le regole sono semplici: Bob non può
portare nulla con sé uscendo dalla stanza

e al più può mettere una carta
nella scatola

Eva non ha mai visto i lucchetti

Bob vince se Eva non riesce ad
indovinare la carta da lui scelta

Quale strategia è ottimale?

Bob seleziona, diciamo, il 6 di quadri
e lo mette nella scatola

Poi osserva i diversi tipi di lucchetto

Forse deve infilare la chiave del
lucchetto nella scatola

O forse è meglio scegliere un lucchetto
a combinazione

Combinazione è scritta sul retro, se la
graffia via forse è la strategia migliore

D'un colpo realizza che le carte restanti
sul tavolo riveleranno la sua scelta

perché una mancherà dal mazzo

I lucchetti sono un diversivo

Non deve estrarre la carta,
deve invece lasciarla nel mazzo

Non ricorda la posizione della carta e
mischia il mazzo in modo casuale

Mescolare è il miglior lucchetto. Non fa
trapelare informazione sulla vostra scelta

Ora la carta scelta può essere
una qualsiasi

Ora può lasciare le carte in vista

Bob vince perché Eva può solo tirare a
sorte dato che Bob non ha lasciato tracce

Pure se Eva avesse una potenza di calcolo
illimitata, può solo tirare a sorte

Questa è la definizione di
SEGRETEZZA PERFETTA

Il 1 Settembre 1945 C. Shannon pubblicò
un articolo classificato al riguardo.

Shannon dimostrò che il codice
di Vernam è perfettamente segreto

Shannon ragiona nei seguenti termini:

Immaginiamo che Alice scriva un messaggio
lungo 20 caratteri a Bob

Questa situazione è come scegliere
una pagina dallo spazio dei messaggi

che può pensarsi è come l'insieme di tutti
i possibili messaggi lunghi 20 caratteri

Qualunque cosa a cui possiate pensare, se
è lunga 20 caratteri, è pagina della pila

Alice utilizza una chiave condivisa,
che è una lista di 20 traslazioni casuali

Lo spazio delle chiavi è l'insieme
di ogni possibile risultato

Scegliere una chiave è equivalente a
scegliere una pagina nella pila

Traslando la sequenza del messaggio
originario genera il messaggio cifrato

Lo spazio dei testi cifrati rappresenta
tutti i risultati possibili della codifica

Applicando la chiave, ella sceglie una
pagina specifica in questo insieme

Lo spazio dei messaggi ha la stessa
dimensione dello spazio delle chiavi

Questa proprietà definisce la
segretezza perfetta

chi ha solo il messaggio cifrato sa solo
che ogni messaggio è parimenti probabile

Questo vuol dire che niente può aiutarci
visto che dobbiamo tirare a caso

Problema col codice di Vernam è doversi
scambiare le chiavi in anticipo

Per risolvere questo problema è necessario
introdurre il concetto di pseudo-casualità