Cílem diferenciálního soukromí je poskytnout prostředky k maximalizaci přesnosti dotazů ze statistických databází a zároveň minimalizovat šance na identifikaci jejich záznamů.
Vezměme si důvěryhodnou stranu, která drží datový soubor citlivých informací (např. lékařské záznamy, informace o registraci voličů, používání e-mailů) s cílem poskytovat globální, statistické informace o veřejně dostupných datech při zachování soukromí uživatelů, jejichž informace datový soubor obsahuje. Takový systém se nazývá statistická databáze.
Pojem nerozlišitelnosti, později nazývaný diferenciální soukromí, formalizuje pojem „soukromí“ ve statistických databázích.
Činnosti důvěryhodného serveru jsou modelovány pomocí randomizovaného
algoritmu .
Randomizovaný algoritmus je
-diferenciálně soukromý pokud pro všechny datové soubory
a
které se liší o jeden prvek (tj. data jedné osoby), a všechny
,
kde pravděpodobnost je převzata přes mince algoritmu a označuje výstupní rozsah algoritmu .
Pozn.: Diferenciální soukromí je podmínkou pro uvolňovací mechanismus, nikoli pro datový soubor.
To znamená, že pro jakékoli dva datové soubory, které jsou si blízké (tedy které se liší v jednom prvku), se bude daný diferenciálně soukromý algoritmus chovat přibližně stejně na obou datových souborech. Definice dává silnou záruku, že přítomnost nebo nepřítomnost jednotlivce výrazně neovlivní konečný výstup dotazu.
Například předpokládejme, že máme databázi lékařských záznamů, kde každý záznam je dvojice (Jméno,X), kde označuje, zda osoba má cukrovku nebo ne. Například:
Nyní předpokládejme, že škodlivý uživatel (často nazývaný protivník) chce zjistit, zda má Chandler cukrovku nebo ne. Jako vedlejší informaci ví, ve kterém řádku databáze Chandler pobývá. Nyní předpokládejme, že protivník smí použít pouze určitou formu dotazu, která vrací částečný součet prvních řádků sloupce v databázi. Aby protivník zjistil stav Chandlerovy cukrovky, jednoduše provede . Jeden pozoruhodný rys, který tento příklad zdůrazňuje, je: jednotlivé informace mohou být kompromitovány i bez explicitního dotazování na konkrétní individuální informace.
Podívejme se na tento příklad trochu dále. Nyní konstruujeme
nahrazením (Chandler,1) za (Chandler,0). Pojďme
nazvat uvolňovací mechanismus (který uvolní výstup
) jako . Říkáme
je -diferenciálně
soukromý pokud splňuje definici, kde lze uvažovat jako o singletonové
množině (něco jako atd.), pokud je výstupní
funkce diskrétní náhodné proměnné
(tj. má pravděpodobnostní hmotnostní funkci (pmf)); jinak pokud je
spojitá náhodná proměnná (tj. má pravděpodobnostní hustotu
funkce (pdf)), pak lze uvažovat jako o malém
rozsahu reálií (něco jako
).
V podstatě, pokud takové existují, pak přítomnost nebo nepřítomnost konkrétního
jedince v databázi nemění
distribuci výstupu dotazu o významné množství a
tak zajišťuje soukromí jednotlivých informací v informačním
teoretickém smyslu.
V minulosti selhaly různé ad hoc přístupy k anonymizaci veřejných záznamů, když se výzkumníkům podařilo identifikovat osobní informace propojením dvou nebo více samostatně neškodných databází. Dvěma známými případy úspěšných „Linkage Attacks“ byly databáze Netflix Database a databáze Massachusetts Group Insurance Commission (GIC)
medical encounter.
Netflix nabídl odměnu ve výši 1 000 000 dolarů za 10% vylepšení svého systému doporučení. Netflix také uvolnil sadu tréninkových dat pro konkurenční vývojáře, aby mohli trénovat své systémy. Při uvolnění této sady dat poskytli prohlášení o vyloučení odpovědnosti: Aby bylo chráněno soukromí zákazníků, byly odstraněny všechny osobní údaje identifikující jednotlivé zákazníky a všechna zákaznická ID byla nahrazena náhodně přiřazenými ID.
Netflix není jediným dostupným portálem pro hodnocení filmů na webu; existuje mnoho dalších, včetně IMDB. Na IMDB se mohou jednotlivci registrovat a hodnotit filmy a mají možnost neuchovávat své údaje v anonymitě. Narayanan a Shmatikov propojili anonymizovanou školicí databázi Netflixu s databází Imdb (s použitím data hodnocení uživatelem) a částečně tak anonymizovali školicí databázi Netflixu. Je tedy jasné, že individuální informace uživatele byly ohroženy.
Massachusetts Group Insurance Commission (GIC) databáze zdravotních střetů
V tomto případě Latanya Sweeneyová z Carnegie Mellon University propojila anonymizovanou GIC databázi (která uchovávala datum narození, pohlaví a PSČ každého pacienta) a záznamy o registraci voličů, aby identifikovala zdravotní záznamy guvernéra státu Massachusetts.
Vrátíme-li se k hlavnímu proudu diskuse na téma Diferenciální soukromí,
citlivost ( ) funkce je
pro všechny , Liší se v nejvýše jeden prvek, a .
Abychom do toho dostali více intuice, vraťme se na příklad lékařské databáze a dotazu (který může být také vnímán jako funkce ), abychom zjistili, kolik lidí v prvních řádcích databáze má cukrovku. Je jasné, že pokud změníme jednu z položek v databázi, pak se výstup dotazu změní maximálně o jednu. Takže citlivost tohoto dotazu je jedna. Tak se stává, že existují techniky (které jsou popsány níže), pomocí kterých můžeme vytvořit diferenciálně soukromý algoritmus pro funkce s nízkou citlivostí.
Kompromis mezi užitkem a soukromím
Kompromis mezi přesností statistik odhadnutých způsobem chránícím soukromí a parametrem soukromí ε. Tento kompromis je studován v a
.
Mnoho diferenciálně privátních algoritmů spoléhá na přidání řízeného šumu k funkcím s nízkou citlivostí. Tento bod rozvedeme tak, že vezmeme speciální druh šumu (jehož jádro je Laplaceovo rozdělení tj. funkce hustoty pravděpodobnosti , střední nuly a směrodatné odchylky ). Nyní v našem případě definujeme výstupní funkci jako reálnou hodnotovou funkci (nazývanou jako přepisový výstup ) , kde a je původní reálný hodnotový dotaz/funkce, kterou plánujeme provést v databázi. Nyní jasně můžeme považovat za spojitou náhodnou proměnnou, kde
což je nanejvýš . Můžeme považovat za faktor soukromí . Tak následuje diferenciálně soukromý mechanismus (jak je patrné z definice). Pokud se pokusíme použít tento koncept v našem příkladu diabetu pak z výše uvedeného odvozeného faktu vyplývá, že abychom měli jako -diferenciální soukromý algoritmus, musíme mít .
I když jsme zde použili Laplaceův šum, ale můžeme použít i jiné formy zvuků, které také umožňují vytvořit diferenciálně soukromý mechanismus, jako je Gaussův šum (kde je samozřejmě potřeba mírné zmírnění definice diferenciálního soukromí).
Sekvenční složení
Pokud se dotážeme na ε-diferenciální mechanismus ochrany soukromí v časech, a randomizace mechanismu je nezávislá pro každý dotaz, pak by výsledek byl -diferenciálně soukromý. V obecnějším případě, pokud existují nezávislé mechanismy: , jejichž soukromí zaručuje diferenciální soukromí, respektive, pak jakákoli jejich funkce: je -diferenciálně soukromý.
Pokud by se navíc předchozí mechanismy počítaly na nesouvislých podmnožinách soukromé databáze, pak by funkce byla místo toho -diferenciálně soukromá.
Obecně platí, že ε-diferenciální soukromí je navrženo tak, aby chránilo soukromí mezi sousedními databázemi, které se liší pouze v jednom řádku. To znamená, že žádný protivník s libovolnými pomocnými informacemi nemůže vědět, zda jeden konkrétní účastník předložil své informace. To je však také rozšiřitelné, pokud chceme chránit databáze lišící se v řádcích, což se rovná protivník s libovolnými pomocnými informacemi může vědět, zda konkrétní účastníci předložili své informace. Toho lze dosáhnout, protože pokud se položky změní, dilatace pravděpodobnosti je ohraničena místo , tj. pro D1 a D2 lišící se v položkách:
Tudíž nastavení ε namísto dosažení požadovaného výsledku (ochrana položek). Jinými slovy, místo toho, aby byla každá položka ε-diferenciálně privátně chráněna, je nyní každá skupina položek ε-diferenciálně privátně chráněna (a každá položka je -diferenciálně privátně chráněna).
Pro tři datové soubory D1, D2 a D3, kdy se D1 a D2 liší v jedné položce a D2 a D3 se liší v jedné položce (implicitně se D1 a D3 liší nejvýše v 2 položkách), platí pro ε-diferenciálně soukromý mechanismus následující :
Důkaz lze rozšířit na místo 2.
Transformace je -stabilní, pokud je kladivová vzdálenost mezi a je nanejvýš -krát kladivová vzdálenost mezi a pro jakékoliv dvě databáze . Věta 2 v tvrdí, že pokud existuje mechanismus, který je -diferenciálně soukromý, pak kompozitní mechanismus je -diferenciálně soukromý.
To by mohlo být zobecněno na skupinové soukromí, protože velikost skupiny by mohla být myšlena jako kladivová vzdálenost mezi
a (kde obsahuje skupinu a ne). V tomto případě je -diferenciálně soukromé.