Secure Two-Party Matrix Multiplication from Lattices and Its Application to Encrypted Control

إليك ملخص تقني مفصل لورقة "ضرب المصفوفات الآمن بين طرفين باستخدام الشبكات (Lattices) وتطبيقاته في التحكم المشفر" للباحث كاورو تيرانيشي.

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

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

• قيود بيئات الخادم الواحد: غالبًا ما تؤدي الأساليب الحالية التي تستخدم التشفير المتماثل (Homomorphic Encryption - HE) في بيئة الخادم الواحد إلى أعباء حسابية عالية على العميل. فتكاليف فك التشفير والتشفير لدى العميل تتجاوز في كثير من الأحيان تكلفة الحساب الأصلي غير المشفر، مما يجعلها غير عملية للتحكم في الوقت الفلي (Real-time).
• قيود بيئات الأطراف المتعددة: بينما يقلل الحساب متعدد الأطراف (MPC) باستخدام المشاركة السرية (Secret Sharing) من حمل العميل، تواجه بروتوكولات الطرفين الحالية عقبات كبيرة:
  • تعقيد الضرب: يتطلب ضرب قيمتين مشتركتين سرياً بشكل آمن عادةً جولات متعددة من الاتصال أو عمليات حساب مسبق معقدة (مثل Beaver triples).
  • عبء العميل: إن توليد Beaver triples أو إدارة التفاعلات متعددة الجولات ينقل العبء الحسابي مرة أخرى إلى العميل.
  • قيود البنية التحتية: تتطلب البدائل الفعالة مثل "المشاركة السرية المكررة" (Replicated Secret Sharing) ثلاثة أطراف على الأقل غير متواطئين، مما يزيد من تكاليف النشر.

التحدي الجوهري: كيفية تحقيق ضرب المصفوفات الآمن في بيئة مكونة من طرفين مع اتصال من جولة واحدة، مع ضمان أن يكون التعقيد الحسابي عبر الإنترنت (Online) للعميل أقل من حساب التحكم الأصلي غير المشفر.

2. المنهجية

يقترح المؤلفون بروتوكولاً جديداً للحساب بين طرفين (2PC) لـ الضرب التقريبي للمصفوفات للأعداد ذات الفاصلة الثابتة. يدمج الحل بين المشاركة السرية الجمعية (Additive Secret Sharing) وتشفير الشبكات (Lattice-based Cryptography) (تحديداً التعلم مع الأخطاء LWE وحل العدد الصحيح القصير SIS).

أ. الأسس التشفيرية

• التعلم مع الأخطاء (LWE): يُستخدم لتشفير المتجهات. يتم تشكيل النص المشفر $c$ كـ $A^T s + x + e \pmod q$، حيث $x$ هي الرسالة، و$s$ هو المفتاح السري، و$e$ هو حد الخطأ.
• حل العدد الصحيح القصير (SIS): يُستخدم لإنشاء الالتزامات (Commitments). يتم تشكيل الالتزام $h$ كـ $Ay + Br \pmod q$، حيث $y$ هي الرسالة و$r$ هو متجه عشوائي قصير.
• المشاركة السرية (Secret Sharing): مخطط جمعي قياسي حيث يتم تقسيم المصفوفة $X$ إلى حصص $JXK_0 = R$ و $JXK_1 = X - R$. يمكن للأطراف جمع أو طرح الحصص محلياً دون تفاعل.

ب. الآلية الجوهرية: الضرب الداخلي التقريبي

يستفيد البروتوكول من خاصية رياضية مشتقة من LWE وSIS لحساب الضرب الداخلي دون الكشف عن المدخلات.
بالنظر إلى:

1. نصوص LWE المشفرة للمتجه $x$: $c = A^T s + x + e$ و $c' = B^T s + e'$.
2. التزام SIS للمتجه $y$: $h = Ay + Br$.

يحسب البروتوكول:
$$c^T y + (c')^T r - s^T h \approx x^T y \pmod q$$
تُلغى الحدود التي تتضمن المفتاح السري $s$ والمتجه العشوائي $r$، مما يترك الضرب الداخلي $x^T y$ بالإضافة إلى حد ضجيج صغير.

ج. هيكل البروتوكول (Mult)

ينقسم البروتوكول إلى ثلاث مراحل:

1. الإعداد (Offline): يقوم العميل بتوليد المعاملات العامة (المصفوفات العشوائية $A, B$) وينشر سلسلة مرجعية مشتركة (CRS).
2. مرحلة العمل غير المتصل (Client-side Offline): يقوم العميل بتشفير مصفوفة المدخلات $X$ إلى أعداد صحيحة ذات فاصلة ثابتة، ويولد نصوص LWE المشفرة ($C, C'$) وحصص المفتاح السري ($J S K$). تُرسل هذه البيانات إلى طرفي الحوسبة ($P_0, P_1$).
3. مرحلة العمل المتصل (Online Interactive):
   • يقوم العميل بتشفير مصفوفة المدخلات الثانية $Y$، ويقسمها إلى حصص $J \bar{Y} K$، ويرسلها إلى الأطراف.
   • يقوم الأطراف محلياً بتوليد حصص عشوائية للمتجه $R$.
   • يقوم الأطراف بحساب حصة الالتزام $J H K$ محلياً باستخدام خطية المشاركة السرية.
   • يقوم الأطراف بإعادة بناء $H$ (جولة واحدة من الاتصال) ويحسبون حصص النتيجة $J \bar{Z} K$ باستخدام الصيغة: $C^T J \bar{Y} K + (C')^T J R K - J S K^T H$.
   • يرسل الأطراف $J \bar{Z} K$ إلى العميل، الذي يقوم بإعادة بناء النتيجة النهائية $Z$.

د. الحساب بالفاصلة الثابتة والدقة

يعمل البروتوكول على أعداد ذات فاصلة ثابتة $Q_{\langle k, \ell \rangle}$ (حيث $k$ هو إجمالي عدد البتات، و$\ell$ هو عدد بتات الكسر). يستنتج المؤلفون حدوداً رياضية (التمهيد 1 والنظرية 1) لضمان:

1. عدم تجاوز الحد (No Modular Wrap-around): يجب أن يكون طول البت $k$ صغيراً بما يكفي بالنسبة للمقياس $q$ لمنع التجاوز (Overflow).
2. الدقة: يجب أن يكون طول بت الكسر $\ell$ كبيراً بما يكفي لإبقاء خطأ التقريب (الضجيج) تحت عتبة محددة $\epsilon$.

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

1. بروتوكول 2PC بجولة واحدة: أول بروتوكول يحقق الضرب التقريبي للمصفوفات بين طرفين في جولة اتصال واحدة، مما يلغي الحاجة إلى تفاعلات متعددة الجولات أو حسابات مسبقة ثقيلة على العميل (مثل Beaver triples).
2. تعقيد منخفض للعميل: تم تقليل التعقيد الحسابي للعميل في مرحلة العمل المتصل (Online) إلى $O(n_x + n_u)$ (توليد الحصص وإعادة بناء النتائج)، وهو أقل بكثير من تعقيد $O(n_x n_u)$ لضرب المصفوفات المباشر. وهذا يجعل عبء العميل أقل من مهمة التحكم الأصلية غير المشفرة.
3. ضمانات دقة نظرية: توفر الورقة شروطاً صارمة لمعاملات الفاصلة الثابتة ($k, \ell$) لضمان بقاء خطأ التقريب ضمن حد مرغوب فيه، مع مراعاة ضجيج الشبكة والتقييد (Quantization).
4. إثبات الأمان: تم إثبات أمان البروتوكول تحت افتراضات الشبكة القياسية (LWE و SIS) في النموذج شبه الأمين (Semi-honest model)، مما يضمن عدم تعلم الأطฝ่าย الحوسبة أي شيء عن المدخلات ($X, Y$) أو المخرجات ($Z$).

4. النتائج والتقييم

قام المؤلفون بالتحقق من صحة البروتوكول من خلال تطبيقه على قانون تحكم خطي ($u = Kx + v$).

• إعداد المحاكاة:
  • النظام: نظام زمني خطي ثابت (LTI) بمتجه حالة مكون من حالتين ومدخل تحكم واحد.
  • المعاملات: تم ضبط معاملات LWE لأمان 128 بت ($n=212, q=2^{108}, \sigma=3.2$).
  • الفاصلة الثابتة: $k=53$ بت، $\ell=44$ بت.
• مقاييس الأداء:
  • الاتصال: جولة واحدة فقط من التفاعل بين طرفي الحوسبة (تبادل الالتزام المعاد بناؤه $H$).
  • تحليل الخطأ: ظل خطأ مدخل التحكم $\| \tilde{u} - \hat{u} \|_{max}$ (الفرق بين نتيجة التشفير المكممة والنتيجة المثالية المكممة) تحت الحد النظري $\epsilon = 2^{-10}$.
  • أداء التحكم: كان الخطأ بين مدخل التحكم المشفر ومدخل التحكم الأصلي غير المشفر ضئيلاً، مما أثبت أن النظام يحافظ على الاستقرار والأداء رغم التشفير والتقييد.
• التعقيد: تم التأكد من أن عمليات العميل في مرحلة العمل المتصل هي خطية في أبعاد الحالة/المدخلات، بينما عملية التحكم الأصلية هي تربيعية (ضرب مصفوفة في متجه).

5. الأهمية

يمثل هذا العمل تقدماً كبيراً في أنظمة التحكم التي تحافظ على الخصوصية:

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