Abstrakt. Förutsatt att det finns enkelriktade funktioner, visar vi att det inte finns någon polynom-tid, differentialt privat algoritm A som tar en databas D. ( {0, 1} d ) n och utdata en "syntetisk databas" D alla vars tvåvägs marginaler är ungefär lika med D. (En tvåvägs marginal är fraktionen av databasraderna x 0, 1} d med ett givet par värden i ett givet par kolumner.) Detta besvarar en fråga från Barak et al. (PODS '07), som gav en algoritm kör i tid poly(n, 2 d ). Våra bevis kombinerar en konstruktion av svårsanitära databaser baserade på digitala signaturer (av Dwork et al., STOC '09) med kodning baserad på probabilistiskt kontrollerbara bevis. Vi presenterar också både negativa och positiva resultat för att generera "avsmalnande" syntetiska data, där andelen rader i D som uppfyller en predikat c uppskattas genom att tillämpa c på varje rad av D och aggregera resultaten på något sätt.
Ullman och Vadhan REF visar att om man antar ett sätt funktioner existerar, finns det en absolut konstant α * > 0 så att ingen polynom tid differentialt privat algoritm kan producera syntetiska data som bevarar alla 2-vägs marginaler upp till fel α * n, för en databas som innehåller n = poly(d) individer.
PCPs and the Hardness of Generating Private Synthetic Data
{'venue': 'TCC', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}