Diferenciální soukromí vyskočil z výzkumných prací na tech novinové titulky loni, když na WWDC keynote, Apple VICEPREZIDENT pro Inženýrství Craig Federighi oznámila, Apple použití pojmu chránit soukromí uživatelů na iOS.

byla to poslední instance obecného trendu: uživatelé a inženýři se probudili k důležitosti ochrany soukromí v softwaru. Vysoce profilovaná porušení soukromí, jako je „Boží režim“ společnosti Uber, jasně ukázala, s jakou lehkostí mohou zaměstnanci společnosti zneužívat citlivá data shromážděná od svých zákazníků.

množství citlivých dat, která jsou digitálně zaznamenávána, rychle roste. Lidé se nyní spoléhají na digitální služby pro více svých plateb, přeprava, navigace, nakupování, a zdraví než kdy jindy. Tento nový sběr dat vytváří stále rostoucí způsoby, jak porušovat soukromí.

ale také vytváří vzrušující příležitosti-zlepšit dopravní sítě—snížit kriminalitu—léčit nemoci – pokud jsou k dispozici správným vědcům a výzkumníkům. Existuje přirozené napětí mezi ochranou soukromí jednotlivců v datovém souboru a umožněním analytiky, která by mohla vést k lepšímu světu.

diferenciálně soukromé algoritmy jsou slibným technickým řešením, které by mohlo zmírnit toto napětí, což analytikům umožňuje provádět benigní agregátní analýzu a zároveň zaručit smysluplnou ochranu soukromí každého jednotlivce.

tato rozvíjející se oblast technologie stojí za zvážení v každém systému, který se snaží analyzovat citlivá data. Ačkoli diferenciální záruka soukromí byla koncipována teprve před deseti lety, byla úspěšná v akademické sféře a průmyslu. Vědci rychle vymýšlejí a vylepšují odlišně soukromé algoritmy, z nichž některé byly přijaty jak v Apple iOS, tak v prohlížeči Google Chrome.

Tento článek pojednává o historické faktory vedoucí k diferenciální soukromí v jeho současné podobě, spolu s definice diferenciální ochrany osobních údajů a příklad rozdílně vlastní algoritmy. Poté se podívá na některé nedávné vysoce postavené implementace odlišně soukromých algoritmů společností Google, Apple a dalších.

pozadí

diferenciálně soukromé algoritmy jsou nejnovější v desetiletí staré oblasti technologií pro analýzu dat zachovávající soukromí. Dva dřívější pojmy přímo ovlivnily rozdílné soukromí:

1. minimální velikost sady dotazů
2. Daleniova definice statistického zveřejnění.

nejprve je vysvětlíme, protože poskytují užitečné pozadí pro rozdílné soukromí.

minimální velikost sady dotazů první koncept je minimální velikost sady dotazů, která—stejně jako diferenciálně soukromé algoritmy-má za cíl zajistit bezpečnost agregovaných dotazů. Souhrnné dotazy jsou ty, kde je vrácená hodnota vypočtena přes podmnožinu záznamů v datovém souboru, jako jsou počty, průměry nebo částky. Může být užitečné uvažovat o agregovaných dotazech jako o dotazech SQL, které začínají „vybrat součet“, „vybrat počet“ nebo „vybrat AVG“. Jiné typy agregovaných dotazů zahrnují pohotovostní tabulky a histogramy.

minimální velikost sady dotazů je omezení, které se snaží zajistit, aby agregované dotazy nemohly unikat informace o jednotlivcích. Vzhledem k tomu, některé nakonfigurované prahové číslo T, to zajišťuje, že každý souhrnný dotaz je proveden na souboru nejméně T záznamy. Minimální velikost sady dotazů by blokovala agregované dotazy zaměřené na méně než T jednotlivců. Například, pokud T=2, zablokuje následující:

„vyberte AVG (plat) kde name = ‚Troy Brown‘;“.

protože tento dotaz by vedl průměr nad jedním záznamem (předpokládáme, že existuje pouze jeden Troy Brown).

použití minimálních velikostí sady dotazů zabraňuje určitým útokům, ale nepřichází se zárukou soukromí a v praxi je mohou zkušení útočníci obejít. Útočník může například provést výše uvedený útok pomocí:

“ vybrat částku (plat);“.

“ vyberte součet (plat) kde jméno != ‚Troy Brown‘;“.

nebo dokonce, pokud známe věk Troye Browna (45) a pozici (WR), jednoznačně ho identifikujte:

„vyberte součet(plat), kde pozice = ‚WR‘;“.

„vyberte součet (plat) kde pozice =‘ WR ‚ a věk != 45;

takové útoky se nazývají trackerové útoky a nelze je zastavit omezením minimální velikosti dotazu. Kvůli těmto útokům byly minimální velikosti sady dotazů považovány za nedostatečnou obranu pro ochranu dotazovacích systémů (viz Denningova práce). K zajištění soukromí bylo zapotřebí něco lepšího, se zárukou.

Dalenius statistické zveřejňování definice

V roce 1977, statistik Roztrhl Dalenius navrhované striktní definici ochrany osobních údajů: že útočník by se měli naučit nic o jedince, který nevěděli, před použitím citlivých údajů. Ačkoli tato záruka selhala (a uvidíme proč), je důležité pochopit, proč je rozdílné soukromí konstruováno tak, jak je.

Daleniova definice selhala, protože v roce 2006 počítačová vědkyně Cynthia Dwork dokázala, že tuto záruku nelze poskytnout—jinými slovy, jakýkoli přístup k citlivým údajům by tuto definici soukromí porušil. Problém, který zjistila, byl, že určité typy základních informací mohou vždy vést k novému závěru o jednotlivci. Její důkaz je ilustrován v následující anekdotě: Vím, že Alice je o dva palce vyšší než průměrná litevská žena. Pak jsem se komunikovat s dataset litevských žen a výpočet průměrné výšky, které jsem předtím nevěděla. Teď přesně znám Aliciinu výšku, i když nebyla v datovém souboru. Je nemožné zohlednit všechny typy základních informací,které by mohly vést k novému závěru o jednotlivci z použití datové sady.

Dwork po prokázání výše uvedeného navrhl novou definici: diferenciální soukromí.

co je rozdílné soukromí?

diferenciální soukromí zaručuje následující: že útočník se o jednotlivci nemůže dozvědět prakticky nic víc, než by se dozvěděl, kdyby v datovém souboru chyběl záznam této osoby. Zatímco slabší než Dalenius definice soukromí, záruka je dost silný, protože to zarovná s reálném světě pobídky—jednotlivci nemají žádnou motivaci, aby se neúčastnili v dataset, protože analytici, že dataset bude čerpat stejné závěry o tom, že jednotlivé jednotlivce, zda sám patří v dataset, nebo ne. Jako jejich citlivé osobní údaje, je téměř irelevantní v výstupy systému, uživatelé mohou být jisti, že organizace, zpracování jejich údajů není porušení jejich soukromí.

analytici, kteří se učí „prakticky nic víc o jednotlivci“, znamená, že jsou omezeni na nevýznamně malou změnu víry o jakémkoli jednotlivci. (Zde a níže, „změna“ označuje změnu mezi použitím datové sady a použitím stejné datové sady mínus záznam jedné osoby.) Rozsah této změny je řízen parametrem známým jako ϵ, který určuje hranici změny pravděpodobnosti jakéhokoli výsledku. Nízká hodnota ϵ, například 0, 1, znamená, že jen velmi málo se může změnit ve víře o jakémkoli jednotlivci. Vysoká hodnota ϵ, například 50, znamená, že víra se může podstatně více změnit. Formální definice je následující.

algoritmus je ϵ-diferenciálně soukromé, pokud a pouze pokud

Pr ≤ e^ϵ * Pr

pro všechna x, a pro všechny dvojice datových souborů D, D‘, kde D‘ je D s jeden záznam—tj. jedna osoba je dat chybí. Symbol e označuje matematickou konstantu. Všimněte si, že tato definice má smysl pouze pro randomizované algoritmy. Algoritmus, který poskytuje deterministický výstup, není kandidátem na diferenciální soukromí.

primární přitažlivost diferenciální záruky ochrany osobních údajů je její omezení na částku, kterou se každý analytik může dozvědět o jednotlivci. Navíc, to má následující užitečné vlastnosti:

• Composability: pokud dva dotazy jsou zodpovězeny s diferenciální soukromí záruky úrovni ϵ1 a ϵ2, pár dotazů, na které se vztahuje záruka úrovni (ϵ1 + ϵ2). Připomeňme, že vyšší hodnota ϵ znamená slabší záruku.
• síla proti libovolným podkladovým informacím: záruka se v žádném případě nespoléhá na to, jaké základní informace útočník zná. Tato vlastnost je jedním z hlavních důvodů, proč je rozdílné soukromí silnější než dřívější záruka soukromí, k-anonymita.
• bezpečnost při následném zpracování: neexistují žádná omezení ohledně toho, co lze provést s odlišně soukromým výsledkem – bez ohledu na to, s čím je kombinován nebo jak je transformován, je stále odlišně soukromý.

Jak je této záruky dosaženo v softwaru? Diferenciálně soukromé algoritmy jsou randomizované algoritmy, které přidávají šum v klíčových bodech algoritmu. Jedním z nejjednodušších algoritmů je Laplaceův mechanismus, který může po zpracování výsledků agregovaných dotazů (např. počty, součty a prostředky) učinit je odlišně soukromými. Níže je uveden příklad Java kódu pro Laplaceův mechanismus specifický pro počítání dotazů:

import org.apache.commons.math3.distribution.LaplaceDistribution;double laplaceMechanismCount(long realCountResult, double epsilon) { LaplaceDistribution ld = new LaplaceDistribution(0, 1 / epsilon); double noise = ld.sample(); return realCountResult + noise;}

klíčovou částí této funkce jsou

1. vytvořit Instanci Laplaceova rozdělení pravděpodobnosti (viz Obrázek 1) se středem v 0 a měřítko 1/ϵ. Používáme implementaci Apache Commons, „LaplaceDistribution“, která je konstruována se dvěma argumenty: průměrem distribuce a měřítkem distribuce. Všimněte si, že nižší epsilon (více soukromí) vede k většímu měřítku, a tím k širší distribuci a většímu šumu.
2. nakreslete z této distribuce jeden náhodný vzorek. Tato funkce sample () má náhodné číslo mezi 0 a 1 a na toto číslo aplikuje inverzní kumulativní distribuční funkci Laplaceovy distribuce (CDF). Výsledkem tohoto procesu je náhodné číslo, takže jeho pravděpodobnost, že bude nějaká konkrétní hodnota, odpovídá distribuci. Jako alternativní způsob, jak přemýšlet o tom, jestli tato ukázka funkce byla vyvolána milion krát milion vzorků, tvar histogramu z těchto vzorků by odpovídaly tvaru Laplaceova rozdělení.
3. rušit skutečnou hodnotu přidáním náhodné hodnoty z kroku 2.

uvažujme, proč je tento algoritmus odlišně soukromý tím, že vezmeme hledisko útočníka jménem Eve. Řekněme, že soubor dat je data o duševním zdraví a Eva vymyslela sledovací útok (viz výše), který odhalí, zda její cíl, Bob, dostává poradenství pro alkoholismus nebo ne. Pokud je výsledek dotazu 48, Eve ví, že Bob dostává poradenství; pokud je to 47, Eve ví opak.

ať už je odpověď 47 nebo 48, Laplaceův mechanismus vrátí hlučný výsledek někde kolem 47 nebo 48. Může se vrátit 49, 46 nebo dokonce s menší pravděpodobností 44 nebo 51 (viz obrázek 2 pro histogram). V praxi je pro Eve bude nemožné být velmi jistý, o tom, zda správná odpověď byla 47 nebo 48, a tudíž její přesvědčení o tom, zda Bob je v poradně pro alkoholismus nebo se nebude významně měnit.

Obrázek 1: Laplaceova distribuce se středem na 0 se stupnicí 1. Na obrázku je funkce hustoty pravděpodobnosti (PDF) distribuce—osa y je relativní pravděpodobnost, že proměnná bude mít hodnotu na ose x.

Obrázek 2: pravděpodobné výsledky počítání dotazu pro dva scénáře, kde skutečná odpověď je 47 a když je to 48. Malý počet výstupů by nestačil k rozlišení, ze které distribuce pocházejí. Epsilon je nastaven na 0,67.

možná jste v tomto bodě pozorovali, že Eve může proříznout šum opakováním dotazu mnohokrát a zjistit, zda se odpovědi shlukují kolem 47 nebo 48. Aby se této taktice zabránilo, musí mít soukromé systémy „rozpočet na ochranu soukromí“ , což je limit součtu použitých v každém dotazu. Tento limit funguje kvůli výše popsané vlastnosti skládatelnosti diferenciálního soukromí. Mohou požádat několik relativně nízkošumových dotazů nebo mnoho stovek dotazů s vysokým šumem, ale v každém případě nebudou schopni s jistotou zjistit, zda je skutečná odpověď 47 nebo 48.

nakonec si všimněte, že Laplaceův mechanismus pro počty je pouze jeden jednoduchý diferenciálně soukromý algoritmus. Laplaceův mechanismus lze rozšířit tak, aby fungoval pro součty a další souhrnné dotazy. Navíc, tam jsou zásadně odlišné algoritmy, které prokazatelně splňují diferenciální soukromí záruku. Několik stojí za prozkoumání jsou soukromé multiplikativní váhy algoritmus, multiplikativní váhy exponenciální mechanismus, a DualQuery.

Diferenciální soukromí v akci

V červnu 2016, Apple oznámila, že začne používat diferencovaně vlastní algoritmy, aby sbírat behaviorální statistiky z iphone. Toto oznámení, kromě toho, což způsobuje obrovský nárůst v diferenciální soukromí zájem, ukázal, že diferenciální soukromí může pomoci velkých organizací získat nové hodnoty z dat, které se dříve ani nedotkl, kvůli obavám soukromí.

ačkoli Apple dosud zveřejnil několik podrobností, algoritmus použitý v iPhone se zdá být podobný projektu Google rapport. Google implementoval v prohlížeči Chrome funkci, která shromažďuje statistiky chování z prohlížečů Chrome pomocí odlišně soukromého randomizovaného algoritmu odezvy.

v randomizované odpovědi je náhodný šum přidán do statistik před jejich odesláním do kolektoru. Pokud je například skutečná statistika 0, prohlížeč s určitou pravděpodobností nahradí 0 náhodně vybraným 0 nebo 1. Každý uživatel má velkou míru popření hodnoty, kterou jeho software hlásí, protože by to mohla být náhodná hodnota. Společně však signál vyniká nad náhodným šumem a organizace shromažďující statistiky (tj.

zajímavé je, že ani Google, ani Apple, pokud víme, neodhalily hodnotu, která jde s jejich rozdílnou zárukou soukromí. Tuto hodnotu potřebujeme, abychom pochopili ochranu nabízenou zárukou. Pokud použijí dostatečně vysokou hodnotu, mohou se analytici stále s vysokou důvěrou dozvědět citlivá fakta o uživatelích. Pro smysluplnou ochranu soukromí je nutná nízká hodnota ϵ.

odlišně soukromé algoritmy byly také implementovány do analytických produktů chránících soukromí, jako jsou ty, které vyvinul můj zaměstnavatel Privitar. Tyto produkty umožňují společnostem, které pracují s cenné, citlivé údaje začlenit rozdílně soukromé algoritmy do jejich datové architektury, poskytování záruk soukromí jejich uživatelů, zatímco ještě provedení smysluplné analýzy na data.

při pohledu do budoucna

inženýrská i výzkumná komunita mají cesty vpřed s odlišným soukromím. Pro inženýry, úkolem je vzdělávat se v diferenciálním soukromí a zajistit, aby byl používán tam, kde je to vhodné pro ochranu soukromí uživatelů. Pro výzkumné pracovníky je najít stále více a lépe diferencovaně soukromé algoritmy, což zlepšuje sadu nástrojů, pomocí kterých můžeme povolit analýzu dat zachovávající soukromí.

všichni můžeme získat ze zavedení záruk soukromí a úspěchů analýzy dat. Z obou důvodů se těšíme na další organizace, které se zabývají rozdílným soukromím.

O Autorovi

Charlie Cabot je senior údaje vědec na Privitar, o ochraně osobních údajů startup, který vytváří vysoce výkonné software pro datové anonymizace, včetně šumů a generalizačních algoritmů a diferencovaně soukromých mechanismů pro usnadnění bezpečného používání citlivých datových souborů. Charlie se zaměřuje na prokazatelné záruky soukromí a statistický dopad anonymizace na analytiku a vědu o datech. Dříve pracoval v kybernetické bezpečnosti, Charlie inženýrství strojového učení-učení řízené přístupy k detekci malware a je modelován kybernetické útoky na počítačové sítě.