Qual è attualmente il miglior algoritmo di Searchable Encryption (SE) che funziona in pratica?

Ero alle questo talk all'inizio di quest'anno e sono rimasto impressionato da l'approccio. Il prodotto si chiama EncryptedQuery che tenta di risolvere il problema (presumo correlato) di Recupero di informazioni private . PIR è probabilmente un requisito più strong di SE poiché con PIR, anche il server db non è autorizzato a sapere cosa hai cercato o quale record è stato restituito.

I miei appunti sul talk:

• Motivazione: casi in cui desideri mantenere privati i tuoi pattern di accesso ai dati.
• PIR è intrecciato con i problemi del trasferimento dimentico e del calcolo sicuro multipunto.
• Nel 2016 NSA ha aperto in open-source uno stack di software PIR chiamato PIRK
• Nel 2017 il progetto PIRK è andato in pensione. La società Envieta ha preso il progetto e lo ha rinominato EncryptedQuery
• Utilizza la crittografia Paillier, che è omomorfica nel senso che l'aggiunta nello spazio del testo in chiaro diventa una moltiplicazione nello spazio del testo cifrato.

La mia comprensione dell'algoritmo (probabilmente errata, sebbene avesse senso al momento) è che il richiedente crittografa una stringa

encr_req = encr(0 0 0 0 0 1 0 0 0 0 ...}

dove dice che la colonna k th contenente 1 è il numero di riga che desidera recuperare. Una volta che questa stringa è crittografata, il server non sa quale colonna contiene 1.

Quindi il server itera sul database facendo

sum_i( encr_req[i] * encr(data[i]) )

Poiché Paillier è omomorfico e tutti tranne uno dei valori di testo in chiaro è 0, questo è equivalente a

0*data[0] + 0*data[1] + ... + 1*data[k] + 0*data[k+1] + ...

Quindi, quando decifri, avrai il tuo risultato.

decr( sum_i( encr_req[i] * encr(data[i]) ) ) = data[k]

Pro:

• Il server è in grado di gestire il recupero degli elementi dal database tramite ID senza sapere quale ID è stato richiesto.
• La larghezza di banda della risposta è bassa: sum_i( encr_req[i] * encr(data[i]) ) è la larghezza di un singolo campo del database.
• Può essere esteso per richiedere più articoli nella stessa query.

Contro:

• Prestazioni: per ogni richiesta, il server deve eseguire iterazioni sull'intero database, crittografando ogni voce con la chiave pubblica del richiedente.
• Tutte le righe nel database devono avere la stessa larghezza di bit (che si desidera mantenere piccole per motivi di prestazioni nel passaggio di crittografia).
• Il numero di voci nel database e il loro ordine devono essere corretti e conosciuti dal richiedente.
• Per DB di grandi dimensioni o meno strutturati, utilizza una crittografia ricercabile più generale (ma meno sicura).

TL; DR non sono sicuro che questo in realtà risponda alla domanda di HelloWorld su quale sia la migliore crittografia ricercabile: /

È scarso perché la crittografia ricercabile è raramente pratica.

In generale, significa che stai utilizzando una cifratura molto debole o stai decifrando tutto mentre vai. Il primo caso è negativo perché è possibile utilizzare i modelli nella crittografia per interromperlo con un campione sufficientemente grande. Il secondo metodo, più consigliabile, è dolorosamente lento perché devi decodificare l'intero set di dati per eseguire una singola query. In ogni caso, la Searchable Encryption è veramente pratica con insiemi di dati molto piccoli.

Un esempio di dove lo useresti sarebbe se vuoi essere in grado di cercare un singolo record dipendente per parole chiave. L'ID del dipendente non sarebbe criptato; quindi, è possibile utilizzarlo solo per interrogare i record di quella persona, quindi è possibile trasferire l'intera serie di record alla propria applicazione per decrittografarla. Quindi cerca i dati decrittografati e dai loro output solo i campi di cui hai bisogno.

Detto questo, ci sono molte promesse con la crittografia ordinabile, purché si stiano facendo ricerche esatte. La crittografia ordinabile imposta l'ambito di ciascuna nuova stringa crittografata tra quelle che dovrebbe essere ordinata; quindi, diciamo che quanto segue è vero:

7iFA384S4BPmuXokR9rcMI37SKnClqnE = ant
E10ZJbnmvJHs3MOKkzDXw7sd037kLCUJ = cat
miHBVXxATe1Jg6G97ug86zv31BxrpRAa = dog
z0L9f8Py12euq9Nhy9Zk0e9L83F8MiBi = man

Se volessi aggiungere "volpe" alla lista, il mio algoritmo di crittografia tornerebbe tra "miHBVXxATe1Jg6G97ug86zv31BxrpRAa" e "z0L9f8Py12euq9Nhy9Zk0e9L83F8MiBi" risultante in qualcosa del tipo:

7iFA384S4BPmuXokR9rcMI37SKnClqnE = ant
E10ZJbnmvJHs3MOKkzDXw7sd037kLCUJ = cat
miHBVXxATe1Jg6G97ug86zv31BxrpRAa = dog
Pe2624gcRjP6YGWOnhiW2xnRomAjDYQK = fox // sorts alphabetically between dog and man
z0L9f8Py12euq9Nhy9Zk0e9L83F8MiBi = man

Funziona perché la prima parte della stringa crittografata è solo l'ordinamento delle informazioni e la seconda parte è i dati crittografati effettivi

SortingId(Pe2624gcRjP6YG), EncyptedData(WOnhiW2xnRomAjDYQK)

Una volta che hai ordinato la crittografia, questo significa due cose, una che puoi ordinare i dati crittografati con la stessa facilità dei dati non crittografati, ma in secondo luogo, significa che puoi usare un metodo simile per unire l'ordinamento in modo selettivo decifrare. Non so personalmente cosa facciano i database effettivamente non lo supportano ancora, ma nella lista precedente, se cerco "man" e decifro "dog", so che i primi 2 elementi non sono man, quindi io non è necessario decrittografarli per cercarli. Ciò significa che più grande è il set di dati, più piccola è la percentuale del set di dati che è necessario decodificare per trovare le cose.