Paillier este un cifr securizat CPA, astfel încât orice putem deduce din textele cifrate necesită cheia privată. Astfel, „Vreau să găsesc…” necesită ca „Eu” să aibă cheia privată, iar apoi „Am o matrice criptată” implică „Eu” să pot descifra fiecare dintre textele cifrate, ceea ce face ca întrebarea să fie discutabilă.
Prin urmare, vom schimba declarația problemei în: avem cel mult $k$ întreg mic $m_i\in[0,\ell)$ (în problema pe care o dorim $k\ge6$, și $\ell>20$); și vrem o metodă publică pentru a le exprima $m_i$ criptat ca $c_i$ folosind Criptosistemul Paillier și combinați $c_i$ într-un singur $c$ așa cum facem noi în Paillier. Asta înseamnă a face un produs modulo $n$ al $c_i$, și opțional înmulțiți modulo $n$ printr-un text cifrat pentru $0$ pentru a masca în continuare rezultatul. Vrem lucruri astfel încât o persoană care deține cheia privată să poată determina $c$ dacă $0$ a fost prezent în setul de date inițial al $m_i$. Asta schimbă două lucruri importante în declarația inițială a problemei:
- Există această noțiune de a combina textele cifrate $c_i$ în $c$, cu $c_i$ indisponibil pentru deținătorul cheii private.
- Nu avem „o matrice criptată”. Vrem să avem unul, dar suntem liberi să definim cum este făcut, atâta timp cât este cu o criptare care utilizează Paillier. Fără o astfel de libertate, nu există nicio soluție, deoarece decriptarea Paillier va permite doar obținerea $m=(\sum m_i)\bmod n$ și nu există nicio modalitate de a spune din asta dacă an $m_i$ a fost $0$.
Iată ceva în care nu vom ști doar dacă $0$ a fost prezent în $m_i$, vom ști, de asemenea, de câte ori fiecare număr întreg în $[0,\ell)$ a fost prezent în matricea originală.
În acest sens, codificăm $m_i$ în $m'_i=(k+1)^{m_i}$ înainte de a aplica criptarea Paillier. Paillier ne va lăsa să combinăm textele cifrate $c_i$ apoi descifrați combinația $c$ în $m'=(\sum m'_i)\bmod n$. Din $m'$ putem deduce de câte ori fiecare număr întreg în $[0,\ell)$ a fost prezent în $m_i$, atâta timp cât $k(k+1)^{\ell-1}<n$, prin exprimare $m'$ în bază $k+1$ și privind degetele/membrelor. Voi sări peste algebra pentru cum și voi folosi un exemplu în zecimală (astfel $k=9$). $m_0=2$, $m_1=4$, $m_2=5$, $m_3=10$, $m_4=0$, $m_5=20$ codifică pentru $m'_0=100$, $m'_1=10000$, $m'_2=100000$, $m'_3=10000000000$, $m'_4=1$, $m'_5=0$, $m'_6=100000000000000000000$ în zecimală. Vom lua $m'=1000000000010000110101$, din care putem spune că a fost exact câte unul din fiecare $0$, $2$, $4$, $5$, $10$, $20$ în matricea originală a $m_i$, privind poziția cifrelor diferite de zero și văzând că sunt $1$. Dacă $20$ a fost schimbat în $0$, rezultatul ar fi $m'=10000110102$ și am ști că sunt două $m_i=0$, deoarece cifra cea mai din dreapta este $2$.
Întrebarea nu spune ce noi nu doresc ca deținătorul cheii private să poată determina din $c$. Poate că vrem să limităm asta la a determina dacă a existat o $0$, cu la fel de puține scurgeri despre câte $0$ pe cat posibil.
În acest sens, putem codifica fiecare $m_i\ne0$ la $m'_i=0$, și fiecare $m_i=0$ la un număr întreg $m'_i$ în $[1,\l etaj n/k\rfloor)$ alese la întâmplare cu o distribuție puternic părtinitoare către valori scăzute. Când decriptarea combinației este zero, se știe că nu a fost zero în $m_i$, si nimic altceva. Altfel, se știe că a fost zero și s-au scurs puține informații despre câte. Distribuția poate fi optimizată pentru a minimiza această scurgere, aceasta fiind lăsată ca un exercițiu cititorului.
Este posibil să rafinați lucrurile astfel încât unul cu cheia privată și $c_i$ Pot găsi $m_i$, dar (ca mai sus) unul cu cheia privată și $c$ pot obține puține informații despre $m_i$, dincolo de aceea este $0$. Nu voi detalia pentru că asta nu este în enunțul problemei.
La fel de multe lucruri de criptare homomorfă, acestea sunt sisteme teoretice drăguțe cu mici probleme de potrivire din viața reală.
