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

ضع في الاعتبار طرف مؤتمن، متحصّل على قاعدة بيانات من المعلومات الحساسة (على سبيل المثال لا حصر: سجلات إحصائية، معلومات تسجيل الناخبين، أو استعمالات البريد الإلكتروني).

هذا الطرف يهدف إلى نشر معلومات إحصائية عامة عن تلك البيانات لعموم الناس، مع الحفاظ على خصوصية المستخدمين ممن كانت بياناتهم مسجلة في قاعدة البيانات. مثل هذا النظام يسمّى "قاعدة بيانات إحصائية".

مفهوم "لاقابلية التمييز" [2]، المسماة لاحقاً بـالخصوصية التفاضلية[1]، تُمنْهِج مفهوم "الخصوصية" في قواعد البيانات الإحصائية.

(لاقابلية التمييز = indistinguishability)

الإجراءات المتخذة من قبل الخادم (الطرف) المؤتمن يمكن نمذجتها عن طريق خوارزمية عشوائية، نسميها هنا ${\displaystyle {\mathcal {A}}\,\!}$.

الخوارزمية العشوائية ${\displaystyle {\mathcal {A}}\,\!}$ تملك الخصوصية التفاضلية "ε" إذا كان لكل زوج من قواعد البيانات ${\displaystyle D_{1}\,\!}$

و

${\displaystyle D_{2}\,\!}$ ، مختلفين في عنصر واحد فقط، نجد المعادلة التالية متحققة لكل ${\displaystyle S\subseteq \mathrm {Range} ({\mathcal {A}})}$ في مجال الخرج الخاص بالخوارزمية:

${\displaystyle \Pr[{\mathcal {A}}(D_{1})\in S]\leq \exp(\epsilon )\times \Pr[{\mathcal {A}}(D_{2})\in S]\,\!}$

ملحوظة: الخصوصية التفاضل هو خاصية من خصائص آلية النشر (الخوارزمية العشوائية ${\displaystyle {\mathcal {A}}}$)، وليست من خصائص قاعدة البيانات في حد ذاتها.

معنى ما سبق أن آلية النشر (${\displaystyle {\mathcal {A}}}$) ستتصرف بنفس الطريقة تقريباً، لأي قاعدتي بيانات متجاورتين (مختلفان في عنصر واحد فقط)، على كلتاهما. هذا التعريف للخصوصية التفاضلية يضمن (بشدّة) أن وجود فردٍ معين من عدمه لن يؤثر على نتيجة الاستعلام بشكل ملحوظ.

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

تصوّر لو مستخدم خبيث (أحياناً يلقّب بالـ"خِصْم") يريد معرفة إن كان شريف مصاباً بالسكّري أم لا. هذا المستخدم يعرف أيضاً أن شريف يقبع في الصف الخامس من الجدول. لو الخِصْم بإمكانه الاستعلام بصورة معينة، ${\displaystyle Q(i)}$، حيث نتيجة الاستعلام عبارة عن مجموع "س" لأول ${\displaystyle i}$ صف، فبإمكان الخصم بكل بساطة أن يراجع قيمة الاستعلام ${\displaystyle Q(5)-Q(4)}$ لمعرفة إن كان شريف مصاباً بالسكّري من عدمه.

من اللافت للنظر ان هذا المثال يوضح ان معلومات الأفراد يمكن أن تُفضح حتى بدون الاستعلام عن الفرد بعينه.

• بوابة تعمية