Predicting Module-Lattice Reduction

ملخص تقني: التنبؤ باختزال الشبكة النمطية (Module-Lattice Reduction)

بيان المشكلة
تتناول الورقة البحثية سؤالاً حرجاً في تحليل التشفير للأنظمة التشفيرية القائمة على الشبكات النمطية (مثل معايير NIST المتمثلة في ML-KEM وML-DSA وFN-DSA): هل اختزال الشبكة النمطية (تحديداً module-BKZ) أكثر كفاءة أم أقل كفاءة من اختزال الشبكة غير المهيكلة (BKZ) عند إعطائه نفس أوراكل (oracle) مسألة أقصر متجه (SVP)؟

بينما أرست الأعمال النظرية التأسيسية وجود متغيرات نمطية لخوارزميات LLL وخوارزميات الاختزال بالكتل (block-reduction)، فقد ركزت على السلوك التقاربي في أسوأ الحالات. وهناك قلق محدد، تم تسليط الضوء عليه كـ "Q8" في تقديم Kyber لـ NIST، يفترض أن البنية الجبرية للشبكات النمطية فوق الحقول الدورية (cyclotomic fields) قد تسمح بتسريع (على سبيل المثال، عامل من $d$ إلى $d^2$) أو على العكس، قد تؤدي إلى تدهور جودة القاعدة المختزلة مقارنة بـ BKZ غير المهيكلة. تهدف الورقة إلى تقديم تحليل ملموس للحالة المتوسطة للإجابة عما إذا كان module-BKZ يوفر مكسباً أو خسارة من حيث حجم الكتلة $\beta$ المطلوب لتحقيق جودة قاعدة معينة (الميل/slope).

المنهجية
يستخدم المؤلفون تحليلاً قائماً على الاستدلال (heuristic) مدعوماً بتجارب واسعة النطاق للتنبؤ بـ "ميل" (slope) ملف القاعدة بعد تشغيل module-BKZ. يُعرف الميل بأنه معدل اضمحلال المعايير اللوغاريتمية لمتجهات تعامد غرام-شميت (Gram-Schmidt orthogonalized vectors).

1. التنفيذ التجريبي: طور المؤلفون أول تنفيذ مفتوح المصدر لـ module-BKZ للحقول الدورية (حتى الموصل 16)، باستخدام مكتبات fplll وG6K الموجودة. وقد عالجوا التحديات التقنية المتعلقة بالحفاظ على البنية النمطية أثناء تقليل الحجم (size reduction) واستخدام "التعميل الدوري" (cyclic embedding) لضمان توافق حاصل الضرب الأثر (trace inner product) مع مكتبات اختزال الشبكات الصحيحة القياسية.
2. النمذجة النظرية (Module-Lattice GSA): قاموا بتوسيع فرضية المتسلسلة الهندسية (GSA)، المستخدمة عادةً لـ BKZ غير المهيكلة، لتشمل الشبكات النمطية. يتضمن ذلك نمذجة الـ $K$-profile المتوقع (المتوسط عبر درجة $d$ للحقل العددي) لقاعدة مختزلة.
3. تفكيك الميل: يتم تفكيك ميل module-BKZ المتوقع إلى أربعة حدود متميزة ($t_1$ إلى $t_4$) تقود الانحراف عن BKZ غير المهيكلة:
   • $t_1$ (فرضية غاوس - Gaussian Heuristic): الطول المتوقع لأقصر متجه في شبكة نمطية عشوائية، معدلاً وفقاً لعدد جذور الوحدة ($\mu_K$).
   • $t_2$ (فجوة المميز - Discriminant Gap): حد يعتمد على مميز $\Delta_K$ للحقل $K$.
   • $t_3$ (فجوة الانحراف - Skewness Gap): يقيس انحراف المعيار الجبري للمتجه عن معياره الإقليدي (انحراف المتجه عبر التضمينات).
   • $t_4$ (فجوة المؤشر - Index Gap): يأخذ في الاعتبار مؤشر المثالي (ideal) المولد بواسطة أقصر متجه داخل النمط (module).
4. التحليل التقاربي: اشتق المؤلفون صيغة تقاربية لـ "حجم الكتلة المكافئ" $\beta_{eq}$ المطلوب لكي يطابق module-BKZ ميل BKZ غير المهيكلة بحجم كتلة $\beta$.

المساهمات والنتائج الرئيسية

• التنبؤ الكمي بالميل: توفر الورقة صيغة ملموسة تتنبأ بميل module-BKZ كدالة لحجم الكتلة $\beta$، ودرجة الحقل $d$، ومميز الحقل $\Delta_K$.
• المميز كمحرك أساسي: حدد التحليل أن المميز $\Delta_K$ هو الكمية الأساسية التي تقود الفرق في الأداء. وتحديداً، فإن الحد $\ln(|\Delta_K|/d^d)$ يحدد ما إذا كان module-BKZ يحقق مكسباً أو خسارة في الكفاءة.
• ربح/خسارة حجم الكتلة التقاربي: اشتق المؤلفون العلاقة التقاربية التالية لحجم الكتلة المكافئ $\beta_{eq}$:
  $$\beta_{eq} \approx \beta + \ln\left(\frac{|\Delta_K|}{d^d}\right) \frac{\beta}{d \ln \beta} + (d - 1)$$
  • الحقول الدورية ذات القوى الثنائية (Power-of-Two Cyclotomic Fields): بالنسبة للحقول التي يكون موصلها قوة للعدد 2 (وهي ذات صلة بمعايير NIST الحالية)، يكون $|\Delta_K| = d^d$. وبالتالي، يختفي الحد اللوغاريتمي، وتهيمن القيمة الخطية $d-1$ على التكلفة. هذا يعني أن module-BKZ يتطلب حجم كتلة أكبر بمقدار $d-1$ تقريباً لتحقيق نفس الميل مثل BKZ غير المهيكلة. وهذا يؤكد ويحدد القلق الذي أثير في Q8 الخاص بـ Kyber، مما يشير إلى عقوبة طفيفة في الأداء بدلاً من تسريع.
  • الحقول الدورية الأخرى: بالنسبة للحقول التي تحتوي على عوامل أولية فردية في موصلها (مثل موصلات من الشكل $2^i \cdot 3^j$)، يكون $|\Delta_K| < d^d$. في هذه الحالات، يكون الحد اللوغاريتمي سالباً، مما ينتج عنه مكسب تحت-خطي (sublinear gain) في حجم الكتلة المطلوب ($\Theta(\beta / \ln \beta)$). وهذا يترجم إلى تسريع تحت-أسي (subexponential speedup) في تعقيد الهجوم.
• التحقق التجريبي: تتوافق البيانات التجريبية للمؤلفين على مختلف الحقول الدورية ($\mathbb{Q}(\omega_3), \mathbb{Q}(\omega_4), \mathbb{Q}(\omega_{15}), \mathbb{Q}(\omega_{16})$) بشكل جيد مع تنبؤاتهم. وتؤكد البيانات أن $\mathbb{Q}(\omega_3)$ و $\mathbb{Q}(\omega_{15})$ يظهران ملفات أكثر تسطحاً (اختزال أفضل) مقارنة بالخط المرجعي غير المهيكل، بينما يظهر $\mathbb{Q}(\omega_{16})$ (القوة الثنائية) ملفاً أسوأ.

الأهمية والادعاءات
تدعي الورقة أنها أول عمل يقدم تحليلاً ملموساً للحالة المتوسطة لـ module-BKZ، متجاوزةً الحدود النظرية للحالة الأسوأ. وتكمن أهميتها في:

1. حل مسألة Q8: إنها تعالج مباشرة السؤال المفتوح المتعلق بكفاءة module-BKZ على الحقول الدورية ذات القوى الثنائية، مستنتجة أنه بالنسبة لهذه الحقول المحددة، لا توفر البنية النمطية تسريعاً على BKZ غير المهيكلة؛ بل في الواقع، تفرض عبئاً إضافياً صغيراً (تتطلب حجم كتلة أكبر).
2. تحديد البناءات البديلة: تسلط الضوء على أن مخططات الشبكات النمطية التي تستخدم موصلات ذات عوامل أولية فردية صغيرة (مثل 3، 5) قد تكون أضعف بكثير مما كان يُعتقد سابقاً، حيث توفر البنية الجبرية تسريعاً تحت-أسي لهجمات الاختزال الشبكي.
3. الأدوات العملية: من خلال توفير أول تنفيذ مفتوح المصدر لـ module-BKZ، يمكن المؤلفون إجراء المزيد من التجارب وتقديرات الأمان للأنظمة القائمة على الشبكات النمطية.

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