Utilizing Circulant Structure to Optimize the Implementations of Linear Layers

ملخص تقني: استغلال البنية الدائرية لتحسين تنفيذ الطبقات الخطية

بيان المشكلة
يعد تحسين الطبقات الخطية في التشفير المتماثل أمراً بالغ الأهمية لكل من التنفيذات خفيفة الوزن (المقيدة بعدد البوابات والمساحة) وتقييمات الأمن الكمي (المقيدة بعمق الدائرة وتكلفة DW). وبينما توجد خوارزميات استدلالية لتخليق دوائر CNOT (الكمية) ودوائر XOR (الكلاسيكية) للمصفوفات القابلة للعكس العامة، إلا أنها غالباً ما تفشل في استغلال الخصائص الجبرية المحددة المتأصلة في التصاميم التشفيرية بالكامل. فالعديد من المصفوفات واسعة الاستخدام، مثل تلك الموجودة في MixColumn لـ AES وWhirlwind، تمتلك بنية دائرية (circulant structure). وتتعامل الطرق الحالية المتطورة، مثل طريقة Shi وFeng [SF24]، مع هذه المصفوفات كأنها مصفوفات ثنائية عامة بمقاس $n \times n$، مما قد يؤدي إلى تفويت فرص لتقليل عمق الدائرة وعدد البوابات عبر استغلال خصائصها الدائرية الكامنة.

المنهجية
يقترح المؤلفون إطار عمل جديد يستخدم صراحةً البنية الدائرية للمصفوفات لتوجيه عملية تخليق دوائر فعالة. وتتضمن المنهجية الأساسية استراتيجية تفكيك تكرارية (recursive decomposition) تقوم بتحويل مصفوفة دائرية فوق امتداد حقل (على سبيل المثال، $F_{2^k}$ أو $GL(F_2, m)$) إلى شكل أبسط، وتحديداً مصفوفة مثلثية علوية، قبل تطبيق التحسين الاستدلالي القياسي.

المكونات التقنية الرئيسية تشمل:

1. التحويل الكتلي التكراري: تثبت المبرهنة 3 أن المصفوفة الدائرية بمقاس $2^k \times 2^k$ فوق $F_2[x]$ يمكن تحويلها إلى مصفوفة مثلثية علوية كتلية باستخدام عمليات الصف والعمود الأولية. تقوم الخوارزمية بتقسيم المصفوفة تكرارياً إلى كتل $A$ و $B$ (حيث $M = \begin{smallmatrix} A & B \\ B & A \end{smallmatrix}$)، مع تطبيق عمليات لتصفير كتل محددة (على سبيل المثال، التحويل إلى $\begin{smallmatrix} A+B & B \\ A+B & \dots \end{smallmatrix}$).
2. استكشاف مسارات التحويل: يلاحظ المؤلفون أن الاختيارات المختلفة لعمليات الصف والعمود خلال الخطوة التكرارية تؤدي إلى مصفوفات وسيطة مختلفة. تستكشف الخوارزمية (الخوارزمية 1) مسارات تحويل متعددة (تصل إلى $4^{2^k-1}$ احتمال لـ $k$ صغيرة) لإيجاد المسار الذي ينتج أكثر الدوائر كفاءة لاحقاً.
3. التوقف المبكر والحل البديل: إدراكاً منهم بأن فائدة التكرار تتضاءل عند المستويات العميقة، قدم المؤلفون استراتيجية (الخوارزمية 2) لإيقاف التكرار مبكراً. تكرر الخوارزمية عبر "أحجام كتل" مختلفة، مما يغير عمق التكرار فعلياً. إذا تم إيقاف التكرار مبكراً، يتم تمرير المصفوفة الناتجة إلى محسن استدلالي قياسي (Heu) لتخليق CNOT/XOR العام. يتضمن هذا أيضاً استراتيجية "الحل البديل" حيث يكون عمق التكرار صفراً، مما يعامل المصفوفة كحالة عامة.
4. التحسين الآلي: على عكس النهج اليدوي السابق (مثل [ZSWS24] لـ AES)، يقوم هذا الأسلوب بأتمتة عملية إيجاد الشكل الأكثر بساطة للمصفوفة وتسلسلات البوابات المقابلة، مما يلغي الحاجة إلى التدخل البشري.

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

• إطار عمل مبتكر: يعد هذا أول عمل يستخدم بشكل منهجي البنية الدائرية للطبقات الخطية لتحسين تنفيذ الدوائر، مما يسد الفجوة بين الخصائص الجبرية للمصفوفات واستدلالات تخليق الدوائر.
• التخليق الآلي: يوفر المؤلفون خوارزمية مؤتمتة تحل محل عمليات التحسين اليدوية المخصدة لحالات معينة. وهي تولد تسلسلات من مصفوفات التحويل التي تسمح للاستدلالات اللاحقة بإيجاد تنفيذات أكثر كفاءة.
• التحسين المزدوج: إطار العمل قابل للتطبيق على كل من الدوائر الكمية (تقليل عدد CNOT والعمق) والدوائر الكلاسيكية (تقليل عدد عمليات XOR، وتحديداً g-XOR وs-XOR).

النتائج
قيم المؤلفون طريقتهم على مجموعة بيانات من الطبقات الخطية من شفرات الكتل (بما في ذلك AES وWhirlwind وClefia وPRIDE، ومصفوفات MDS).

• عمق الدائرة الكمية:

  • Whirlwind M0: قللت الطريقة المقترحة عمق الدائرة من 28 (الناتج عن أفضل حالة سابقة بواسطة [SF24]) إلى 17، وهو تحسن بنسبة 39%. كما تم تقليل عدد البوابات من 286 إلى 200.
  • AES MixColumn: حققت الطريقة المؤتمة عمقاً قدره 10، وهو ما يطابق نتيجة أفضل حالة تم تحسينها يدوياً بواسطة Zhang et al. [ZSWS24]. بلغ عدد البوابات 107، وهو أكثر بـ 2 CNOT فقط من النتيجة اليدوية (105) وأفضل بكثير من الـ 131 CNOT التي حققتها [SF24].
  • مصفوفات أخرى: لوحظت انخفاضات كبيرة في العمق للمصفوفات ذات الكثافة العالية (مثل Whirlwind وSKOP15 8x8)، بينما كانت التحسينات طفيفة أو غير موجودة للمصفوفات المتفرقة (sparse) حيث تعمل الاستدلالات بشكل جيد بالفعل.

• الدائرة الكلاسيكية (عدد XOR):

  • Whirlwind M0: حققت الطريقة عدد s-XOR بلغ 159، متفوقة على أفضل نتيجة سابقة وهي 173 (Yuan et al. [YWS+24]) بنسبة تقارب 8%.
  • الأداء العام: بينما تتسبب الطريقة عموماً في زيادة حجم العمليات للعديد من المصفوفات، فقد نجحت في التفوق على أفضل النتائج الحالية لمصفوفات محددة عالية الكثافة مثل Whirlwind M0 وM1.

الأهمية والادعاءات
يزعم البحث أن استغلال البنية الدائرية هو مسار قوي لم يتم استغلاله سابقاً لتحسين الطبقات الخطية. ويؤكد المؤلفون أن نهجهم:

1. يتفوق على الاستدلالات الحالية للمصفوفات الكثيفة المحددة حيث تعاني الاستراتيجيات الجشعة القياسية.
2. يؤتمت التحسين اليدوي، محققاً نتائج مقاربة للدوائر التي تم ضبطها بواسطة خبراء بشريين (كما في حالة AES MixColumn) دون الحاجة لتدخل يدوي.
3. يوفر معياراً أساسياً جديداً لتقييمات الأمن الكمي، مما يقدم تقديرات أكثر دقة لعمق الطبقات الخطية، وهو أمر بالغ الأهمية لحساب تكلفة DW (العمق $\times$ العرض) في تقييمات الأمن لما بعد الكم.

يخلص المؤلفون إلى أنه على الرغم من أن الطريقة ليست متفوقة عالمياً لجميع أنواع المصفوفات (خاصة المتفرقة منها)، إلا أنها تقدم ميزة كبيرة للمصفوفات ذات البنية الدائرية والكثافة العالية، مما يثبت إمكانية دمج الخصائص الجبرية في تخليق الدوائر.