Learning with errors vs learning with rounding : a performance evaluation for homomorphic encryption

In recent years, interest in performing operations over encrypted data has been growing more and more in cryptographic systems. This is due to the fact that looking at cryptographic systems we can see a weakness in the management of sensitive information. For example, by keeping our data saved in the cloud, encrypted through the secret keys, we consider them safe but when we need to carry out operations, from editing a text document to searching a database, it is necessary to decrypt the data and make them vulnerable. Homomorphic Encryption (HE) allows us to do these operations without decrypting the data, as it allows to perform an arbitrary computation over encrypted data by manipulating only ciphertexts, thus retaining the confidentiality of the encrypted data even when being employed in a given computation. Just like all cryptographic systems, homomorphic encryption also has limitations that hinder its adoption on a large scale. Currently, the main limitation is definitely the high performance overhead, which makes homomorphic calculations so slow that they are not practical for many of the applications where adoption of homomorphic encryption may be extremely useful. In the literature it is proposed to use schemes whose security is based on Learning With Rounding (LWR) problem instead of Learning With Errors (LWE) problem, in order to remove the Gaussian sampling employed in LWE based schemes, which is expected to introduce advantages in terms of performance. However, this claim has not been verified as neither implementations nor experimental campaigns have been provided. With this thesis work, we provide the first detailed implementations of the GSW scheme (created by Gentry, Sahai and Waters), an existent HE scheme based on LWE, and the scheme based on LWR derived from GSW, with the intent of comparing the performance of such two schemes. By carrying out experimental measurements on the schemes, it really turns out that the elimination of the Gaussian noise distribution leads to smaller ciphertexts and therefore to an improvement in performance, both from the point of view of the execution time and from the point of view of the memory occupation. These results show that the performance of HE schemes may be improved by building them from LWR rather than LWE.

Negli ultimi anni l’interesse nell’eseguire operazioni su dati cifrati sta crescendo sempre di più nei sistemi crittografici. Questo è dato dal fatto che guardando ai sistemi crittografici possiamo notare una debolezza nella gestione delle informazioni sensibili. Per esempio, tenendo i nostri dati salvati in cloud, crittograficamente codificati attraverso chiavi segrete, li riteniamo al sicuro ma nel momento in cui abbiamo il bisogno di effettuare delle operazioni, dalla modifica di un documento di testo alla ricerca su un database, occorre decifrare i dati e renderli vulnerabili. La crittografia omomorfa ci permette di fare queste operazioni senza doverli decifrare, infatti consente di eseguire un calcolo arbitrario su dati cifrati manipolando solo i testi cifrati, mantenendo così la riservatezza dei dati cifrati anche quando viene impiegato in un determinato calcolo. Proprio come tutti i sistemi crittografici, anche la crittografia omomorfica presenta dei limiti che ne ostacolano l’adozione su larga scala. Attualmente, la principale limitazione è sicuramente l’alto overhead generato, che rende i calcoli omomorfi così lenti da non risultare pratici per molte delle applicazioni dove l’adozione della crittografia omomorfa può essere estremamente utile. In letteratura viene proposto di usare degli schemi la cui sicurezza è basata sul problema Learning With Rounding (LWR) invece che sul problema Learning With Errors (LWE), in modo da rimuovere il campionamento Gaussiano impiegato negli schemi basati su LWE, supponendo che introduca vantaggi in termini di prestazioni. Questa affermazione però non è stata verificata poiché non sono state fornite né implementazioni né condotte campagne sperimentali. Con questo lavoro di tesi, si forniscono le prime implementazioni dettagliate dello schema GSW (ideato da Gentry, Sahai e Waters), schema già esistente basato su LWE, e dello schema basato su LWR derivato da GSW, con l’intento di comparare le prestazioni di questi due schemi. Effettuando misure sperimentali sugli schemi risulta davvero che l’eliminazione del rumore Gaussiano porti a un più piccolo testo cifrato e quindi ad un miglioramento prestazionale, sia dal punto di vista del tempo di esecuzione e sia dal punto di vista della memoria occupata. Questi risultati mostrano che le prestazioni degli schemi di crittografia omomorfa possono essere migliorate costruendo gli schemi a partire dal problema LWR piuttosto che dal problema LWE.