Marginaltabeller är den valda metoden för myndigheter som publicerar statistiska sammanfattningar av kategoriska uppgifter. I detta dokument får vi lägre gränser för hur stor snedvridning (buller) som är nödvändig i dessa tabeller för att säkerställa integriteten för känsliga uppgifter. Vi utökar en rad av senaste arbete om omöjliga resultat för privat dataanalys [9, 12, 13, 15 ] till en naturlig och viktig klass av funktioner. Betrakta en databas bestående av n rader (en per individ), varje rad som består av d binära attribut. För varje delmängd av T-attribut av storlek  på T = k, har marginaltabellen för T 2 k-poster. Varje post räknar hur många gånger i databasen en viss inställning av dessa attribut inträffar. Vi erbjuder lägre gränser för att släppa alla `d k ́k -attribute marginaltabeller under flera olika begrepp om integritet. (1) Vi ger effektiva polynomiska tidsattacker som gör det möjligt för en motståndare att rekonstruera känslig information som ges otillräckligt störda marginella bordsutsläpp. I synnerhet, för en konstant k, vi får en snäv gräns för e  och (min { ε n, på den genomsnittliga snedvridningen per post för varje mekanism som släpper alla k-attribute marginaler samtidigt som den ger "attribute" integritet (ett svagt begrepp underförstått av de flesta integritetsdefinitioner). (2) Våra rekonstruktionsattacker kräver en ny lägre gräns på det minsta enskilda värdet av en slumpmässig matris med korrelerade rader. Låt M (k) vara en matris med `d k ́r ows bildas genom att ta alla möjliga k-way entry-wise produkter av en underliggande uppsättning d slumpmässiga vektorer från {0, 1} n. För konstant k, visar vi att det minsta singular värdet av M (k) är e  och ( ε d k ) med hög sannolikhet (samma asymptotic bundna som för oberoende rader). (3) Vi får starkare lägre gränser för marginaltabeller som tillfredsställer olika privatliv. Vi ger en lägre gräns för * Den fullständiga versionen [20] innehåller bevis utelämnade här. 1 Notationen döljer omvänt polylogaritmiska faktorer i d, n, k.
Särskilt när k är en konstant, Kasiviswanathan et al. EXEMPEL PÅ PRINCIPEN
The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
{'venue': "STOC '10", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}