Tecnica che usa le funzioni hash per autenticare efficientemente gruppi di file e offre anche un metodo alternativo alla trasformazione Merkle-Damgard per estendere il dominio di una funzione hash collision-resistant
Un utente vuole memorizzare un file di grande dimensione sul cloud e dopo un po’ di tempo ha la necessità di scaricarlo, ma non è sicuro che il file è stato mantenuto integro
L’idea è mantenere sulla macchina il digest del file $H(File)$, risparmiando memoria
Quando si scarica un file viene calcolato il suo hash $H(File')$ per verificare l’uguaglianza e quindi l’integrità del file con il file presente sul computer
In presenza di file multipli non è molto efficiente, perché dovrebbe memorizzare $H(x_1),..,H(x_t)$
L’idea è memorizzare i digest seguendo la struttura ad albero
Abbiamo inizialmente $t$ foglie per tutti i file che verranno caricati sul cloud, e i nodi vengono costruiti con la concatenazione dei digest dei file
Come risultato finale avremo un valore hash come radice
In questo modo basta che l’utente calcoli e memorizzi localmente il valore hash presente all’interno della radice dell’albero $h_1.._8$ per poi fare l’upload dei file $x_1,..,x_8$ nel cloud
Successivamente, per verificare l’integrità di $x_i$, riceve dal cloud $x_i$ e tutti i valori hash associati ai nodi adiacenti al path da $x_i$ alla radice
Sia $(Gen_H, H)$ collision-resistant, allora $(Gen_H,MT_t)$ è collision-resistant per $t$ fissato
Lo schema richiede: