Segretezza perfetta vs segretezza computazionale

La nozione di segretezza computazionale nasce dalla necessità di rilassare le assunzioni utilizzate nella segretezza perfetta, in particolare:

• l'ipotesi di avversari con potere illimitato, che nella segretezza perfetta impedisce la costruzione di schemi di cifratura praticabili
• l'assunzione di probabilità di errore zero, che risulta eccessivamente restrittiva in scenari pratici

Si considera un modello in cui:

• gli avversari sono PPT
• la probabilità di successo di un attacco è trascurabile

Necessità del rilassamento

In uno schema di cifratura con $|K|<|M|$

• Adv può decifrare $c$ usando tutte le chiavi $k \in K$ ottenendo una lista $L$ di messaggi $L \nsupseteq M$ → rivela informazioni sul messaggio $m$
• similmente, se Adv possedesse coppie $(m_1,c_1),..,(m_l,c_l)$ potrebbe tentare di decifrare le coppie fino a trovare $k$ ed usarla successivamente per decifrare un nuovo $c$

Ricerche esaustive come le precedenti permettono ad Adv di avere successo con probabilità $1$ in tempo lineare in $|K|$ → dobbiamo limitare il tempo di esecuzione di Adv

Adv può anche scegliere a caso una chiave e usare le coppie per verificare la correttezza → esegue in tempo costante e ha successo con probabilità $\frac{1}{|K|}$ → dobbiamo ammettere piccole probabilità di successo

Computazionalmente sicuro

<aside> 💡

Uno schema è sicuro se qualsiasi Adv PPT ha successo nella rottura dello schema con al più probabilità trascurabile

</aside>

Algoritmi efficienti

<aside> 💡

$A$ esegue in tempo polinomiale se $\exist$ $p(\cdot ): \forall$ $x \in \{0,1\}^*$ , $A(x)$ termina in al più $p(|x|)$ passi

</aside>

Probabilità di successo trascurabili

<aside> 💡

Una funzione $f:\N\to \R^+$ è trascurabile se $\forall$ polinomio positivo $p$ $\exist$ $n_0: \forall$ $n > n_0$ risulta $f(n) < \frac{1}{p(n)}$

</aside>