Modification to Fully Homomorphic Modified Rivest Scheme

Questo documento descrive lo schema FHMRS, ne evidenzia una vulnerabilità di sicurezza e propone una modifica (mFHMRS) per mitigarla.

L'essenziale

Ecco una spiegazione semplice e creativa del documento, pensata per chiunque voglia capire di cosa si tratta senza impazzire con le formule matematiche.

Immagina di avere un castello di carte (il tuo sistema di crittografia) che permette di fare calcoli su dati segreti senza mai doverli aprire. Questo è il sogno della Crittografia Omomorfica: puoi manipolare i dati "in scatola" e, quando li apri alla fine, il risultato è corretto.

Il documento parla di un sistema chiamato FHMRS (uno schema basato su un'idea vecchia di Rivest) e di come gli autori abbiano dovuto aggiornarlo (diventando mFHMRS) perché c'era un buco nella sicurezza.

Ecco la storia divisa in tre atti:

1. Il Sistema Originale: La Cassaforte Perfetta (ma con un difetto)

Immagina che il sistema originale (FHMRS) sia una cassaforte speciale.

• Come funziona: Metti un messaggio segreto (es. "100") dentro una scatola. La cassaforte lo nasconde usando due chiavi magiche (numeri primi, chiamiamoli P e Q) e un numero segreto extra (U).
• Il trucco: La cassaforte divide il messaggio in due pezzi e li nasconde in due stanze diverse (modulo P e modulo Q).
• Il potere: Puoi sommare o moltiplicare questi pezzi senza sapere cosa c'è dentro. Se sommi due scatole chiuse, ottieni una nuova scatola che, una volta aperta, contiene la somma dei due messaggi originali. È come se potessi mescolare due cocktail in bicchieri opachi e ottenere il gusto corretto senza vedere gli ingredienti.

Il Problema (L'Attacco):
Gli autori hanno scoperto che questo sistema aveva un difetto fatale se qualcuno avesse fatto troppe moltiplicazioni.
Immagina di moltiplicare le scatole tante volte. Alla fine, il "rumore" (i numeri casuali aggiunti per nascondere il messaggio) diventa così grande che la scatola si espande.
Se un hacker vede il messaggio originale e la scatola corrispondente (un attacco chiamato Known Plaintext Attack), può fare un semplice calcolo matematico (il Massimo Comun Divisore) per scoprire il numero segreto U. Una volta che ha U, ha la chiave maestra per aprire tutte le scatole. È come se, guardando quanto è cresciuta la scatola dopo averci messo dentro un oggetto, l'hacker capisse esattamente quanto era grande il segreto usato per nasconderlo.

2. La Soluzione: La Nuova Cassaforte a "Molti Chiavi" (mFHMRS)

Per risolvere questo problema, gli autori hanno modificato il sistema, creando il mFHMRS.
Invece di usare solo due chiavi (P e Q), ora usano molte chiavi (P1, P2, P3... fino a Pn).

• L'Analogia del Puzzle:
  Nel vecchio sistema, il messaggio era diviso in 2 pezzi. Se l'hacker trovava il segreto, tutto crollava.
  Nel nuovo sistema, il messaggio è diviso in 10, 20 o più pezzi (come un puzzle con centinaia di tessere).
  Ogni pezzo è nascosto in una stanza diversa con una chiave diversa.

• Perché è più sicuro?
  Quando l'hacker prova a fare lo stesso trucco matematico (guardare la differenza tra messaggio e scatola), non trova più un unico numero segreto U facile da isolare. Trova solo un caos di numeri mescolati tra tante chiavi diverse.
  Per rubare il segreto, l'hacker dovrebbe indovinare tutte le chiavi contemporaneamente. È come cercare di indovinare la combinazione di 50 lucchetti diversi contemporaneamente, invece di uno solo.

3. Perché funziona davvero? (La Sicurezza)

Il documento spiega che questo nuovo sistema è resistente a tre tipi di "ladri":

1. Il Ladro che prova tutte le chiavi (Brute Force):
   Con così tante chiavi (numeri primi) grandi, il numero di combinazioni possibili è astronomico. Sarebbe come cercare un ago in un universo di paglia. Ci vorrebbero più anni di quelli che l'universo stesso esiste per provarle tutte.

2. Il Ladro Matematico (Attacchi Lattice):
   Questi sono hacker molto intelligenti che usano la geometria multidimensionale per trovare i segreti. Gli autori hanno dimostrato che, grazie alla dimensione delle chiavi e al numero di pezzi del puzzle, la "geometria" del sistema è così contorta che anche il matematico più furbo non riesce a trovare la strada dritta per il segreto.

3. Il Ladro che risolve equazioni:
   Se l'hacker ha sia il messaggio che la scatola, prova a scrivere delle equazioni per trovare i segreti. Ma nel nuovo sistema, le equazioni hanno così tante variabili sconosciute (i numeri casuali e le molte chiavi) che non si possono risolvere. È come cercare di trovare il prezzo di mele e pere sapendo solo il totale di 50 scontrini diversi, senza sapere quanti frutti c'erano in ognuno.

In Sintesi: Cosa abbiamo imparato?

• Il vecchio sistema (FHMRS) era come una porta blindata con un solo buco nella serratura: se qualcuno vedeva come si apriva una volta, poteva copiare la chiave.
• Il nuovo sistema (mFHMRS) è come un labirinto con centinaia di porte, ognuna con una serratura diversa. Anche se un ladro ne apre una, non può entrare perché le altre sono chiuse e non sa come aprirle.
• Il risultato: Possiamo fare calcoli su dati segreti (in cloud, su server pubblici) senza che nessuno, nemmeno il gestore del server, possa leggere i dati o rubare le chiavi.

È un passo avanti fondamentale per la privacy: permette di fare "magia" con i dati senza mai doverli rivelare.

Sommario tecnico

Ecco una sintesi tecnica dettagliata del documento in italiano, strutturata secondo le sezioni richieste.

Titolo: Modifiche allo Schema Rivest Modificato per l'Omomorfismo Completo (FHMRS)

Autori: Sona Alex e Bian Yang (NTNU, Norvegia)

---

1. Il Problema: Vulnerabilità dello Schema FHMRS Originale

Il documento analizza lo Fully Homomorphic Modified Rivest Scheme (FHMRS), uno schema crittografico a chiave simmetrica basato sul Teorema Cinese del Resto (CRT). Sebbene lo schema originale supportasse l'omomorfismo completo (addizioni e moltiplicazioni su dati cifrati), gli autori identificano una grave vulnerabilità di sicurezza quando lo schema supporta moltiplicazioni omomorfe consecutive.

• Attacco a Testo Piatto Conosciuto (KPA): Quando lo schema supporta $N$ moltiplicazioni consecutive, la dimensione dei parametri crittografici ($p$ e $q$) deve essere sufficientemente grande per garantire la correttezza del decifrato. Tuttavia, questa configurazione porta a una situazione in cui la riduzione modulare durante la cifratura non altera il valore interno $(m_i + g_i \cdot u)$.
• Meccanismo dell'Attacco: Un attaccante che possiede coppie (cifrato, testo in chiaro) può calcolare la differenza tra il cifrato e il testo in chiaro per ottenere direttamente il termine $g_i \cdot u$. Calcolando il Massimo Comun Divisore (GCD) di queste differenze per diverse coppie, l'attaccante può recuperare il parametro segreto $u$, compromettendo l'intero schema.

2. Metodologia: La Proposta mFHMRS

Per mitigare l'attacco KPA descritto, gli autori propongono una versione modificata chiamata Modified FHMRS (mFHMRS). Le modifiche fondamentali includono:

• Aumento del Numero di Moduli (Shares): Invece di utilizzare due primi segreti ($p, q$), lo schema mFHMRS genera un insieme di $N+S$ primi segreti ($p_1, p_2, ..., p_{N+S}$), dove $N$ è il numero di moltiplicazioni supportate e $S$ è un parametro di sicurezza aggiuntivo.
• Ridimensionamento dei Parametri:
  • I primi $p_i$ sono scelti in modo che la loro dimensione in bit ($l_{p_i}$) sia inferiore alla somma dei bit di $u$ e del numero casuale $g$ ($l_u + l_g + 1$). Questo impedisce che il valore $(m_i + g_i \cdot u)$ rimanga invariato dopo la riduzione modulare, rendendo impossibile l'estrazione diretta di $g_i \cdot u$.
  • Viene impostato il vincolo $l_u > l_{p_i}$ per garantire che le differenze tra i numeri casuali $g$ portino a differenze imprevedibili nei termini di errore $k_i$, rendendo inefficaci gli attacchi basati su equazioni lineari.
• Generazione dei Cifrati: Il cifrato è ora una tupla di $N+S$ componenti, ciascuna calcolata come $(m_i + g_i \cdot u) \mod p_j$.
• Decifrato: Utilizza il Teorema Cinese del Resto generalizzato per ricostruire il valore intero $(m_i + g_i \cdot u)$ dai $N+S$ resti, seguito da una riduzione modulare per $u$ per recuperare il messaggio originale.

3. Contributi Chiave

1. Identificazione della Vulnerabilità: Dimostrazione formale che lo schema FHMRS originale è vulnerabile a un attacco KPA quando supporta moltiplicazioni omomorfe, a causa della relazione lineare tra cifrato e testo in chiaro.
2. Progetto di uno Schema Resiliente (mFHMRS): Introduzione di una struttura basata su multipli moduli segreti ($N+S$) che rompe la linearità sfruttabile nell'attacco originale.
3. Analisi di Sicurezza Completa:
   • Attacchi Brute-Force: Analisi dello spazio delle chiavi, dimostrando che la complessità cresce esponenzialmente con il numero di moduli segreti.
   • Attacchi Basati su Reticoli (Lattice-based): Dimostrazione che l'algoritmo LLL (Lenstra–Lenstra–Lovász) non riesce a trovare vettori brevi sufficienti per recuperare i segreti $u$ o $p_i$, grazie alla scelta accurata delle dimensioni dei bit ($l_p, l_u, l_g$).
   • Attacchi a Equazioni Lineari: Analisi che mostra come l'imprevedibilità delle differenze tra i numeri casuali $g$ e i termini di errore $k$ renda risolvibile il sistema di equazioni solo con uno sforzo computazionale proibitivo.
4. Parametri di Sicurezza Formalizzati: Definizione di vincoli matematici precisi per la scelta delle dimensioni dei bit dei parametri segreti in funzione della sicurezza desiderata ($\lambda$), del numero di moltiplicazioni ($N$) e delle addizioni ($A$).

4. Risultati

• Robustezza contro KPA: Lo schema mFHMRS resiste efficacemente agli attacchi a testo piatto conosciuto. Anche con la conoscenza di coppie (cifrato, testo in chiaro), l'attaccante non può isolare $u$ o i primi $p_i$ a causa della riduzione modulare efficace e della struttura a più moduli.
• Resistenza agli Attacchi Lattice: L'analisi teorica conferma che la lunghezza dei vettori nel reticolo costruita dall'attaccante supera la soglia di successo degli algoritmi di riduzione (come LLL), rendendo il recupero dei segreti computazionalmente impossibile.
• Correttezza del Decifrato: Viene dimostrato che, rispettando i vincoli dimensionali ($l_{p_i} > \frac{(N+1)(l_g + l_u + 1) + A}{N+S}$ e $l_u > l_M$), il processo di decifrato ricostruisce correttamente il messaggio originale dopo $N$ moltiplicazioni e $A$ addizioni.
• Complessità Computazionale: Per un livello di sicurezza di 128 bit ($\lambda=128$) con una moltiplicazione ($N=1$), lo schema richiede primi di circa 128-130 bit e un cifrato di dimensioni massime di 384 bit, mantenendo un equilibrio tra sicurezza e efficienza.

5. Significato

Questo lavoro è significativo nel campo della crittografia omomorfa per i seguenti motivi:

• Correzione di un Difetto Critico: Risolve una falla fondamentale in uno schema esistente che ne limitava l'uso pratico in scenari reali dove la moltiplicazione è necessaria.
• Approccio Simmetrico Efficiente: Propone una soluzione basata su chiavi simmetriche (più veloce delle controparti a chiave pubblica come RSA o ECC in termini di operazioni omomorfe) che mantiene la sicurezza contro attacchi moderni basati su reticoli.
• Guida per l'Implementazione: Fornisce linee guida pratiche e formule matematiche per dimensionare i parametri crittografici in base alle esigenze specifiche dell'applicazione (numero di operazioni previste), facilitando l'adozione sicura di questo schema in ambienti cloud e di calcolo distribuito.

In sintesi, il documento trasforma lo FHMRS da uno schema teoricamente interessante ma vulnerabile a una proposta pratica e sicura (mFHMRS), fornendo un'analisi rigorosa delle sue difese contro le principali minacce crittografiche attuali.