2025-11-10T02:59:44.540641

A Characterization of Semi-Involutory MDS Matrices

Chatterjee, Laha
In symmetric cryptography, maximum distance separable (MDS) matrices with computationally simple inverses have wide applications. Many block ciphers like AES, SQUARE, SHARK, and hash functions like PHOTON use an MDS matrix in the diffusion layer. In this article, we first characterize all $3 \times 3$ irreducible semi-involutory matrices over the finite field of characteristic $2$. Using this matrix characterization, we provide a necessary and sufficient condition to construct MDS semi-involutory matrices using only their diagonal entries and the entries of an associated diagonal matrix. Finally, we count the number of $3 \times 3$ semi-involutory MDS matrices over any finite field of characteristic $2$.
academic

توصيف مصفوفات MDS شبه الالتفافية

المعلومات الأساسية

  • معرّف الورقة: 2406.12842
  • العنوان: توصيف مصفوفات MDS شبه الالتفافية
  • المؤلفون: Tapas Chatterjee (معهد الهند للتكنولوجيا روبار)، Ayantika Laha (معهد الهند للتكنولوجيا روبار)
  • التصنيف: cs.CR (التشفير والأمان)
  • تاريخ النشر: 1 يناير 2025 (الإصدار الثاني)
  • رابط الورقة: https://arxiv.org/abs/2406.12842

الملخص

في علم التشفير المتماثل، تتمتع مصفوفات الفصل الأقصى (MDS) التي تتمتع بحساب معكوس بسيط بتطبيقات واسعة النطاق على الحقول المحدودة. تستخدم العديد من أنظمة التشفير الكتلية مثل AES و SQUARE و SHARK بالإضافة إلى دوال التجزئة مثل PHOTON مصفوفات MDS في طبقة الانتشار. تقدم هذه الورقة أولاً توصيفاً لجميع مصفوفات شبه الالتفافية غير القابلة للاختزال 3×3 على الحقول المحدودة ذات الخاصية 2. بناءً على توصيف هذه المصفوفات، نوفر شروطاً ضرورية وكافية لبناء مصفوفات MDS شبه الالتفافية باستخدام عناصر قطرية فقط والعناصر المصفوفة القطرية ذات الصلة. أخيراً، نحسب عدد مصفوفات MDS شبه الالتفافية 3×3 على أي حقل محدود ذي خاصية 2.

السياق البحثي والدافع

خلفية المشكلة

  1. أهمية طبقة الانتشار: في علم التشفير المتماثل، يشكل مفهوم "الالتباس والانتشار" الذي اقترحه Shannon أساس تصميم الأنظمة التشفيرية. تتحمل طبقة الانتشار مسؤولية إخفاء العلاقة بين النص المشفر والنص الواضح، وتوفر مصفوفات MDS بسبب عدد فروعها الأقصى انتشاراً مثالياً.
  2. متطلبات الكفاءة الحسابية: في تطبيقات التشفير الخفيف الوزن، لا يُطلب من مصفوفات MDS فقط توفير الأمان، بل يجب أن يتمتع معكوسها بتنفيذ فعال. تحظى المصفوفات الالتفافية (A² = I) باهتمام كبير لأن معكوسها هو نفسها.
  3. حدود الطرق الموجودة:
    • فضاء البحث عن مصفوفات MDS الالتفافية محدود نسبياً
    • لا توجد مصفوفات دورانية التفافية لبعض الأحجام
    • هناك حاجة إلى فئات مصفوفات أوسع لتوسيع خيارات التصميم

الدافع البحثي

تقدم هذه الورقة مصفوفات شبه الالتفافية كتعميم للمصفوفات الالتفافية، وتُعرّف بأنها المصفوفات التي توجد لها مصفوفات قطرية غير منفردة D₁ و D₂ بحيث M⁻¹ = D₁MD₂. يوسع هذا التعميم بشكل كبير فئات المصفوفات المتاحة لتصميم التشفير.

المساهمات الأساسية

  1. التوصيف النظري: توصيف كامل لجميع مصفوفات شبه الالتفافية غير القابلة للاختزال 3×3 على الحقول المحدودة ذات الخاصية 2
  2. طريقة البناء: توفير شروط ضرورية وكافية لبناء مصفوفات MDS شبه الالتفافية 3×3 باستخدام ستة معاملات فقط (3 عناصر قطرية + 3 عناصر مصفوفة قطرية ذات صلة)
  3. نتائج العد: حساب دقيق لعدد مصفوفات MDS شبه الالتفافية 3×3 على F₂ᵐ بمقدار (2ᵐ-1)⁵(2ᵐ-2)(2ᵐ-4)
  4. تعميم النتائج الموجودة: تعميم نتائج Güzel وآخرين حول مصفوفات MDS الالتفافية إلى فئة أكبر من مصفوفات شبه الالتفافية

شرح الطريقة

تعريف المهمة

دراسة مصفوفات 3×3 على الحقل المحدود F₂ᵐ ذي الخاصية 2، مع المتطلبات التالية:

  • الخاصية شبه الالتفافية: وجود مصفوفة قطرية غير منفردة D بحيث تكون ADA مصفوفة قطرية
  • خاصية MDS: جميع المصفوفات المربعة الجزئية من A غير منفردة
  • عدم القابلية للاختزال: لا يمكن تحويل A من خلال تشابه التبديل إلى شكل مختزل

النظريات الأساسية

النظرية 4.1 (توصيف البنية)

لتكن A مصفوفة شبه التفافية غير قابلة للاختزال 3×3، والمصفوفة القطرية المرتبطة بها D = diag(d₁,d₂,d₃)، يمكن التعبير عن العناصر غير القطرية كما يلي:

  • a₁₂ = (a₁₁d₁ + a₃₃d₃)d₂⁻¹x
  • a₁₃ = (a₁₁d₁ + a₂₂d₂)d₃⁻¹xy
  • a₂₁ = (a₂₂d₂ + a₃₃d₃)d₁⁻¹x⁻¹
  • a₂₃ = (a₂₂d₂ + a₁₁d₁)d₃⁻¹y
  • a₃₁ = (a₃₃d₃ + a₂₂d₂)d₁⁻¹(xy)⁻¹
  • a₃₂ = (a₃₃d₃ + a₁₁d₁)d₂⁻¹y⁻¹

حيث x,y ∈ F₂ᵐ* عناصر غير صفرية.

النظرية 4.5 (الشروط الضرورية والكافية لـ MDS)

تكون المصفوفة A ذات البنية المذكورة أعلاه مصفوفة MDS شبه التفافية إذا وفقط إذا:

  • a₁₁d₁ + a₂₂d₂ ≠ 0
  • a₁₁d₁ + a₃₃d₃ ≠ 0
  • a₂₂d₂ + a₃₃d₃ ≠ 0
  • a₁₁d₁ + a₂₂d₂ + a₃₃d₃ ≠ 0

نقاط الابتكار التقني

  1. الإطار الموحد: معاملة المصفوفات الالتفافية كحالة خاصة من المصفوفات شبه الالتفافية، مما يوفر إطار تحليل موحد
  2. البناء المعامل: توصيف كامل لمصفوفات MDS شبه الالتفافية 3×3 من خلال 8 معاملات، مما يبسط بشكل كبير فضاء البحث
  3. تقنية العد: استخدام مبدأ الاستبعاد والشمول لحساب عدد مجموعات المعاملات التي تحقق الشروط بدقة

إعداد التجارب

التحقق النظري

تركز الورقة بشكل أساسي على العمل النظري، مع التحقق من النتائج النظرية من خلال أمثلة محددة:

المثال 4.6: بناء مصفوفة MDS شبه التفافية على F₂₄

  • كثيرة الحدود المولدة: x⁴ + x³ + 1
  • اختيار المعاملات: a₁₁=1, a₂₂=α, a₃₃=α², d₁=α, d₂=α, d₃=α³+1, x=1, y=α
  • التحقق من استيفاء جميع شروط MDS

التحقق من العد

التحقق من صيغة العد من خلال الحساب المحدد:

  • F₂₂: 0 مصفوفة MDS شبه التفافية
  • F₂₃: 403,368 مصفوفة MDS شبه التفافية
  • F₂₄: 127,575,000 مصفوفة MDS شبه التفافية

نتائج التجارب

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

  1. اكتمال البنية: نجح في توصيف بنية جميع مصفوفات شبه الالتفافية 3×3، مما يثبت أنه يمكن تحديدها بالكامل من خلال 8 معاملات
  2. تحديد MDS: توفير شروط موجزة لتحديد متى تتمتع مصفوفة شبه التفافية بخاصية MDS
  3. نمو الكمية: مقارنة بمصفوفات MDS الالتفافية، يزداد عدد مصفوفات MDS شبه الالتفافية بشكل كبير:
    • مصفوفات MDS الالتفافية على F₂₃: 1,176
    • مصفوفات MDS شبه الالتفافية على F₂₃: 403,368 (نمو بحوالي 343 مرة)

الاكتشافات النظرية

  1. الخاصية التعميمية: تعمم الخاصية شبه الالتفافية حقاً الخاصية الالتفافية، وتوجد مصفوفات MDS شبه التفافية لكن ليست التفافية
  2. الميزة الحسابية: لا تزال معكوسات مصفوفات MDS شبه الالتفافية قابلة للحصول عليها من خلال ضرب مصفوفة قطرية بسيطة، مما يحافظ على الكفاءة الحسابية
  3. الوجود: لا توجد مصفوفات MDS شبه التفافية تحقق الشروط على F₂₂، لكن توجد كميات كبيرة من هذه المصفوفات على F₂ᵐ (m≥3)

الأعمال ذات الصلة

التطور التاريخي

  1. دراسة المصفوفات الالتفافية: قدم Youssef وآخرون (2007) أول تحويل خطي التفافي في علم التشفير
  2. طرق بناء MDS: قدم Gupta و Ray (2013) طرقاً متعددة لبناء مصفوفات MDS
  3. قيود المصفوفات الدورانية: أثبت Gupta وآخرون عدم وجود مصفوفات دورانية التفافية
  4. مفهوم شبه الالتفافي: قدم Cheon وآخرون (2021) مفهوم المصفوفات شبه الالتفافية

مساهمة هذه الورقة

مقارنة بالأعمال الموجودة، تقوم هذه الورقة بـ:

  • تطبيق مفهوم شبه الالتفافي لأول مرة على بناء مصفوفات MDS
  • توفير فضاء تصميم أكبر من المصفوفات الالتفافية
  • تقديم نتائج عد دقيقة

الخلاصة والمناقشة

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

  1. توصيف كامل للبنية الجبرية لمصفوفات شبه الالتفافية 3×3
  2. إنشاء ارتباط بين الخاصية شبه الالتفافية وخاصية MDS
  3. إثبات القيمة العملية لمصفوفات MDS شبه الالتفافية في تصميم التشفير

القيود

  1. قيود الأبعاد: النتائج الحالية تنطبق فقط على مصفوفات 3×3
  2. قيود الخاصية: تركز النظرية بشكل أساسي على الحقول المحدودة ذات الخاصية 2
  3. عدم القابلية للاختزال: يتطلب أن تتمتع المصفوفة بخاصية عدم القابلية للاختزال

الاتجاهات المستقبلية

  1. التعميم إلى مصفوفات ذات أبعاد أعلى (خاصة الرتبة الزوجية أو رتب قوى 2)
  2. دراسة الحالة على حقول محدودة ذات خصائص أخرى
  3. استكشاف تطبيقات المصفوفات شبه الالتفافية في أنظمة التشفير الفعلية

التقييم المتعمق

المميزات

  1. اكتمال النظرية: توفير توصيف كامل لمصفوفات MDS شبه الالتفافية 3×3، مع نتائج نظرية صارمة
  2. القيمة العملية: توفير أدوات جديدة لتصميم التشفير، مع توسيع فضاء التصميم
  3. الكفاءة الحسابية: الحفاظ على بساطة حساب المصفوفة العكسية، مما يناسب التطبيقات الخفيفة الوزن
  4. العد الدقيق: توفير عدد دقيق للوجود، مما يساعد في الاختيار العشوائي

أوجه القصور

  1. قيود الأبعاد: النظر فقط في حالة 3×3، لا تزال تعميمات الأبعاد الأعلى مسألة مفتوحة
  2. تعقيد البناء: على الرغم من توفير شكل معامل، لا يزال البناء الفعلي يتطلب استيفاء شروط متعددة
  3. التحقق من التطبيق: نقص تحليل الأمان في أنظمة التشفير الفعلية

التأثير

  1. المساهمة النظرية: توفير رؤى جديدة لنظرية المصفوفات على الحقول المحدودة
  2. تطبيق التشفير: توفير مصفوفات مرشحة جديدة لتصميم التشفير الخفيف الوزن
  3. ابتكار الطريقة: يمكن تعميم طريقة العد على مشاكل مماثلة أخرى

السيناريوهات المناسبة

  1. التشفير الخفيف الوزن: مناسب لتصميم أنظمة تشفير كتلية في بيئات الموارد المحدودة
  2. دوال التجزئة: يمكن استخدامها في بناء دوال تجزئة تتطلب طبقة انتشار فعالة
  3. البحث النظري: توفير أساس لمزيد من البحث في الحالات ذات الأبعاد الأعلى

المراجع

تستشهد الورقة بـ 25 مرجعاً ذا صلة، تشمل بشكل أساسي:

  • الأعمال الأساسية لنظرية التشفير لـ Shannon
  • خوارزميات التشفير الكلاسيكية مثل AES
  • النتائج النظرية المهمة لبناء مصفوفات MDS
  • أحدث التطورات البحثية في المصفوفات شبه الالتفافية

يحقق هذا العمل تقدماً جوهرياً على أساس النظرية الموجودة، مما يضع أساساً متيناً لنظرية وتطبيق مصفوفات MDS شبه الالتفافية.