Különböző adatvédelem

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. február 15-én felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

A differenciális adatvédelem olyan módszerek összessége, amelyek a legpontosabb lekérdezéseket biztosítják egy statisztikai adatbázishoz , miközben minimálisra csökkentik az egyes rekordok azonosításának lehetőségét abban.

Bevezetés

A differenciális adatvédelem az egyének érzékeny adatainak elvesztésének matematikai meghatározása, amikor személyes adataikat termék létrehozásához használják fel. A kifejezést Cynthia Dwork alkotta meg 2006-ban [1] , de Dwork, Frank McSherry , Kobe Nissim és Adam D. Smith [2] korábbi publikációjában is használják . A munka különösen Nissim és Irit Dinur [3] [4] kutatásán alapul, akik kimutatták, hogy lehetetlen egy privát statikus adatbázisból információkat közzétenni anélkül, hogy a magánjellegű információk egy részét feltárnák, és hogy a teljes adatbázis nyilvánosságra hozható. meglehetősen kis számú kérés eredményének közzétételével [4] .

A vizsgálatot követően világossá vált, hogy a statisztikai adatbázisok bizalmas kezelését a meglévő módszerekkel nem lehet biztosítani, és ennek eredményeként új adatbázisokra van szükség, amelyek korlátozzák a statisztikai adatban foglalt személyes adatok elvesztésével járó kockázatokat. adatbázis. Ennek eredményeként olyan új módszerek születtek, amelyek a legtöbb esetben lehetővé teszik az adatbázisból származó pontos statisztikák készítését, miközben magas szintű bizalmasságot biztosítanak [5] [6] .

Alapelv és illusztráció

A differenciált adatvédelem azon alapul, hogy véletlenszerűséget viszünk be az adatokba.

A társadalomtudományokban kifejlesztett egyszerű példa [7] az, hogy megkérünk egy személyt, hogy válaszoljon arra a kérdésre: „Van Önnek A tulajdonsága?” a következő eljárás szerint:

feldobni egy érmét
Ha feljönnek a fejek, válaszolj őszintén a kérdésre.
Ellenkező esetben dobja újra, ha feljön, válaszoljon "Igen", ha farok - "Nem"

A bizalmasság azért merül fel, mert a válaszból nem lehet biztosan tudni, hogy egy személy rendelkezik-e adott tulajdonsággal. Mindazonáltal ezek az adatok jelentősek, hiszen azoknak az embereknek a negyedétől érkezik pozitív válasz, akik nem rendelkeznek ezzel a tulajdonsággal, és háromnegyedétől azok, akik valóban rendelkeznek ezzel. Így, ha p az A-val rendelkező emberek valós aránya, akkor (1/4) (1- p) + (3/4) p = (1/4) + p / 2 pozitív válaszokat várunk. Ezért lehet becsülni R.

Formális definíció és használati példa

Legyen ε egy pozitív valós szám, A pedig egy valószínűségi algoritmus , amely egy adathalmazt vesz be bemenetként (az adatok birtokában lévő megbízható fél tevékenységét jelöli). Jelölje A képét im A - val . Az A algoritmus ε - differenciálisan privát , ha az összes adathalmaz esetében , amelyek egy elemben (azaz egy személy adataiban) különböznek, valamint az im A halmaz összes S részhalmaza : $D_{1}$ $D_{2}$

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

ahol P a valószínűség.

E definíció szerint a differenciált adatvédelem az adatközzétételi mechanizmus feltétele (azaz az adatkészletről információt kiadó megbízható fél határozza meg), nem maga az adatkészlet. Ez intuitív módon azt jelenti, hogy bármely két hasonló adatkészlet esetén a differenciális privát algoritmus megközelítőleg ugyanúgy fog viselkedni mindkét adatkészleten. A definíció erős garanciát ad arra is, hogy egy egyén jelenléte vagy hiánya nem befolyásolja az algoritmus végső kimenetét.

Tegyük fel például, hogy van egy orvosi feljegyzések adatbázisa, ahol minden rekord egy pár ( Név , X ), ahol nulla vagy egy, amely azt jelzi, hogy a személynek gyomorhurutja van-e vagy sem : $D_{1}$ $x$

Név	Gastritis jelenléte (X)
Ivan	egy
Péter	0
Vasilisa	egy
Michael	egy
Maria	0

Tegyük fel most, hogy egy rosszindulatú felhasználó (amelyet gyakran támadónak neveznek) ki akarja deríteni, hogy Mihailnak gyomorhurutja van-e vagy sem. Tételezzük fel azt is, hogy tudja, melyik sor tartalmaz információkat Mikhailról az adatbázisban. Most tegyük fel, hogy a támadó csak egy adott lekérdezési formát használhat, amely az adatbázisban lévő oszlop első sorainak részösszegét adja vissza . Annak megállapítására, hogy Mihailnak gyomorhurutja van-e, a támadó lekérdezéseket hajt végre: és , majd kiszámítja a különbséget. Ebben a példában , és , tehát különbségük . Ez azt jelenti, hogy a "Gastritis jelenléte" mezőnek Mikhail sorában egyenlőnek kell lennie . Ez a példa bemutatja, hogyan kerülhet veszélybe az egyes információk, még akkor is, ha egy adott személy adataira nem kérnek kifejezett kérést. $Q_{i}$ $én$ $x$ $Q_{4}(D_{1})$ $Q_{3}(D_{1})$ $Q_{4}(D_{1})=3$ $Q_{3}(D_{1})=2$ $egy$ $egy$

Folytatva ezzel a példával, ha úgy építjük fel az adatkészletet , hogy (Mikhail, 1) lecseréljük (Mikhail, 0), akkor a támadó meg tudja különböztetni az adathalmazt az egyes adatkészletek kiszámításával . Ha egy támadó egy ε-differenciális privát algoritmuson keresztül szerezne értékeket, kellően kis ε-hoz, akkor nem tudna különbséget tenni a két adatkészlet között. $D_{2}$ $D_{2}$ $D_{1}$ ${\displaystyle Q_{4}-Q_{3))$ $Q_{i}$

A fent leírt érmepélda -differentially private [8] . $(\ln 3)$

Határesetek

Az az eset, amikor ε = 0, ideális a titoktartás megőrzéséhez, mivel az adatbázisban szereplő személyről információ megléte vagy hiánya nem befolyásolja az algoritmus eredményét, azonban egy ilyen algoritmus értelmetlen a hasznos információk szempontjából, mivel még nulla emberszámmal ugyanazt vagy hasonló eredményt ad.

Ha ε a végtelenbe hajlik, akkor bármely valószínűségi algoritmus megfelel a definíciónak, mivel az egyenlőtlenség mindig teljesül. $P[{\mathcal {A}}(D_{1})\in S]\leq \infty \times P[{\mathcal {A}}(D_{2})\in S],$

Érzékenység

Legyen pozitív egész szám, legyen adathalmaz és függvény. A függvény érzékenységét [9] -vel jelöljük - a képlet határozza meg $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},

az összes adatkészletpáron és in , legfeljebb egy elemben különbözik egymástól, és ahol a normát jelöli . $D_{1}$ $D_{2}$ $\mathcal{D}$ ${\displaystyle \lVert \cdot \rVert _{1))$ $\ell _{1}$

Az orvosi adatbázis fenti példájában, ha figyelembe vesszük a függvény érzékenységét , akkor egyenlő a -val , mivel az adatbázis bármely rekordjának megváltoztatása olyasmihez vezet, ami vagy megváltozik, vagy nem változik. $d$ $Q_{i}$ $egy$ $Q_{i}$ $egy$

Laplace mechanizmus

Tekintettel arra, hogy a differenciális adatvédelem valószínűségi fogalom, bármely módszere szükségszerűen véletlenszerű összetevőt tartalmaz. Némelyikük, mint például a Laplace-módszer, a szabályozott zaj hozzáadását használja a kiszámítandó függvényhez.

A Laplace-módszer hozzáadja a Laplace-zajt, vagyis a Laplace-eloszlásból származó zajt, amely valószínűségi sűrűségfüggvényként fejezhető ki, és amelynek nulla az átlaga és a szórása . Határozzuk meg a kimeneti függvényt valós értékű függvényként, ahol , és az a lekérdezés, amelyet az adatbázisban terveztünk végrehajtani. Így folytonos valószínűségi változónak tekinthető , ahol ${\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})))}}\,\!

ami nem több, mint (pdf - valószínűségi sűrűségfüggvény vagy valószínűségi sűrűségfüggvény). Ebben az esetben az ε adatvédelmi tényezőt jelölhetjük . Így a definíció szerint ε-differenciálisan privát. Ha ezt a fogalmat próbáljuk használni a fenti példában a gyomorhurut jelenlétére vonatkozóan, akkor ahhoz, hogy ε-differenciális magánfüggvény legyen, teljesülnie kell , mivel ). $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$

A Laplace-zajon kívül más típusú zaj (például Gauss) is használható, de ezekhez szükség lehet a differenciális magánélet definíciójának enyhe lazítására [10] .

Összetétel

Következetes alkalmazás

Ha egy lekérdezést ε-differenciálisan biztonságos időkben hajtunk végre, és a bevitt véletlenszerű zaj minden lekérdezésnél független, akkor a teljes adatvédelem (εt)-differenciális lesz. Általánosabban szólva, ha léteznek független mechanizmusok: , amelyeknek az adatvédelmi garanciái rendre azonosak , akkor bármely funkció -különbözõen privát lesz [11] . $T$ $N$ ${\mathcal {M}}_{1},\dots ,{\mathcal {M}}_{n}$ ${\displaystyle \epsilon _{1},\dots ,\epsilon _{n))$ $g({\mathcal {M}}_{1},\pontok ,{\mathcal {M}}_{n})$ $(\sum \limits _{i=1}^{n}\epsilon _{i})$

Párhuzamos kompozíció

Továbbá, ha a lekérdezéseket az adatbázis nem átfedő részhalmazaira hajtják végre, akkor a függvény -differenciálisan privát lesz [11] . $g$ $(\max _{i}{\epsilon }_{i})$

Csoport adatvédelem

A differenciált adatvédelmet általában arra tervezték, hogy megvédje az olyan adatbázisok adatait, amelyek csak egy sorral különböznek egymástól. Ez azt jelenti, hogy egy tetszőleges segédinformációval rendelkező ellenfél sem tudhatja, hogy valamelyik résztvevő megadta-e az adatait. Ez a fogalom azonban kiterjeszthető egy csoportra, ha meg akarjuk védeni a sorokban eltérő adatbázisokat, hogy a támadó tetszőleges támogató információval ne tudhassa, hogy az egyes tagok megadták-e az adataikat. Ez akkor érhető el, ha a definícióból a képletet [12] -re cseréljük , akkor D 1 és D 2 esetén soronként eltérő $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]\,\!

Így az (ε/c) paraméter használata ε helyett lehetővé teszi a kívánt eredmény elérését és a karakterláncok védelmét. Más szóval, ahelyett, hogy minden elem ε-differenciálisan privát lenne, most minden elemcsoport ε-differenciálisan privát, és minden elem (ε/c)-különbözetileg privát. $c$ $c$

Különböző adatvédelem alkalmazása valós alkalmazásokra

A mai napig számos felhasználási terület létezik az eltérő adatvédelemre:

Az Egyesült Államok Népszámlálási Hivatala a statisztikák megjelenítésekor [13]
A Google RAPPOR statisztikákat gyűjt a nem kívánt szoftverekről, amelyek sértik a felhasználói beállításokat [14] ( a RAPPOR nyílt forráskódú megvalósítása )
Google , a forgalmi előzmények megosztására [15] .
2016. június 13-án az Apple bejelentette azon szándékát, hogy az iOS 10 -ben differenciált adatvédelmet kíván alkalmazni intelligens támogatási és technológiai kínálatának javítására [16]

Jegyzetek

↑ Dwork Cynthia, 2006 , p. nyolc.
↑ Cynthia Dwork, Frank McSherry, Kobbi Nissim és Adam Smith=. Zaj-érzékenység kalibrálása privát adatelemzésben // Proceedings of the Third Conference on Theory of Cryptography (TCC'06), Shai Halevi és Tal Rabin (szerk.). - Springer-Verlag, Berlin, Heidelberg, 2006. - 266. o . - doi : 10.1007/11681878_14 .
↑ Dwork Cynthia, 2006 , p. 12.
↑ 12 Nissim et al, 2003 , pp. 202-206.
↑ HILTON, MICHAEL. Különböző adatvédelem: történelmi felmérés (határozatlan idejű) . , 1. o
↑ Dwork, 2008 , pp. 3-13.
↑ Roth et al, 2014 , p. tizenöt.
↑ Roth et al, 2014 , p. harminc.
↑ Dwork et al, 2006 , pp. 271-272.
↑ Dwork, 2008 , p. 16.
↑ 12 McSherry , 2009 , p. 6.
↑ Dwork Cynthia, 2006 , p. 9.
↑ Machanavajjhala et al, 2008 , p. egy.
↑ Erlingsson et al, 2014 , p. egy.
↑ A városi mobilitás kezelése technológiával – Andrew Eland . Google Policy Europe Blog . Hozzáférés időpontja: 2017. december 19. Az eredetiből archiválva : 2017. december 10. (határozatlan)
↑ Apple – Sajtóinformáció – Az Apple bemutatja az iOS 10-et, a valaha volt legnagyobb iOS-kiadást . Apple . Hozzáférés időpontja: 2016. június 16. Az eredetiből archiválva : 2017. április 29. (határozatlan)

Irodalom

Ashwin Machanavajjhala, Daniel Kifer, John M. Abowd, Johannes Gehrke, Lars Vilhuber. Adatvédelem: Az elmélet találkozik a gyakorlattal a térképen // 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 // Proceedings of the 21st ACM Conference on Computer and Communications Security (CCS). — 2014.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, Adam Smith. A zaj és az érzékenység kalibrálása a privát adatok elemzésében // Theory of Cryptography Conference (TCC). - Springer, 2006. - doi : 10.1007/11681878_14 .
Frank D. McSherry. Adatvédelmi integrált lekérdezések: kiterjeszthető platform a magánélet védelmét megőrző adatelemzéshez // Proceedings of the 35th SIGMOD International Conference on Management of Data (SIGMOD). - 2009. - doi : 10.1145/1559845.1559850 .
Cynthia Dwork, Aaron Roth. A differenciált adatvédelem algoritmikus alapjai // Az elméleti számítástechnika alapjai és irányzatai. - 2014. - augusztus (9. kötet). - doi : 10.1561/0400000042 .
Dwork, Cynthia. Differential Privacy: A Survey of Results // Agrawal, Manindra; Du, Dingzhu; Duan, Zhenhua; Li, Angsheng A számítási modellek elmélete és alkalmazásai. Előadásjegyzetek számítástechnikából. - Springer Berlin Heidelberg, 2008. - április 25. doi : 10.1145 / 773153.773173 .
Dwork, Cynthia. Különböző adatvédelem . - Nemzetközi Kollokvium Automatákról, Nyelvekről és Programozásról (ICALP), 2006. - doi : 10.1007/11787006_1 .
Irit Dinur, Kobbi Nissim. Információk feltárása a magánélet védelme mellett // A huszonkettedik ACM SIGMOD-SIGACT-SIGART szimpózium az adatbázis-rendszerek alapelveiről (PODS '03) előadásai. - ACM, New York, NY, USA, 2003. - doi : 10.1145/773153.773173 .