Condivisione della tecnologia

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Risorse di apprendimento:
Crittografia completamente omomorfica I: teoria e fondamenti (insegnante Yu Yu dell'Università Jiao Tong di Shanghai)
Crittografia completamente omomorfa II: Teoria e costruzione della crittografia completamente omomorfa (Insegnante Xiang Xie)

---

Al giorno d'oggi, gli schemi di crittografia completamente omomorfi di seconda generazione (come BGV e BFV) e di terza generazione sono tutti basati su LWE. Ora anche gli schemi completamente omomorfi avanzati sono basati su LWE, quindi questo articolo riassume le conoscenze di base di LWE.
Innanzitutto considera che vogliamo crittografare un numero$S$, ora utilizzando una serie di${UN}_{iooooo}$Giusto$S$Crittografa e ottieni${UN}_{iooooo}S$, infatti, può essere risolto risolvendo il massimo comun divisore MCD$S$ .Tuttavia, se viene aggiunto un rumore casuale$e_{iooooo}$,Ottenere${UN}_{iooooo}S+e_{iooooo}$, allora sarà difficile da risolvere$S$ valore. Questo processo è la mia semplice comprensione di LWE. Il cosiddetto errore è un rumore.

Il processo di calcolo della crittografia completamente omomorfa è diviso in tre fasi: generazione della chiave KeyGen, crittografia Enc, calcolo omomorfico Eval e decrittografia Dec. ,

Generazione di chiavi:

Per prima cosa costruisci l'equazione di cui sopra,$S\cdot UN+e=SUN+e$, quindi ottenere la chiave pubblica pk ($-UN$E$SUN+e$splicing) e la chiave privata sk ($S$ e 1). Si ottiene quindi che il risultato della moltiplicazione tra pk e sk è un rumore casuale e (vicino a 0).

Inc.:

La chiave pubblica pk utilizzata per la crittografia, r è un vettore casuale contenente solo 0 o 1 e m è l'informazione da crittografare (inserita nel bit più basso del vettore).

Dicembre:

Dopo aver calcolato il prodotto interno della chiave privata sk utilizzata per la decrittazione e ct, trova mod 2 per ottenere il risultato della decrittazione.

Prova di correttezza:

Moltiplica sk e pk per ottenere 2e (la condizione soddisfatta da KeyGen), quindi esegui il prodotto interno con r per ottenere un piccolo rumore uniforme. Il risultato finale è m+ un piccolo rumore uniforme, quindi il rumore può essere eliminato dal mod 2. Ottieni il risultato della decrittazione m. Questo è il motivo per cui il rumore costruito è 2e, non e. Da quanto ho capito, costruendo un rumore casuale con numeri pari, è conveniente utilizzare il mod 2 per eliminare il rumore durante la decrittazione.

Prova di sicurezza:

Quando pk è pseudo-casuale e r ha un'entropia sufficientemente elevata (ovvero, la casualità è forte?), sia pk che pk moltiplicati per r sono pseudo-casuali. Dopo aver aggiunto naturali e vettori con m, anche il risultato della crittografia è pseudo-casuale.

Quella che segue è la descrizione stereotipata dell’insegnante Xiang Xie:
Formula di crittografia: testo cifrato c = chiave pubblica pk ✖️ casuale r + testo in chiaro m
Formula di decrittazione: testo in chiaro m = <testo cifrato sk, chiave privata sk> mod q mod 2

Su questa base, il mod 2 può essere utilizzato per decifrare il valore del testo in chiaro m. Finché il rumore è sufficientemente piccolo, la precisione può essere garantita.
C'è qualcosa che bisogna distinguere qui: quanto sopra$PK=(UN,B=UN{S}^{\prime }+2e)$è la soluzione BGV e BFV lo è$PK=(UN,B=UN{S}^{\prime }+e)$, la differenza è che BGV codifica le informazioni in bit bassi, mentre BFV codifica i messaggi in bit alti (verrà spiegato durante l'apprendimento di BFV).

Eval (omomorfismo additivo e omomorfismo moltiplicativo):

Si noti che l'addizione o la moltiplicazione omomorfa comporterà un significativo accumulo di rumore e la moltiplicazione ha un trend di crescita quadratico.
Quindi parliamo di come decrittografare il risultato della moltiplicazione omomorfa. Puoi vedere la seguente formula: La moltiplicazione di due testi cifrati equivale a fare rispettivamente il prodotto tensoriale del testo cifrato e della chiave privata, e quindi a fare il prodotto interno. Quindi ovviamente sia il testo cifrato che la chiave privata hanno raddoppiato le loro dimensioni. L'esempio è una prova di equivalenza.

Quindi la domanda è: come ripristinare la dimensione del testo cifrato e la dimensione della chiave privata dopo la moltiplicazione omomorfa? Questo è il problema che il cambio chiave risolve.

Quella che segue è la descrizione dell’insegnante Xiang Xie:

Commutazione chiave

L'obiettivo è ripristinare la dimensione del testo cifrato e della chiave privata a una dimensione lineare.

Ora trova la moltiplicazione dei testi cifrati c1 e c2:

Il processo di cui sopra si basa sul concetto di scomposizione dei bit:

Quella che segue è la descrizione dell’insegnante Xiang Xie:

L'obiettivo di Key Switching: convertire la chiave privata$\tilde{S}$giù$\tilde{C}$ Converti in chiave privata$S$giù$C$,E$\tilde{C}$E$C$Sono tutti crittografati con lo stesso testo in chiaro.
Un concetto fondamentale qui è Key Switching Key (KSK), che significa utilizzare una chiave privata$S$per crittografare$\tilde{S}$。

Attraverso il processo Key Switching è possibile derivare la chiave privata$S\otimes S$è diventato lineare$S$, mentre il testo cifrato cambia da$\tilde{C}$è diventato lineare$C$ .E lo si può vedere dall'ultima riga della formula dopo il cambio di chiave$⟨C,S⟩$e l'originale$⟨\tilde{C},S\otimes S⟩$C'è una differenza di rumore tra$2{\tilde{C}}^T\tilde{e}$ , questa parte può essere molto grande! Quindi non c'è ancora modo di implementare il cambio chiave qui.

Qui viene introdotta una matrice Gadget G:

Pertanto, il processo di cambio chiave diventa il seguente:

A questo punto, l’errore aggiunto è molto piccolo.
In sintesi, tramite Key Switching, la chiave privata originale$\tilde{S}=S\otimes S$giù$\tilde{C}=C\otimes C$, viene convertito in una chiave privata$S$giù$C$, prestare attenzione alla chiave dopo la commutazione della chiave$S,C$Non sono i valori originali (doppio controllo).

Per BGV, il rumore dell'addizione aumenta in modo lineare e il rumore della moltiplicazione aumenta in modo quadrato. Sebbene il cambio di chiave possa supportare la moltiplicazione (limitando sk a diventare estremamente grande), il rumore è in realtà un rumore molto piccolo aggiunto al rumore della moltiplicazione originale è anche molto grande. Pertanto, questo rumore deve essere ulteriormente ridotto.

Riduzione del modulo

A questo punto, i calcoli di moltiplicazione e addizione omomorfa con una profondità ridotta sono stati implementati tramite LWE. La commutazione della chiave utilizza una nuova chiave per ogni livello. Tuttavia, man mano che la profondità di calcolo aumenta, l'espansione del rumore è esplosiva, quindi non è ancora livellata . FHE (può calcolare l'EHE ad una profondità specificata).
Ora speriamo di implementare un FHE in grado di calcolare una certa profondità senza utilizzare il bootstrap, che richiede la conversione del modulo.

Non capisco bene il processo centrale. In breve, si tratta di trasformare il testo cifrato c dal dominio modulo q al dominio modulo p (p<
Ecco un esempio specifico:
Se la riduzione del modulo non viene eseguita, il rumore aumenterà con una tendenza doppia esponenziale man mano che la profondità aumenta e si verificheranno errori di decrittografia dopo il livello >= 3.

Se la riduzione del modulo viene eseguita a ciascun livello, anche il rumore verrà mantenuto entro un intervallo di valori assoluti, al costo di una riduzione continua del modulo.

Pertanto, se si desidera implementare un FHE livellato, è possibile impostare un modulo$B^D$, quindi puoi calcolare una profondità di$D$circuito (dove$B$ è il limite superiore del rumore del testo cifrato aggiornato).Calcolato$D$Dopo la profondità, il modulo dovrebbe essere ridotto a$B$ , per garantire che non vi siano errori nella decrittografia in questo momento. BGV è un FHE livellato.