Am venit cu o schemă FHE destul de simplă, care nu ar trebui să funcționeze, dar nu îmi pot da seama cum se defectează. Orice ajutor în acest sens este apreciat!

Prima parte

În primul rând, rețineți că dacă am avea un câmp abelian în care calcularea inversului multiplicativ a fost dificil, atunci am putea construi o schemă homomorfă pentru adunare și înmulțire trivial. Să presupunem că mesajul pe care vrem să-l criptăm este $m$. Apoi eșantionăm un element aleatoriu, $e$ (astfel încât să știm $e^{-1}$), iar textul nostru cifrat devine pur și simplu $c=m\cdot e$. Dăm serverului $m \cdot e$ și $e$. Rețineți că, deoarece este dificil să găsiți inversul multiplicativ, serverul nu poate să calculeze pur și simplu $e^{-1}$ și apoi înmulțiți asta cu $m\cdot e$. Oricum, să presupunem că serverul a vrut să efectueze o adăugare cu textul cifrat și o constantă $a$. Pur și simplu ar calcula $a \cdot e$, apoi adăugați-l la $m\cdot e$ a obține $(a+m)\cdot e$. Dacă aceasta nu ar fi o constantă (un alt mesaj criptat), am putea pur și simplu să adăugăm mesajele împreună. Înmulțirea este puțin mai dificilă. Acum, va trebui să ținem evidența câte „e” sunt în textul nostru cifrat. Când clientul dă serverul pentru prima dată $c$, exponentul lui $e$ este pur și simplu $1$, astfel încât să putem stoca acel punct de date ca $(c,1)$. Dacă avem un alt text cifrat $câ = mâ e$, și vrem să le înmulțim împreună, putem găsi asta $(c,1) \cdot (câ,1) = (c\cdot câ,2)$. Rețineți că ceea ce are serverul este $(m \cdot mâ)e^2$. Când serverul dă această valoare înapoi clientului, acesta va da înapoi $(c\cdot câ,2)$, care îi spune clientului că sunt două $e$s în produs. Prin urmare, se poate înmulți pur și simplu $c\cdot câ$ de $e^{-2}$ a obține $m \cdot mâ$. Acum ce se întâmplă dacă calculul nu s-ar fi încheiat aici? Dacă serverul ar avea trei texte cifrate, $c_1,c_2,c_3$, și a vrut să calculeze $c_1\cdot c_2+c_3$. Mai întâi ar calcula $c_1 \cdot c_2 = (c_1c_2,2)$. Acum vrea să calculeze $(c_1c_2,2) + (c_3,1)$. Pentru a face acest lucru, trebuie să calculeze $c_3\cdot e$ a obține $(c_3,2)$, și atunci se poate pur și simplu $(c_1c_2,2) + (c_3,2)=(c_1c_2+c_3,2)$. Când serverul dă această valoare înapoi, clientul se poate multiplica pur și simplu cu $e^{-2}$ si are $m_1m_2+m_3$.

Partea a doua

Pentru a găsi de fapt un câmp în care nu putem calcula inversul este dificil. Soluția cu care am venit (în care nu sunt atât de încrezător) este să valorificăm faptul că poți calcula doar inverse în $\mathbb{F}_p$ dacă știi ordinea câmpului. Altfel este imposibil. Prin urmare, clientul ar putea lucra cu numerele întregi $\mod p$, dar nu i-ar spune niciodată acest lucru serverului. Apoi, ar alege unele aleatorii $e$, calculează $m\cdot e \mod p$, dă-l serverului, iar serverul ar putea face toate calculele cu numărul. Dacă rezultatul calculului este $R$, serverul poate pur și simplu să dea înapoi $(R,n)$ către client (unde $n$ este cantitatea de $e$s), și apoi clientul ar putea pur și simplu să calculeze $R e^{-n} \mod p$ pentru a obține răspunsul. Motivul pentru care acest lucru funcționează este că modulul este complet homomorf; o poți face la mijlocul calculului, la fiecare pas al calculului, sau pur și simplu o faci la sfârșit. În esență, clientul face modulo la început, mascând $m$, iar apoi lasă serverele să facă calcule pe el. Când primește rezultatul, doar calculează modulo. Acest lucru ar fi echivalent cu serverul care face toate calculele în aritmetică modulară tot timpul, dar realizăm acest lucru fără a spune serverului ce $p$ este. Din păcate, acest lucru este ineficient, deoarece aceste numere ar putea crește pentru a avea lungimi arbitrar mari. Pentru a remedia această problemă, clientul ar putea calcula un alt prim, $q$, în timpul fazei de inițializare și apoi calculați $N=pq$. Clientul dă $N$ către server (rețineți că, din ipoteza RSA, acest lucru nu dezvăluie nimic despre $p$). Apoi, serverul ar putea face toate calculele modulo $N$, și, prin urmare, nu ar avea numere întregi care cresc la o dimensiune arbitrar de lungă. Motivul pentru care funcționează este că din moment ce $N$ este un multiplu al $p$, dacă $x \equiv a \mod N$, atunci $x \equiv a \mod p$ (vezi comentariul la acest post, care este ceea ce mi-a dat inspirația pentru această idee).

Calcularea inversului a ceva $\bmod N$ nu este deosebit de greu din pacate. În special, $x^{-1}\bmod N$ este valoarea în $\mathbb{Z}_N$ astfel încât $xx^{-1}\equiv 1\bmod N$. Rețineți că dacă am ști întregul $a, b$ astfel încât

$$aN + bx = 1$$

atunci $x^{-1}\equiv b\bmod N$. Acest lucru se datorează faptului că ecuația de mai sus $\bmod N$ este $ bx\equiv 1\bmod N$, asa de $b$ este „lucru care se înmulţeşte cu $x$ pentru a obține 1 $\bmod N$", adică inversul său.

Cum am putea ajunge $a, b$ astfel încât $aN + bx = 1$? The algoritm euclidian extins ne va da $a, b$ astfel încât $aN+bx= \mathsf{gcd}(x, N)$. Din pacate, $x$ fiind inversabilă $\bmod N$ este echivalent cu $\mathsf{gcd}(x, N) = 1$, deci algoritmul euclidian extins calculează inversele $\bmod N$, și vă sparge criptosistemul destul de eficient (este ceva de genul $O((\log N)^3)$ iirc).