Oracolo random
In crittografia, un oracolo random è una macchina a oracolo, una scatola nera teorica che risponde ad ogni domanda con una risposta veramente random scelta uniformemente all'interno del suo dominio di output. Per ogni domanda specifica la risposta, una volta assegnata dall'oracolo, è sempre uguale. In altri termini, un oracolo random è una funzione matematica che associa ogni possibile domanda ad una risposta random scelta all'interno del suo dominio di output.
Gli oracoli random sono delle astrazioni matematiche usate nelle dimostrazioni crittografiche; sono usati tipicamente quando non ci sono implementazioni note delle funzioni che forniscono le proprietà matematiche richieste dalla dimostrazione. La sicurezza di un sistema provata usando questa dimostrazione viene detta sicurezza all'interno del modello a oracolo random, contrapposta alla sicurezza all'interno del modello standard. In pratica, gli oracoli random sono usati per modellare funzioni crittografiche di hash all'interno di schemi dove sono necessarie delle forti assunzioni di randomicità sull'output delle funzioni di hash.
Una dimostrazione di questo tipo, in genere, argomenta la sicurezza di un protocollo adducendo la necessità, per l'attaccante che vuole violare il protocollo, di risolvere un problema computazionalmente complesso o di indurre l'oracolo ad un comportamento impossibile. Non tutti gli usi delle funzioni crittografiche di hash richiedono oracoli random: alcuni schemi (p.e.: Sistema Cramer-Shoup) richiedono solo qualche proprietà definita all'interno del modello standard, come resistenza alla collisione, resistenza alla preimmagine, resistenza alla seconda preimmagine, ecc.
Gli oracoli random sono stati considerati a lungo nella teoria della complessità computazionale
- Bennett & Gill[1]
- Fiat e Shamir (1986)[2]: utilizzo degli oracoli nella rimozione di interazione dai protocolli per l'identificazione
- Impagliazzo e Rudich (1989)[3]: limitazione intrinseca nell'applicazione ai meccanismi di scambio di chiavi segrete
- Bellare e Rogaway (1993)[4]: utilizzo nelle costruzioni crittografiche sotto forma di produzione di una stringa di bit di lunghezza infinita, da cui ricavare una stringa di lunghezza qualsiasi
L'utilizzo di un oracolo all'interno di una dimostrazione prevede che sia reso disponibile a tutti i partecipanti, avversari inclusi. Oracoli multipli possono essere simulati a partire da un singolo oracolo, utilizzando dei prefissi alle richieste (p.e.: le richieste di formato "1|x" o "0|x" possono essere considerate come richieste "x" rivolte a due oracoli distinti; le richieste di formato "00|x", "01|x", "10|x" e "11|x" possono essere considerate come richieste "x" rivolte a quattro oracoli distinti).
Nessuna funzione reale può implementare un vero oracolo random. Esistono, infatti, degli schemi di autenticazione e crittografia sicuri all'interno del modello a oracolo che diventano banalmente insicuri una volta sostituito l'oracolo random con una funzione reale.[5] Una dimostrazione di sicurezza all'interno del modello a oracolo rafforza comunque la tesi che un attacco ad un protocollo, se impossibilitato a violare le altre assunzioni (come la complessità computazionale), deve concentrarsi nello scoprire proprietà sconosciute e indesiderabili della funzione di hash adottata. La sicurezza di molti schemi è stata dimostrata all'interno del modello a oracolo random: per esempio l'OAEP e il PSS.
Note[modifica | modifica wikitesto]
- ^ Charles H. Bennett, Gill, J., Relative to a Random Oracle A, P^A != NP^A != co-NP^A with Probability 1, in SIAM Journal on Computing, vol. 10, n. 1, 1981, pp. 96–113, ISSN 1095-7111.
- ^ Amos Fiat and Adi Shamir: How to Prove Yourself: Practical Solutions to Identification and Signature Problems. CRYPTO 1986: pp. 186-194
- ^ Russell Impagliazzo and Steven Rudich: Limits on the Provable Consequences of One-Way Permutations STOC 1989: pp. 44-61
- ^ Mihir Bellare and Phillip Rogaway, Random Oracles are Practical: A Paradigm for Designing Efficient Protocols, ACM Conference on Computer and Communications Security 1993, pp. 62-73 (PS and PDF) Archiviato il 4 maggio 2008 in Internet Archive..
- ^ Ran Canetti, Oded Goldreich and Shai Halevi, The Random Oracle Methodology Revisited, STOC 1998, pp. 209-218 (PS and PDF).
Voci correlate[modifica | modifica wikitesto]
Collegamenti esterni[modifica | modifica wikitesto]
- The Random Oracle Model — a cura di Helger Lipmaa
