Separating Oblivious and Adaptive Differential Privacy under Continual Observation

Dit papier lost een open vraag op door een expliciet voorbeeld te presenteren dat aantoont dat er een fundamenteel verschil bestaat tussen de oblivious en adaptieve settings van differentieel privacy onder continue observatie, waarbij het oblivious model aanzienlijk beter presteert dan het adaptieve model.

De kern

De Grote Privacy-Doorbraak: Waarom "Vaste Plannen" en "Aanpassing" Niet Zelfde Zijn

Stel je voor dat je een geheim bewaakt: een lijst met de voorkeuren van duizenden mensen (bijvoorbeeld wie van wie houdt, of wat ze eten). Je wilt deze statistieken delen met de wereld, maar je wilt niet dat iemand terug kan rekenen wie precies wat heeft gezegd. Dit noemen we Differentiële Privacy.

In de wereld van datastroom (waar nieuwe informatie elke seconde binnenkomt), zijn er twee manieren om dit geheim te bewaken. Dit artikel van Bun, Gaboardi en Wagaman laat zien dat deze twee manieren fundamenteel verschillend zijn. Het is alsof je een slot hebt dat werkt voor een vast plan, maar volledig faalt als de inbreker slimme aanpassingen maakt.

Hier is de uitleg in gewone taal, met een paar creatieve vergelijkingen.

1. De Twee Spelers: De "Vaste" vs. De "Slimme"

Om het verschil te begrijpen, moeten we kijken naar twee soorten situaties:

• De Oblivious Setting (De "Vaste Plannen"):
  Stel je voor dat een speler een spelletje speelt tegen een computer. De speler heeft een vast plan gemaakt voordat het spel begon. Hij weet precies welke vragen hij gaat stellen, ongeacht wat de computer antwoordt. De computer hoeft alleen maar te zorgen dat het antwoord niet onthult wie de speler is, maar omdat de vragen al vaststaan, is het voor de computer makkelijker om een veilig antwoord te geven.

  • Vergelijking: Het is alsof je een brief schrijft naar een vriend. Je weet al wat je gaat zeggen voordat je de envelop dichtmaakt. Je kunt de brief zo schrijven dat hij veilig is, omdat je weet wat erin staat.

• De Adaptive Setting (De "Slimme Aanpasser"):
  Hier is de speler veel slimmer. Hij kijkt naar het antwoord van de computer en past zijn volgende vraag daar direct op aan. Hij probeert de computer te "prikken" om meer informatie te onthullen.

  • Vergelijking: Dit is alsof je een detective bent die een verdachte ondervraagt. Als de verdachte iets zegt, vraagt de detective direct: "Oh, dus dat heb je gedaan? Dan moet je ook dit hebben gedaan!" De detective past zijn vragen aan op basis van de antwoorden om het verhaal te reconstrueren.

2. Het Experiment: De "Gouden Naald"

De onderzoekers hebben een specifiek probleem bedacht om te testen welke van de twee situaties veiliger is.

• Het Doel: Er is een geheim getal (een vector) verborgen, laten we het de "Gouden Naald" noemen.
• De Taak: De computer moet een antwoord geven dat een beetje lijkt op de Gouden Naald, maar niet op de vragen die de speler net heeft gesteld.
• De Regels:
  • Als de speler zijn vragen vast heeft staan (Oblivious), kan de computer een "willekeurige versie" van de Gouden Naald maken. Omdat de vragen al bekend zijn, kan de computer deze versie zo maken dat hij aan alle eisen voldoet. Het werkt als een magische sleutel die op alle sloten past.
  • Als de speler slim aanpast (Adaptive), is het een ander verhaal. Elke keer als de computer een antwoord geeft, gebruikt de speler dat antwoord om de volgende vraag te stellen. De speler probeert de computer te dwingen om steeds nieuwe stukjes van de Gouden Naald te onthullen.

3. Het Resultaat: De Klap in het Gezicht

De onderzoekers hebben bewezen wat er gebeurt:

• In de "Vaste" situatie: De computer kan duizenden vragen beantwoorden zonder dat het geheim onthuld wordt. Het is alsof je een muur bouwt die duizend jaar lang standhoudt tegen een storm die al van tevoren is voorspeld.
• In de "Slimme" situatie: De computer faalt al na een handvol vragen (soms maar een paar).
  • Waarom? Omdat de speler slim is, gebruikt hij elk antwoord om de volgende vraag zo te stellen dat de computer gedwongen wordt om een nieuw stukje van het geheim te onthullen. Na een paar stappen heeft de speler genoeg puzzelstukjes verzameld om de hele Gouden Naald (het geheime getal) te reconstrueren.
  • De Metafoor: Stel je voor dat je een geheim woord moet raden.
    • Vast: Je mag 100 keer een vraag stellen, maar je mag niet kijken naar de antwoorden. Je kunt een lijstje maken met vragen die het woord niet onthullen.
    • Slim: Je mag kijken naar het antwoord. Als ik zeg "Het woord begint met A", vraag ik direct "Begint het met B?". Als je antwoordt, weet ik meer. De slimme speler kan het woord in slechts een paar stappen raden, terwijl de vaste speler er uren over doet.

4. Waarom is dit belangrijk?

Vroeger dachten veel mensen dat privacy in een stroom van data (zoals bij het bijhouden van gezondheidsgegevens of verkeer) hetzelfde was, of je nu van tevoren wist wat er ging gebeuren of niet.

Dit artikel zegt: "Nee, dat is niet zo."

Als je een systeem bouwt dat privacy garandeert voor mensen die van tevoren weten wat ze gaan vragen (zoals in een statische database), betekent dat niet dat het veilig is voor een systeem waar de vragen dynamisch worden aangepast (zoals bij machine learning of real-time data-analyse).

• De les: Als je een systeem wilt bouwen dat veilig is tegen slimme aanvallers die hun vragen aanpassen, moet je veel strengere regels hanteren dan als je alleen rekening houdt met vaste plannen. Wat werkt voor het ene, is te zwak voor het andere.

Samenvatting in één zin

Dit artikel bewijst dat een privacy-systeem dat veilig is voor iemand met een vast plan, volledig in elkaar kan storten als die persoon slim genoeg is om zijn vragen aan te passen aan de antwoorden die hij krijgt; het is het verschil tussen een slot dat werkt tegen een sleutel die al in je hand zit, en een slot dat faalt tegen een dief die de sleutel onderweg zelf smeedt.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Separating Oblivious and Adaptive Differential Privacy under Continual Observation" van Bun, Gaboardi en Wagaman, in het Nederlands.

Titel: Het scheiden van Oblivious en Adaptieve Differentiële Privacy onder Continue Observatie

Auteurs: Mark Bun, Marco Gaboardi, Connor Wagaman (Boston University)
Datum: 11 maart 2026

---

1. Probleemstelling en Context

Het artikel adresseert een open vraag uit de literatuur (gesteld door Jain et al., ICML 2023) over de fundamentele verschillen tussen twee modellen van Differentiële Privacy (DP) in de context van continue observatie (ook wel continue release genoemd).

In dit model ontvangt een algoritme data als een stroom (stream) en geeft bij elke tijdstap $t$ een output vrij. De privacyvereiste is dat de volledige reeks outputs ononderscheidbaar blijft voor twee invoerstromen die slechts in één individuele datapunt verschillen.

Er worden twee settings onderscheiden:

1. Oblivious (Onbewust) Setting: De invoerstream is van tevoren vastgesteld en onafhankelijk van de output van het algoritme. De privacy moet alleen gelden voor deze vooraf bepaalde stream.
2. Adaptieve Setting: De invoer kan adaptief worden gekozen op basis van eerdere outputs van het algoritme. Een adversary kan de volgende datapunt kiezen na het zien van de vorige output. Dit is cruciaal voor toepassingen zoals machine learning (bijv. Stochastic Gradient Descent), waar de keuze van data-punten vaak afhankelijk is van eerdere gradienten.

De open vraag was: Bestaat er een specifiek probleem waarbij een algoritme in de oblivious setting accuraat kan zijn voor een lange tijdsduur, maar in de adaptieve setting faalt na slechts een constant aantal stappen?

2. Methodologie en Het Gedefinieerde Probleem

De auteurs introduceren een nieuw probleem, aangeduid als $P_{\alpha, d, T}$, dat is geïntroduceerd door de "correlated vector queries" uit eerder werk (Bun, Steinke, Ullman, 2017), maar aangepast aan de continue observatie context.

Het Probleem:

• Setup-fase: Een gevoelige bitstring $b \in \{\pm 1\}^d$ arriveert. Er wordt geen output gegenereerd.
• Aankomst-fase: Er arriveren $T$ vectoren $v_1, \dots, v_T \in \{\pm 1\}^d$, één per tijdstap.
• Output: Bij elke stap $t$ moet het algoritme een vector $y(t) \in \{\pm 1\}^d$ outputten.
• Accuraatheidseis (Loss Function): De output $y(t)$ moet voldoen aan twee voorwaarden:
  1. Het moet een sterke correlatie hebben met de geheime string $b$ (namelijk $\langle y(t), b \rangle \approx \alpha d$).
  2. Het moet zo min mogelijk correlatie hebben met alle vectoren die tot nu toe zijn aangekomen ($v_1, \dots, v_t$). Formeel: $|\langle y(t) - \alpha b, v \rangle| \leq \frac{\alpha^2 d}{100}$ voor alle $v \in \{v_1, \dots, v_t\}$.

De Kern van het Onderscheid:
In de oblivious setting zijn alle $v_1, \dots, v_T$ van tevoren bekend. Het algoritme kan dus één enkele vector genereren die voldoet aan alle constraints tegelijk.
In de adaptieve setting kiest de adversary de volgende vector $v_{t+1}$ op basis van de vorige output $y(t)$. De adversary kan $v_{t+1}$ zo kiezen dat deze orthogonaal is aan de huidige output, waardoor het algoritme gedwongen wordt om bij elke stap "nieuwe" informatie over $b$ te onthullen om aan de correlatie-eis te voldoen.

3. Belangrijkste Resultaten

De auteurs bewijzen een scherpe scheiding tussen de twee settings via twee stellingen:

Stelling 1: Een efficiënt algoritme voor de Oblivious Setting

• Resultaat: Er bestaat een $(\varepsilon, 0)$-DP algoritme dat het probleem $P_{\alpha, d, T}$ accuraat oplost voor een exponentieel groot aantal tijdstappen ($T = 2^{\Omega(\varepsilon^4 d)}$).
• Methodologie: Het algoritme gebruikt een gerandomiseerde respons (randomized response) op elke bit van $b$ om een vector $y$ te genereren. Dezezelfde vector $y$ wordt bij elke tijdstap uitgegeven.
• Redenering: Omdat de invoerstream $v_1, \dots, v_T$ van tevoren vaststaat, kan de kans dat $y$ voldoet aan de orthogonaliteits-eisen met alle $v_i$ tegelijk worden gebonden via de Hoeffding-ongelijkheid en een unie-bond (union bound). De privacy wordt gegarandeerd door de eigenschappen van randomized response.

Stelling 2: Een ondergrens voor de Adaptieve Setting

• Resultaat: Voor elke $(\varepsilon, \delta)$-DP algoritme in de adaptieve setting (met $\varepsilon = 1/5, \delta = 1/20$) is het onmogelijk om het probleem accuraat op te lossen voor meer dan een constant aantal tijdstappen ($T = O(1/\alpha^2)$).
• Methodologie: De auteurs construeren een specifieke adversary die het algoritme dwingt tot privacy-lekken.
  • De adversary kiest een willekeurige bitstring $b$.
  • Bij elke stap $t$ kiest de adversary $v_{t+1} = y(t)$ (de vorige output).
  • Omdat het algoritme accuraat moet zijn, moet de nieuwe output $y(t+1)$ sterk gecorreleerd zijn met $b$, maar orthogonaal zijn met $y(t)$. Dit dwingt het algoritme om een nieuwe, onafhankelijke "view" van $b$ te genereren.
  • Na $T = O(1/\alpha^2)$ stappen verzamelt de adversary een reeks vectoren $y(1), \dots, y(T)$ die allemaal sterk gecorreleerd zijn met $b$ maar onderling bijna orthogonaal.
• Reconstructie: Met behulp van een reconstructielemma (uit [BSU19]) kan de adversary uit deze verzameling vectoren een schatting $\tilde{b}$ van de originele string $b$ reconstrueren met hoge waarschijnlijkheid.
• Privacy Schending: Als de adversary $b$ kan reconstrueren, kan hij de "challenge bit" (een specifieke bit in $b$ die de twee naburige datasets onderscheidt) correct raden. Dit betekent dat de totale variatie-afstand (Total Variation Distance) tussen de views van de adversary voor de twee datasets te groot is, wat de differentieel privacy garantie schendt.

4. Bijdragen en Significatie

1. Beantwoording van een Open Vraag: Het artikel beantwoordt bevestigend de vraag van Jain et al. (2023) of er een probleem bestaat dat de oblivious en adaptieve settings scheidt. Dit is de eerste expliciete scheiding die wordt aangetoond voor continue observatie.
2. Fundamenteel Inzicht: Het werk toont aan dat adaptiviteit een veel strengere beperking is voor privacy in stroomalgoritmen dan eerder werd gedacht. Waar een oblivious algoritme exponentieel lang kan draaien, faalt een adaptief algoritme na slechts een constant aantal stappen.
3. Technische Nuance: De auteurs benadrukken dat hun bewijs niet zomaar een "black-box" toepassing is van eerdere resultaten over query-sets. De structuur van het probleem (één constraint per ronde die groeit in plaats van een nieuwe set constraints) vereist een aangepaste reconstructie-argumentatie die specifiek is voor de continue observatie context.
4. Implicaties voor Machine Learning: Gezien de connectie tussen adaptieve continue observatie en privé machine learning (zoals private SGD), suggereert dit resultaat dat algoritmen die adaptief zijn in de keuze van data of parameters, fundamenteel beperkter zijn in hun privacy-accuuraatheid dan hun oblivious tegenhangers.

Conclusie

De auteurs tonen aan dat er een fundamentele kloof bestaat tussen differentieel privacy in oblivious en adaptieve stroomsettings. Voor het gedefinieerde probleem van gecorreleerde vector queries is het mogelijk om in de oblivious setting een oplossing te vinden die duizenden stappen lang accuraat blijft, terwijl in de adaptieve setting elke poging tot accuraatheid na een paar stappen leidt tot een inbreuk op de privacy. Dit onderstreept het belang van het expliciet modelleren van adaptiviteit bij het ontwerpen van privacy-bewuste streaming systemen.