Bridges connecting Encryption Schemes

1. Il Problema

Il lavoro affronta la necessità di trasformare in modo sicuro ed efficiente i testi cifrati da uno schema di cifratura a un altro. Sebbene concetti come la Proxy Re-Encryption (PRE) e la Universal Proxy Re-Encryption esistano in letteratura, la realizzazione pratica di protocolli di conversione tra schemi arbitrari è spesso difficile, richiedendo primitive complesse come l'oscuramento indistinguibile (indistinguishability obfuscation).

In contesti specifici come la Crittografia Omomorfa Ibrida, è fondamentale poter passare da un cifrario simmetrico (usato per l'efficienza) a un cifrario omomorfo (usato per il calcolo) o tra diversi schemi omomorfi. Manca tuttavia una definizione formale e un'analisi di sicurezza rigorosa per queste trasformazioni, che gli autori chiamano "Ponti" (Bridges).

2. Metodologia e Definizioni Fondamentali

Definizione di "Ponte" (Bridge)

Gli autori definiscono un ponte $B_{\iota, f}$ tra due schemi di cifratura $S_1$ e $S_2$ come una tripletta composta da:

1. Funzione di iniezione ($\iota$): Una mappa polinomiale e invertibile (con complessità polinomiale) che trasforma lo spazio dei messaggi di $S_1$ in quello di $S_2$.
2. Algoritmo di generazione della chiave del ponte ($bk$): Un algoritmo probabilistico che, partendo dalle chiavi segrete e pubbliche di $S_1$ e $S_2$, genera una chiave di ponte. Questa chiave contiene le informazioni necessarie per eseguire la trasformazione.
3. Algoritmo di trasformazione ($f$): Un algoritmo probabilistico che prende in input la chiave del ponte $bk$ e un testo cifrato $c_1$ di $S_1$, producendo un testo cifrato $c_2$ di $S_2$ tale che la decifratura di $c_2$ con la chiave di $S_2$ restituisca $\iota(m)$, dove $m$ è il messaggio originale.

Modello di Sicurezza

Per analizzare la sicurezza, gli autori associano a ogni ponte uno schema di cifratura associato ($G_f$).

• Lo spazio dei messaggi di $G_f$ è quello di $S_1$.
• Lo spazio dei cifrati è il prodotto cartesiano dei cifrati di $S_1$ e $S_2$.
• La chiave pubblica di $G_f$ include le chiavi pubbliche di entrambi gli schemi e la chiave del ponte $bk$.
• La sicurezza del ponte è definita come la sicurezza IND-CPA (Indistinguishability under Chosen Plaintext Attack) di questo schema associato $G_f$.

3. Contributi Chiave

A. Ricetta Generale per la Costruzione (Ispirata a Gentry)

Gli autori propongono un metodo generale per costruire ponti, ispirato alla procedura di Recrypt (o bootstrapping) utilizzata da Craig Gentry per ottenere la crittografia omomorfa completa (FHE).

• Meccanismo: Se si ha uno schema $S$ e uno schema omomorfo $H$ che può valutare il circuito di decifratura di $S$, è possibile costruire un ponte da $S$ a $H$.
• Funzionamento: La chiave del ponte consiste nelle cifrature (sotto $H$) dei bit della chiave segreta di $S$. L'algoritmo di trasformazione $f$ esegue omomorficamente il circuito di decifratura di $S$ utilizzando queste cifrature come input, producendo una cifratura del messaggio originale sotto $H$.

B. Teorema Principale di Sicurezza (Teorema 2)

Il risultato teorico centrale afferma che la sicurezza di un ponte si riduce alla sicurezza del primo schema ($S_1$) più un'assunzione tecnica aggiuntiva.

• Assunzione Tecnica: L'insieme delle distribuzioni delle chiavi del ponte (che includono le cifrature della chiave segreta di $S_1$) deve essere computazionalmente indistinguibile da un insieme di distribuzioni in cui tali cifrature sono sostituite da cifrature di un valore fisso (es. zero).
• Implicazione: Se $S_1$ è IND-CPA sicuro e l'assunzione di indistinguibilità è soddisfatta, allora il ponte è IND-CPA sicuro.

C. Validazione dei Ponti di Tipo Gentry

Gli autori dimostrano che i ponti costruiti secondo la "ricetta di Gentry" soddisfano naturalmente l'assunzione tecnica richiesta dal Teorema 2 (Proposizione 2), garantendo così la loro sicurezza basandosi sulla sicurezza degli schemi sottostanti.

D. Esempi e Varianti

• Ponti Gentry: Vengono presentati quattro esempi diversi di ponti dallo schema CSGN (una variante basata su distribuzioni finite) a vari schemi FHE, mostrando come diverse rappresentazioni del circuito di decifratura portino a ponti diversi.
• Ponti "Entangled" (Senza Chiave): Viene presentato un esempio di ponte tra lo schema Goldwasser-Micali (GM) e lo schema Sander-Young-Yung (SYY) che ha una chiave del ponte vuota. In questo caso, la trasformazione è possibile solo perché le chiavi segrete dei due schemi sono identiche e le strutture matematiche sono correlate in modo specifico. Questo introduce il concetto di "entanglement" tra schemi di cifratura.

4. Risultati Sperimentali

Gli autori hanno implementato e testato i ponti descritti negli appendici:

• Ambiente: Esecuzione su CPU Intel (I7-4770 e I7-1068NG7) utilizzando le librerie HElib, SEAL e TFHE.
• Scenari:
  1. Valutazione di monomi: Confronto tra l'esecuzione diretta di operazioni omomorfe su schemi FHE (BGV, BFV, TFHE) e l'uso di un ponte per trasformare cifrati da uno schema leggero (CSGN) a uno FHE.
  2. Circuiti di confronto: Valutazione omomorfa di circuiti di confronto bit-a-bit utilizzando il ponte GM-SYY.
• Risultati:
  • Per monomi di alto grado, l'approccio ibrido (CSGN + Ponte) risulta più veloce rispetto all'esecuzione diretta in FHE, poiché le operazioni in CSGN sono molto economiche e il ponte gestisce la transizione di rumore in modo efficiente.
  • Nel caso del ponte GM-SYY, l'implementazione del circuito di confronto mostra tempi di esecuzione che crescono linearmente con la dimensione dei dati in input, confermando l'efficienza pratica del protocollo.
  • I tempi di esecuzione variano a seconda della libreria FHE target (es. TFHE richiede bootstrapping automatico che aumenta i tempi per circuiti profondi, mentre BGV/BFV permettono parametri senza bootstrapping per certi livelli).

5. Significato e Impatto

Questo lavoro fornisce un quadro teorico unificato per la conversione di testi cifrati tra schemi diversi, colmando il divario tra la teoria delle categorie (dove i ponti sono morfismi) e la crittografia pratica.

• Sicurezza Formale: Offre la prima definizione rigorosa di sicurezza IND-CPA per i ponti, superando le analisi precedenti basate sulla Proxy Re-Encryption.
• Flessibilità: Dimostra che non è necessario un protocollo universale complesso per ogni coppia di schemi; basta che uno schema possa valutare il circuito di decifratura dell'altro (o che esistano relazioni strutturali specifiche, come nel caso "entangled").
• Applicabilità: È cruciale per l'ottimizzazione delle applicazioni di calcolo su dati cifrati (Cloud Computing), permettendo di combinare l'efficienza dei cifrari simmetrici o leggeri con la potenza computazionale degli schemi FHE completi.

In sintesi, il paper stabilisce che la sicurezza di un ponte dipende fondamentalmente dalla sicurezza dello schema di partenza e dalla capacità di mascherare la chiave segreta durante la trasformazione, fornendo sia la teoria che le prove pratiche per l'adozione di tali protocolli.