Module Lattice Security (Part II): Module Lattice Reduction via Optimal Sign Selection

ملخص تقني: أمن الشبكات المودولية عبر الاختيار الأمثل للإشارات

تقدم هذه الورقة، التي ألفها مينغ-شينغ لو (Ming-Xing Luo)، تقدماً كبيراً في التحليل الجبري لشبكات المودول (Module Lattices)، وتستهدف تحديداً مسألة "التعلم مع الأخطاء المودولية" (MLWE) التي تشكل حجر الزاوية لمعايير ما بعد الكم من قبل المعهد الوطني للمعايب والتقنية (NIST)، مثل ML-KEM (FIPS 203).

1. المشكلة: توسيع خوارزمية CDPR لتشمل الشبكات المودولية

يتمثل التحدي الجوهري الذي تعالجه الورقة في توسيع خوارزمية اختزال الشبكة CDPR (Cramer-Ducas-Peikert-Regev) من الشبكات المثالية (Ideal Lattices) ذات الرتبة ($d=1$) إلى الشبكات المودولية (Module Lattices) ذات الرتبة ($d \geq 2$).

بينما توفر خوارزمية CDPR تحسيناً أسياً على خوارزميات الشبكات العامة للشبكات المثالية — حيث تحقق عامل تقريب قدره $\exp(\tilde{O}(\sqrt{n}))$ مقارنة بـ $\exp(\tilde{O}(n))$ للخوارزميات العامة — فإن توسيع هذا النطاق ليشمل المودولات كان صعباً بسبب التعقيد الجبري المتزايد. علاوة على ذلك، فإن خطوة "اختيار الإشارة" (sign-selection) في مسار CDPR (اختيار الإشارات لتقليل خطأ فك التشفيد) اعتمدت تاريخياً على استدلالات جشعة (greedy heuristics) أدت إلى تباين ينمو مع أبعاد الحلقة (ring dimension)، مما قد يضعف كفاءة الهجوم.

2. المنهجية

يستخدم المؤلف نهجاً متعدد المراحل لسد الفجوة بين الاختزال المثالي والاختزال الموديولي:

• التفكيك عبر تعامد الأثر (Trace Orthogonality): يستفيد المؤلف من الخاصية الفريدة لحلقات السيكلوتوميك من الدرجة $2^k$ حيث يكون الأساس القوي (power basis) متعامداً في الأثر (trace-orthogonal). يسمح هذا بتفكيك المودول إلى $d$ من المودولات الفرعية المستقلة من الرتبة 1.
• تطبيق CDPR القطري (Diagonal CDPR Application): بدلاً من التعامل مع المودول ككيان واحد عالي الأبعاد، تقوم الخوارزمية بتطبيق هجوم CDPR بشكل مستقل على كل مودول فرعي من الرتبة 1 ناتج عن متجهات غرام-شميت الخطية $K$.
• التحسين العددي (MILP): تمت إعادة صياغة مسألة اختيار الإشارة الفرعية كمسألة برمجة خطية بأعداد صحيحة مختلطة (MILP). وهذا ينقل العمل من نهج "البرج الجشع" (tower greedy) نحو تحسين دقيق لتباين $L_\infty$.
• التحكم في الدقة (التقريب بمقياس CRT): لجعل الخوارزمية قابلة للتنفيذ على الأجهزة التقليدية دون الحاجة إلى حسابات ذات دقة لانهائية، قدم المؤلف طريقة للتقريب عند الأعداد الأولية المنقسمة كلياً باستخدام نظرية الباقي الصينية (CRT) وتحويلات NTT.

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

• اختزال المودول الأساسي (النظرية 5.1): خوارزمية جديدة تحقق عامل هيرميت قدره $\exp(\tilde{O}(\sqrt{n}))$. والأهم من ذلك، أن عامل اختزال المودول $\alpha_d$ هو $O(1)$ ومستقل عن الرتبة $d$، بشرط أن يستوفي الأساس المدخل "فرضية التوازن" (والتي تتحقق طبيعياً في القواعد الموزعة وفق MLWE).
• الاختيار الأمثل للإشارة (النظرية 7.1): من خلال حل مسألة MILP، يثبت المؤلف أن التباين المتوازن الأمثل $\delta^*$ هو ثابت عالمي $\approx 0.4407$، وهو مستقل عن حجم مجموعة المدار (orbit group). وهذا يؤدي إلى تضييق عامل التقريب بمقدار $\sqrt{nk}$ مقارنة بالطرق السابقة.
• التنفيذ ذو الدقة المحدودة (النظرية 6.1): تسمح مقدمة التقريب بمقياس CRT للخوارزمية بالعمل بتعقيد كلاسيكي قدره $O(d^2 r^n \log n)$ من عمليات البت، باستخدام حسابات NTT فعالة.

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

• الأداء على ML-KEM: بالنسبة لمعايير ML-KEM (مثل $n=256, d=4$)، تحافظ الخوارزمية على عامل تقريب عالي الكفاءة.
• تحليل التعقيد: ينقسم الهجوم إلى مرحلة معالجة مسبقة كلاسيكية (غرام-شميت وتقليص الحجم) ومرحلة كمومية (حل مسألة المثال الرئيسي - Principal Ideal Problem). يتناسب التكلفة الكمومية خطياً مع الرتبة $d$.
• المقارنة مع الهجمات العامة: توضح الورقة أنه بينما يعد الهجوم أقوى بكثير من اختزال BKZ العام (الذي يمتلك عامل تقريب قدره $\exp(\tilde{O}(dn))$)، إلا أنه لا يزال يترك فجوة أمنية كبيرة لـ ML-KEM.

5. الأهمية والآثار الأمنية

توفر الورقة إطاراً نظرياً صارماً لفهم أمن التشفير القائم على المودولات ضد الهجمات الجبرية.

الأهمية:

1. تضييق الحدود: تعمل الورقة على تنقيح عوامل التقريب المعروفة لـ module-SVP، مما يوفر رؤية أكثر دقة للحالة الأسوأ في التحليل الجبري التشفيري.
2. الكفاءة الخوارژيتمية: توفر مخططاً لتنفيذ عملي محدود الدقة لهجوم كمومي متقدم.
3. تأكيد الأمن: والأهم من ذلك، أن النتائج تؤكد أمن ML-KEM. فحتى مع تحسين توسيع CDPR والاختيار الأمثل للإشارة، يظل عامل التقريب $\exp(\tilde{O}(\sqrt{n}))$، وهو لا يزال كبيراً جداً لكسر المعايير المستخدمة في معايير NIST (الفجوة الأمنية تظل حوالي $2^{12}$ لـ ML-KEM-768).

باختثناء، نجحت الورقة في توسيع هجوم شبكات مثالية قوي ليشمل بيئة المودول مع تحسين مكوناته الداخلية، مما وفر في النهاية هامش أمان أكثر دقة للجيل القادم من معايير التشفير لما بعد الكم.