Abstract-Diferential privacy är ett ramverk för att kvantifiera i vilken utsträckning individuell integritet i en statistisk databas bevaras samtidigt som användbar aggregerad information om databasen släpps. I detta dokument, inom de kategorier av mekanismer som är omedvetna om databasen och frågorna bortom den globala känsligheten, karakteriserar vi den grundläggande kompromissen mellan integritet och nytta i differentiell integritet, och härleda den optimala -differentiellt privata mekanismen för en enda realvärderad frågefunktion under en mycket allmän nyttomaximering (eller kostnadsminimering) ram. Den klass av bullersannolikhetsfördelningar i den optimala mekanismen har stegformade sannolikhetstäthetsfunktioner som är symmetriska (runt ursprunget), monotont minskande och geometriskt sönderfallande. Trappmekanismen kan ses som en geometrisk blandning av enhetliga sannolikhetsfördelningar, vilket ger en enkel algoritmisk beskrivning av mekanismen. Trappmekanismen generaliserar dessutom naturligt till diskreta frågeutgångsinställningar samt mer abstrakta inställningar. Vi härleder uttryckligen parametern för den optimala trappmekanismen för 1 och 2 kostnadsfunktioner. Jämföra de optimala prestanda med de vanliga Laplacian mekanismen, visar vi att i den höga integriteten (är liten), Laplacian mekanismen är asymptotiskt optimal som → 0; i den låga integriteten ( är stor), den minsta magnitud och andra stund av buller är ( e (− /2) ) och ( 2 e (−2 /3) ) som → +∞, respektive, medan motsvarande siffror när du använder Laplacian mekanismen är / och 2 2 / 2, där är känsligheten i frågefunktionen. Vi drar slutsatsen att fördelarna med trappmekanismen är mer uttalade i det måttligt låga integritetssystemet.
Geng och Viswanath REF karakteriserade den grundläggande kompromissen mellan integritet och nytta i differential integritet och härledde trappmekanismen för en enda verkligt värderad frågefunktion under en mycket allmän nyttomaximering ram.
The Optimal Noise-Adding Mechanism in Differential Privacy
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Mathematics', 'Computer Science']}