Explicit cost analysis of Toom-4 multiplication for incomplete NTT in lattice-based cryptography

ملخص تقني: تحليل التكلفة الصريح لضرب Toom-4 في الـ NTT غير المكتملة في التشفير القائم على الشبكات

بيان المشكلة
يعد ضرب كثيرات الحدود عملية أساسية في أنظمة التشفير القائمة على الشبكات مثل Kyber (ML-KEM) وDilithium (ML-DSA)، والتي تُجرى عادةً فوق حلقات البواقي $R_q = \mathbb{F}_q[x]/\langle x^n + 1 \rangle$. وبينما توفر تحويلات "عدد النظريات" (NTT) سرعة ضرب من رتبة $O(n \log n)$، إلا أنها تتطلب بصرامة الشرط $2n \mid (q-1)$. هذا القيد يحد من اختيار المعلمات ويمكن أن يضر بأهداف الأمان أو الكفاءة.

لمعالجة ذلك، قدم Hafiz وآخرون (2025) "الـ NTT غير المكتملة" (incomplete NTT)، والتي تخفف قيد المعدل عبر إجراء NTT مبتور بعمق $\ell$ (حيث $2^{\ell+1} \mid (q-1)$) ودمجه مع ضرب كثيرات الحدود التقليدي للمسائل الفرعية المتبقية. وبينما تُعد خوارزمية Karatsuba مفهومة جيداً ضمن هذا الإطار، فإن التكلفة الدقيقة لضرب Toom-4 — وتحديداً ثوابتها المتعلقة بالجمع والضرب — لم يتم التعبير عنها بشكل يتوافق مع نموذج تكلفة الـ NTT غير المكتملة. تركز التحليلات الحالية لـ Toom-Cook (مثل Bodrato وZanoni) على التحسين العام ولكنها ليست مدمجة مباشرة في الإطار الهجين المحدد المطلوب للـ NTT غير المكتملة.

المنهجية
يقدم المؤلفون تنفيذاً ملموساً لضرب Toom-4 مصمماً خصيصاً لإطار عمل الـ NTT غير المكتملة، ويستنتجون نموذجاً صريحاً لعدد العمليات.

1. استراتيجية التنفيذ: يتبنى المؤلفون نقاط التقييم الصحيحة $\{0, \pm 1, \pm 2, 3, \infty\}$ لتجنب الثوابت الكسرية. ويتم تأجيل جميع عمليات القسمة إلى خطوة قياس نهائية.
2. تحسين سلسلة الجمع: المكون الحرج لمنهجيتهم هو استخدام سلاسل الجمع لحساب المضاعفات القياسية اللازمة خلال مرحلة الاستيفاء (interpolation). بدلاً من إجراء عمليات ضرب قياسية فردية، يقوم المؤلفون ببناء سلاسل جمع دنيا للمعاملات المستهدفة المطلوبة من مصفوفة Vandermonde العكسية. وهذا يسمح بتحديد دقيق لعدد عمليات الجمع والطرح المطلوبة.
3. اشتقاق التكلفة: يفصل المؤلفون أعداد العمليات إلى عمليات الجمع/الطرح ($A$) وعمليات الضرب ($M$) فوق حقل المعاملات $\mathbb{F}_q$. ويشتقون صيغاً تكرارية لخطوات Toom-4 (التقسيم، التقييم، الضرب التكراري، الاستيفاء، وإعادة التركيب) ويدمجونها في النموذج الموزون لتكلفة الـ NTT غير المكتملة التي وضعها Hafiz وآخرون.
4. التحليل الهجين: تدرس الدراسة استراتيجيات هجينة تجمع بين Toom-4 وKaratsuba والـ NTT غير المكتملة. ومن خلال تقليل دالة التكلفة الموزونة $C_w(n; \ell, L)$ (حيث $w$ هي التكلفة النسبية للجمع إلى الضرب)، يحدد المؤلفون عمق التكرار الأمثل $L$ لمختلف أحجام المسائل الفرعية.

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

• نموذج تكلفة صريح لـ Toom-4: يقدم البحث أول نموذج تكلفة صريح لـ Toom-4 متوافق مع إطار عمل الـ NTT غير المكتملة. وهو يفصل الأعداد الدقيقة للجمع والضرب، بما في ذلك العوامل الثابتة المشتقة من سلاسل الجمع المحسنة.
• التحقق من سلسلة الجمع: يوفر المؤلفون سكربتات تحقق (متاحة في مستودعهم) تؤكد مثالية سلاسل الجمع المستخدمة لثوابت الاستيفاء، مما يضمن أن الأعداد المستخرجة هي الدنيا بالنسبة لنقاط التقييم المختارة.
• تحسين الاستراتيجية الهجينة: تحدد الدراسة نطاقات معلمات محددة حيث يتفوق الهجين (Toom-4/Karatsuba) على Karatsuba الصرف أو Toom-4 الصرف ضمن سياق الـ NTT غير المكتملة.
• التحقق التجريبي: قام المؤلفون بتنفيذ الطريقة الهجنة المقترحة في لغة Python وتحققوا من التنبؤات النظرية مقابل أوقات التشغيل التجريبية باستخدام موديلات (primes) غير صديقة للـ NTT (مشابهة في الحجم لموديل Dilithium ولكن مع قيم 2-adic مقيدة).

النتائج
يكشف التحليل أن فعالية Toom-4 في هذا السياق تعتمد بشدة على عمق الـ NTT المسموح به ($\ell$) وحجم المسألة الفرعية الناتج ($d = n/2^\ell$):

• نطاق العمق المحدود: عندما يكون عمق الـ NTT المسموح به صغيراً (على سبيل المثال، $\ell=0$ أو $\ell=1$)، تكون المسائل الفرعية كبيرة بما يكفي لتوفير مكاسب كبيرة من Toom-4. على سبيل المثال، مع $n=256$ و$\ell=0$، قللت الطريقة الهجينة التكلفة الموزونة بنسبة 5% تقريباً مقارنة بـ Karatsuba الصرف وتفوقت بشكل كبير على Toom-4 الصرف.
• التكرار الأمثل: يختلف عمق التكرار الأمثل $L$ مع $d$. بالنسبة لـ $d \le 128$، الاستراتيجية المثلى هي $L=0$ (Karatsuba صرف). بالنسبة لـ $d=256$، فإن $L=1$ هو الأمثل، ولـ $d \ge 512$، فإن $L=2$ هو الأمثل.
• التأكيد التجريبي: أكدت التجارب على الأعداد الأولية ذات القيم 2-adic المقيدة النموذج النظري. عندما كان أقصى عمق مسموح به في حده الأدنى ($\ell_{max}=0$)، تفوقت الطريقة الهجينة بشكل ملحوظ على Karatsuba (على سبيل المثال، 14.182 مللي ثانية مقابل 16.722 مللي ثانية لـ $n=256$). ومع زيادة العمق المسموح به، تضاءلت ميزة الأداء للطريقة الهجينة، لتتقارب في النهاية مع Karatsuba عندما تصبح المسائل الفرعية صغيرة جداً.

الأهمية والادعاءات
يدعي المؤلفون بتواضع أن مساهمتهم الأساسية ليست خوارزمية ضرب جديدة، بل هي تحليل دقيق لمستوى الثوابت لـ Toom-4 مصمم خصيصاً لإطار عمل الـ NTT غير المكتملة. ويؤكدون أن نموذج التكلفة الصريح هذا يسد فجوة في الأدبيات، مما يسمح بالتقييم المنهجي للاستراتيجيات الهجينة في السيناريوهات التي لا تتوفر فيها NTT كاملة.

تخلص الورقة إلى أن Toom-4 هي الأكثر فائدة في "نطاق العمق المحدود" للـ NTT غير المكتملة، وتحديداً عندما يحد التقييم 2-adic لـ $q-1$ من عمق التحويل. في هذه الحالات، تقدم الاستراتيجية الهجية المقترحة تحسيناً ملموساً في الأداء مقارنة بالنهج المعتمد على Karatsuba القياسي. ويشير المؤلفون إلى أن تنفيذهم الحالي هو بلغة Python وأن العمل المستقبلي يتضمن تحسين التنفيذات منخفضة المستوى (مثل C/C++) ومزيد من التقييم في مخططات الشبكات الملموسة.