Denna tidning bevisar att en "gamla hund", nämligen den klassiska Johnson-Lindenstrauss transformerar, "performerar nya tricks" - det ger ett nytt sätt att bevara differential integritet. Vi visar att om vi tar två databaser, D och D, sådan att (i) D − D är en rank-1 matris av avgränsade norm och (ii) alla singular värden av D och D är tillräckligt stora, sedan multiplicera antingen D eller D med en vektor av iid normala Gaussians ger två statistiskt nära fördelningar i betydelsen av differential integritet. Dessutom räcker det med en liten, deterministisk och offentlig förändring av inputen för att hävda att D:s alla unika värden är stora. Vi tillämpar Johnson-Lindenstrauss förvandlas till uppgiften att approximera cut-queries: antalet kanter som korsar en (S,S)-skuren i en graf. Vi visar att JL transform tillåter oss att publicera en sanitized graf som bevarar kant differential integritet (där två grafer är grannar om de skiljer sig åt på en enda kant) samtidigt lägga till endast O( ska/ ) slumpmässiga buller till någon given fråga (w.h.p). Jämföra additivt buller från vår algoritm med befintliga algoritmer för att svara på cut-queries på ett differentialt privat sätt, överträffar vi alla andra på små skärningar (------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Vi tillämpar också vår teknik för uppgiften att uppskatta variansen av en given matris i varje given riktning. Den JL transform tillåter oss att publicera en sanitized covariance matris som bevarar differential integritet w.r.t begränsade ändringar (varje rad i matrisen kan ändras med som mest en norm-1 vektor) samtidigt lägga till slumpmässiga brus av magnitud oberoende av storleken på matrisen (w.h.p). Däremot inför befintliga algoritmer ett fel som beror på matrisdimensionerna.
REF visar att JL-transformeringen av data bevarar differentialintegritet under förutsättning att datamatrisens minsta enskilda värde är stort.
The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy
{'venue': '2012 IEEE 53rd Annual Symposium on Foundations of Computer Science', 'journal': '2012 IEEE 53rd Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}