Differential Privacy Fundamentals

আক্রমণ থেকে প্রতিরক্ষায়

আগের অধ্যায়ে সমস্যাটা পরিষ্কার হলো — ML মডেল তার ট্রেইনিং ডেটা মনে রাখে, আর এই "স্মৃতি" বের করার জন্য attacker-দের কাছে কাজ করা technique আছে। এখন প্রশ্ন হলো: কোনো system কে কি আমরা গাণিতিকভাবে প্রমাণ করতে পারি যে এটা private? শুধু "মনে হচ্ছে নিরাপদ" না — সত্যিকারের, mathematical proof?

এটাই করে Differential Privacy। এটা privacy-র একটা formal mathematical definition, যেটা আজকের দিনে gold standard। Apple, Google, US Census Bureau, আর যেকোনো serious privacy-preserving ML system এটা ব্যবহার করে।

এই অধ্যায়ে আমরা সেই formal ভিত্তি তৈরি করব: Differential Privacy কী বলে, মূল parameter গুলো কী অর্থ বহন করে, এটা আসলে কী guarantee দেয় — আর কী দেয় না।

Differential Privacy কী?

Differential Privacy (DP) হলো একটা mathematical guarantee — একটা randomized algorithm-এর behavior নিয়ে। সহজ ভাষায় বললে:

কোনো একজন মানুষের ডেটা থাকুক বা না থাকুক — algorithm-এর output প্রায় একই রকম দেখাবে।

এই কথাটা একটু ভেঙে বুঝি, কারণ প্রতিটা শব্দ গুরুত্বপূর্ণ।

"প্রায় একই রকম" — ঠিক একই না। DP কিছু randomness (noise) যোগ করে যাতে output distribution-টা একটু controlled পরিমাণে shift করতে পারে যখন একজনের data পাল্টায়। Adversary noisy output দেখে, raw computation দেখে না।

"একজন মানুষের ডেটা থাকুক বা না থাকুক" — এটাই privacy guarantee। Adversary যত কিছুই জানুক না কেন, output দেখে সে নিশ্চিতভাবে বলতে পারবে না Alice dataset-এ ছিল কিনা।

"Randomized algorithm" — DP সবসময় এমন algorithm-এর জন্য define করা হয় যেগুলো random output দেয়। Deterministic algorithm-এ DP হয় না — কারণ same input সবসময় same output দেয়, আর changed input সবসময় different output দেয়।

Formal definition

ধরো $\mathcal{M}$ একটা randomized algorithm (যাকে mechanism বলা হয়) যেটা dataset নিয়ে কিছু output দেয়। $\mathcal{M}$ হলো $(\varepsilon, \delta)$-differentially private যদি, সব neighboring dataset pair $D$ আর $D'$-এর জন্য (যেগুলো ঠিক একটা record-এ আলাদা), আর সব possible output set $S$-এর জন্য:

$$\Pr[\mathcal{M}(D) \in S] \leq e^{\varepsilon} \cdot \Pr[\mathcal{M}(D') \in S] + \delta$$

পড়ার উপায়: $D$ তে চালালে mechanism-এর output $S$-এ পড়ার probability, $D'$ তে চালালে সেটার $e^\varepsilon$ গুণের চেয়ে বেশি হবে না — plus একটা ছোট slack $\delta$।

প্রথম দেখায় ভয় লাগতে পারে। এই অধ্যায়ে একটা একটা করে সব symbol পরিষ্কার হয়ে যাবে।

Neighboring Datasets

Privacy নিয়ে কথা বলার আগে, "দুটো dataset এক record-এ আলাদা" — এই কথাটার exact মানে ঠিক করতে হবে।

Neighboring dataset pair $(D, D')$ মানে দুটো dataset যেগুলো ঠিক একটা row-এ — একজন মানুষের record-এ — আলাদা। "আলাদা" মানে কী সেটার দুটো standard definition আছে, আর choice-টা গুরুত্বপূর্ণ:

Bounded DP (substitute model): $D'$ পাওয়া যায় $D$ থেকে একজনের record replace করে। দুটো dataset-এর size same। এটা model করে: "এই মানুষের আসল data ব্যবহার হয়েছিল, নাকি কোনো default দিয়ে replace হয়েছিল?"

Unbounded DP (add/remove model): $D'$ পাওয়া যায় $D$ থেকে একজনের record যোগ করে বা বাদ দিয়ে। $|D|$ আর $|D'|$-এর পার্থক্য 1। এটা model করে: "এই মানুষ dataset-এ ছিলই কি না?"

ML context-এ unbounded model (add/remove) সবচেয়ে common, কারণ এটা সরাসরি সেই প্রশ্নের উত্তর দেয় যেটা আমরা সবচেয়ে বেশি care করি: এই মানুষ কি training set-এ ছিলই? Membership inference attack ঠিক এই প্রশ্নটার উত্তর খোঁজে — আর add/remove definition দিয়ে DP সেটাকে formally বন্ধ করে।

Neighboring Datasets — Bounded vs UnboundedIllustration coming soon

Neighbors-এর definition কেন গুরুত্বপূর্ণ

ধরো তুমি bounded model দিয়ে DP prove করলে, কিন্তু attacker জিজ্ঞেস করছে "এই মানুষ dataset-এ ছিল কিনা" — এটা unbounded-style প্রশ্ন। তোমার prove করা DP certificate সেই attacker-এর actual goal-এ কাজ নাও করতে পারে। সবসময় check করো neighborhood definition তোমার privacy goal-এর সাথে মিলছে কিনা।

ε (Epsilon)

$\varepsilon$ (epsilon) হলো privacy budget — মূল parameter যেটা control করে adversary mechanism-এর output দেখে কতটা information পেতে পারে।

আবার inequality-তে তাকাই: $\Pr[\mathcal{M}(D) \in S] \leq e^{\varepsilon} \cdot \Pr[\mathcal{M}(D') \in S] + \delta$।

Neighboring dataset-এ output probability-র ratio bounded by $e^\varepsilon$। যখন $\varepsilon = 0$, $e^0 = 1$ — $D$ আর $D'$-এ output distribution identically same। Perfect privacy, কিন্তু সম্পূর্ণ useless (infinite noise লাগবে)। $\varepsilon$ বাড়লে algorithm neighboring dataset-এ আরও আলাদা output দিতে পারে — বেশি utility, কম privacy।

$$\frac{\Pr[\mathcal{M}(D) \in S]}{\Pr[\mathcal{M}(D') \in S]} \leq e^{\varepsilon}$$

সহজ ভাষায়: দুটো probability-র log-ratio bounded by $\varepsilon$। ছোট $\varepsilon$ মানে distribution গুলো বেশি similar — distinguish করা কঠিন — privacy শক্তিশালী।

ε-এর practical মানে

একটা useful interpretation: $\varepsilon = \ln(3) \approx 1.1$ হলে, output দেখে adversary Alice-এর membership নিয়ে তার belief সর্বোচ্চ 3 গুণ update করতে পারবে। $\varepsilon = \ln(10) \approx 2.3$ হলে সেই factor হবে 10। $\varepsilon = 0$ হলে output কিছুই reveal করে না।

ε কী নয়

Common ভুল: $\varepsilon$ failure-এর probability না। "$\varepsilon = 1$ মানে adversary-র 1/e সম্ভাবনায় success" — এটা ভুল। এটা probability-র ratio-কে bound করে — distribution নিয়ে multiplicative statement, কোনো bad event-এর probability না।

δ (Delta)

$\delta$ (delta) হলো failure probability — DP guarantee-তে একটা ছোট additive slack। এটা represent করে সেই probability যেখানে ε-level protection সম্পূর্ণভাবে ভেঙে পড়তে পারে।

Definition আবার দেখি: $\Pr[\mathcal{M}(D) \in S] \leq e^{\varepsilon} \cdot \Pr[\mathcal{M}(D') \in S] + \delta$।

$\delta$ ছাড়া (অর্থাৎ $\delta = 0$): pure differential privacy — guarantee একদম absolute, সব possible output আর সব neighboring dataset pair-এর জন্য। সবচেয়ে শক্তিশালী form।

$\delta > 0$ থাকলে: approximate differential privacy — guarantee $1 - \delta$ probability-তে holds। $\delta$ probability-তে mechanism সম্পূর্ণ fail করতে পারে — Alice-এর data সরাসরি reveal হয়ে যেতে পারে।

$$\underbrace{\varepsilon\text{-DP}}_{\text{pure DP}} \;\;\Leftrightarrow\;\; (\varepsilon, 0)\text{-DP}$$$$(\varepsilon, \delta)\text{-DP} \;\;\text{with}\;\; \delta > 0 \;\;\text{হলো approximate DP}$$

Pure DP হলো approximate DP-র special case যেখানে $\delta = 0$। সব pure $\varepsilon$-DP mechanism $(\varepsilon, 0)$-DP।

δ কেন দরকার?

Pure DP theoretically সুন্দর, কিন্তু practically সীমাবদ্ধ। অনেক useful mechanism — যেমন Gaussian noise যোগ করা — শুধু approximate DP satisfy করে, pure DP না। Gaussian mechanism, যেটা neural network-এর private training-এর standard algorithm DP-SGD-এর ভিত্তি, সেটা $(\varepsilon, \delta)$-DP satisfy করে কিন্তু $\varepsilon$-DP না।

তাই $\delta$ একটা pragmatic relaxation: catastrophic failure-এর tiny probability accept করে বিনিময়ে normal case-এ অনেক ভালো utility পাওয়া যায়।

δ কতটা ছোট হওয়া উচিত?

Convention হলো $\delta$ $1/n$-এর চেয়ে অনেক ছোট হওয়া উচিত, যেখানে $n$ dataset-এর size। Intuition: $\delta > 1/n$ হলে, $\delta$ probability-তে mechanism কারো data expose করতে পারে, আর $n$ জন মানুষ থাকায় expected exposed সংখ্যা 1-এর বেশি হতে পারে। $\delta = 1/n$ বা ছোট রাখলে failure probability population size-এর তুলনায় negligible হয়।

Privacy Guarantee

দুটো parameter এখন পরিষ্কার। এবার পুরো ছবিটা একসাথে দেখি: $(\varepsilon, \delta)$-DP আসলে adversary-কে কী guarantee দেয়?

Adversary কী শিখতে পারে, কী পারে না

ধরো $\mathcal{M}$ হলো $(\varepsilon, \delta)$-DP, আর adversary output $o = \mathcal{M}(D)$ দেখতে পাচ্ছে। Adversary algorithm সম্পর্কে সব জানে, population সম্পর্কেও সব জানে — কিন্তু Alice-এর record $D$-এ ছিল কিনা জানে না।

Adversary Alice-এর membership নিয়ে কী infer করতে পারবে?

$o$ দেখার আগে: Adversary-র কিছু prior belief আছে যে Alice dataset-এ ছিল।

$o$ দেখার পরে: Adversary Bayes' rule দিয়ে belief update করতে পারে। DP guarantee বলে তার posterior bounded। $1-\delta$ probability-তে, $o$ দেখে adversary-র belief সর্বোচ্চ $e^\varepsilon$ multiplicative factor-এ shift করতে পারে।

$$\frac{\Pr[\text{Alice in } D \mid o]}{\Pr[\text{Alice not in } D \mid o]} \leq e^{\varepsilon} \cdot \frac{\Pr[\text{Alice in } D]}{\Pr[\text{Alice not in } D]}$$

সহজ ভাষায়: DP সীমাবদ্ধ করে output দেখে adversary Alice-এর membership নিয়ে কতটা belief update করতে পারবে। Odds ratio সর্বোচ্চ $e^\varepsilon$ ফ্যাক্টরে shift করতে পারে (plus $\delta$ failure probability)।

Guarantee টা unconditional

এটাই DP-কে remarkable করে তোলে: guarantee টা hold করে adversary-র computational power, background knowledge, বা কতটা output দেখেছে — সব কিছু নির্বিশেষে। "আমরা assume করছি attacker X জানে না" — এরকম কোনো caveat নেই। যেকোনো adversary-র বিরুদ্ধে guarantee কাজ করে।

Heuristic defense-এর সাথে তুলনা করো — output perturbation বা anonymization। সেগুলোতে implicit assumption থাকে attacker সম্পর্কে: "মনে করছি attacker-এর কাছে side information নেই," বা "ধরছি attacker polynomially কম query করবে।" DP-তে এরকম কোনো assumption নেই।

Post-processing immunity

DP-র একটা সবচেয়ে useful property: যদি $\mathcal{M}$ $(\varepsilon, \delta)$-DP হয়, তাহলে যেকোনো function $f$-এর জন্য composed mechanism $f \circ \mathcal{M}$ও $(\varepsilon, \delta)$-DP। DP mechanism-এর output আরও process করলে তার privacy guarantee দুর্বল হয় না।

মানে হলো: তোমার model DP guarantee নিয়ে release করা হয়ে গেলে, model-এ আরও computation — fine-tuning, prediction, distillation — করলেও privacy guarantee কমে না। DP certificate টা preserved থাকে।

Privacy–Utility Tradeoff

এতক্ষণ DP কী protect করে সেটা জানলাম। এখন কঠিন প্রশ্ন: DP-র cost কী?

উত্তর হলো: utility। Differential privacy achieve করতে হলে তোমাকে algorithm-এর output-এ noise যোগ করতে হবে। Noise মানে output কম accurate, কম useful, কম informative। বেশি privacy চাইলে (ছোট ε) বেশি noise লাগে, বেশি utility যায়।

এটাই privacy–utility tradeoff, আর এটা DP design-এর bug না — এটা information theory-র fundamental, unavoidable consequence।

Tradeoff কেন fundamental

একটা information-theoretic argument। ধরো তুমি একটা dataset-এর গড় উচ্চতা publish করতে চাও, আর এটা ε-DP হওয়া চাই। Average-এর sensitivity (একজন মানুষ কতটা পাল্টাতে পারে) depend করে উচ্চতার range-এর উপর। একজনের contribution mask করতে noise দরকার যার standard deviation $1/\varepsilon$ scale-এ grow করে। ε 10 গুণ ছোট করলে 10 গুণ বেশি noise লাগবে — আর published average 10 গুণ কম useful হবে।

ML model-এ এটা play out করে training-এ। DP-SGD (standard DP training algorithm) প্রতি training step-এ gradient-এ noise যোগ করে। এই noise:

• Convergence slow করে (same accuracy পেতে বেশি training step লাগে)
• Final accuracy cap করে (noise permanently signal-to-gradient ratio কমায়)
• ছোট dataset-এ বেশি খারাপ (signal-to-noise ratio $\sqrt{n}$ scale করে, তাই ছোট $n$-এ utility কম)

python

Copy

এই code simplified। মূল কথা: privacy gradient quality-কে cost করে, আর gradient quality model performance চালায়।

Tradeoff practically navigate করা

"সঠিক ε কত?" — এর universal উত্তর নেই। Application, dataset size, data-র sensitivity, আর regulatory environment-এর উপর নির্ভর করে।

Tradeoff symmetric না

একটা important asymmetry: DP-র utility loss সাধারণত extremes-এ অনেক বেশি খারাপ। ε = 10 থেকে ε = 5 যেতে প্রায় কোনো utility হারাতে নাও পারো (noise আগেই ছোট ছিল)। ε = 1 থেকে ε = 0.5 যেতে model useless হয়ে যেতে পারে। এই non-linearity মানে: tradeoff curve-এর middle-টাই interesting — যেখানে ε-র সামান্য change utility-তে dramatic effect ফেলতে পারে।

Privacy–Utility Tradeoff CurveIllustration coming soon

মূল কথা

সাধারণ ভুল

নিজেকে যাচাই করো

এরপর কোথায় যাব

এখন আমাদের কাছে differential privacy-র formal language আছে: definition, দুটো parameter, guarantee কী মানে, আর কেন utility cost হয়। কিন্তু এতক্ষণ সব abstract। স্বাভাবিক পরের প্রশ্ন: differentially private mechanism আসলে কীভাবে তৈরি করো?

উত্তর শুরু হয় sensitivity ধারণা দিয়ে — একটা query বা gradient একজনের data পাল্টালে কতটা change করতে পারে। সেখান থেকে দুটো fundamental noise mechanism: pure DP-র জন্য Laplace noise, আর approximate DP-র জন্য Gaussian noise। এই tool গুলো, plus composition theorem যেটা multiple operation জুড়ে ε budget track করতে দেয় — এগুলো মিলে private system তৈরির complete toolkit। সেখানেই আমরা পরে যাচ্ছি।