{"id":3512,"date":"2024-01-20T04:05:07","date_gmt":"2024-01-19T19:05:07","guid":{"rendered":"https:\/\/saraheee.com\/?p=3512"},"modified":"2024-03-05T19:29:35","modified_gmt":"2024-03-05T10:29:35","slug":"foundation-differential-privacy-definition","status":"publish","type":"post","link":"https:\/\/saraheee.com\/ko\/2024\/01\/foundation-differential-privacy-definition\/","title":{"rendered":"[Algorithmic Foundations] #1. Differential Privacy definition"},"content":{"rendered":"

Differential Privacy<\/h4>\n\n\n\n

\ud1b5\uacc4\uac12\uc73c\ub85c \ub370\uc774\ud130\ub97c \ucd94\ub860\ud560 \uc218 \uc5c6\ub3c4\ub85d \ud558\ub294 \uac83\uc774 DP\uc758 \ubaa9\ud45c
\uc775\uba85\ud654\uc640 \uac19\uc740 \uae30\uc874 \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638 \ubc29\ubc95\uc758 \ud55c\uacc4\ub97c \uace0\ub824\ud558\uc5ec \ub300\uaddc\ubaa8 \ub370\uc774\ud130 \uc138\ud2b8\uc5d0\uc11c \uac1c\uc778\uc758 \uac1c\uc778\uc815\ubcf4\ub97c \ubcf4\ud638\ud574\uc57c \ud558\ub294 \ubb38\uc81c\uc5d0 \ub300\uc751\ud558\uae30 \uc704\ud574 \ub4f1\uc7a5<\/p>\n\n\n\n

Requirement: for all D, D’ differing on one row, and all q \u2200 sets T,
Pr[M(D, q) \u2208 T] \u2272 (1+\u03b5) \u30fb Pr[M(D’, q) \u2208 T]<\/p>\n\n\n\n

Definition 2.4<\/mark> (Differential Privacy). A randomized algorithm M with domain \\(\\mathbb{N^{|\\textrm{X}|}}\\) is \\((\\varepsilon, \\delta)\\)-differentially private if for all \\(\\mathcal{S} \\subseteq Range(\\mathcal{M})\\) and for all x, y \\(\\in \\mathbb{N^{|\\textrm{X}|}}\\) such that \\(\\left| x-y \\right|_1 \\leq 1\\):<\/p>\n\n\n\n

\\(Pr[\\mathcal{M}(x) \\in \\mathcal{S}] \\leq exp(\\varepsilon) Pr[\\mathcal{M}(y) \\in \\mathcal{S}] + \\delta\\)<\/p>\n\n\n\n

the simpler case where \\(\\delta\\) = 0<\/p>\n\n\n\n

\\(exp(-\\epsilon) \\leq \\frac{Pr[M(x) = r]}{Pr[M(y) = r]} \\leq exp(\\epsilon)\\)<\/p>\n\n\n\n

DP\ub294 \ub370\uc774\ud130 \uc9d1\ud569\uc744 \ubd84\uc11d\ud560 \ub54c \uac15\ub825\ud55c \uac1c\uc778\uc815\ubcf4 \ubcf4\ud638\ub97c \ubcf4\uc7a5\ud558\uae30 \uc704\ud574 \uac1c\ubc1c\ub428
\ud55c \uac1c\uc778\uc758 \ub370\uc774\ud130\ub97c \ucd94\uac00\ud558\uac70\ub098 \uc81c\uac70\ud574\ub3c4 \ubd84\uc11d \uacb0\uacfc\uc5d0 \ud070 \uc601\ud5a5\uc744 \ubbf8\uce58\uc9c0 \uc54a\uc544\uc57c \ub370\uc774\ud130 \uc138\ud2b8\uc5d0 \ud3ec\ud568\ub41c \uac1c\uc778\uc758 \uac1c\uc778\uc815\ubcf4\ub97c \ubcf4\ud638\ud560 \uc218 \uc788\uc74c<\/p>\n\n\n\n

M: (Randomized algorithm) \ud504\ub85c\uc138\uc2a4\uc5d0\uc11c \ubb34\uc791\uc704\ud654\ub97c \uc0ac\uc6a9\ud558\ub294 \uc54c\uace0\ub9ac\uc998. \ub370\uc774\ud130 \uc138\ud2b8\ub97c \uc785\ub825\uc73c\ub85c \ubc1b\uc544 \ubd84\uc11d\uc5d0 \uc0ac\uc6a9\ub418\ub294 \ucd9c\ub825\uc744 \uc0dd\uc131\ud568<\/p>\n\n\n\n

X: \ub370\uc774\ud130 \uc720\ud615\uc758 \uc138\uacc4 \ub610\ub294 \ub370\uc774\ud130 \uc694\uc18c\uac00 \ucde8\ud560 \uc218 \uc788\ub294 \ubaa8\ub4e0 \uac00\ub2a5\ud55c \uac12\uc758 \uc9d1\ud569
(e.g., medical dataset, X could include \ub098\uc774, \ud608\uc555, \ucf5c\ub808\uc2a4\ud14c\ub864 \uc218\uce58)
the universe of data types or the sets of all possible values that a data element can take
|X|: set X\uc758 \ud06c\uae30, \ub2e4\uc591\ud55c \ub370\uc774\ud130 \uc720\ud615 \ub610\ub294 \uc18d\uc131\uc758 \uc218
N: \uc790\uc5f0\uc218 \uc9d1\ud569, dataset\uc758 \uac01 \uc694\uc18c\uc5d0 \ub300\ud574 \uac00\ub2a5\ud55c \uac1c\uc218 \ub610\ub294 \uc218\ub7c9\uc758 \ubc94\uc704
\\(N^{|\\textrm{X}|}\\): (Domain) \uc54c\uace0\ub9ac\uc998\uc774 \ucc98\ub9ac\ud560 \uc218 \uc788\ub294 \ubaa8\ub4e0 \ub370\uc774\ud130 \uc138\ud2b8\uc758 \uc9d1\ud569
S \u2286 Range(M): \uc54c\uace0\ub9ac\uc998 M\uc5d0\uc11c \uac00\ub2a5\ud55c \ubaa8\ub4e0 \ucd9c\ub825\uc758 \ud558\uc704 \uc9d1\ud569, \uc54c\uace0\ub9ac\uc998 \ucd9c\ub825\uc744 \ubd84\uc11d\ud560 \ub54c\uc758 \ubaa8\ub4e0 (\uc7a0\uc7ac\uc801) \uacb0\uacfc \uc9d1\ud569
x, y \\(\\in \\mathbb{N^{|\\textrm{X}|}}\\) such that \\(\\left| x-y \\right|_1 \\leq 1\\): \ub3c4\uba54\uc778 \ub0b4 \ub450 \ub370\uc774\ud130 \uc138\ud2b8 x, y, \ub450 \ub370\uc774\ud130 \uc138\ud2b8\uc758 \ucc28\uc774 (measured in the \\(L_1\\) norm), \ub370\uc774\ud130 \uc138\ud2b8\uac00 \ud558\ub098\uc758 \ub370\uc774\ud130\ub97c \uc81c\uc678\ud558\uace0\ub294 \ub3d9\uc77c
\\(L_1\\) norm: \ub9e8\ud574\ud2bc \uac70\ub9ac(Manhattan distance) or \ud0dd\uc2dc \uaddc\ubc94(Taxicab geometry)\uc774\ub77c \ud568, \ud574\ub2f9 \uad6c\uc131 \uc694\uc18c\uc758 \uc808\ub300 \ucc28\uc774\uc758 \ud569<\/p>\n\n\n\n

algorithm M\uc774 dataset x\uc5d0\uc11c \uc2e4\ud589\ub420 \ub54c, \uc9d1\ud569 S\uc5d0\uc11c \uacb0\uacfc\ub97c \uc0dd\uc131\ud560 \ud655\ub960\uc774 dataset y\uc5d0\uc11c \uc2e4\ud589\ub420 \ub54c M\uc774 \uc9d1\ud569 S\uc5d0\uc11c \uacb0\uacfc\ub97c \uc0dd\uc131\ud560 \ud655\ub960\uacfc \ud06c\uac8c \ub2e4\ub974\uc9c0 \uc54a\uc544\uc57c \ud568<\/p>\n\n\n\n

\u03b5 (epsilon): \ud504\ub77c\uc774\ubc84\uc2dc \uc190\uc2e4\uc744 \uce21\uc815\ud558\ub294 \uc74c\uc218\uac00 \uc544\ub2cc \ub9e4\uac1c\ubcc0\uc218(parameter), \ucd9c\ub825 \ud655\ub960\uc774 \uc5bc\ub9c8\ub098 \ub2e4\ub97c \uc218 \uc788\ub294\uc9c0\ub97c \uc81c\uc5b4\ud568
\u03b5\uac00 \uc791\uc744\uc218\ub85d \u2192 \ub450 datasets (differing by only one element)\uc5d0 \ub300\ud55c \uc54c\uace0\ub9ac\uc998 \ucd9c\ub825 \ud655\ub960 \ubd84\ud3ec\uac00 \uc720\uc0ac\ud568 \u2192 \ud504\ub77c\uc774\ubc84\uc2dc\uac00 \uc798 \ubcf4\ud638\ub428<\/p>\n\n\n\n

\u03b4 (delta): another non-negative parameter, usually very small<\/p>\n\n\n\n

Example<\/h5>\n\n\n\n

dataset of individuals’ medical records, \ud2b9\uc815 \uc9c8\ubcd1\uc758 \uc720\ubcd1\ub960\uc744 \ubd84\uc11d
(\u03b5, \u03b4)-differential privacy \uc815\uc758\uc5d0 \ub530\ub974\uba74, dataset \ud3ec\ud568 \uc5ec\ubd80\uc5d0 \uad00\uacc4\uc5c6\uc774 \ubd84\uc11d \uacb0\uacfc(like the calculated prevalence)\ub294 \ud06c\uac8c \ub2e4\ub974\uc9c0 \uc54a\uc544\uc57c \ud568<\/p>\n\n\n\n

<\/p>\n\n\n\n

Reference<\/h4>\n\n\n\n