Implementări practice ale apartenenței la set privat

Declarație problemă

Imaginați-vă că aveți un set (fără elemente duplicat) de ex. S1 = {'a', 'b', 'c'}.

Doriți să partajați o reprezentare privată (și, în mod ideal, atât de mică ca dimensiune, cât și protejată de integritate) a acestui set cu o altă parte (care ar putea avea chei pre-partajate cu dvs.), unde poate verifica (da sau nu) dacă un element la alegere de exemplu. 'b' face parte din set S1.

Care este cea mai simplă combinație de primitive criptografice pe care o puteți folosi pentru a rezolva acest lucru?

Indicatii pana acum

S-ar părea că hashingul setului ar fi ideal (spre deosebire de simpla criptare) din cauza constrângerilor de dimensiune.

Dacă dorim să facem verificări opace de membru, probabil că este nevoie de un fel de criptare homomorfă.

Am citit despre Private-Set-Intersection și Private-Set-Membership, cu toate acestea, implementările pe care le-am găsit nu sunt minime și au alte funcționalități „chiuvetă de bucătărie” care nu sunt de dorit.

Câteva lecturi până acum

• https://engineering.fb.com/2019/03/01/security/homomorphic-hashing/ (https://eprint.iacr.org/2019/227.pdf)
• https://github.com/google/private-membership
• Intersecție cu set privat mai rapid pe baza Extensie OT (pdf)
• Potrivire privată eficientă și intersecție set (pdf)
• Intersecție cu set dezechilibrat mai rapid (pdf)

Ai nevoie doar de un PRF ignorant. Alice calculează și trimite $F_k(x)$ pentru toți $x \în S$, Unde $F$ este un PRF. Alice și Bob folosesc un protocol OPRF pentru a-l lăsa pe Bob să învețe $F_k(y)$ pentru o valoare $y$ la alegerea lui. Dacă $y \în S$ atunci Bob va vedea o potrivire cu valorile trimise de Alice. Dacă $y \nu\în S$ apoi pseudoaleatoria a $F$ implică faptul că $\{ F_k(x) \mid x \in S \}$ toate par aleatorii chiar și date $F_k(y)$. Cu alte cuvinte, aceste valori nu scurg nimic despre valorile specifice ale $x$ în $S$.

Există un protocol OPRF simplu semi-onest pentru PRF $F_k(x) = H(x)^k$, Unde $H$ este un oracol aleatoriu. Funcționează așa:

• Bob alege aleatoriu $r$ si trimite $Y = H(y)^r$ lui Alice.
• Alice trimite $Z = Y^k = H(y)^{rk}$ lui Bob.
• Bob calculează ieșirea $Z^{1/r} = H(y)^k = F_k(y)$.

OPRF-urile securizate rău intenționate nu sunt mult mai scumpe. Puteți găsi câteva Aici și Aici.

Acesta este ceva la care am lucrat.

Aș dori ca „mic” de mai jos să fie mult mai mic decât cel care urmează. Dar acest lucru ar funcționa în scopurile dvs. pentru un set de șiruri binare $S$, hash criptografic $H(x)$, și cheie pre-partajată $k$.

$H(S)=\text{sortare} \{H(x) | x \în S\}$. Numiți asta martorul public pentru $S$. Puteți ascunde dimensiunea setului incluzând hashuri aleatorii la un anumit modul de lungime. Acesta ar fi un martor public fără integritate, dar dă ideea de bază.

Presupunând dimensiunea de $x$ este în general mult mai mare decât $H(x)$, reprezentarea martorului $H(S)$ pentru $S$ este mic comparativ cu reprezentarea pt $S$.

Dacă doriți să restricționați acest lucru la cei cu o cheie simetrică pre-partajată k: (folosesc $+$ pentru adăugare pentru a distinge de setul „astfel încât”)

$H^2(k+S)=\text{sort} \{H(k+H(k+x)) | x \în S\}$. Adăugați o sumă de control cu ​​cheie pentru o verificare a integrității.

$\text{martor pentru S}: H^2(k+S) + H(k+H^2(k+S))$

Din nou, pentru a ascunde dimensiunea $S$ ai putea întotdeauna să adaugi hashe-uri aleatorii la o dimensiune maximă sau (imperfect) la un modul de dimensiune.

Se verifică calitatea de membru: trimite $(n,H(k+n) \bigoplus H(k+x))$ Unde $n$ este un număr crescător (poate fi implicat, cum ar fi un marcaj de timp). Destinatarul poate descoperi $H(k+x)$ si apoi calculeaza $H(k+H(k+x))$ pentru a vedea dacă este în setul de martori.