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^[1].

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.