Diferenciální soukromí

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 15. února 2022; kontroly vyžadují 2 úpravy .

Diferenciální soukromí je soubor metod, které poskytují nejpřesnější dotazy do statistické databáze a zároveň minimalizují možnost identifikace jednotlivých záznamů v ní.

Úvod

Diferenciální soukromí je matematická definice ztráty citlivých dat jednotlivců, když jsou jejich osobní informace použity k vytvoření produktu. Termín byl vytvořen Cynthia Dwork v roce 2006 [1] , ale je také použit v dřívější publikaci Dwork, Frank McSherry , Kobe Nissim a Adam D. Smith [2] . Práce se opírá zejména o výzkum Nissima a Irita Dinura [3] [4] , kteří prokázali, že není možné publikovat informace ze soukromé statické databáze bez odhalení některých soukromých informací a že je možné zpřístupnit celou databázi zveřejněním výsledků celkem malého počtu žádostí [4] .

Po provedení studie se ukázalo, že není možné zajistit důvěrnost ve statistických databázích pomocí stávajících metod, a v důsledku toho vznikla potřeba nových metod, které by omezily rizika spojená se ztrátou soukromých informací obsažených ve statistice. databáze. V důsledku toho byly vytvořeny nové metody, které ve většině případů umožňují poskytovat přesné statistiky z databáze a zároveň poskytují vysokou úroveň důvěrnosti [5] [6] .

Princip a ilustrace

Diferenciální soukromí je založeno na zavedení náhodnosti do dat.

Jednoduchý příklad rozvinutý ve společenských vědách [7] je požádat osobu, aby odpověděla na otázku "Máte atribut A?" podle následujícího postupu:

hodit si mincí
Pokud se objeví hlavy, odpovězte na otázku upřímně.
V opačném případě hoďte znovu, pokud se objeví hlavou, odpovězte "Ano", pokud jsou to ocasy - "Ne"

Důvěrnost vzniká proto, že z odpovědi nelze s jistotou poznat, zda má člověk daný atribut. Tyto údaje jsou však významné, protože kladné odpovědi pocházejí od čtvrtiny lidí, kteří tento atribut nemají, a tří čtvrtin těch, kteří jej skutečně mají. Pokud tedy p je skutečný podíl lidí s A, pak očekáváme, že dostaneme (1/4) (1- p) + (3/4) p = (1/4) + p / 2 kladné odpovědi. Proto lze odhadnout R.

Formální definice a příklad použití

Nechť ε je kladné reálné číslo a A je pravděpodobnostní algoritmus , který bere jako vstup sadu dat (představuje akce důvěryhodné strany, která má data). Označte obrázek A im A . Algoritmus A je ε - diferenciálně soukromý , pokud pro všechny soubory dat a lišící se jedním prvkem (tj. data jedné osoby), stejně jako všechny podmnožiny S množiny im A : $D_{1}$ $D_{2}$

$P[{\mathcal {A}}(D_{1})\in S]\leq e^{\epsilon }\times P[{\mathcal {A}}(D_{2})\in S ],$

kde P je pravděpodobnost.

Podle této definice je rozdílné soukromí podmínkou mechanismu zveřejňování dat (to znamená, že je určeno důvěryhodnou stranou, která uvolňuje informace o datovém souboru), nikoli datovým souborem samotným. Intuitivně to znamená, že pro jakékoli dvě podobné datové sady se bude diferenciální privátní algoritmus chovat přibližně stejně na obou datových sadách. Definice také poskytuje silnou záruku, že přítomnost nebo nepřítomnost jednotlivce neovlivní konečný výstup algoritmu.

Předpokládejme například, že máme databázi lékařských záznamů , kde každý záznam je dvojice ( Jméno , X ), kde je nula nebo jedna označující, zda má osoba gastritidu nebo ne: $D_{1}$ $X$

název	Přítomnost gastritidy (X)
Ivane	jeden
Petr	0
Vasilisa	jeden
Michaele	jeden
Maria	0

Nyní předpokládejme, že uživatel se zlými úmysly (často označovaný jako útočník) chce zjistit, zda má Michail gastritidu nebo ne. Předpokládejme také, že ví, který řádek obsahuje informace o Michailovi v databázi. Nyní předpokládejme, že útočník může použít pouze určitou formu dotazu , která vrací částečný součet prvních řádků sloupce v databázi. Aby útočník zjistil, zda má Michail gastritidu, provede dotazy: a , poté vypočítá jejich rozdíl. V tomto příkladu jsou , a , takže jejich rozdíl je . To znamená, že pole "Přítomnost gastritidy" v Michailově řádku by se mělo rovnat . Tento příklad ukazuje, jak mohou být jednotlivé informace ohroženy i bez výslovné žádosti o údaje konkrétní osoby. $Qi}$ $i$ $X$ $Q_{4}(D_{1})$ $Q_{3}(D_{1})$ $Q_{4}(D_{1})=3$ $Q_{3}(D_{1})=2$ $jeden$ $jeden$

Pokračujeme-li v tomto příkladu, pokud sestavíme datovou sadu nahrazením (Mikhail, 1) za (Mikhail, 0), pak bude útočník schopen rozlišit od pomocí výpočtů pro každou datovou sadu. Pokud by útočník získal hodnoty pomocí ε-diferenciálního privátního algoritmu pro dostatečně malé ε, pak by nebyl schopen rozlišit mezi dvěma datovými soubory. $D_{2}$ $D_{2}$ $D_{1}$ ${\displaystyle Q_{4}-Q_{3))$ $Qi}$

Výše popsaný příklad mince je -diferenciálně soukromý [8] . $(\ln 3)$

Hraniční případy

Případ, kdy ε = 0 je ideální pro zachování důvěrnosti, protože přítomnost nebo nepřítomnost jakýchkoli informací o jakékoli osobě v databázi neovlivňuje výsledek algoritmu, ale takový algoritmus je z hlediska užitečných informací nesmyslný, protože i s nulovým počtem lidí to dá stejný nebo podobný výsledek.

Jestliže ε inklinuje k nekonečnu, pak jakýkoli pravděpodobnostní algoritmus bude vyhovovat definici, protože nerovnost je vždy splněna. $P[{\mathcal {A}}(D_{1})\in S]\leq \infty \times P[{\mathcal {A}}(D_{2})\in S],$

Citlivost

Nechť je kladné celé číslo, množina dat a funkce. Citlivost [9] funkce, označovaná , je určena vzorcem $d$ $\mathcal{D}$ $f\colon {\mathcal {D}}\rightarrow \mathbb {R} ^{d}$ $\Delta f$

\Delta f=\max \lVert f(D_{1})-f(D_{2})\rVert _{1},

přes všechny páry datových souborů a v , které se neliší o více než jeden prvek a kde označuje normu . $D_{1}$ $D_{2}$ $\mathcal{D}$ ${\displaystyle \lVert \cdot \rVert _{1))$ $\ell _{1}$

Ve výše uvedeném příkladu lékařské databáze, pokud vezmeme v úvahu citlivost funkce , pak se rovná , protože změna kteréhokoli ze záznamů v databázi vede k něčemu, co se buď změní, nebo se nezmění. $d$ $Qi}$ $jeden$ $Qi}$ $jeden$

Laplaceův mechanismus

Vzhledem k tomu, že diferenciální soukromí je pravděpodobnostní koncept, má každá jeho metoda nutně náhodnou složku. Některé z nich, jako je Laplaceova metoda, používají přidání řízeného šumu k funkci, která se má vypočítat.

Laplaceova metoda přidává Laplaceův šum, tedy šum z Laplaceova rozdělení , který lze vyjádřit jako funkci hustoty pravděpodobnosti a který má nulovou střední hodnotu a směrodatnou odchylku . Definujme výstupní funkci jako funkci se skutečnou hodnotou ve tvaru kde , a je dotaz, který jsme plánovali provést v databázi. Lze ji tedy považovat za spojitou náhodnou veličinu , kde ${\text{noise}}(y)\propto \exp(-|y|/\lambda )\,\!$ ${\sqrt {2}}\lambda \,\!$ ${\mathcal {A}}\,\!$ ${\mathcal {T}}_{\mathcal {A}}(x)=f(x)+Y\,\!$ $Y\sim {\text{Lap}}(\lambda )\,\!\,\!$ $F\,\!$ ${\mathcal {T}}_{\mathcal {A}}(x)\,\!$

{\frac {\mathrm {pdf} ({\mathcal {T}}_({\mathcal {A}},D_{1}}(x)=t)}{\mathrm {pdf} ({ \mathcal {T}}_{{\mathcal {A}},D_{2}}(x)=t)}}={\frac {{\text{noise}}(tf(D_{1})) }{{\text{noise}}(tf(D_{2})))}}\,\!

což není více než (pdf - funkce hustoty pravděpodobnosti nebo funkce hustoty pravděpodobnosti). V tomto případě můžeme označit faktor soukromí ε. Tedy podle definice je ε-diferenciálně privátní. Pokud se pokusíme použít tento koncept ve výše uvedeném příkladu o přítomnosti gastritidy, pak aby to byla ε-diferenciální privátní funkce, musí platit , protože ). $e^{\frac {|f(D_{1})-f(D_{2})|}{\lambda }}\leq e^{\frac {\Delta (f)}{\lambda } }\,\!$ ${\frac {\Delta (f)}{\lambda }}\,\!$ ${\mathcal {T}}\,\!$ ${\mathcal {A}}\,\!$ $\lambda =1/\epsilon$ $\Delta (f)=1$

Kromě Laplaceova šumu lze použít i jiné typy šumu (například gaussovský), které však mohou vyžadovat mírné zmírnění definice diferenciálního soukromí [10] .

Složení

Konzistentní aplikace

Pokud provedeme dotaz ε-diferenčně zabezpečené časy a zavedený náhodný šum je nezávislý pro každý dotaz, pak bude celkové soukromí (εt)-diferenciální. Obecněji řečeno, pokud existují nezávislé mechanismy: , jejichž záruky soukromí jsou stejné , pak bude jakákoli funkce -diferenciálně soukromá [11] . $T$ $N$ ${\mathcal {M}}_{1},\tečky ,{\mathcal {M}}_{n}$ ${\displaystyle \epsilon _{1},\tečky ,\epsilon _{n))$ $g({\mathcal {M}}_{1},\tečky ,{\mathcal {M}}_{n})$ $(\sum \limits _{i=1}^{n}\epsilon _{i})$

Paralelní kompozice

Také pokud jsou dotazy prováděny na nepřekrývajících se podmnožinách databáze, pak by funkce byla -diferenciálně soukromá [11] . $G$ $(\max _{i}{\epsilon }_{i})$

Soukromí skupiny

Diferenciální soukromí je obecně navrženo tak, aby chránilo soukromí mezi databázemi, které se liší pouze o jeden řádek. To znamená, že žádný protivník s libovolnými pomocnými informacemi nemůže vědět, zda nějaký jednotlivý účastník poskytl své informace. Tento koncept však lze rozšířit na skupinu, pokud chceme chránit databáze, které se liší řádky, aby útočník s libovolnými podpůrnými informacemi nemohl vědět, zda jednotliví členové poskytli své informace. Toho lze dosáhnout, pokud se vzorec z definice nahradí [ 12] , pak pro D 1 a D 2 lišící se řádky $C$ $C$ $\exp(\epsilon )$ $\exp(\epsilon c)$ $C$

\Pr[{\mathcal {A}}(D_{1})\in S]\leq \exp(\epsilon c)\times \Pr[{\mathcal {A}} (D_{2}) \in S]\,\!

Použití parametru (ε/c) místo ε tedy umožňuje dosáhnout požadovaného výsledku a chránit struny. Jinými slovy, místo toho, aby každý prvek byl ε-diferenciálně soukromý, je nyní každá skupina prvků ε-diferenciálně soukromý a každý prvek je (ε/c)-diferenciálně soukromý. $C$ $C$

Použití rozdílového soukromí na aplikace v reálném světě

K dnešnímu dni existuje několik způsobů využití rozdílového soukromí:

US Census Bureau při zobrazování statistik [13]
Google RAPPOR za účelem shromažďování statistik o nežádoucím softwaru, který porušuje uživatelské preference [14] ( implementace RAPPOR s otevřeným zdrojovým kódem )
Google , za sdílení statistik historie návštěvnosti [15] .
Dne 13. června 2016 společnost Apple oznámila svůj záměr použít v iOS 10 rozdílné soukromí ke zlepšení své chytré podpory a nabídky technologií [16]

Poznámky

↑ Dwork Cynthia, 2006 , s. osm.
↑ Cynthia Dwork, Frank McSherry, Kobbi Nissim a Adam Smith=. Kalibrace šumu na citlivost v analýze soukromých dat // Sborník příspěvků ze třetí konference o teorii kryptografie (TCC'06), Shai Halevi a Tal Rabin (Eds.). - Springer-Verlag, Berlín, Heidelberg, 2006. - S. 266 . - doi : 10.1007/11681878_14 .
↑ Dwork Cynthia, 2006 , s. 12.
↑ 12 Nissim et al, 2003 , pp. 202-206.
↑ HILTON, MICHAEL. Diferenciální soukromí: Historický průzkum (neurčitý) . , str. 1
↑ Dwork, 2008 , pp. 3-13.
↑ Roth et al, 2014 , str. patnáct.
↑ Roth et al, 2014 , str. třicet.
↑ Dwork et al, 2006 , pp. 271-272.
↑ Dwork, 2008 , str. 16.
↑ 12 McSherry , 2009 , str. 6.
↑ Dwork Cynthia, 2006 , s. 9.
↑ Machanavajjhala et al, 2008 , s. jeden.
↑ Erlingsson a kol., 2014 , str. jeden.
↑ Řešení městské mobility pomocí technologií od Andrewa Elanda . Blog Google Policy Europe . Datum přístupu: 19. prosince 2017. Archivováno z originálu 10. prosince 2017. (neurčitý)
↑ Apple – Informace pro tisk – Apple představuje iOS 10, největší verzi iOS všech dob . Apple . Datum přístupu: 16. června 2016. Archivováno z originálu 29. dubna 2017. (neurčitý)

Literatura

Ashwin Machanavajjhala, Daniel Kifer, John M. Abowd, Johannes Gehrke, Lars Vilhuber. Privacy: Theory meets Practice on the Map // In Proceedings of the 24th International Conference on Data Engineering, (ICDE). — 2008.
Úlfar Erlingsson, Vasyl Pihur, Aleksandra Korolova. RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response // Sborník z 21. konference ACM o počítačové a komunikační bezpečnosti (CCS). — 2014.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, Adam Smith. Kalibrace šumu na citlivost v analýze soukromých dat // Konference Teorie kryptografie (TCC). - Springer, 2006. - doi : 10.1007/11681878_14 .
Frank D. McSherry. Soukromé integrované dotazy: rozšiřitelná platforma pro analýzu dat o ochraně soukromí // Sborník příspěvků z 35. mezinárodní konference SIGMOD o správě dat (SIGMOD). - 2009. - doi : 10.1145/1559845.1559850 .
Cynthia Dwork, Aaron Roth. Algoritmické základy diferenciálního soukromí // Základy a trendy v teoretické informatice. - 2014. - Srpen (vol. 9). - doi : 10.1561/0400000042 .
Dwork, Cynthie. Diferenciální soukromí: Průzkum výsledků // Agrawal, Manindra; Du, Dingzhu; Duan, Zhenhua; Li, Angshengova teorie a aplikace výpočtových modelů. Poznámky z přednášek z informatiky. - Springer Berlin Heidelberg, 2008. - 25. dubna. doi : 10.1145 / 773153.773173 .
Dwork, Cynthie. Diferenciální soukromí . - Mezinárodní kolokvium o automatech, jazycích a programování (ICALP), 2006. - doi : 10.1007/11787006_1 .
Irit Dinur, Kobbi Nissim. Odhalování informací při ochraně soukromí // Sborník příspěvků z dvacátého druhého sympozia ACM SIGMOD-SIGACT-SIGART o Principech databázových systémů (PODS '03). - ACM, New York, NY, USA, 2003. - doi : 10.1145/773153.773173 .