Under det senaste årtiondet har differentiell integritet fått en utbredd spridning inom integritetsgemenskapen. Dessutom har det fått stor uppmärksamhet från verifieringsgemenskapen, vilket resulterar i flera framgångsrika verktyg för att formellt bevisa olika integritet. Även om deras tekniska tillvägagångssätt varierar mycket, alla befintliga verktyg bygger på resonemang principer som härrör från sammansättning teorem av differential integritet. Även om detta räcker för att verifiera de flesta vanliga privata algoritmer, det finns flera viktiga algoritmer vars integritet analys inte enbart förlitar sig på komposition teorem. Deras bevis är betydligt mer komplexa och är för närvarande utom räckhåll för verifieringsverktyg. I detta dokument utvecklar vi kompositionsmetoder för att formellt verifiera differentialintegritet för algoritmer vars analys går utöver kompositionsteorem. Våra metoder bygger på djupa kopplingar mellan differentiell integritet och probabilistiska kopplingar, ett etablerat matematiskt verktyg för resonemang om stokastiska processer. Även när kompositionen teorem inte är till hjälp, kan vi ofta bevisa integritet genom en koppling argument. Vi demonstrerar våra metoder på två algoritmer: exponentiell mekanism och ovanstående threshold algoritm, den kritiska komponenten i den berömda Sparse Vector algoritm. Vi verifierar dessa exempel i en relationell programlogik apRHL +, som kan konstruera ungefärliga kopplingar. Denna logik utvidgar den befintliga apRHL-logiken med mer allmänna regler för Laplace-mekanismen och den ensidiga Laplace-mekanismen, och nya strukturella regler som möjliggör punktvisa resonemang om integritet; alla regler är inspirerade av kopplingen till koppling. Medan vårt dokument presenteras ur ett formellt verifieringsperspektiv, anser vi att dess huvudsakliga insikt är av oberoende intresse för den differentiella integriteten.
Många av dessa tekniker bygger på sammansättning egenskaper integritet, även om det finns vissa undantag REF.
Proving Differential Privacy via Probabilistic Couplings
{'venue': "LICS '16", 'journal': None, 'mag_field_of_study': ['Computer Science']}