Applicazioni pratiche di algoritmi di crittografia omomorfa?

Question

Sembra che ci siano state cose interessanti in corso nella crittografia: la prima crittografia omomorfa lo schema è apparso di recente ( spiegazione , HT ). In parole povere, è un modo per codificare x in f (x) in modo tale da poter calcolare f (x + y) facilmente conoscendo < code> f (x) e f (y) anche se non è possibile ripristinare facilmente x e y (e lo stesso per f (x * y) ).

Quali sono le applicazioni pratiche per schemi di questo tipo (una volta stabilita la loro sicurezza)? Per me, sembra che potrebbero rendere molto più semplice la scrittura di algoritmi per la manipolazione di dati privati.

Ecco i miei pensieri :

1. voto elettronico
2. verifica dell'integrità dei dati privati ??
3. c'è una possibilità che possa aiutare la privacy in generale?

Esempio : ho conti con le banche A, B, C. L'entità X vuole confermare che ho più di $ 1000 in totale; accetterebbe felicemente le dichiarazioni delle banche A, B, C o D, ma sfortunatamente non ho abbastanza soldi in un singolo conto. La banca A crittografa le informazioni sui miei $ 500 dollari con la mia chiave pubblica; allo stesso modo, le banche B e C crittografano le informazioni che ho rispettivamente $ 200 e $ 300. Mandano questi dati a X, che li aggiunge a un numero che dimostrano di essere effettivamente crittografato $ 1000 (crittografando $ 1000 con la mia chiave pubblica e dimostrando che il risultato è lo stesso). Ho provato qualcosa senza rivelare a X quanti soldi ho in ciascun account.

Un altro esempio : i bravi cittadini X_1, ..., X_n si stanno unendo per selezionare uno dei due candidati, uno dei quali è il libero bevitore di latte A mentre un altro è un B amante della pistola portante (tutti i nomi sono immaginari). Decidono di volere che il voto sia privato ma rapido. Inviano i loro voti nel formato vettoriale (1, vote_A, vote_B, vote_None) crittografati alla Commissione elettorale che li aggiunge pubblicamente e ottiene il risultato nel modulo (count, count_A, count_B, count_None) . Dopo aver verificato che count = count_A + count_B + count_None , i funzionari dichiarano la vittoria di uno dei candidati, dopo di che l'elezione viene dichiarata non valida dal giudice per qualche motivo estraneo al voto elettronico e combattuto nel tribunale per i prossimi 10 anni, ma, ehi, non è comunque un mio problema.

Note : - Credo che quel particolare esempio sia stato possibile con RSA anche prima, poiché richiede solo omomorficità in una sola operazione. La speranza è che possiamo avere cose radicalmente più interessanti con più operazioni - quindi, vieni con degli esempi!

• Mi piacerebbe in particolare vedere le risposte contenenti codice e / o sviluppare framework che hanno la possibilità di essere utilizzati nella pratica, il motivo è che SO non è un forum teorico di informatica.

• L'algoritmo omomorfo, per ripetere quanto detto di seguito nei commenti, consente di creare un programma che gestisca i dati senza conoscerli. Sfortunatamente, i tipi di programmi sono alquanto limitati: non puoi avere if (x = 0) ... perché x è crittografato e ogni passaggio è molto lento ( ci sono alcuni reticoli coinvolti).

Answer 1

Ecco uno scatto selvaggio nel buio:

Stiamo pensando di proteggere il testo in chiaro dalla persona che esegue il calcolo su di esso. E se l'obiettivo fosse proteggere sia il testo in chiaro che l'algoritmo?

Prendi, ad esempio, le macchine MRI. La parte più costosa della macchina per risonanza magnetica è l'algoritmo in cui la macchina analizza i dati di risonanza magnetica. Per questo motivo, sono pesantemente protetti da dispositivi hardware progettati per distruggere il programma prima di lasciarsi esaminare da una parte non attendibile (o da chiunque per quella materia).

Se un produttore di risonanza magnetica potesse centralizzare il calcolo dei dati MRI, sarebbe una fantastica riduzione del rischio di perdere il loro algoritmo. Tuttavia, le leggi impediscono loro di accedere ai dati dei pazienti privati.

! La crittografia omomorfa consente che ciò avvenga laddove i dati del paziente e l'algoritmo sono entrambi protetti. La crittografia omomorfa "completamente" (ovvero indurre un omomorfismo ad anello sui dati crittografati) consente a un insieme di calcoli molto più efficiente e robusto di operare sui dati.

Answer 2

Come fanatico della PKI, se anche la crittografia omomorfa fosse un sistema chiave assimmetrico, allora hai alcune possibilità davvero interessanti nel mondo della firma. Il firmatario potrebbe potenzialmente firmare il messaggio e un destinatario potrebbe ritrasmettere parte del messaggio e la parte corrispondente del testo cifrato a terzi.

In notazione di funzione, sarebbe:

Segni utente:

segno (testo semplice, chiave privata) = testo cifrato

e trasmette:

invia (testo in chiaro, testo cifrato, certificato)

L'applicazione ottiene segmenti:

plaintext = desideratoPlaintext + otherPlaintext

e calcola la stessa conversione del testo cifrato, usando qualcosa come:

se testo cifrato :: testo in chiaro allora ?? :: desiderato Testo

per trovare il testo desiderato

L'applicazione inoltra i contenuti desiderati solo al servizio esterno:

invia (wishPlaintext, wishCiphertext, certificate)

E il servizio può verificare questo messaggio come se l'utente lo avesse inviato direttamente.

Questo dipende dall'algoritmo di hash usato per comprimere il testo in chiaro anche omomorfo. In caso contrario, questo non funzionerà ... o che non viene applicato alcun algoritmo hash.

Questo potrebbe essere molto utile nei casi in cui si desidera che un servizio esterno faccia qualcosa in risposta a una richiesta dell'utente firmata, ma non si desidera esporre tutto ciò che l'utente ha inviato a quel servizio esterno.

Un esempio potrebbe essere un semplice sistema di ordinazione di pacchetti: invio a un'app Web una richiesta di acquisto di una raccolta di articoli. Per essere super-sicuro, firmo un Ordine di acquisto che conferma che desidero (e prometto di pagare) alcuni # di articoli, spediti in un luogo specifico, entro una data specifica e con alcune informazioni di pagamento specifiche. Ora ... l'app Web vorrà che accadano diverse cose:

• La finanza deve addebitare il mio account e iniziare a ricevere un pagamento da me
• L'inventario deve estrarre gli articoli dallo stock o gestire eventuali problemi di esaurimento
• La spedizione deve ricevere dall'inventario e spostare le cose al mio indirizzo

Non vi è alcun motivo per cui l'inventario o la spedizione sappiano come pago la mia fattura. E potrebbe non esserci motivo per cui la finanza conosca il mio indirizzo di spedizione ... In ogni caso, il testo desiderato e il testo desiderato cambiano, a seconda di chi sia il destinatario. Ciò è ancora più potente in un sistema come Amazon.com ha utilizzato libri in cui l'entità da cui ho acquistato (Amazon) è diversa dall'entità che fornisce l'articolo (il venditore di libri usati).

Leggendo l'articolo sulla crittografia reticolare, sembra più un sistema di chiavi simmetriche ... che non è così favorevole alla firma dei messaggi.

Sul concetto di "mai dire mai", non direi che era irragionevole utilizzarlo per applicazioni sulla privacy. Ma sembra decisamente problematico che tu possa trovare diversi modi per passare dal testo cifrato al testo normale.

Answer 3

La più grande applicazione della crittografia omomorfa sarebbe nel data mining, IMHO. L'uso di questo algoritmo potrebbe risolvere allo stesso tempo i problemi sia della privacy che della scoperta di tendenze. Ad esempio, supponiamo che la tua azienda organizzi informazioni di vendita su alcuni provider SAS. Ora, quel fornitore potrebbe fornirti sofisticati servizi di data mining, senza che tu debba rivelare effettivamente le tue informazioni reali. Fondamentalmente, saresti in grado di inviare i tuoi dati a un fornitore di calcolo, fargli utilizzare i suoi cicli della CPU per calcolare per tuo conto e restituirti i dati crittografati. Sarebbe davvero fantastico per le aziende che stanno cercando di passare a sistemi basati su cloud, ma che hanno problemi di privacy / IP che impediscono loro di farlo.

Un'altra potenziale applicazione, a un livello più basso e più personale, sarebbe la gestione di tutti i tipi di dati finanziari. L'esempio esteso di ilya può essere applicato all'archiviazione delle dichiarazioni dei redditi da parte del tuo commercialista senza effettivamente vedere le tue informazioni finanziarie, l'elaborazione delle carte di credito ecc.

Tuttavia, terrei la mia eccitazione fino a quando lo schema non sarà testato rigorosamente e ritenuto sicuro. Gli algoritmi di crittografia hanno la famigerata abitudine di fallire il loro primo test, andare a una revisione e ripetere il ciclo fino a quando non sono "certificati". da qualche autorità governativa.

Answer 4

Potresti essere interessato a vedere la versione piuttosto clamorosamente negativa di Bruce Schneier sulla crittografia omomorfa su:

http://www.schneier.com /blog/archives/2009/07/homomorphic_enc.html?nc=11

Answer 5

Non so quanto sarà costoso il calcolo f (x) + f (x) , ma forse potrebbe essere usato come un modo per implementare un database crittografato.

Puoi archiviare 1 milione di righe di alcuni dati crittografati come f (x_1) , f (x_2) , ... f (x_n) . Puoi farlo

SELECT SUM(x)
FROM Foo
WHERE y = 'some value'

Che potrebbe essere calcolato eseguendo prima SUM (f (x)) , quindi decodificandolo in SUM (x) .

Answer 6

Con questo puoi eseguire un circuito arbitrario non ricorsivo di profondità limitata, quindi data una lunghezza logaritmica della chiave puoi eseguire un algoritmo NC1 (sostanzialmente un circuito booleano feed-forward).

Quindi, come puoi usarlo?

Vediamo Mappa / Riduzione di un circuito e schema di riduzione su una serie di input.

Prima i dati:

Probabilmente non vogliamo che il client debba aver crittografato tutti i dati che cercheremo, quindi puoi fornire 1 crittografato e 0 crittografato al server e lasciarlo usare la struttura ad anello per costruire numeri interi crittografati arbitrari per noi, oppure possiamo semplicemente usarli direttamente come bit. In questo modo il server può fornire alcuni o tutti i dati che stiamo cercando. Per i numeri interi può costruirli con l'aritmetica contadina (doppia o doppia e aggiungere 1 per ogni bit), per i bit fornisce solo il bit crittografato appropriato.

Possiamo mescolare e abbinare valori booleani e interi nei nostri progetti, ottenendo un if / then / else (che richiede la valutazione di entrambi i rami stile SIMD) valutando cond * then + (1 - cond) * else usando 1 come vero e 0 come falso in cond, quindi puoi cavartela usando l'aritmetica incorporata del tuo anello per rendere i tuoi circuiti più superficiali.

D'altra parte, potremmo aver pre-crittografato anche alcuni dati, ma dal momento che dovrete continuare a riciclare la stessa chiave impostata per usarli, questo diventa molto difficile da ottenere.

Quindi, ora abbiamo i dati forniti dal server. Ora, crittografa le cose che non vuoi che il server sappia, come quello che stai cercando, e fai in modo che le inseriscano nel circuito nei punti giusti, ad esempio come input aggiuntivo per la tua funzione cartografica.

Dovremmo essere in grado di mappare un circuito arbitrario simile a NC1 su ciascun ingresso per estrarre un campo, moltiplicare alcuni valori e generalmente mapparlo in una forma che è possibile ridurre a buon mercato.

Quindi riduci quei frammenti usando circuiti più piccoli, ad esempio per un semplice monoide che ha un risultato ben delimitato dalle dimensioni. (ad esempio, mappi per ottenere un bit che indica se hai trovato una corrispondenza e quindi riduci contando quei bit con un piccolo circuito sommatore)

Dato che devi solo costruire il circuito logicamente e simularne l'esecuzione su questi bit crittografati nell'anello omomorfo, probabilmente potresti implementarlo relativamente rapidamente usando un piccolo DSL, cioè qualcosa come Lava in Haskell, supponendo che tu abbia la crittografia omomorfa pezzi diritti.

Inoltre, tieni presente che ogni gate è seriamente costoso da eseguire.

Quindi, per riassumere,

1. Fornisci al server 1 e 0 crittografati e qualsiasi metainfo crittografato per la tua mappa e riduci le funzioni.
2. Per ogni punto dati, codificalo nel tuo anello omomorfo, alimenta il tuo circuito della mappa sia l'input che la meta info per ottenere un valore adatto per la riduzione.
3. In un albero binario bilanciato (o altra disposizione bilanciata per ridurre l'altezza dell'albero), applica l'operazione di riduzione all'output dal tuo circuito e a qualsiasi metainfo della mappa crittografata.
4. Consegnare il risultato al client per la decrittazione

Answer 7

Il problema con l'attuale algoritmo di crittografia omomorfa è che puoi solo eseguire un circuito polilaritmico (NC1) con esso, che esclude quasi tutto ciò che è interessante algoritmicamente.

Inoltre non sembra che la complessità della codifica sia in alcun modo inferiore alla complessità dell'esecuzione del circuito pollogaritmico, quindi non hai raccolto alcun lavoro gratuito al primo arrossimento, a meno che tu non faccia qualcosa di particolarmente complicato con esso.

Answer 8

Il calcolo distribuito come SETI @ Home, i progetti di ripiegamento delle proteine, ecc., sono abbastanza popolari perché sfruttano la donazione di tempo della CPU e l'elettricità da migliaia di utenti. Ancora più interessante sarebbe un modello in cui le persone possono essere pagate per fornire queste risorse per progetti commerciali. Tuttavia, nessuna società responsabile desidera spedire i propri dati a migliaia di computer anonimi per l'elaborazione. Se riesci ad applicare in modo efficiente algoritmi ai dati crittografati, diventa possibile delegare l'elaborazione a chiunque senza una relazione di fiducia.

Answer 9

Il voto elettronico è in effetti un'applicazione pratica della crittografia omomorfa, ovvero http://heliosvoting.org/

Answer 10

Alcune applicazioni bancarie potrebbero diventare più veloci con l'aiuto della Crittografia omomorfa.

Possono eseguire operazioni con dati crittografati su cloud anziché trasferirli da cloud a locale e rimetterli su cloud. Inoltre, non è necessario crittografare-decifrare-eseguire operazioni-crittografare la pipeline, crittografare-eseguire operazioni sarebbe OK.