Programmi con schema di accesso alla memoria indipendente dai dati

In questa tesi vengono raccolti alcuni importanti risultati ottenuti nello studio di macchine oblivious. Ne descriveremo la realizzazione per una MT con memorie a nastri monodimensionali. Introdurremo una procedura per l'emulazione on-line di MT con memorie a nastri k-dimensionali per mezzo di MT con memorie a nastri monodimensionali con l'evidente intento di generalizzare l'implementazione del caso monodimensionale ad una qualunque macchina di Turing con storage a nastro k-dimensionale. Verrà esposto il concetto di ORAM e saranno descritti degli algoritmi per due tipologie di compilatori ORAM, secondo il modello path-ORAM e gerarchico. Analizzando le prestazioni dell'algoritmo ispirato al modello path-ORAM emergono forti limitazioni, particolarmente evidenti nel overhead di memoria. Il modello gerarchico offre migliori performance in esecuzione e in occupazione di memoria a discapito di un notevole aumento nella complessità dell'algoritmo.