Căutare sigură din punct de vedere criptografic a valorii într-un set

Caut o soluție elegantă la problema care ar putea părea banală de a căuta o anumită valoare într-un set cunoscut de valori fără a dezvălui ce valoare căutăm. Permiteți-mi să o descriu într-un mod clasic:

Alice își va sărbători în curând ziua de naștere și vrea să știe dacă cineva din clasa ei are ziua de naștere în aceeași zi cu ea. Din păcate, singura persoană care știe datele de naștere ale tuturor oamenilor din clasă (cu excepția celei a Alicei) este Malory. Cum ar putea Alice să o întrebe pe Malory dacă cineva are ziua de naștere în aceeași zi, fără să-și dezvăluie propria dată?

Presupunere:

1. Malory este deschisă să o ajute pe Alice și va răspunde în mod legitim la orice întrebări. Cu toate acestea, ea poate răspunde doar da sau nu.
2. Alice o va întreba o singură dată pe Malory. Malory nu o poate influența pe Alice să o facă să pună din nou aceeași întrebare.Cu toate acestea, în viitor, Alice s-ar putea să întrebe singură despre diferitele date (de exemplu, ziua de naștere a lui Bob).
3. Alice nu are nevoie și nici nu vrea să știe datele de naștere ale tuturor celor dintr-o clasă. Ea ar dori să obțină un răspuns de la Malory, punând o singură întrebare.

O modalitate destul de simplă de a aborda această problemă este aplicarea hash. Alice își împinge ziua de naștere și îi transmite aceste informații lui Malory, cerându-i în același timp să pună în ordine zilele de naștere ale tuturor persoanelor pe care le cunoaște și să-i spună dacă se potrivește. Problema este că Malory, care ar dori să știe ziua de naștere a lui Alice, poate enumera toate datele posibile (deoarece entropia de intrare este scăzută) și poate verifica una câte una dacă se potrivește cu ceea ce a întrebat Alice. Aș dori să elimin această amenințare.

M-am gândit să aplic maparea unu-la-mulți la ziua de naștere. Deoarece o dată ar putea fi reprezentată de mai multe valori, atacul de enumerare ar deveni imposibil de fezabil. Prima problemă este că nu văd o modalitate ușoară de a o lăsa pe Malory să facă o comparație matematică atomică cu setul ei de date. A doua problemă este că, dacă se poate face o astfel de comparație, este încă posibil ca Malory să facă un nou set și să facă din nou operația de căutare (ceea ce se traduce efectiv prin atac de enumerare). Astfel, maparea unu-la-mulți pe care o aplică Alice ar trebui să fie parametrizată de caracteristica unică a unui set în care Malory îl caută.

Sper că nu am adus prea multă confuzie și voi aprecia orice ajutor, referințe, mențiuni de algoritmi sau probleme similare! De asemenea, voi aprecia opinia dvs. dacă credeți că această problemă nu poate fi rezolvată cu ipotezele date! Dacă unele dintre ele sunt neclare, anunțați-mă și voi face tot posibilul să-mi clarific intenția.

Tu descrii problema 1 din $n$ Transfer neglijent cu $n=366$ dacă se cere ca Alice să nu primească informații străine. Metodele lui Kolesnikov et al în lucrarea lor âPRF neîntemeiat eficient în loturi cu aplicare la intersecția setului privatâ dă o idee a ceea ce este posibil.

Dacă este acceptabil ca Alice să obțină informații suplimentare, atunci problema este una dintre ele regăsirea informațiilor private. Lucrarea de sondaj a lui Ostrovsky și Skeith âUn sondaj privind regăsirea informațiilor private într-o singură bază de date: tehnici și aplicații â oferă o bună imagine de ansamblu.

A doua abordare, mai simplă, datorită unui comentariu al lui @Mikero:

Alice alege o cheie privată uniform aleatorie $b$. Ziua de naștere a lui Alice este de $k$a-a zi a anului. Alice trimite $A = bH_p(k)$ la Malory, unde funcţia $H_p()$ înseamnă a hash intrarea și a interpreta rezultatul ca un punct EC.

Malory alege o cheie privată uniform aleatorie $e$. Malory are o funcție $F_e(i)$ care iese $eH_p(i)$ dacă cel puțin o persoană se naște în acea zi a anului și, în caz contrar, emite un punct EC ales aleatoriu.

Pentru fiecare valoare a $i$ astfel încât $0\leq i \leq 365$, trimite Malory $F_e(i)$ lui Alice. În plus, Malory trimite $Q = eA$ lui Alice.

calculează Alice $Z = b^{-1}Q == b^{-1}eA == b^{-1}ebH_p(k) == eH_p(k)$.

Alice verifică apoi dacă $Z$ se potrivește cu oricare dintre cele 366 de ieșiri ale $F_e(i)$ pe care Malory i-a trimis-o lui Alice. Dacă există o potrivire, atunci Alice împarte ziua de naștere cu altcineva.

Explicație: Am creat un „1-OPRF”, ceea ce înseamnă o funcție pseudo-aleatorie uită pe care Alice o poate interoga o dată cu asistența oarbă a lui Malory, dar pe care Malory o poate interoga de mai multe ori.

PRF este pur și simplu Malory orbește un punct EC $H_p(i)$ (Unde $H_p(i)$ reprezintă o anumită zi $i$ al anului ca punct EC), cu cheia sa privată $e$, prin calcul $eH_p(i)$. Din cauza problemei logului discret al curbei eliptice, niciun observator (inclusiv Alice) nu poate prezice rezultatul $eH_p(i)$ pentru orice $i$ fără cunoaștere a secretului $e$. Aceasta înseamnă că atunci când nimeni nu se naște într-o anumită zi, Alice nu poate spune că Malory a trimis un punct EC aleatoriu în loc de ieșirea reală a PRF, deoarece ieșirea PRF este imprevizibilă pentru Alice.

Alice își orbește intrarea în PRF prin alegerea unui factor orbitor $b$ si trimiterea $bH_p(k)$ lui Malory în loc să trimită (și astfel să dezvăluie) $k$. Alice dezactivează răspunsul inversând înmulțirea cu $b$, și este astfel capabil să interogheze PRF fără ca Malory să cunoască intrarea pe care o folosește Alice.

Consecința este că Malory i-a trimis Alicei o listă de puncte EC care includ doar rezultatul real al PRF pentru acele zile din an în care se naște cel puțin o altă persoană. În plus, Alice a reușit să interogă orbește PRF-ul pentru rezultatul zilei sale de naștere și poate vedea dacă acel rezultat apare în lista de posibile ieșiri PRF trimise de Malory.

Malory nu a învățat $k$, iar Alice nu poate afla altceva decât dacă își împarte ziua de naștere cu cel puțin o altă persoană.

O abordare este de a face 1-din-n transfer neglijent. Malory îi va trimite lui Alice o listă cu 366 de valori boolean criptate (pentru a permite zilele de naștere pe 29 februarie), unde fiecare boolean va indica dacă cineva are o zi de naștere în acea zi a anului.Alice va putea decripta doar unul dintre cei 366 de valori boolean și, astfel, va putea ști doar dacă altcineva are o zi de naștere în acea zi a anului.

Articolul wikipedia la care l-am legat în paragraful de mai sus face referire la mai multe abordări de implementare pentru a obține un transfer neglijent 1-din-n. Iată o abordare la care am gândit-o tocmai acum (cu meritul lui @IlmariKaronen pentru o îmbunătățire foarte elegantă):

Alice se naște în ziua $k$ a anului, unde $0\leq k\leq 365$. Alice trimite cheia publică $P = xG-kH$ la Malory, unde $x$ este o cheie privată scalară uniform aleatorie. $H$ se calculează ca $H = H_p(G)$, unde funcția $H_p()$ înseamnă să trimiți valoarea și să interpretezi rezultatul ca un punct EC. Alegerea $H$ în acest mod înseamnă jurnalul discret al $H$ w.r.t. $G$ este de necunoscut, adică $h$ nu poate fi cunoscut astfel încât $H==hG$.

Malory calculează 366 de chei publice $\{Q\}$ a formei $Q_i=P+iH$ pentru toate valorile de $i$ Unde $0\leq i\leq 365$.

Cheia privată corespunzătoare fiecărei chei publice $Q_i$ va fi $q_i == x - kh + ih == x+(i-k)h$.

Din moment ce am demonstrat deja asta $h$ este de necunoscut, asta înseamnă că $q_i$ va fi cunoscut de Alice doar când $i==k$, in care caz $q_k$ va fi egal cu $x$.

Astfel, Malory va fi calculat 366 de chei publice pentru care Malory poate fi sigură că Alice poate cunoaște doar cheia privată corespunzătoare uneia dintre ele.

Pentru fiecare zi a anului $i$, Malory folosește schema El Gamal după cum urmează: Malory alege un scalar uniform aleatoriu $e_i$și îi oferă lui Alice perechea $(E_i, F_i)$ Unde $E_i = e_iG$, $F_i = e_iQ_i + H_p(v_i)$ si unde $v_i$ va fi specificat ca $0$ dacă nimeni nu are o zi de naștere în acea zi a anului, sau ca $1$ dacă cel puțin o persoană are o zi de naștere în acea zi a anului.

Pentru a decripta $v_k$, calculează Alice $V_k = F_k - xE_k$. Alice verifică apoi dacă $V_k\overset{?}{=}H_p(0)$ sau $V_k\overset{?}{=}H_p(1)$, și astfel știe dacă $v_k$ este $0$ sau $1$. Acest lucru funcționează pentru că $q_k==x$ și $Q_k==xG$, Așadar $xE_k==x\cdot e_kG==e_k\cdot xG==e_kQ_k$.

Alice va fi putut determina doar dacă altcineva s-a născut în ziua respectivă $k$ al anului, iar Malory nu va putea determina $k$.

Există o nouă regăsire a informațiilor private cu sisteme complet homomorfe,

• 2014 PIR eficient la lățime de bandă de la NTRU Yarkin Doröz, B. Sunar, Ghaith Hammouri

Aceasta este o schemă de criptare privată care poate avea valoarea la index $i$ din matricea de pe serverul semi-onest. Serverul nu învață nimic și returnează doar valoarea la index $i$. Putem modifica acest lucru ca;

1. Mallory criptează toate zilele de naștere existente $b_i$, $0 \leq i \leq 366 $ cu cheia publică FHE a lui Alice. (Criptarea 366$\cdot 8$ biți, nu neapărat toate zilele, zilele de naștere existente sunt suficiente și acest lucru economisește spațiu în seturi mari.

   $$c_i = \operatorname{FHE-Enc}(A_{pub}, b_i)$$

   Dacă folosim bazate pe biți (HLibe, TFHE), atunci fiecare $c_i$ este o matrice de dimensiune 8.

2. Alice își trimite ziua de naștere $A$ criptat cu cheia ei publică pentru Mallory (criptare pe 8 biți).

   $$a = \operatorname{FHE-Enc}(A_{pub}, A)$$

3. Mallory execută Circuitul de egalitate FHE la fiecare zi de naștere criptată

   $$t_i = \operatorname{FHE-Compare}(A_{pub}, c_i,a)$$

4. Mallory SAU rezultatele cu FHE folosind abordarea arborelui binar pentru a reduce adâncimea circuitului (este posibil cu însumarea în loc de SAU) și returnați rezultatul înapoi lui Alice.

   $$o = \operatorname{FHE-OrAll}(A_{pub}, [t_0,\ldots,t_n])$$

5. Alice decriptează rezultatul pic cu cheia lor privată;

   $$ b = \operatorname{FHE-Dec}(A_{priv})$$

   • dacă $b=1$ atunci există cel puțin un student cu dată $A$
   • dacă $b=0$ atunci nu exista nici un student cu data $A$.

Ce este garantat;

1. Mallory nu poate afla care sunt datele interogate $A$ deoarece este criptat cu FHE - securitate semantică există.
2. Mallory nu poate induce datele interogate din rezultat din același motiv ca mai sus; din $(A,o)$.
3. Circuitul nu dezvăluie nimic despre elementele interne ale datelor, în afară de ce funcție este calculată - circuitul calculează existența datelor fără a dezvălui rezultatul.
4. Alice află doar existența zilei de naștere, nimic mai mult! Alice primește doar un pic $b$, există sau nu. Acest lucru nu returnează numărul zilelor de naștere egale.
5. Alice întreabă o singură dată.
6. Mallory trimite doar criptare de un bit $b$! Prin urmare, o schemă destul de eficientă în bandă.

1. Mallory pregătește o matrice de biți de dimensiunea 366 inițializată la zero. $$B = [b_0,b_1,\ldots,b_{366}] = 0$$

2. Mallory a stabilit zilele de naștere existente la 1. Like; $$B = [0,0,1,\ldots,0] $$

3. Mallory criptează matricea de biți cu cheia publică a lui Alice (cheia publică FHE) și obține o altă matrice de dimensiunea 366.

   $$c_i = \operatorname{FHE-Enc}(A_{pub}, B[i]) \;\; \text{pentru }\; 0\leq i \leq 366 $$

4. Alice pregătește o altă matrice de biți de dimensiunea 366 în care numai ziua ei de naștere este setată la 1 rest setată la 0. $$A = [0,0,0,\ldots,1,\ldots,0] $$

5. Similar cu Mallory, Alice are cheia ei publică și trimite matricea rezultată către Mallory.

   $$a_i = \operatorname{FHE-Enc}(A_{pub}, A[i]) \;\; \text{pentru }\; 0\leq i \leq 366 $$

6. Mallory execută cu înțelepciune componenta de operare FHE-AND pe matricele criptate. $$c_i = \operatorname{FHE-And}(A_{pub}, A[i], B[i])$$

7. Mallory SAU biți din matricea rezultată și returnează rezultatul înapoi la Alice.

   $$b = \operatorname{FHE-OrAll}(A_{pub}, [c_0,\ldots,c_{366}])$$

8. Alice decriptează rezultatul pic cu cheia lor privată;

   $$ b = \operatorname{FHE-Dec}(A_{priv})$$

   • dacă $b=1$ atunci există cel puțin un student cu dată $A$
   • dacă $b=0$ atunci nu exista nici un student cu data $A$.

Ce este garantat;

1. La fel ca schema de bază.
2. De data aceasta, în loc să cripteze 9 biți, Alice criptează 366 de biți (creștere de aproximativ 40 de ori a costului/timpului inițial de trimitere)
3. Mallory, pe de altă parte, a primit multă îmbunătățire a timpului și a memoriei
   1. Nu este nevoie de o operațiune grea de egalitate FHE.
   2. Dimensiunea textului cifrat stocat a fost redusă cu ~40.
4. Rezultatul, pe de altă parte, este încă criptarea de 1 bit.
5. Această schemă economisește mult timp în proces.