Efficient Mod Approximation and Its Applications to CKKS Ciphertexts

إليك ملخص تقني مفصل للورقة البحثية بعنوان "تقريب دالة المود (Mod) الفعال وتطبيقاته على نصوص CKKS المشفرة" للباحث يو فاي زو (Yufei Zhou).

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

يُستخدم نظام التشفير المتماثل (HE) من نوع CKKS على نطاق واسع للحسابات التقريبية على الأعداد الحقيقية المشفرة، ولكنه يدعم فطرياً عمليات الجمع والضرب فقط. وهو يفتقر إلى الدعم المباشر للعمليات غير الخطية أو المنفصلة، وتحديداً دالة المود (modulus function - $x \mod p$).

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

2. المنهجية

يقترح المؤلفون إطار عمل مبتكر يرتكز على تقريب كثير حدود عالي الدقة لدالة المود، والذي يعمل كأساس لتعبئة البيانات الفعالة وغيرها من التحويلات التشفيرية.

أ. تقريب دالة المود بدقة

• المنهج: بدلاً من الاعتماد على التقريبات المثلثية الصالحة فقط للفترات الصغيرة، يستخدم المؤلفون الاستكمال بكثير الحدود (polynomial interpolation) بالتزامن مع توسيع متسلسلة تشيبيشيف (Chebyshev series expansion).
• أخذ العينات المنفصلة: تعامل الطريقة دالة المود كمجموعة من نقاط العينات المنفصلة $(i, i \mod p)$ للمدخلات الصحيحة في الفترة $[0, B]$.
• متسلسلة تشيبيشيف: لتجنب ظاهرة رونج (Runge phenomenon) وعدم الاستقرار العددي المرتبط باستكمال لاجرانج لدرجات عالية، قام المؤلفون بملاءمة البيانات باستخدام متسلسلة تشيبيشيف من النوع الأول.
  • يتم رسم خريطة لنطاق المدخلات إلى $[-1, 1]$.
  • يتم حل المعاملات عبر طريقة المربعات الصغرى، مع اختيار الحل ذو الحد الأدنى من معيار $\ell_2$ لضمان الاستقرار.
• عامل القياس ($\delta$): لمنع تضخم الخطأ أثناء التقييم المتماثل (حيث تؤدي المعاملات التي تزيد عن 1 إلى نمو سريع للضجيج)، قدم المؤلفون عامل قياس $\delta$. يقومون بتعديل $\delta$ بشكل تكراري لضمان بقاء جميع قيم تقييم كثير الحدود الوسيطة أقل من 1 بشكل صارم، مما يضمن الاستقرار العددي دون الحاجة إلى عملية الـ bootstrapping.
• التقييم: تُستخدم طريقة باترسون-ستوكماير (Paterson–Stockmeyer) لتقييم كثيرات حدود تشيبيشيف ذات الدرجة العالية بكفاءة داخل دائرة CKKS.

ب. مخططات تعبئة البيانات (Data Packing Schemes)

بناءً على عملية "المود" المتماثلة الفعالة، تم تصميم مخططين جديدين لتعبئة البيانات لتعظيم استغلال خانات النصوص الصريحة (plaintext slots) في CKKS للمدخلات ذات الأعداد الصحيحة الصغيرة:

1. BitStack:
   • الآلية: تقوم بدمج التمثيلات الثنائية (binary representations) لعدة عناصر في عدد صحيح واحد كبير.
   • تفريغ البيانات (Unpacking): يستخدم دالة المود المتماثلة لاستخراج الطبقات بالتتابع (على سبيل المثال، $x \mod 2^{l_1}$ تستخرج الطبقة الأولى).
   • المزايا: مدمجة للغاية؛ لا يوجد تكرار في التمثيل الثنائي.
   • العيوب: عملية تفريغ البيانات تسلسلية، مما يؤدي إلى تراكم الخطأ وزيادة استخدام العمق الضربي (multiplicative depth).
2. CRTStack (مكدس نظرية الباقي الصينية):
   • الآلية: تقوم بتعبئة البيانات عبر حل نظام من التطابقات $x \equiv a_i \pmod{P_i}$، حيث $P_i$ هي معاملات متباينة (pairwise coprime).
   • تفريغ البيانات: يستخدم عمليات المود المتماثلة مع معاملات مختلفة ($P_i$) لاستخراج الطبقات بالتوازي.
   • المزايا: التفريغ المتوازي يقلل زمن التأخير؛ الأخطاء في كل طبقة مستقلة (لا يوجد تراكم للأخطاء).
   • العيوب: يتطلب اختيار معاملات متباينة، مما قد يؤدي إلى بعض التكرار في النطاق.

ج. تطبيقات إضافية

• التقريب المتماثل (Homomorphic Rounding): تمكن دالة المود من تنفيذ وظائف Floor و Ceil و Round للأعداد الصحيحة الصغيرة باستخدام العلاقة: $\text{Floor}(x, p) = (x - \text{Mod}(x, p)) / p$.
• تحويل مشاركة الأسرار إلى HE: تم اقتراح مخطط تحويل عام لتحويل المشاركات الجمعية (additive secret shares) (من الحوسبة متعددة الأطراف MPC) مباشرة إلى نصوص CKKS المشفرة دون تعديل مخطط مشاركة الأسرار الأساسي. ويتم ذلك عبر جمع المشاركات المشفرة وتطبيق دالة المود المتماثلة لإعادة بناء السر.

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

1. تقريب مبتكر للمود: طريقة تقريب لكثير الحدود باستخدام متسلسلات تشيبيشيف تحقق دقة عالية (تصل إلى $10^{-8}$) عبر كامل نطاق المدخلات الصحيحة المحدود، متجاوزةً قيود تقريبات النطاق الجزئي السابقة.
2. تعبئة بيانات فعالة: تقديم BitStack و CRTStack، اللذين يقللان بشكل كبير من عبء الاتصالات ووقت التشفير لمدخلات الأعداد الصحيحة الصغيرة عن طريق تعبئة عدة قيم في نص مشفر واحد.
3. التقريب المتماثل: تنفيذ عمليات التقريب الدقيقة لنصوص CKKS، مما يسمح بمعالجة تشبه الأعداد الصحيحة على الحسابات التقريبية لـ HE.
4. تحويل مشاركة الأسرار: أول مخطط كامل لتحويل المشاركات الجمعية إلى نصوص CKKS المشفرة باستخدام عمليات CKKS فقط، مما يسد الفجوة بين MPC و HE.

4. النتائج التجريبية

أُجريت التجارب باستخدام مكتبة OpenFHE على معالج Intel Xeon Gold.

• دقة التقريب: حققت الطريقة المقترحة متوسط خطأ مطلق منخفض جداً يصل إلى $10^{-8}$ (مع درجة كثير حدود 45+)، متفوقة بشكل كبير على النماذج المرجعية مثل Lee et al. [LLL+21] (خطأ $\approx 2.0$) وتقريبات OpenFHE القياسية.
• كفاءة تعبئة البيانات:
  • الاتصال: قللت طرق التعبئة المقترحة حركة مرور البيانات المرفوعة (upload traffic) بما يقرب من رتبتين عشريتين مقارنة بتشفير CKKS القياسي.
  • السرعة: مقارنة بإطار عمل Rubato Transcipher، كانت الطريقة المقترحة أسرع بـ 1.6 مرة في تفريغ البيانات (156 ثانية مقابل 407 ثوانٍ) وحققت خطأً أقل بـ 10 مرات ($4.0 \times 10^{-6}$ مقابل $7.5 \times 10^{-5}$).
  • زمن التأخير: في ظل عرض نطاق ترددي متوسط (400–600 كيلوبايت/ثانية)، كان إجمالي زمن التأخير (التشفير + الرفع + التفريغ) أقل من كل من أنظمة CKKS و Transcipher القياسية.
• التقريب والتحويل: حقق التقريب المتماثل أخطاء في حدود $10^{-10}$. كما حافظ تحويل مشاركة الأسرار على أخطاء في حدود $10^{-8}$ حتى مع زيادة عدد الأطراف.

5. الأهمية

يعالج هذا العمل فجوة حرجة في عملية تطبيق CKKS في التطبيقات الواقعية التي تتضمن أعداداً صحيحة صغيرة (مثل البيانات الجينية، معالجة الصور، وبيانات مستشعرات IoT).

• القابلية للتوسع: من خلال تقليل عدد النصوص المشفرة المطلية لرفع البيانات بشكل جذري، فإنه يخفف من اختناق الاتصال الذي يحد حالياً من اعتماد HE.
• التوسع الوظيفي: يوسع القدرة التعبيرية الوظيفية لـ CKKS بما يتجاوز الحسابات الخطية، مما يتيح العمليات غير الخطية الأساسية مثل التقريب والاختزال الموديلي (modular reduction).
• التوافق التشغيلي: يوفر مخطط تحويل مشاركة الأسرار جسراً سلساً بين الحوسبة متعددة الأطراف الآمنة (MPC) والتشفير المتماثل (HE)، مما يسمح ببناء بنيات هجينة للحفاظ على الخصوصية.
• القيود: الطريقة محسنة حالياً للمدخلات الصحيحة الصغيرة (النطاقات المحدودة، عادة $B < 100$) وليست مخصصة لعمليات الـ bootstrapping واسعة النطاق حيث يكون نطاق المدخلات شاسعاً. ومع ذلك، فإن هذا يغطي مجموعة واسعة من حالات الاستخدام العملية في تحليل البيانات والتعلم الآلي.