الخصوصية التفاضلية

ليكن ε عددًا حقيقيًا موجبًا و${\displaystyle {\mathcal {A}}}$ليكن لدينا خوارزمية عشوائية تأخذ مجموعة بيانات كمدخل (تمثل إجراءات الطرف الموثوق الذي يحتفظ بالبيانات).${\displaystyle {\textrm {im}}\ {\mathcal {A}}}$يشير إلى صورة${\displaystyle {\mathcal {A}}}$.

الخوارزمية${\displaystyle {\mathcal {A}}}$يُقال إنها توفر خصوصية تفاضلية (ε، δ) إذا، بالنسبة لجميع مجموعات البيانات${\displaystyle D_{1}}$و${\displaystyle D_{2}}$التي تختلف في عنصر واحد (أي بيانات شخص واحد)، وجميع المجموعات الفرعية${\displaystyle S}$ل${\displaystyle {\textrm {im}}\ {\mathcal {A}}}$:

$${\displaystyle \Pr[{\mathcal {A}}(D_{1})\in S]\leq e^{\varepsilon }\Pr[{\mathcal {A}}(D_{2})\in S]+\delta .}$$

حيث تُحسب الاحتمالية بناءً على العشوائية التي تستخدمها الخوارزمية. ^{[ 6 ]} يُطلق على هذا التعريف أحيانًا اسم "الخصوصية التفاضلية التقريبية"، مع اعتبار "الخصوصية التفاضلية البحتة" حالة خاصة عندما${\displaystyle \delta =0}$في الحالة الأخيرة، يُقال عادةً أن الخوارزمية تُحقق خصوصية التفاضل من النوع ε (أي، مع حذف${\displaystyle \delta =0}$).

توفر الخصوصية التفاضلية ضمانات قوية ومتينة تسهل التصميم المعياري وتحليل الآليات الخاصة التفاضلية نظرًا لقابليتها للتركيب ، وقوتها في مواجهة المعالجة اللاحقة ، وتدهورها التدريجي في وجود بيانات مترابطة .

وفقًا لهذا التعريف، تُعدّ الخصوصية التفاضلية شرطًا على آلية الإفصاح (أي الطرف الموثوق الذي يُفصح عن معلومات حول مجموعة البيانات) وليس على مجموعة البيانات نفسها. وهذا يعني، ببساطة، أنه بالنسبة لأي مجموعتي بيانات متشابهتين، فإن خوارزمية الخصوصية التفاضلية ستتصرف بشكل متقارب على كلتيهما. ويضمن هذا التعريف بقوة أن وجود فرد أو غيابه لن يؤثر بشكل كبير على الناتج النهائي للخوارزمية.

على سبيل المثال، لنفترض أن لدينا قاعدة بيانات للسجلات الطبية${\displaystyle D_{1}}$حيث يمثل كل سجل زوجًا ( الاسم ، X )، حيث${\displaystyle X}$هو متغير منطقي (Boolean) يشير إلى ما إذا كان الشخص مصابًا بمرض السكري أم لا. على سبيل المثال:

لنفترض الآن أن مستخدمًا خبيثًا (يُطلق عليه غالبًا اسم الخصم ) يريد معرفة ما إذا كان تشاندلر مصابًا بمرض السكري أم لا. ولنفترض أيضًا أنه يعرف في أي صف من قاعدة البيانات يوجد تشاندلر. ولنفترض الآن أن الخصم مسموح له فقط باستخدام شكل معين من الاستعلام.${\displaystyle Q_{i}}$والتي تُعيد المجموع الجزئي للأول${\displaystyle i}$صفوف الأعمدة${\displaystyle X}$في قاعدة البيانات. وللعثور على حالة مرض السكري لدى تشاندلر، يقوم الخصم بتنفيذ${\displaystyle Q_{5}(D_{1})}$و${\displaystyle Q_{4}(D_{1})}$ثم يحسب الفرق بينهما. في هذا المثال،${\displaystyle Q_{5}(D_{1})=3}$و${\displaystyle Q_{4}(D_{1})=2}$وبالتالي فإن الفرق بينهما هو 1. وهذا يشير إلى أن حقل "يعاني من مرض السكري" في صف تشاندلر يجب أن يكون 1. يوضح هذا المثال كيف يمكن اختراق المعلومات الشخصية حتى بدون الاستعلام صراحةً عن معلومات فرد معين.

استكمالاً لهذا المثال، إذا قمنا بإنشاء${\displaystyle D_{2}}$باستبدال (تشاندلر، 1) بـ (تشاندلر، 0)، سيتمكن هذا الخصم الخبيث من التمييز${\displaystyle D_{2}}$من${\displaystyle D_{1}}$عن طريق الحساب${\displaystyle Q_{5}-Q_{4}}$لكل مجموعة بيانات. إذا كان مطلوبًا من الخصم استلام القيم${\displaystyle Q_{i}}$عبر${\displaystyle \varepsilon }$خوارزمية خاصة تفاضليًا، لحجم صغير بما فيه الكفاية${\displaystyle \varepsilon }$، عندها لن يكون قادراً على التمييز بين مجموعتي البيانات.

تشير قابلية التركيب إلى حقيقة أن التوزيع المشترك لمخرجات الآليات الخاصة التفاضلية (التي ربما يتم اختيارها بشكل تكيفي) يفي بمفهوم الخصوصية التفاضلية. ^{[ 3 ]}

• التركيب التسلسلي. إذا استعلمنا عن آلية خصوصية تفاضلية من نوع إبسيلون${\displaystyle t}$إذا كانت مرات، وكانت عشوائية الآلية مستقلة لكل استعلام، فإن النتيجة ستكون${\displaystyle \varepsilon t}$-خاصة بشكل تفاضلي. في الحالة الأكثر عمومية، إذا كان هناك${\displaystyle n}$آليات مستقلة:${\displaystyle {\mathcal {M}}_{1},\dots ,{\mathcal {M}}_{n}}$والتي تضمن الخصوصية${\displaystyle \varepsilon _{1},\dots ,\varepsilon _{n}}$الخصوصية التفاضلية، على التوالي، ثم أي دالة${\displaystyle g}$منهم:${\displaystyle g({\mathcal {M}}_{1},\dots ,{\mathcal {M}}_{n})}$يكون${\displaystyle \left(\sum \limits _{i=1}^{n}\varepsilon _{i}\right)}$-خاصة بشكل تفاضلي. ^{[ 7 ]}

• التركيب المتوازي. إذا تم حساب الآليات السابقة على مجموعات فرعية منفصلة من قاعدة البيانات الخاصة، فإن الدالة${\displaystyle g}$سيكون${\displaystyle (\max _{i}\varepsilon _{i})}$- بشكل خاص تفاضلي بدلاً من ذلك. ^{[ 7 ]}

الخاصية المهمة الأخرى للاستخدام المعياري للخصوصية التفاضلية هي المتانة في مواجهة المعالجة اللاحقة. ويُعرَّف هذا بأنه يعني أنه بالنسبة لأي دالة حتمية أو عشوائية${\displaystyle F}$محدد على صورة الآلية${\displaystyle {\mathcal {A}}}$، لو${\displaystyle {\mathcal {A}}}$يفي بمتطلبات الخصوصية التفاضلية من النوع ε، وكذلك يفعل${\displaystyle F({\mathcal {A}})}$[ ^{3 ]​}

تتيح خاصية التركيب بناء وتحليل الآليات ذات الخصوصية التفاضلية بشكل معياري ^{[ 3 ]} ، وتحفز مفهوم ميزانية فقدان الخصوصية . فإذا كانت جميع العناصر التي تصل إلى البيانات الحساسة لآلية معقدة تتمتع بخصوصية تفاضلية منفصلة، ​​فإن تجميعها، متبوعًا بأي معالجة لاحقة، سيتمتع بها أيضًا. ^{[ 3 ]}

بشكل عام، صُممت خصوصية إبسيلون التفاضلية لحماية الخصوصية بين قواعد البيانات المتجاورة التي تختلف في صف واحد فقط. هذا يعني أنه لا يمكن لأي مُهاجم، مهما كانت معلوماته الإضافية، معرفة ما إذا كان مشارك معين قد قدم معلوماته. ومع ذلك، فإن هذا المفهوم قابل للتوسيع. ^{[ 3 ]} قد نرغب في حماية قواعد البيانات التي تختلف في${\displaystyle c}$صفوف، وهو ما يعني أن الخصم الذي يمتلك معلومات مساعدة عشوائية يعرف ما إذا${\displaystyle c}$قام مشاركون محددون بتقديم معلوماتهم. ويمكن تحقيق ذلك لأنه إذا${\displaystyle c}$تتغير العناصر، ويكون تمدد الاحتمال محدودًا بـ${\displaystyle \exp(\varepsilon c)}$بدلاً من${\displaystyle \exp(\varepsilon )}$[ ^{8 ]} أي، بالنسبة لـ ^D1 _و D2 _{المختلفتين} في${\displaystyle c}$أغراض:$${\displaystyle \Pr[{\mathcal {A}}(D_{1})\in S]\leq \exp(\varepsilon c)\cdot \Pr[{\mathcal {A}}(D_{2})\in S]\,\!}$$وبالتالي يتم تعيين ε بدلاً من ذلك إلى${\displaystyle \varepsilon /c}$يحقق النتيجة المرجوة (حماية${\displaystyle c}$^{[ 3 ]} بعبارة أخرى، بدلاً من أن يكون كل عنصر محميًا بشكل خاص تفاضلي من النوع ε، فإن كل مجموعة من${\displaystyle c}$العناصر محمية بشكل خاص تفاضلي من النوع ε (وكل عنصر هو${\displaystyle (\varepsilon /c)}$(محمي بشكل تفاضلي). ^{[ 3 ]}

يمكن اعتبار الخصوصية التفاضلية بمثابة تحديد لمعدلات الخطأ في اختبار الفرضيات. لنفترض فرضيتين:

• ${\displaystyle H_{0}}$بيانات الفرد غير موجودة في مجموعة البيانات.

• ${\displaystyle H_{1}}$بيانات الفرد موجودة في مجموعة البيانات.

ثم هناك معدلان للخطأ:

• معدل النتائج الإيجابية الكاذبة (FPR): ${\displaystyle P_{\text{FP}}=\Pr[{\text{تخمين الخصم }}H_{1}\mid H_{0}{\text{ صحيح}}].}$

• معدل النتائج السلبية الكاذبة (FNR): ${\displaystyle P_{\text{FN}}=\Pr[{\text{تخمين الخصم }}H_{0}\mid H_{1}{\text{ صحيح}}].}$

الحماية المثالية تعني أن معدلات الخطأ متساوية، ولكن بالنسبة لإعداد ثابت (ε، δ)، يمكن للمهاجم تحقيق المعدلات التالية: ^{[ 9 ]}

• ${\displaystyle \{(P_{\text{FP}},P_{\text{FN}})\mid P_{\text{FP}}+e^{\varepsilon }P_{\text{FN}}\geq 1-\delta ,\ e^{\varepsilon }P_{\text{FP}}+P_{\text{FN}}\geq 1-\delta \}}$

تضيف آلية لابلاس ضوضاء لابلاس (أي الضوضاء الناتجة عن توزيع لابلاس ، والتي يمكن التعبير عنها بدالة كثافة الاحتمال).${\displaystyle {\text{noise}}(y)\propto \exp(-|y|/\lambda )\,\!}$، والتي لها متوسط ​​يساوي صفرًا وانحراف معياري${\displaystyle {\sqrt {2}}\lambda \,\!}$). الآن في حالتنا، نحدد دالة الإخراج لـ${\displaystyle {\mathcal {A}}\,\!}$كدالة ذات قيم حقيقية (تسمى مخرجات النسخ بواسطة${\displaystyle {\mathcal {A}}\,\!}$) مثل${\displaystyle {\mathcal {T}}_{\mathcal {A}}(x)=f(x)+Y\,\!}$أين${\displaystyle Y\sim {\text{Lap}}(\lambda )\,\!\,\!}$و${\displaystyle f\,\!}$هذا هو الاستعلام/الدالة الأصلية ذات القيم الحقيقية التي خططنا لتنفيذها على قاعدة البيانات. الآن من الواضح${\displaystyle {\mathcal {T}}_{\mathcal {A}}(x)\,\!}$يمكن اعتبارها متغيرًا عشوائيًا مستمرًا، حيث

$${\displaystyle {\frac {\mathrm {pdf} ({\mathcal {T}}_{{\mathcal {A}},D_{1}}(x)=t)}{\mathrm {pdf} ({\mathcal {T}}_{{\mathcal {A}},D_{2}}(x)=t)}}={\frac {{\text{noise}}(t-f(D_{1}))}{{\text{noise}}(t-f(D_{2}))}}\,\!}$$

وهو على الأكثر${\displaystyle e^{\frac {|f(D_{1})-f(D_{2})|}{\lambda }}\leq e^{\frac {\Delta (f)}{\lambda }}\,\!}$يمكننا أن نأخذ في الاعتبار${\displaystyle {\frac {\Delta (f)}{\lambda }}\,\!}$أن يكون عامل الخصوصية${\displaystyle \varepsilon \,\!}$. هكذا${\displaystyle {\mathcal {T}}\,\!}$يتبع آلية خصوصية تفاضلية (كما يتضح من التعريف أعلاه). إذا حاولنا تطبيق هذا المفهوم في مثال مرض السكري، فإنه يترتب على الحقيقة المستنتجة أعلاه أنه لكي يكون${\displaystyle {\mathcal {A}}\,\!}$كما هو الحال${\displaystyle \varepsilon \,\!}$نحتاج إلى خوارزمية خاصة تفاضلية${\displaystyle \lambda =1/\varepsilon \,\!}$على الرغم من أننا استخدمنا ضوضاء لابلاس هنا، إلا أنه يمكن استخدام أشكال أخرى من الضوضاء، مثل الضوضاء الغاوسية، ولكنها قد تتطلب تخفيفًا طفيفًا لتعريف الخصوصية التفاضلية. ^{[ 8 ]}

ومن الأمثلة البسيطة، التي تم تطويرها بشكل خاص في العلوم الاجتماعية ، ^{[ 12 ]} أن نطلب من الشخص الإجابة على السؤال "هل تمتلك السمة أ ؟"، وفقًا للإجراء التالي:

1. ألقِ قطعة نقدية .
2. إذا ظهرت الصورة، فأعد رمي العملة مرة أخرى (متجاهلاً النتيجة)، وأجب عن السؤال بصدق.
3. إذا ظهرت الكتابة، فأعد رمي العملة مرة أخرى وأجب بـ "نعم" إذا ظهرت الصورة، و"لا" إذا ظهرت الكتابة.

(إن الرمية الإضافية التي تبدو زائدة عن الحاجة في الحالة الأولى ضرورية في المواقف التي قد يلاحظ فيها الآخرون مجرد عملية رمي العملة، حتى لو ظلت النتيجة الفعلية مخفية.) تنشأ السرية بعد ذلك من إمكانية دحض الردود الفردية.

لكن، بشكل عام، تُعدّ هذه البيانات ذات الاستجابات الكثيرة ذات دلالة، إذ تُمنح الاستجابات الإيجابية لربع الأشخاص الذين لا يمتلكون السمة (أ) ، ولثلاثة أرباع الأشخاص الذين يمتلكونها بالفعل. وبالتالي، إذا كانت (p) هي النسبة الحقيقية للأشخاص الذين يمتلكون السمة (أ) ، فإننا نتوقع الحصول على (1/4)(1- p ) + (3/4) p = (1/4) + ( p /2) من الاستجابات الإيجابية. ومن ثم، يُمكن تقدير قيمة (p) .

وعلى وجه الخصوص، إذا كانت السمة أ مرادفة للسلوك غير القانوني، فإن الإجابة بـ "نعم" لا تعد جريمة، طالما أن لدى الشخص احتمالًا للإجابة بـ "نعم"، مهما كان ذلك الاحتمال.

على الرغم من أن هذا المثال، المستوحى من الاستجابة العشوائية ، قد يكون قابلاً للتطبيق على البيانات الجزئية (أي إصدار مجموعات البيانات مع كل استجابة فردية)، إلا أن الخصوصية التفاضلية، بحكم تعريفها، تستبعد إصدار البيانات الجزئية، ولا تنطبق إلا على الاستعلامات (أي تجميع الاستجابات الفردية في نتيجة واحدة)، لأن ذلك من شأنه أن ينتهك المتطلبات، وتحديدًا إمكانية الإنكار المعقول لمشاركة الشخص أو عدم مشاركتها. ^{[ 13 ] [ 14 ]}

تحوّل${\displaystyle T}$يكون${\displaystyle c}$مستقر إذا كانت مسافة هامينغ بين${\displaystyle T(A)}$و${\displaystyle T(B)}$هو على الأكثر${\displaystyle c}$- مضروبًا في مسافة هامينغ بين${\displaystyle A}$و${\displaystyle B}$لأي قاعدتي بيانات${\displaystyle A,B}$إذا كانت هناك آلية${\displaystyle M}$إنه${\displaystyle \varepsilon }$-خاصة بشكل تفاضلي، ثم الآلية المركبة${\displaystyle M\circ T}$يكون${\displaystyle (\varepsilon \times c)}$-خاصة بشكل تفاضلي. ^{[ 7 ]}

يمكن تعميم ذلك على خصوصية المجموعة، حيث يمكن اعتبار حجم المجموعة بمثابة مسافة هامينغ.${\displaystyle h}$بين ${\displaystyle A}$و${\displaystyle B}$(أين${\displaystyle A}$يحتوي على المجموعة و${\displaystyle B}$لا يفعل). في هذه الحالة${\displaystyle M\circ T}$يكون${\displaystyle (\varepsilon \times c\times h)}$-خاصة بشكل تفاضلي.

في عام 1977، وضع توري دالينيوس الأسس الرياضية لكبح الخلايا . ^{[ 15 ]} كان توري دالينيوس إحصائيًا سويديًا أسهم في حماية الخصوصية الإحصائية من خلال بحثه المنشور عام 1977، والذي كشف عن نقطة أساسية تتعلق بقواعد البيانات الإحصائية، وهي أنه لا ينبغي لقواعد البيانات الكشف عن معلومات تخص فردًا ما لا يمكن الوصول إليها بطريقة أخرى. ^{[ 16 ]} كما وضع تصنيفًا لأنواع الإفصاحات الإحصائية. ^{[ 4 ]}

في عام ١٩٧٩، صاغت دوروثي دينينغ وبيتر جيه . دينينغ وماير دي. شوارتز مفهوم "المتتبع"، وهو خصم قادر على معرفة المحتويات السرية لقاعدة بيانات إحصائية من خلال إنشاء سلسلة من الاستعلامات الموجهة وحفظ نتائجها. ^{[ ١٧ ]} أظهرت هذه الأبحاث، بالإضافة إلى أبحاث لاحقة، أن خصائص الخصوصية في قاعدة البيانات لا يمكن الحفاظ عليها إلا من خلال النظر في كل استعلام جديد في ضوء (ربما جميع) الاستعلامات السابقة. يُطلق على هذا المجال من العمل أحيانًا اسم " خصوصية الاستعلام"، وكانت النتيجة النهائية أن تتبع تأثير الاستعلام على خصوصية الأفراد في قاعدة البيانات يُعد مسألة صعبة الحل (NP-hard ).

في عام 2003، أثبت كوبي نسيم وإيريت دينور أنه من المستحيل نشر استعلامات عشوائية على قاعدة بيانات إحصائية خاصة دون الكشف عن قدر من المعلومات الخاصة، وأن محتوى المعلومات الكامل لقاعدة البيانات يمكن الكشف عنه بنشر نتائج عدد قليل بشكل مدهش من الاستعلامات العشوائية - أقل بكثير مما أشارت إليه الدراسات السابقة. ^{[ 18 ]} تُعرف هذه الظاهرة العامة باسم القانون الأساسي لاستعادة المعلومات ، وقد أدت فكرتها الرئيسية، وهي أنه في الحالة العامة، لا يمكن حماية الخصوصية دون إدخال قدر من التشويش، إلى تطوير مفهوم الخصوصية التفاضلية.

في عام ٢٠٠٦، نشرت سينثيا دورك ، وفرانك ماكشيري ، وكوبي نسيم، وآدم د. سميث مقالًا ^{[ ٣ ]} يحدد بدقة مقدار التشويش المطلوب إضافته، ويقترح آلية معممة لتحقيق ذلك. كما وضع هذا المقال أول تعريف رسمي للخصوصية التفاضلية. ^{[ ٤ ]} وقد حاز عملهم على جائزة TCC Test-of-Time لعام ٢٠١٦ ^{[ ١٩ ]} وجائزة غودل لعام ٢٠١٧. ^{[ ٢٠ ]}

ومنذ ذلك الحين، أظهرت الأبحاث اللاحقة أن هناك العديد من الطرق لإنتاج إحصاءات دقيقة للغاية من قاعدة البيانات مع ضمان مستويات عالية من الخصوصية . ^{[ 1 ]}

• معايرة الضوضاء وفقًا للحساسية في تحليل البيانات الخاصة ، سينثيا دورك ، فرانك ماكشيري ، كوبي نسيم ، وآدم سميث. 2006. في وقائع المؤتمر الثالث حول نظرية التشفير (TCC'06). سبرينغر-فيرلاغ، برلين، هايدلبرغ، 265-284. معايرة الضوضاء وفقًا للحساسية في تحليل البيانات الخاصة (هذا هو المنشور الأصلي لكتاب الخصوصية التفاضلية، وليس المقالة التي تحمل الاسم نفسه لدورك والتي نُشرت في العام نفسه).
• الخصوصية التفاضلية: مسح للنتائج بقلم سينثيا دورك، مايكروسوفت للأبحاث، أبريل 2008 (يعرض ما تم اكتشافه خلال العامين الأولين من البحث حول الخصوصية التفاضلية.)
• الخصوصية التفاضلية: مدخل تمهيدي لغير المتخصصين ، ألكسندرا وود، ميكا ألتمان ، آرون بيمبينيك، مارك بن، ماركو غابورد، وآخرون، مجلة فاندربيلت لقانون الترفيه والتكنولوجيا، المجلد 21، العدد 1، خريف 2018. (وثيقة تمهيدية جيدة، ولكنها بالتأكيد *ليست* مناسبة لغير المتخصصين!)
• صحيفة حقائق التكنولوجيا: الخصوصية التفاضلية بقلم راينا غاندي وأمريتا جايانتي، مركز بيلفر للعلوم والشؤون الدولية، خريف 2020
• الخصوصية التفاضلية وتعداد الولايات المتحدة لعام 2020 ، دراسات حالة معهد ماساتشوستس للتكنولوجيا في المسؤوليات الاجتماعية والأخلاقية للحوسبة، العدد: شتاء 2022 (يناير). الخصوصية التفاضلية وتعداد الولايات المتحدة لعام 2020 .
• غارفينكل، سيمسون (2025). الخصوصية التفاضلية . معهد ماساتشوستس للتكنولوجيا الصحافة المعرفة الأساسية. مطبعة معهد ماساتشوستس للتكنولوجيا. دوى : 10.7551/ميتبرس/15354.001.0001 . رقم ISBN 9780262551656.
• بوين، كلير مكاي وسيمسون غارفينكل، فلسفة الخصوصية التفاضلية ، إشعارات AMS، نوفمبر 2021.

• دليل عملي للمبتدئين في الخصوصية التفاضلية، بقلم كريستين تاسك، جامعة بيردو، أبريل 2012