Applica operazioni omomorfiche su dati crittografati di grandi dimensioni
Attualmente sto sperimentando sulla crittografia omomorfica utilizzando la libreria PALISADE .
Voglio applicare semplici operazioni come addizioni e moltiplicazioni su grandi input crittografati. Ad esempio, l'input A[3200]e l'input di B[4096]entrambi i vettori / array di valori int vengono crittografati. Con questi due input Enc(A)e Enc(B)voglio applicare una moltiplicazione:
EvalMult(Enc(A[0]), Enc(B[42]))
*0 and 42 denoting the indexes of the corresponding inputs
** no SIMD needed
Per quanto mi riguarda l'implementazione dei requisiti sopra descritti potrebbe essere risolta in due modi differenti:
Impacchetta gli input in un unico testo cifrato (simile al SIMD) e per le operazioni che potrei usare
EvalIndexAt()per ottenere il giusto valore dall'input crittografato.Crittografa ogni valore da A e B separatamente.
Non sono del tutto sicuro di quale delle soluzioni descritte sarebbe la migliore in termini di efficienza . Il primo approccio ha questo grande vantaggio che è necessario un solo processo di crittografia per l'intero input, ma questo ha lo svantaggio che devo sempre accedere all'elemento corretto usando il EvalAtIndex()metodo e più grandi sono gli input, più lento è il calcolo dei risultati EvalAtIndexKeyGen(). (Almeno sulla mia macchina)
Il secondo approccio sembra più adatto perché EvalAtIndex()non è necessario, ma ha il costo di crittografare ciascun valore separatamente, il che richiede un po 'di tempo.
Qualche consiglio sui pensieri?
Risposte
Grazie per la domanda.
Il vantaggio principale dell'approccio n. 1 (SIMD) è che puoi eseguire addizioni e moltiplicazioni di vettori (di 4096 o più numeri interi / reali) utilizzando una singola addizione o moltiplicazione omomorfa (molto efficiente). La rotazione (chiamata EvalAtIndexPALISADE) è un'operazione extra che consente di accedere a indici individuali o di eseguire una sommatoria efficiente (come nel prodotto interno), moltiplicazione di matrici, ecc. Questo approccio ha anche un fattore di espansione del testo cifrato molto più approccio # 2. Generalmente l'opzione n. 1 è preferita nella pratica (e non riesco a pensare a nessun caso d'uso reale in cui vorrei andare con l'opzione n. 2).
Per ridurre al minimo il costo della moltiplicazione, forse potresti impacchettare il vettore in blocchi contigui in modo da aver bisogno di una singola rotazione per un blocco. Per esempio,
EvalMult(Enc(A[0:5]),Enc(B[42:47))
Un'altra tecnica che puoi usare è EvalFastRotation(disponibile solo per CKKS e BGVrns in PALISADE v1.10.x). Se hai bisogno di più rotazioni dello stesso testo cifrato, puoi precalcolare qualcosa per il testo cifrato e quindi utilizzare rotazioni più economiche (il massimo vantaggio si ottiene con la commutazione della chiave BV) - vedihttps://gitlab.com/palisade/palisade-development/-/blob/master/src/pke/examples/advanced-real-numbers.cpp per un esempio.
Ci sono anche modi per ridurre al minimo il numero di chiavi da generare se hai bisogno di rotazioni multiple (calcola solo approssimativamente una radice quadrata del numero di rotazioni necessarie), ad esempio, usando la tecnica baby-step-giant-step descritta in https://eprint.iacr.org/2018/244 (queste tecniche possono essere implementate nella tua applicazione basata su PALISADE).
È inoltre possibile utilizzare un ordine speciale di impacchettamento di un vettore se lo schema per eseguire la moltiplicazione è noto (in questo modo la rotazione preparerà diversi blocchi attraverso il vettore utilizzando un'unica operazione di rotazione). Le rotazioni sono cicliche (wrap around) sia in CKKS che in BGVrns quando gli # slot di testo in chiaro (dimensione batch) sono uguali a ring dimension/ 2. Se hai un vettore più piccolo di quello, puoi sempre clonare / replicare il vettore piccolo tante volte quanto necessario riempire ring dimension/ 2.
In sintesi, il più grande miglioramento dell'efficienza può essere ottenuto se pensi al tuo problema in termini di vettori simil SIMD. Quindi puoi riformulare il tuo problema / modello per sfruttare appieno il set di strumenti che HE fornisce. In un certo senso, questo è simile alla programmazione che utilizza istruzioni vettorializzate, ad esempio AVX, o programmazione a matrice (come in MATLAB).