Abstract-Begreppet om en universell nyttomaximering integritetsmekanism infördes nyligen av Ghosh, Roughgarden, och Sundararajan [STOC 2009]. Detta är mekanismer som garanterar optimal nytta för en stor grupp av informationskonsumenter samtidigt, samtidigt som Differentiell integritet bevaras [Dwork, McSherry, Nissim, och Smith, TCC 2006]. Ghosh, Roughgarden och Sundararajan har, ganska överraskande, visat ett fall där det finns en sådan universellt optimal differentierad privat mekanism, när informationskonsumenterna är Bayesian. Detta resultat utvidgades nyligen av Gupte och Sundararajan [PODS 2010] till att även omfatta riskutsatta konsumenter. Båda positiva resultat handlar om mekanismer (cirka) datorisering en enda räkning fråga (dvs. antalet individer som uppfyller en specifik egenskap i en viss population), och utgångspunkten för vårt arbete är en försök att utvidga dessa resultat till liknande inställningar, såsom summa frågor med icke-binära individuella värden, histogram, och två (eller fler) räkna frågor. Vi visar dock att det inte finns något universellt optimalt system för alla dessa frågor, både för Bayesian-konsumenterna och för konsumenterna i riskzonen. För Bayesian fallet går vi längre, och ger en karakterisering av de funktioner som medger universellt optimala mekanismer, visar att en universell-optimal mekanism existerar, i huvudsak, endast för en (enkel) räkna fråga. I hjärtat av vårt bevis är en representation av en frågefunktion f genom dess integritet begränsning graf G f vars kanter motsvarar värden som resulterar i att tillämpa f till angränsande databaser.
Brenner och Nissim REF visade att sådana universellt optimala privata mekanismer inte finns för två räknefrågor eller för en enda icke-binär summa fråga.
Impossibility of Differentially Private Universally Optimal Mechanisms
{'venue': '2010 IEEE 51st Annual Symposium on Foundations of Computer Science', 'journal': '2010 IEEE 51st Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Computer Science', 'Mathematics']}