In che modo la crittografia omomorfica completa o parziale è vantaggiosa per il cloud?

È già possibile, tramite sistemi di voto end-to-end come Helios , archiviare pubblicamente i voti votati nella nuvola in modo criptato, quindi che il pubblico possa aggiungerli per confermare i totali e verificare anche che il proprio voto sia stato effettivamente incluso nel totale. Senza dare a qualcuno una "ricevuta" che può utilizzare per vendere il proprio voto. Sorprendente, ma vero. È fantastico per le elezioni private a basso rischio. Nota comunque che anche l'inventore di Helios, Ben Adida, dice "Un governo l'elezione è qualcosa che non si vuole fare su Internet ", citando sia il potenziale di virus informatici per corrompere il voto e la possibilità di intimidazione degli elettori.

Questo è possibile poiché è necessaria solo l'aggiunta, e quindi funzionano approcci omomorfi parziali. Mi aspetto che troveremo altri casi interessanti come questo, ma un vero calcolo generale richiederà ulteriori progressi in termini di efficienza.

Si noti che il "Pratico?" la carta di riferimento parla delle dimensioni dei testi cifrati in uno schema dell'ordine di 50 kB. Ciò significa che ogni numero (ad esempio in una serie di dati di un laboratorio medico) è rappresentato da un testo cifrato che è di 4 ordini di grandezza più grande ... Ciò rende il costo dell'archiviazione del cloud piuttosto poco pratico.

E D.W. scrive in un commento sopra:

In some cases, it may be worse than that: it may be that you have to construct a boolean circuit, and each bit may be represented by some ginormous ciphertext. No, it is not practical today. It is many orders of magnitude away from being economically viable. But it's so darn cool...

La mia opinione è che

• La crittografia omomorfica è un importante progresso nell'informatica teorica, che potrebbe avere enormi implicazioni per la sicurezza
• ... o potrebbe rimanere un bel giocattolo, utile solo per problemi molto ristretti come la trasparenza delle elezioni.

La crittografia omomorfica riguarda gli schemi di crittografia che consentono il calcolo con il valore crittografato senza decrittografarli. Ad esempio, dati E (a) e E (b) (la crittografia di a e b ), puoi calcolare E (a + b) senza conoscere a , b né la chiave di decrittazione.

Gli schemi di crittografia omomorfa sono molto utili negli schemi di voto, con la seguente struttura: gli elettori crittografano i loro voti, la proprietà omomorfica è usata per aggiungere tutti i voti e il risultato è decifrato (con decrittazione di gruppo da parte di un gruppo di autorità che hanno bisogno di riunire, in un modo molto pubblico, per eseguire una decrittazione). Esistono diversi schemi di crittografia omomorfica, alcuni dei quali sono noti da decenni (ad esempio, El Gamal). Sono efficienti e sicuri (sicuri quanto la crittografia asimmetrica può essere). Si noti che la crittografia omomorfica risolve la questione del conteggio anonimo, ma questa è solo una piccola parte di un corretto schema di voto (ad esempio l'elettore deve anche provare che ha crittografato uno 0 o un 1, non un 20 - altrimenti, potrebbe ottenere 20 voti ). La crittografia omomorfica può essere utilizzata anche nei sistemi di cassa digitali, anche qui per garantire l'anonimato o alcune altre proprietà.

Completamente crittografia omomorfica è un termine che è stato coniato quando sono stati trovati schemi di crittografia che hanno conservato due operazioni algebriche in una struttura ad anello: vale a dire E ( a) e E (b) , puoi calcolare E (a + b) e E (ab) . Si scopre che con queste due operazioni, puoi calcolare praticamente tutto. È qui che entra in scena la "nuvola": la nuvola è potente, ma non affidabile; quindi, puoi crittografare i tuoi dati, inviarli al cloud che esegue il calcolo che vuoi eseguire e quindi decrittografare il risultato.

Offloading computations to the cloud è, in questo momento, una pura fantasia. Gli schemi di crittografia completamente omomorfi più efficienti attualmente noti, basati su uno schema di Gentry (pubblicato nel 2009), sono ancora molto costosi, e la parte "calcolo arbitrario" implica la rappresentazione del calcolo come un circuito in cui ciascuno la porta logica viene emulata attraverso la propria crittografia omomorfica. Non stiamo parlando di un rallentamento 10x qui; piuttosto, stiamo parlando dell'intero cloud Amazon EC2 che non è in grado, in un giorno, di eseguire omomorfaticamente un calcolo che richiederebbe un secondo su un singolo iPhone. Quindi, mentre questo è molto interessante da un punto di vista teorico, ci vorrà un po 'di tempo prima che venga scoperto qualcosa nella pratica. Inoltre, il 2009 è abbastanza recente; tradizionalmente, aspettiamo almeno da 5 a 10 anni prima di dichiarare che uno schema di crittografia asimmetrico è "sicuro".

La crittografia omomorfica è una categoria di sistemi; alcune implementazioni potrebbero essere deboli e altre potrebbero essere forti, ma non ha senso parlare dell'intera categoria come "debole" o cryptanalyzable.

I crittosistemi parzialmente omomorfici (che prima venivano chiamati solo "omomorfi" prima che venissero scoperti cryptosystems completamente omomorfi) sono stati usati in cripto per un po ', incluso, come fa notare Neal, nel mio sistema di votazione, Helios. In questi sistemi, è possibile eseguire una sola operazione, aggiunta o moltiplicazione, sotto le copertine della crittografia. Ciò ti consente di fare cose interessanti, come il conteggio dei voti individuali e solo la decifrazione del conteggio.

Ora, quando dico "non usare Helios per le elezioni pubbliche", non è a causa di alcuna debolezza nella crittografia omomorfica. Questa è la parte più strong del sistema. Il problema con il voto online è che il tuo client desktop potrebbe essere compromesso dal malware, modificando così il tuo voto prima che venga crittografato. La porzione di conteggio omomorfo è abbastanza sicura e non ci sono attacchi noti contro di essa.

Boneh, Goh e Nissim hanno progettato un cryptosystem più omomorfo nel 2005, in cui è possibile eseguire qualsiasi numero di aggiunte, seguito da una moltiplicazione, seguita da un numero qualsiasi di aggiunte, prima della decifrazione. Ciò ha consentito applicazioni più interessanti, ad es. il mio lavoro sul Public Mixing (applicabile anche al voto), in cui è possibile mischiare un insieme di valori crittografati in un'operazione pubblica, senza rivelare in quale ordine li si mescola (piuttosto pazzi, quando ci si pensa.)

I crittosistemi completamente omomorfici, in cui è possibile eseguire aggiunte e moltiplicazioni arbitrarie, sono stati ritenuti impossibili fino al lavoro di Gentry un paio di anni fa. Ciò che è significativo in questa categoria di crittosistema è che è possibile esternalizzare completamente qualsiasi calcolo nel cloud senza mai rivelare dati in testo semplice. Ad esempio, se si desidera eseguire una ricerca a tutto testo della parola "crittografia" su un corpo di testo, è possibile crittografare il corpus, crittografare la parola "crittografia" e inviarlo a un'altra parte che eseguirà il testo completo cerca su dati completamente crittografati e restituisci a te il risultato cifrato, che potrai poi decifrare per ottenere la risposta. Il sistema che computa il calcolo avrebbe conosciuto nulla sul corpus o sulla query di ricerca. Piuttosto sorprendente.

Ovviamente, ciò ha senso solo se il processo di crittografia e il processo di esecuzione delle operazioni omomorfiche sono ancora meno costosi sul cloud rispetto a quelli eseguiti manualmente sul proprio computer locale. Siamo molto, molto lontani da quello. Detto questo, i cryptosystems migliorano solo con il tempo, quindi forse vedremo che il calcolo omomorfico generico diventa utile in pochi anni.

Nel frattempo, ci sono probabilmente molti problemi specifici - non un calcolo generico - che possono essere esternalizzati in modo più sicuro grazie alla tecnologia omomorfica.

Come possono essere usati? Proprio adesso? Non possono Sono troppo lenti per la maggior parte / tutte le applicazioni pratiche. Oggi non è necessario considerare la crittografia omomorfica per uso produttivo, troppo lento.

La speranza è che, se riusciremo a migliorare gli algoritmi per renderli molto più veloci, un giorno o l'altro in futuro, potrebbe consentirci di eseguire calcoli nel cloud senza affidarci al fornitore di servizi cloud. Il sogno è che noi crittografiamo localmente tutti i nostri dati, inviamo i dati crittografati al provider cloud, il cloud provider può fare tutto il calcolo che volevamo sui dati (mentre è ancora in forma crittografata), finendo con i risultati finali in forma crittografata, e quindi possiamo scaricare i risultati e decrittografarli localmente. Il risultato è che il provider cloud non riesce a vedere i nostri dati. Questo è il sogno, comunque, e la crittografia completamente omomorfica ha il potenziale per aiutarci a realizzare questo sogno un giorno - se i crittografi possono capire come renderlo molto più veloce.