Qual è lo stato dell'arte della crittografia omomorfica?

7

Ho l'impressione da alcune risorse internet che ho scremato che la crittografia omomorfica è ancora molto inefficiente dal punto di vista computazionale. Tuttavia, un comunicato stampa di Infineon del 2010 dice che le CPU delle chip card possono fare calcoli in forma crittografata. Non ci sono quindi ostacoli più pratici alle crittografie omomorfe oggi, dal momento che le CPU comuni sono certamente più potenti di quelle su chip card?

    
posta Mok-Kong Shen 14.09.2012 - 14:43
fonte

5 risposte

9

Esistono due tipi di crittografia omomorfica .

La crittografia parzialmente omomorfica riguarda il calcolo di un tipo di operazione su valori crittografati. Ad esempio, conosci E (m 1 ) e E (m 2 ) e, senza conoscere il chiave privata, puoi calcolare E (m 1 * m 2 ) . Diversi algoritmi efficienti che ne consentono sono noti, in particolare ElGamal (che consente di moltiplicare i messaggi crittografati) e il sistema di crittografia Paillier (che consente di aggiungere messaggi crittografati). La crittografia parzialmente omomorfica è utile per alcuni protocolli, ad es. votazione elettronica (l'idea è che si possano calcolare insieme voti cifrati e decrittografare il risultato alla fine). La crittografia parzialmente omomorfa funziona bene e lo ha fatto per almeno un decennio.

La crittografia completamente omomorfica riguarda il calcolo di due tipi di operazioni su valori crittografati: da E (m 1 ) e E (m 2 ) , puoi calcolare E (m 1 * m 2 ) e E (m 1 + m 2 ) . La crittografia completamente omomorfica consente calcoli arbitrari; in definitiva, è possibile fornire input crittografati a un computer biiig, che eseguirà il calcolo e fornirà il risultato crittografato, senza la necessità di fidarsi di quel grande computer. L'idea è che lo stato di un transistor in un circuito virtuale può essere crittografato e le aggiunte / moltiplicazioni sono sufficienti per emulare le variazioni di stato in base agli input del transistor. Il grande computer dovrebbe eseguire una CPU virtuale, con alcune operazioni omomorfiche per ogni transistor nella CPU virtuale e per ogni clock. Inutile dire che questo sembra costoso.

Sfortunatamente, i più noti algoritmi di crittografia completamente omomorfi (derivati dal lavoro di Gentry nel 2009) sono terribilmente lenti e inefficienti, il che non ne vale la pena (cioè l'intero cloud Amazon S3 non può calcolarlo omomorficamente più veloce di quello che una singola smartcard potrebbe fare a meno della crittografia). L'area di ricerca non è morta, lontana da esso; ma è molto nuovo e non ha ancora prodotto nulla di pratico.

    
risposta data 14.09.2012 - 23:14
fonte
6

No. La crittografia completamente omomorfica non è pratica oggi - non su un computer desktop e non su una chip-card. Vedi, ad esempio, la seguente domanda sul nostro sito gemello, Crypto.SE: Qual è il crittosistema completamente pratico più omomorfico? . (Estratto: "nessuno di questi è pratico ... ancora".) Il comunicato stampa che state leggendo probabilmente è stato distorto dalle persone delle relazioni di pubblicazione. Ehi, succede.

È possibile eseguire la crittografia omomorfica parzialmente in modo ragionevolmente efficiente, ma è molto più limitato nelle sue applicazioni e non ha la potenza o l'utilità della crittografia completamente omomorfica.

Per ulteriori informazioni su questo argomento, vedere le seguenti domande:

Utilizza la barra di ricerca in alto a destra di questo sito e su Crypto.SE , per trovare ulteriori informazioni sulla crittografia omomorfica .

    
risposta data 15.09.2012 - 08:17
fonte
3

Non sei sicuro di come leggere tra le righe sul documento della stampa, ma sto vedendo qui che non è affatto morto, e sto vedendo un sacco di argomenti caldi su di esso per quanto riguarda Cloud Security - che ha almeno un certo livello di senso su una vista macroscopica, sebbene la parte di me che in realtà ha usato per implementare soluzioni di sicurezza dice "non ci credo finché non la vedi".

La mia opinione su ciò che sto vedendo in Google è che è ancora molto nel mondo della ricerca universitaria - ancora molta matematica da fare e molte analisi computazionali. Ci vorrà un po 'di tempo prima che le aziende investano di più in qualsiasi cosa relativa all'hardware o a qualcosa di significativo nelle implementazioni di software, con cui intendo un peice di software molto solido, testato e certificato utilizzabile per l'elaborazione su larga scala (rispetto a qualcosa in un laboratorio per scopi di verifica).

Sembra che il valore della capacità sia abbastanza alto da permettere di finanziare la ricerca.

Aggiunta basata sul commento:

Con più scavi, vedo cose come:

Il che mi fa rimanere fedele alla mia asserzione iniziale - con pubblicazioni di questo tipo pubblicate in questo lasso di tempo, la natura di come esattamente questa matematica possa essere implementata al meglio sta ancora attraversando un certo livello di evoluzione. Sono disposto ad accettare "non ci sono ostacoli pratici" nel senso di "semplicemente non abbiamo trovato un modo per farlo con la tecnologia in un modo efficiente nel tempo" - ma direi che in questa fase del gioco, Non vedo nessuno nel settore che stia facendo soldi vendendo una soluzione del genere, quindi anche se abbiamo capito come eseguire i calcoli in modo efficiente, non vedo che venga ancora utilizzato in fase di implementazione. Non sto dicendo che non arriverà, ma non c'è ancora, e probabilmente ci saranno ancora ostacoli all'implementazione - probabilmente saranno risolvibili con tempo e denaro, il che aumenterà la disponibilità non appena l'industria si farà strada attraverso un po 'di guida utilizzare i casi e dimostra che le soluzioni possono essere scalate.

    
risposta data 14.09.2012 - 15:06
fonte
1

Temo che questo comunicato stampa di Infineon sia fuorviante. Infineon ha pubblicato un documento sulla sicurezza di valutazione Common Criteria per il chip SLE 78 (disponibile per il download qui ). Dalla lettura di questo documento si può dedurre che, sebbene i dati siano crittografati in memoria, sul bus e nei registri, di fatto viene decrittografato quando viene utilizzato per i calcoli (ad esempio dall'ALU).

La crittografia completamente omomorfica è sicuramente non calcolabile su una chip card in questo momento.

    
risposta data 15.09.2012 - 23:00
fonte
-1

Nella sua risposta (e un commento) David Wachtfogel era dell'opinione che una frase implicata nel comunicato stampa di Infinion, vale a dire "nella CPU stessa", molto probabilmente si riferisca ai registri della CPU e non alla stessa ALU. Se questo è davvero il caso, l'apparente paradosso potrebbe essere spiegato. Mi piace comunque riferire che ho scritto un'email a Mr. Janke, un membro del team di Infinion che ha sviluppato il chip, e ho ottenuto quanto segue nella sua risposta:

Aus den Zertifizerungsreports bzw. den Security Targets können Sie entnehmen (Quelle: link ):

  • "Il TOE fornisce una crittografia completa su chip che copre l'intero core, bus, memorie e codificatori crittografici che non lasciano testo in chiaro sul chip." [Der Begriff "core" beinhaltet auch die CPU inklusive der ALU, vgl. Abbildung auf Seite 16.]

  • "Nessun dato in chiaro viene gestito in nessun punto del TOE e quindi anche le due CPU calcolano interamente mascherate e in aggiunta vengono applicate modifiche alle maschere dinamiche." [Hier wird deutlich, dass die CPU mit verschlüsselten Daten arbeiten, wobei die Schlüssel sich dynamisch verhalten.]

Questi paragrafi hanno evidentemente affermato con fermezza il contrario. Quindi cosa considerano gli esperti nella realtà?

    
risposta data 08.11.2012 - 19:46
fonte

Leggi altre domande sui tag