Secure and Parallel Determinant Computation for Large-Scale Matrices in Edge Environments

ملخص تقني: حساب المحددات الآمن والمتوازي للمصفوفات ضخمة الحجم في بيئات الحافة

بيان المشكلة
أدى الاعتماد السريع لإنترنت الأشياء (IoT) وحوسبة الحافة إلى خلق طلب على أطر عمل قابلة للتوسع وفعالة في استهلاك الطاقة للتعامل مع المهام الحسابية المكثفة. ويعد حساب محدد المصفوفة (MDC) عملية بالغة الأهمية في أنظمة التحكم، والتشفير، والتعلم الآلي. ومع ذلك، فإن الخوارزميات التقليدية، مثل تحليل LU، تمتلك تعقيداً حسابياً تكعيبياً قدره $O(n^3)$، مما يجعلها غير عملية للمصفوفات واسعة النطاق في بيئات الحافة محدودة الموارد. علاوة على ذلك، فإن تقنيات الاستعانة بمصادر خارجية الآمنة الموجودة، بما في ذلك التشفير المتماثل والحوسبة متعددة الأطراف الآمنة (SMPC)، تفرض عبئاً حسابياً كبيراً يحد من إمكانية التطبيق في الوقت الفعلي. وبينما توجد بعض الحلول المتوازية، إلا أنها غالباً ما تواجه تحديات في القابلية للتوسع، حيث تعتمد عادةً على نماذج ذات خادمين ثابتين لا تستغل موارد الحافة الموزعة بكفاءة أو تتعامل مع أبعاد المصفوفات غير القابلة للقسمة دون حشو مفرط.

المنهجية
يقترح البحث إطار عمل حساب المحدد المتوازي الآمن (SPDC)، المصمم لتمكين حساب MDC الذي يحافظ على الخصوصية عبر عدد عشوائي ($N$) من خوادم الحافة غير الموثوقة. يعمل إطار العمل من خلال ثلاثة بروتوكولات أساسية: بروتوكول تعمية المصفوفة المحافظ على الخصوصية (PMOP)، وبروتوكول الحساب المتوازي الآمن (SPCP)، وبروت protocols استعادة النتائج والتحقق (RRVP).

1. تشويه العناصر المركب (CED): لضمان الخصوصية، يستخدم إطار العمل طريقة تشفير خفيفة الوزن تجمع بين تقنيتين:

   • تعمية العناصر (EWO): يتم تحويل عناصر المصفوفة عبر القسمة على مستوى العنصر (EWD) أو الضرب على مستوى العنصر (EWM) باستخدام متجه تعمية سري مشتق من بذرة تشفيرية.
   • نظرية دوران بانث (PRT): تحويل هندسي مبتكر يقوم بتدوير هيكل المصفوفة (بزاوية 90 أو 180 أو 270 درجة) بناءً على البذرة. تضمن نظرية PRT أن القيمة المطلقة للمحدد تظل ثابتة (أو تتغير علامتها بشكل يمكن التنبؤ به) بغض النظر عن حجم المصفوفة بمقدار 4، مما يخفي الأنماط الهيكلية دون تغيير خصائص المحدد الأساسية.

2. تحليل LU المتوازي: يعمم إطار العمل نموذج تحليل LU المتوازي لدعم عدد $N \geq 2$ من الخوادم.

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

3. التحقق والاستعادة:

   • المصادقة: للتحقق من سلامة النتيجة بأقل عبء على العميل، يقدم البحث خوارزميتين خفيفتي الوزن للمصادقة، Q2 (احتمالية، تعتمد على القياس باستخدام متجه عشوائي) و Q3 (حتمية، تعتمد على القياس باستخدام العناصر القطرية). تحل هاتان الخوارزميتان محل طرق المخرجات المتجهة، مما يقلل الحمل الحسابي. كما تم إدخال عتبة $\epsilon(N)$ لمراعاة الاختلافات في الفاصلة العائمة في البيئات متعددة الخوادم.
   • فك التشفير: يستعيد العميل المحدد الأصلي باستخدام البذرة ومكونات LU التي تم التحقق منها، مع تطبيق عامل تصحيح بناءً على زاوية الدوران وطريقة التعمية المستخدمة.

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

• بنية قابلة للتوسع بعدد $N$ من الخوادم: على عكس الأعمال السابقة المقتصرة على خادمين، يدعم SPDC عدداً عشوائياً من خوادم الحافة غير الموثوقة، مما يحسن استغلال الموارد والقابلية للتوسع.
• آلية تعمية مبتكرة: يوفر دمج نظرية دوران بانث (PRT) مع تعمية العناصر ضمانات خصوصية قوية من خلال إخفاء القيم العددية وهيكل المصفوفة مع الحفاظ على خصائص المحدد.
• التحقق الفعال: يقلل إدخال خوارزميات المصادقة القائمة على القياس (Q2 و Q3) من العبء الحسابي الإجمالي للعميل مقارنة بطرق التحقق المتجهة الحالية.
• التعامل المرن مع المصفوفات: يدعم إطار العمل المصفوفات المربعة ذات الأحجام الزوجية والفردية، حيث يطبق تمديد الأبعاد فقط عند الضرورة القصوى للتقسيم، مما يقلل من الحسابات الزائدة.

النتائج وتحليل الأداء
يقدم البحث تقييماً للأداء نظرياً بدلاً من الاختبار التجريبي.

• العبء الحسابي: يظهر البروتوكـ المقترح أدنى تعقيد إجمالي عبر مراحل توليد البذرة، وتوليد المفتاح، والتشفير، والمصادقة، وفك التشفير مقارنة بالبروتوكولات الرائدة (مثل Lei et al. و Fu et al. و Liu et al. و Gao et al.).
• القابلية للتوسع: يتم تقليل تعقيد الحساب المتوازي من $O(n^3)$ إلى حوالي $O(n^2)$ عن طريق توزيع أعباء العمل على $N$ من الخوادم.
• الأمن: يوفر إطار العمل عدم تميز ضد المهاجمين الذين يحاولون استنتاج المصفوفة الأصلية أو المحدد. وهو مقاوم للتواطؤ، حيث يمنع نمط الاتصال أحادي الاتجاه والتشفير الموزع أي مجموعة من الخوادم من إعادة بناء البيانات الأصلية دون بذرة العميل السرية.
• ملاءمة النشر: صُمم إطار العمل خصيصاً لبيئات الحافة، حيث يدعم الأجهزة محدودة الموارد وتكوينات الخوادم غير المتجانسة، على عكس الحلول السابقة التي تركز على السحابة أو ذات الطوبولوجيا الثابتة.

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