L'entropia misura l'incertezza media di una variabile casuale X o se vogliamo di un processo. Lavorando in base 2 è il minimo numero di bit necessari in media per rappresentare il valore x della variabile casuale X.
H(X) = - Σ p(x) · log(p(x)) x ∈ X
Ad esempio se la variabile casuale X è il lancio della monetina "fair" la distribuzione di probabilità è {P(H)=½, P(T)=½} => H(X) = - (½ · (-1) + ½ · (-1)) = -(-½ - ½) = 1
Cosa si intende per segretezza perfetta di un cifrario? Quali sono le condizioni necessarie e/o sufficienti per ottenerla?
Uno schema di cifratura (Gen, Enc, Dec) su uno spazio di messaggi 𝓜 si definisce perfettamente segreto se ∀ distribuzione di probabilità su 𝓜 , ∀ m ∈ 𝓜 , ∀ testo cifrato c ∈ 𝘊 t.c. P[C = c] > 0):
P[M = m|C = c] = P[M = m] cioè c non ci fornisce informazioni su m
P[Enc(m) = c] = P[Enc(m') = c] ∀ m, m' ∈ 𝓜 e c ∈ 𝘊
k k