💻 computer science

SafeStats: Efficient 2PC Protocols for Data Statistic-Related Functions

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

المؤلفون الأصليون: Tanren Liu, Xianjia Meng, Yang Liu, Xin Kang, Chenhui You, Yong Zeng, Zhuo Ma

نُشر 2026-07-29

📖 5 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Tanren Liu, Xianjia Meng, Yang Liu, Xin Kang, Chenhui You, Yong Zeng, Zhuo Ma

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

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

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

الخدع السحرية الثلاث لـ SAFESTATS

بدأ الباحثون بالنظر في برنامج جداول بيانات قياسي (مثل Microsoft Excel) لمعرفة ما يفعله الناس فعلياً عند تحليل البيانات. ووجدوا أن كل شيء تقريباً — سواء كان إيجاد الرقم "الأكثر شيوعاً" (المنوال)، أو الرقم "الأوسط" (الوسيط)، أو إجراء اختبار "كا تربيع" (Chi-Square) — يعتمد فقط على ثلاث لبنات بناء أساسية. وقد أعاد SAFESTATS ابتكار هذه اللبنات الثلاث لتعمل بشكل سري وفعال.

1. خدعة "الإزاحة" للعدّ
تخيل أن لديك صفاً من 100 صندوق فارغ، وتريد عدّ كم مرة ظهر رقم سري، وليكن "7"، في قائمة من البيانات. كانت الطريقة القديمة هي طرح سؤال: "هل هذا الرقم 7؟" لكل عنصر في القائمة. إذا كان لديك مليون عنصر، فسيتعين عليك طرح مليون سؤال، وهذا يستغرق وقتاً طويلاً.
يستخدم SAFESTATS خدعة "الإزاحة" بدلاً من ذلك. تخيل أن لديك مفتاح ضوء واحداً يعمل، وبقية المفاتيح مطفأة. إذا كان رقمك السري هو 7، فببساطة قم بإزاحة هذا الضوء "المضاء" سبع درجات جهة اليمين. الآن، أصبح الضوء في الصندوق السابع. تفعل هذا لكل عنصر في قائمتك السرية، ولكنك تفعله بطريقة لا يعرف فيها أحد أي صندوق قمت بنقل الضوء إليه. أخيراً، تقوم فقط بجمع كل الأضواء في كل صندوق. إذا كان الصندوق السابع يحتوي على 50 ضوءاً، فأنت تعلم أن الرقم 7 ظهر 50 مرة. طريقة "الإزاحة" هذه سريعة للغاية لأنها تتجنب الأسئلة المتكررة والبطيئة مثل "هل يساوي؟". وجد الفريق أن هذا النهج جعل عملية العد أسرع بمقدار 4 إلى ما يقرب من 8 مرات، وقلل أيضاً من حجم البيانات المتبادلة بين الطرفين بنفس القدر تقريباً.

2. خدعة "الدلو" للترتيب
ترتيب البيانات السرية عادة ما يكون كابوساً لأنه يتطلب مقارنة الأرقام لمعرفة أيهما أكبر. ولكن ماذا لو لم تكن بحاجة للمقارنة؟ يستخدم SAFESTATS طريقة تسمى "الترتيب بالعد" (Counting Sort)، وهي مثالية عندما لا تكون الأرقام التي ترتبها ضخمة جداً (مثل ترتيب الأعمار من 0 إلى 100، بدلاً من ترتيب أرقام عشوائية ضخمة).
فكر في الأمر كمكتب بريد يحتوي على 100 فتحة بريد. بدلاً من السؤال "هل هذه الرسالة مخصصة للفتحة 5 أم 6؟"، تقوم ببساطة بإسقاط الرسالة في الفتحة التي تطابق رقمها. يقوم SAFESTATS بذلك بشكل سري. إنهم يستخدمون بروتوكول "مؤشر القطاع" (segment indicator). تخيل أن لديك قائمة سرية من الأرقام. بدلاً من ترتيبها واحداً تلو الآخر، ينشئ النظام "خريطة" تقول: "كل الأرقام 5 تذهب في هذا النطاق المحدد من القائمة النهائية". ثم يسقط جميع الأرقام 5 في ذلك النطاق في دفعة واحدة كبيرة. هذا يتجاوز الحاجة إلى المقارنات السرية البطيئة. بالنسبة لمجموعات البيانات ذات النطاقات الصغيرة من القيم، وُجد أن هذه الطريقة الجديدة أسرع بمقدار 3.4 إلى 20.5 مرة من أفضل الطرق الموجودة، وقللت تكاليف الاتصال بمقدار يصل إلى 7.6 مرة.

3. خدعة "التنصيف" للرياضيات الصعبة
تتضمن بعض الصيغ الإحصائية رياضيات معقدة، مثل الجذور التربيعية أو اللوغاريتمات، والتي يصعب حسابها سرياً. الطريقة المعتادة للقيام بذلك هي أولاً تقليص الرقم إلى حجم يمكن التعامل معه (مثل تصغير الخريطة) ثم تخمين الإجابة باستخدام صيغة متعددة الحدود. الجزء البطيء كان تحديد مقدار التصغير المطلوب.
كانت الطريقة القديمة تشبه التحقق من صفحات كتاب صفحة بصفحة للعثور على كلمة معينة. يستخدم SAFESTATS طريقة "التنصيف" (bisection)، وهي تشبه لعبة "خمن الرقم". بدلاً من فحص كل صفحة، تقسم الكتاب إلى نصفين، وتتحقق مما إذا كانت الكلمة في النصف الأول أم الثاني، ثم تقسم ذلك النصف مرة أخرى. تستمر في تقسيم مساحة البحث إلى النصف حتى تجد بالضبط أين يجب تعديل الرقم. هذا النهج القائم على "فرق تسد" قلل الوقت اللازم لهذه الدوال الرياضية بمقدار 1.2 إلى 1.7 مرة، ووفر أيضاً بعض وقت الاتصال.

وضع كل شيء معاً: اختبار "كا تربيع"

لإثبات فعالية مجموعة أدواتهم، اختبر الباحثون SAFESTATS على 14 سيناريو إحصائياً مختلفاً من واقع الحياة. أحد الأمثلة البارزة كان اختبار "كا تربيع" (Chi-Square test)، وهو طريقة شائعة تُستخدم لمعرفة ما إذا كان هناك علاقة بين شيئين (مثل ما إذا كان ارتداء قميص أحمر يؤثر على حظك).
عندما حاولوا تشغيل هذا الاختبار باستخدام الأدوات العامة التقليدية، كان بطيئاً وكثيف الكلام. ولكن عندما استخدموا SAFESTATS، كانت النتائج مبهرة: اشتغل الاختبار أسرع بمقدار 1.5 مرة، وانخفض مقدار البيانات التي كان على الطرفين إرسالها ذهاباً وإياباً بمقدار 4.2 مرة.

الورقة البحثية لا تدعي هذه النتائج فحسب؛ بل قاموا بالفعل ببناء النظام وتشغيل الأرقام. لقد أظهروا أنه من خلال التركيز خصيصاً على احتياجات التحليل الإحصائي — بدلاً من محاولة صنع أداة "شاملة لكل شيء" — استطاعوا إنشاء طريقة أكثر كفاءة للحفاظ على خصوصية البيانات مع الاستمرار في الحصول على الإجابات التي نحتاجها. إنه تذكير بأنه في بعض الأحيان، أفضل طريقة لحل مشكلة ليست ببناء مطرقة أكبر، بل باختراع مفك براغي أفضل.

ملخص تقني: SAFESTATS

بيان المشكلة

يعد التحليل الإحصائي للبيانات الحساسة (مثل السجلات الطبية أو المعاملات المالية) أمراً بالغ الأهمية لاتخاذ القرار، ولكنه يثير مخاوف كبيرة تتعلق بالخصوصية. وبينما تقدمت الحوسبة ثنائية الأطراف الآمنة (2PC) بشكل كبير في العمليات الأولية منخفضة المستوى (الجمع، الضرب) وتطبيقات تعلم الآلة، إلا أنها لا تزال غير فعالة بالنسبة للدوال الإحصائية المحددة. تحاول النهج الحالية عادةً إعادة إنتاج العمليات الإحصائية (مثل الوسيط، الرتبة، المنوال) عن طريق تجميع مباشر لعمليات 2PC العامة. يؤدي هذا التجميع "الساذج" إلى تكاليف باهظة؛ فعلى سبيل المثال، يمكن أن يستغرق حساب دالة الرتبة (Rank) لـ $2^{12}$ عنصر أكثر من 18 دقيقة حتى مع استخدام بروتوكولات متطورة. وتتمثل الاختناقات الأساسية في الاعتماد على اختبارات التساوي الآمنة المكلفة، والمقارنات الآمنة، وعمق الدوائر المتسلسلة التي لا تتوسع بشكل جيد للمهام الإحصائية التي تتضمن مجموعات بيانات كبيرة ذات نطاقات سمات قابلة للتعداد الصغير.

المنهجية

يقترح المؤلفون SAFESTATS، وهو مجموعة أدوات آمنة مصم-مة خصيصاً للتحليل الإحصائي ثنائي الأطراف (2PC). تضمنت عملية التطوير تحليل مكتبة مايكروسوفت إكسل الإحصائية لتحديد أن معظم العمليات الإحصائية تعتمد على ثلاث لبنات بناء أساسية: عد التكرار، الفرز، والدوال الرياضية غير الخطية. يقدم SAFESTATS بروتوكولات متخصصة وفعالة لكل من هذه اللبنات، متجنباً استخدام العمليات العامة حيثما أمكن ذلك.

1. عد التكرار الآمن (استراتيجية القائم على الإزاحة)

تقوم الطرق التقليدية بحساب التكرار عبر إجراء $m$ من اختبارات التساوي لكل عنصر مدخل، مما ينتج عنه $O(m\ell)$ من استدعاءات النقل الآمن (Oblivious Transfer - OT).

الابتكار: يلاحظ SAFESTS أن نتيجة التحقق مما إذا كان مدخل $x$ يساوي أي قيمة $v \in [0, m-1]$ تشكل متجه وحدة بوليني $\vec{e}_x$ . وبدلاً من بناء هذا المتجه عبر $m$ من اختبارات التساوي، يعامل البروتوكول $\vec{e}_x$ كنسخة مزاحة لليمين من متجه الوحدة الأساسي $\vec{e}_0$ بمقدار الإزاحة $x$ .
الآلية: يستخدم البروتوكول استراتيجية إزاحة قائمة على الإزاحة باستخدام تقييم الإزاحة المتجهية العشوائية ( $F_{RVOSE}$ ). وهو يستبدل $m$ من اختبارات التساوي بعملية إزاحة متجه واحدة.
التحسين: في الحالات التي يتجاوز فيها تكرار المنوال نسبة $n/2$ ، يقدم المؤلفون تحسيناً قائماً على نظرية الباقي الصينية (CRT). يقوم هذا التحسين بتفكيك نطاق السمات الكبير إلى نطاقات فرعية أصغر متباينة، مما يسمح ببناء متجهات تكرار أقصر وإعادة بناء المنوال محلياً.

2. الفرز الآمن (القائم على العد مع مؤشرات القطع)

تعاني عمليات الفرز الآمنة العامة (مثل الفرز القائم على المقارنة الآمنة) من ارتفاع في عمق الدائرة وعدد جولات الاتصال، والتي يهيمن عليها تكلفة المقارنة الآمنة.

الابتكار: يقترح SAFESTS فرزاً آمناً قائماً على العد يلغي الحاجة إلى المقارنات الآمنة.
الآلية: يتكون البروتوكول من بناء متجه التكرار (باستخدام الطريقة المذكورة أعلاه) وإدراج العناصر. وللإدراج، يقدم البروتوكول بروتوكول مؤشر القطعة الآمن. يقوم هذا البروتوكول بتوليد متجه مشترك سري يكون قيمته 1 فوق فترة محددة $[a, b]$ و0 في مكان آخر.
الكفاءة: باستخدام مؤشر القطعة، يمكن إدراج جميع العناصر التي لها نفس القيمة في متجه المخرجات عبر عملية ضرب عنصر بعنصر واحد، مما يحقق عمق دائرة ثابتاً ( $O(1)$ ) لمرحلة الإدراج. وهذا يقلل من تعقيد OT من $O(n \log n \log(nm))$ إلى $O(n(m + \log m))$ .
حالة خاصة (المئويات): إدراكاً بأن المئويات لا تتطلب فرزاً كاملاً، يعيد المؤلفون صياغة المشكلة كمسألة اختبار فترات. ومن خلال التحقق من أي فترة في متجه التكرار التراكمي تحتوي على الرتبة المستهدفة $k$ ، يتجنبون الفرز الكامل، مما يحسن الأداء بشكل أكبر للمجالات الصغيرة للسمات.

3. الدوال الرياضية غير الخطية (تقليص النطاق القائم على التنصيف)

يتبع التقييم الآمن للدوال غير الخطية (مثل اللوغاريتم، الجذر التربيعي) عادةً نموذج "التقليص ثم التقريب"، حيث تكون التكلفة الأكثر أهمية هي تقليص النطاق (تحديد البت الأكثر أهمية غير الصفري - MSNZ).

الابتكار: تحدد البروتوكولات الحالية بت الـ MSNZ عبر مسح خطي متسلسل للأرقام، مما يتطلب $O(d)$ من جولات الاتصال.
الآلية: يقدم SAFESTS بروتوكول تقليص نطاق قائم على التنصيف. بدلاً من المسح المتسلسل، يقوم البروتوكول بتقسيم المدخلات تكرارياً واختيار النصف غير الصفري في كل خطوة.
الكفاءة: يقلل هذا من جولات الاتصال لتحديد MSNZ من $O(d)$ إلى $O(\log d)$ ، مما يقلل بشكل كبير من زمن الوصول لتقييم الدوال غير الخطية.

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

دالة العد الآمنة: بروتوكول عد تكرار قائم على الإزاحة يقلل من استدعاءات OT من $O(m\ell)$ إلى $O(\log m)$ ، مع نسخة متغيرة قائمة على نظرية الباقي الصينية لحساب المنوال.
دالة الفرز الآمنة: بروتوكول فرز قائم على العد يستخدم آلية مؤشر القطعة الآمنة لتحقيق جولات اتصال ثابتة وتجنب المقارنات الآمنة، بالإضافة إلى نهج اختبار الفترات للمئويات.
الدوال غير الخطية الآمنة: بروتوكول تحديد MSNZ قائم على التنصيف يقلل جولات الاتصال من $O(n)$ إلى $O(\log n)$ ، جنباً إلى جنب مع تحليل نطاقات تقريب كثيرات الحدود لضغط الفترات.
التنفيذ والتقييم: تنفيذ كامل لـ SAFESTS تم قياس أدائه مقابل 14 حالة إحصائية شائعة (بما في ذلك المنوال، الوسيط، الرتبة، اختبار كا-تربيع، إلخ) ومقارنته بمكتبات 2PC العامة (مثل EzPC).

النتائج

قام المؤلفون بتنفيذ SAFESTS واختباره على 14 حالة تحليل إحصائي. تظهر النتائج تحسينات متسقة مقارنة بالنماذج المرجعية التي تستخدم مباشرة عمليات 2PC العامة:

اختبار كا-تربيع (Chi-Square Test): حقق تسريعاً في وقت التشغيل بمقدار 1.5 $\times$ وتقليلاً في الاتصالات بمقدار 4.2 $\times$ .
عد التكرار: حقق تحسناً في وقت التشغيل بمقدار 4.0–7.9 $\times$ وتحسناً في الاتصالات بمقدار 3.1–8.6 $\times$ مقارنة بالطرق القائمة على التساوي.
الفرز الآمن: حقق تسريعاً في وقت التشغيل بمقدار 3.4–20.5 $\times$ وتقليلاً في الاتصالات بمقدار 1.3–7.6 $\times$ مقارنة بطرق الفرز السابقة القائمة على المقارنة (في السيناريوهات حيث $m \le \log_2 n$ ).
الدوال غير الخطية: حقق تقليلاً في وقت التشغيل بمقدار 1.2–1.7 $\times$ وتقليلاً في الاتصالات بمقدار 1.15–1.16 $\times$ مقارنة بالأعمال الحالية.

الأهمية

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