# Sicurezza dimostrabile

In crittografia un sistema crittografico presenta una sicurezza dimostrabile se i suoi requisiti di sicurezza possono essere fissati formalmente in un modello con precisi assunti, dove colui che cerca di violare il sistema (comunemente denominato "avversario") ha accesso allo stesso ed ha abbastanza risorse computazionali per cercare di forzarlo. La dimostrazione di sicurezza (chiamata "riduzione") è che questi requisiti di sicurezza siano soddisfatti stabilito che le ipotesi riguardanti l'accesso dell'avversario al sistema siano soddisfatte e che siano chiaramente indicate quelle inerenti alla difficoltà computazionale di alcuni calcoli. Esempi di questi requisiti sono stati pubblicati nel 1989 da Shafi Goldwasser e Silvio Micali.
La sicurezza dimostrabile si basa principalmente su due nozioni di sicurezza:
* la sicurezza semantica;
* la sicurezza computazionale.
La prima nozione di sicurezza, antecedente a quella di sicurezza dimostrabile, è quella di sicurezza perfetta ed è stata introdotta da Claude Shannon nel suo celebre articolo Communication theory of secrecy systems pubblicato nel 1949. Come egli stesso ha dimostrato, esiste solo un sistema che è stato provato sia incondizionatamente sicuro, il cifrario di Vernam, dove la chiave crittografica è lunga quanto il testo da cifrare: senza di essa è provatamente impossibile risalire ad alcuna informazione inerente al messaggio in chiaro.
La nozione di sicurezza dimostrabile, invece, si basa sul fatto che, se non si dispone che di una limitata capacità computazionale, sarà possibile risalire al messaggio in chiaro solo con una probabilità detta trascurabile, ovvero minima.

## Distinzioni tra crittografia simmetrica ed asimmetrica

La sicurezza dimostrabile è differente nel caso si parli di crittografia simmetrica o asimmetrica.
Nella crittografia simmetrica può essere dimostrata solo la sicurezza semantica: si può, cioè, dimostrare la resistenza di un sistema crittografico alle sole tecniche di crittanalisi note, come ad esempio la crittanalisi differenziale o quella lineare. Non è però possibile provarne la resistenza a tipologie di attacco ancora sconosciute.
Nella crittografia asimmetrica, invece, il problema si pone in maniera diversa ed è in quest'ultima che si ritrova maggiormente la nozione di sicurezza dimostrabile. I sistemi asimmetrici si basano su dei problemi computazionali riguardanti la teoria dei numeri o l'algebra discreta: ad esempio, un algoritmo come l'ElGamal si basa sul problema dei logaritmi discreti. Lo schema generale della sicurezza dimostrabile è allora quello di provare che la violazione del sistema si riduce dalla risoluzione di un problema considerato difficile ad uno computazionalmente più semplice.

## Critiche ed insuccessi

La terminologia di "sicurezza dimostrabile" è stata però criticata per diverse ragioni da diversi autori: parte del problema risiede nel fatto che può essere fuorviante per i non addetti ai lavori, dato che la sicurezza non può essere provata. Oded Goldreich, ad esempio, pensa che la rigorosa metodologia di analisi della sicurezza dimostrabile sia l'unica forma compatibile con la scienza.
Ci sono stati diversi tentativi di definire la sicurezza, ma essi si sono dimostrati poi incapaci di coprire tutte le sfaccettature del problema: molti degli insuccessi sono stati indicati come attacchi del canale laterale dato che essi utilizzano informazioni che ricadono al di fuori della definizione del canale che deve essere protetto.