Combinatorial Privacy: Private Multi-Party Bitstream Grand Sum by Hiding in Birkhoff Polytopes

إليك ملخص تقني مفصل لورقة البحث بعنوان "الخصوصية التوافقية: المجموع الكلي لتدفق البتات متعدد الأطراف الخاص عبر الإخفاء في متعددات سطوح بيركوف" للباحث برانيث فيباكوما.

1. بيان المشكلة

تعالج الورقة مشكلة المجموع البولياني متعدد الأطراف الخاص. في هذا السيناريو، يمتلك كل عميل من العملاء $k$ تدفقاً ثنائياً (bitstream) خاصاً بطول $n$. يرغب الخادم في حساب العدد الإجمالي للواحدات عبر جميع الـ $kn$بت (المجموع الكلي$S$) دون معرفة تدفق البتات الخاص بكل عميل، أو المجاميع الجزئية، أو أعداد البتات المحددة.

تواجه الحلول الحالية مقايضات كبيرة:

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

تقترح الورقة نموذجاً جديداً يسمى الخصوصية التوافقية (Combinatorial Privacy)، والذي يهدف إلى تحقيق تجميع دقيق مع أمان معلوماتي للخادم الرئيسي وأمان حوسبي للمجمع، دون الحاجة إلى بنية تحتية للمفاتح العامة.

2. المنهجية: بروتوكول PolyVeil

الابتكار الجوهري هو تشفير البيانات الثنائية الخاصة كـ مصفوفات تبديل وإخفائها داخل متعدد سطح بيركوف (مجموعة المصفوفات ثنائية التعيين/doubly stochastic matrices).

أ. الأساس الرياضي

• التشفير: يقوم كل عميل $t$ بتشفير تدفق البتات الخاص به $b_t$ في مصفوفة تبديل قطرية كتلية $M_t$ بحجم $2n \times 2n$. كل بت $b_{t,j}$ يقابل كتلة $2 \times 2$: مصفوفة الوحدة ($I_2$) للصفر، ومصفوفة التبديل ($J_2$) للواحد.
• القناع (Masking): ينشئ العميل مصفوفة مقنعة $D_t$ عن طريق أخذ توليفة محدبة لمصفوفتة الخاصة $M_t$ ومصفوفات التمويه (decoys) العشوائية $P_{t,i}$ من نوع $K_t$:
  $$D_t = \alpha^* M_t + \sum_{i=1}^{K_t} \alpha_{t,i} P_{t,i}$$
  هنا، $\alpha^* \in (0,1)$ هو عامل قياس علني، و $\sum \alpha_{t,i} = 1 - \alpha^*$. وبناءً على مبرهنة بيركوف-فون نيومان، فإن $D_t$ هي مصفوفة ثنائية التعيين.
• الاستخراج الجبري: يستخدم البروتوكول متجهات اختيار محددة $w$ و $y$ بحيث يكون $w^T M_t y = s_t$ (عدد الواحدات في تدفق البتات). وبسبب الخطية، يمكن للخادم حساب قيمة عددية $f_t = w^T D_t y = \alpha^* s_t + \eta_t$، حيث $\eta_t$ هو حد الضجيج المستمد من مصفوفات التمويه.

ب. البنية ذات الطبقتين

تحدد الورقة ثغرة قاتلة في التنفيذات الساذجة (هجوم إلغاء الخلط/De-Shuffling Attack) وتقترح بروتوكولاً مصححاً ذا طبقتين:

1. الطبقة الأولى: الأمان المعلوماتي (الخادم)

   • يتلقى الخادم فقط قيم عددية مجمعة: $F = \sum f_t$ و $H = \sum \eta_t$ (الأخير يتم الحصول عليه عبر مخلط موثوق أو مجمع ضجيج منفصل).
   • يحسب الخادم $S = (F - H) / \alpha^*$.
   • الأمان: رؤية الخادم متطابقة التوزيع لأي مدخلات لها نفس المجموع الكلي $S$. يوفر هذا أماناً مثالياً قائماً على المحاكاة (مسافة إحصائية صفرية)، مما يعني أن الخادم لا يتعلم أي شيء عن المدخلات الفردية، حتى مع قدرة حوسبية لانهائية.

2. الطبقة الثانية: الأمان الحوسبي (المجمع)

   • يتلقى كيان منفصل (المجمع) المصفوفات المقنعة الكاملة $D_t$ ولكن ليس قيم الضجيج $\eta_t$.
   • لمعرفة $s_t$، يجب على المجمع عكس عملية القناع: استعادة $M_t$ من $D_t$.
   • الأمان: يتطلب هذا تقييم كثافة الاحتمال لمصفوفة عشوائية ثنائية التعيين عند نقطة معينة. تثبت الورقة أن حساب هذه الكثافة (وبالتالي احتمالية وجود مصفوفة تبديل مرشحة) هو مسألة #P-hard، وتختزل إلى حساب المنمنم (Permanent) للمصفوفة والمميز المختلط (Mixed Discriminant). وهذا يخلق حاجزاً حوسبياً أمام الخصوم ذوي الزمن متعدد الحدود.

ج. المتغيرات

• النسخة الكاملة: يرى المجمع المصفوفة الكاملة $D_t$. يعتمد الأمان على صعوبة المسألة من نوع #P-hard.
• النسخة المضغوطة: يقوم العملاء بحساب $f_t$ محلياً ويرسلون فقط القيمة العددية إلى المجمع. هذا يقلل الاتصالات إلى $O(k)$ ويسمح بتحليل صارم للخصوصية التفاضلية $(\epsilon, \delta)$.

3. المساهمات الرئيسية

1. نموذج الخصوصية التوافقية: يقدم نموذجاً جديداً للخصوصية يختلف عن الصعوبة القائمة على نظرية الأعداد (MPC/HE) أو الضجيج الإحصائي (DP)، مستفيداً من البنية التوافقية لمتعدد سطح بيركوف.
2. تحليل هجوم إلغاء الخلط: يثبت بصرامة أن البروتوكولات الساذجة التي يرى فيها الخادم قيمًا مرتبطة بالهوية وضجيجاً ممزوجاً هي غير آمنة. تسمح قيد التكامل لعدّ البتات للخادم شبه النزيه بإعادة بناء جميع البيانات الفردية بشكل فريد باحتمالية 1.
3. تصميم بروتوكول ذي طبقتين: يقترح بنية مبتكرة تفصل بين "المعلومات" (المصفوفات) و"الضجيج" (القيم العددية) لضمان عدم قدرة أي كيان واحد على اختراق الخصوصية.
4. إثبات الصعوبة الحوسبية: يوضح أن الاستدلال القائم على الاحتمالية للمجمع هو مسألة #P-hard، مما يوفر حاجزاً حوسبياً قوياً ضد الهجمات ذات الزمن متعدد الحدود.
5. تحليل الخصوصية التفاضلية للعينات المحدودة: يقدم ثوابت صريحة لضمانات $(\epsilon, \delta)$-DP للمجمع في النسخة المضغوطة، مع تحليل المقايضة بين عدد مصفوفات التمويه، ونسبة الإشارة إلى الضجيج (SNR)، ومعايير الخصوصية.

4. النتائج والمكتشفات

• الصحة (Correctness): ينتج البروتوكول المجموع الكلي الدقيق $S$ بدون أي خطأ، حيث تُلغي حدود الضجيج بعضها البعض جبرياً أثناء التجميع.
• أمان الخادم: يحقق الخادم أماناً غير مشروط. رؤيته غير متمايزة إحصائياً لأي مجموعتين من المدخلات تعطيان نفس المجموع $S$.
• أمان المجمع:
  • البروتوكول الكامل: يواجه المجمع مسألة #P-hard. بينما تكون الإشارة مرئية (يمكن اكتشافها من قبل خصم غير محدود القدرة)، إلا أن فك تشفيرها حوسبياً مستعصٍ.
  • البروتوكول المضغوط: يرى المجمع فقط قيمة عددية $f_t = \alpha^* s_t + \eta_t$. تشتق الورقة ضمانات $(\epsilon, \delta)$-DP غير فارغة (non-vacuous).
• توتر "الخصوصية الفارغة" (Vacuous DP Tension):
  • تكشف الورقة عن توتر جوهري:
    • لتحقيق خصوصية تفاضلية غير فارغة (أي $\epsilon$ ذات معنى)، يجب أن تكون نسبة الإشارة إلى الضجيج منخفضة، مما يجعل الإشارة غير قابلة للاكتشاف. في هذا النظام، تصبح بنية بيركوف غير ذات صلة، ويكفي استخدام ضجيج غاوسي بسيط.
    • لاستخدام صعوبة #P-hard لبنية بيركوف، يجب أن تكون الإشارة مرئية (قيمة $\alpha^*$ متوسطة). ومع ذلك، في هذا النظام، تصبح ضمانات الخصوصية التفاضلية فارغة (أي $\epsilon$ ضخم جداً) لأن الإشارة قابلة للاكتشاف.
  • الخلاصة: لا يوجد حالياً متغير واحد يحقق كلاً من الخصوصية التفاضلية غير الفارغة وصعوبة #P-hard في آن واحد. تعمل طبقتي الأمان بمقاييس مختلفة لمعامل $\alpha^*$.

5. الأهمية

• التجميع الدقيق: على عكس الخصوصية التفاضلية، يوفر PolyVeil نتائج دقيقة، وهو أمر بالغ الأهمية لتطبيقات مثل المراقبة الوبائية أو التحليلات الاتحادية الدقيقة حيث يكون الضجيج غير مقبول.
• لا يتطلب بنية تحتية للمفاتيح العامة: لا يتطلب البروتوكول إدارة معقدة للمفاتيح أو تشفيراً بالمفاتيح العامة، بل يعتمد على عمليات متماثلة ومخلط موثوق.
• كفاءة الاتصال: تحقق النسخة المضغوطة تعقيد اتصال قدره $O(k)$، وهو مستقل عن طول تدفق البتات $n$، مما يجعلها قابلة للتوسع بشكل كبير.
• نموذج أمني جديد: ينقل أساس الأمان من "صعوبة التحليل إلى عوامل" أو "صعوبة التعلم مع الخطأ" إلى "صعوبة تفكيك متعدد سطح"، مما يفتح مساراً جديداً للحوسبة الحفاظة على الخصوصية القائمة على الهندسة التوافقية.

6. الأسئلة المفتوحة

تحدد الورقة المشكلة المركزية وهي سد الفجوة بين نظام الخصوصية التفاضلية (حيث تكون الإشارة غير مرئية) ونظام صعوبة #P-hard (حيث تكون الإشارة مرئية ولكن يصعب فك تشفيرها). إن إثبات أن بروتوكولاً واحداً يمكنه تقديم كل من الخصوصية التفاضلية غير الفارغة والصعوبة الحوسبية ضد جميع الهجمات ذات الزمن متعدد الحدود يظل تحدياً غير محلول. بالإضافة إلى ذلك، فإن توسيع إثباتات الأمان إلى النموذج الخبيث (حيث قد ينحرف العملاء عن البروتوكول) يعد اتجاهاً مستقبلياً.