Sicurezza semantica
# Sicurezza semantica

In crittografia si definisce sicurezza semantica un criterio di valutazione della sicurezza in un cifrario a chiave asimmetrica. Affinché un sistema crittografico si possa definire semanticamente sicuro un attaccante che disponga di una potenza di calcolo limitata deve essere incapace di derivare delle informazioni significative sul messaggio (il testo in chiaro) dato il solo testo cifrato e la corrispondente chiave pubblica.

La sicurezza semantica tiene conto solo del caso di un attaccante passivo, vale a dire che osserva soltanto la generazione di testi cifrati. A differenza di altre definizioni di sicurezza, quella semantica non considera il caso di un attaccante in grado di richiedere la decifratura di testi cifrati scelti (attacco con testo cifrato scelto): molti schemi di cifratura semanticamente sicuri sono spesso insicuri contro scenari di questo tipo. Come conseguenza di ciò, la sicurezza semantica è oggi considerata una condizione insufficiente per stabilire il livello di sicurezza di uno schema di cifratura di uso generale.

La nozione di sicurezza semantica fu esposta per la prima volta da Shafi Goldwasser e Silvio Micali in una loro pubblicazione del 1982. Tuttavia, la definizione che essi inizialmente proposero non offriva nessun metodo semplice per dimostrare la sicurezza dei sistemi crittografici reali. Gli autori in seguito dimostrarono che la sicurezza semantica è equivalente alla proprietà dell'indistinguibilità di un testo cifrato. Questa equivalenza permise di verificare la sicurezza dei sistemi crittografici reali, tanto che la definizione di indistinguibilità è ora usata molto più frequentemente della prima definizione di sicurezza semantica.

L'indistinguibilità sotto un attacco con testo in chiaro scelto è definita comunemente dal seguente gioco:

* Ad un attaccante con un tempo di calcolo limitato è data una chiave pubblica, che può usare per generare qualsiasi numero di testi cifrati;
* l'avversario genera 2 messaggi di lunghezza identica $m_{0}$ e $m_{1}$ e li invia ad un oracolo insieme alla chiave pubblica;
* l'oracolo seleziona 1 dei 2 messaggi lanciando una moneta, lo cifra con la chiave pubblica, e restituisce il testo cifrato $c$ risultante.

Il sistema crittografico in esame è considerato indistinguibilmente sicuro sotto un attacco con testo in chiaro scelto (e quindi semanticamente sicuro sotto il medesimo attacco) se l'avversario non può determinare quale dei 2 messaggi è stato scelto e cifrato dall'oracolo con una probabilità significativamente più grande di $1/2$ (il tasso di successo di una scelta casuale). Le varianti di questa definizione definiscono l'indistinguibilità sotto un attacco con testo cifrato scelto ed un attacco adattivo con testo cifrata scelto.

A causa del fatto che l'attaccante possiede la chiave pubblica di cifratura, uno schema di cifratura semanticamente sicuro deve essere per definizione probabilistico, possedere cioè una componente di casualità: se questo non accade, l'attaccante può semplicemente calcolare la cifratura deterministica di $m_{0}$ e $m_{1}$ e comparare i risultati con il testo cifrato $c$ restituito dall'oracolo per indovinare la sua scelta con successo.

Algoritmi di cifratura semanticamente sicuri sono il Goldwasser-Micali, l'ElGamal ed il Paillier: questi schemi sono considerati provatamente sicuri dato che la loro sicurezza semantica può essere ridotta alla risoluzione di alcuni problemi matematici difficilmente risolvibili.

