On Generalizations of Maiorana-McFarland and $\mathcal{PS}_{ap}$ Functions

إليك ملخص تقني مفصل للورقة البحثية بعنوان "حول تعميمات دالات مايورانا-ماكفارلاند ودالات PSap" للباحثة Sezel Alkan وآخرون.

1. بيان المشكلة

تتناول الورقة البحثية تصنيف وبناء الدالات البولينية المنحنية (Boolean bent functions)، وهي دالات تتميز بـ "لا خطية" (nonlinearity) مثالية وتعد بالغة الأهمية في علم التشفير. ويتمثل التحدي المركزي في هذا المجال في بناء دالات منحنية تقع خارج فئة مايورانا-ماكفلاراند المكتملة (MM#).

• السياق: بينما تنتمي جميع الدالات المنحنية في الأبعاد حتى 6 إلى فئة MM# المكتملة، فمن المعروف أنه في البعد 8، تشكل فئة MM# جزءاً ضئيلاً جداً من إجمالي الدالات المنحنية.
• الفجوة: إن طرق البناء الأساسية الموجودة (MM و $PS_{ap}$ الجزئية) وطرق البناء الثانوية (مثل الربط أو Concatenation) غالباً ما تنتج دالات تعود لتصنف ضمن فئات معروفة أو تسمح بتفكيكات محددة (على سبيل المثال، إلى مكونات منحنية أو شبه منحنية).
• الهدف: يهدف المؤلفون إلى:
  1. بناء عائلات من دالات مايورانا-ماكفلارلاند المعممة (GMM) التي ثبت أنها خارج فئة MM#.
  2. استقصاء تفكيك دالات الانتشار الجزئي المعمم ($PS_{ap}$)، وتحديداً ما إذا كان يمكن تكوينها عن طريق ربط دالات منحنية أو شبه منحنية.
  3. تطوير طرق بناء ثانوية جديدة بناءً على مكونات الدالات المتجهية المعممة لـ $PS_{ap}$.

2. المنهجية

يستخدم المؤلفون مزيجاً من التقنيات الجبرية، والتركيبية، والهندسية:

• معيار ديلون (Dillon's Criterion): يستخدمون معياراً يعتمد على المشتقات من الدرجة الثانية لتوصيف العضوية في فئة MM# المكتملة. تنتمي الدالة إلى MM# إذا وفقط إذا كانت تمتلك فضاءً جزئياً من النوع M بأبعاد $n/2$ حيث تتلاشى جميع المشتقات من الدرجة الثانية.
• المنحنيات الجبرية وحقول الدوال: لإثبات أن مشتقات معينة غير ثابتة (وبالتالي لا تسمح بتفكيكات محددة)، يقوم المؤلفون بتحليل عدد النقاط العقلانية لـ منحنيات آرتين-شريير (Artin-Schreier curves) المعرفة فوق الحقول المنتهية. كما يطبقون حد هاسي-ويل (Hasse-Weil bound) وصيغة جنس هيرويتز (Hurwitz genus formula) لإثبات وجود نقاط تنتهك شروط الثبات.
• نظرية الدالات المتجهية: تمتد الدراسة لتشمل الدالات المنحنية المتجهية، مع تحليل دالات مكوناتها ودوالها المزدوجة.
• تقنيات الربط (Concatenation): تبحث الورقة في "التفكيك الرباعي" للدالات، حيث تُعامل الدالة كعملية ربط لأربعة قيود على فضاء جزئي.

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

أ. بناء دالات GMM خارج فئة MM#

قام المؤلفون ببناء عائلة جديدة من دالات GMM التي لا تكافئ أي دالة من فئات MM أو $PS_{ap}$ الكلاسيكية.

• الآلية: يعرفون دالة $f(x, y, z) = f_{(z)}(x) + \text{Tr}_1^k(yz)$، حيث $f_{(z)}$ هي دالات MM.
• الابتكار: على عكس البناءات السابقة حيث تشترك $f_{(z)}$ في فضاء M مشترك كبير، يختار المؤلفون دالات MM تشترك فقط في فضاءات M تافهة (بأبعاد $\le 1$).
• بناء محدد: يستخدمون تبديلات $\pi$ تحقق الخاصية (P)، والتي تضمن أن دالة MM الأساسية تمتلك فضاء M أقصى فريد. ومن خلال تبديل أدوار المتغيرات بناءً على الأثر (trace) لـ $z$، ينشئون دالة GMM يكون فيها بُعد فضاء M الأقصى أقل تماماً من $n/2 + k$.
• النتيجة: تحت ظروف محددة (على سبيل المثال، $m > k + 2$)، تقع هذه الدالات خارج فئة MM#. وتشمل الأمثلة التبديلات القائمة على دالات المعكوس ($x^{2^m-2}$) ودالات غولد ($x^{2^k+1}$).

ب. تفكيك دالات $PS_{ap}$ المعممة

تبحث الورقة فيما إذا كان يمكن تفكيك دالات $PS_{ap}$ المعممة إلى دالات منحنية أو شبه منحنية عبر عملية الربط.

• النتيجة الرئيسية: يثبت المؤلفون أنه بالنسبة لدالات $PS_{ap}$ المعممة ذات الدرجة الجبرية الصغيرة نسبياً مقارنة بحجم الحقل، فإنها لا تسمح بتفكيك منحني أو شبه منحني بشكل عام.
• الإثبات التقني:
  • اشتقوا الدالة المزدوجة $f^*$ لدالة $PS_{ap}$ المعممة.
  • باستخدام التمهيدية 10 (Lemma 10)، أظهروا أن التفكيك المنحني موجود إذا وفقط إذا كانت المشتقة من الدرجة الثانية للدالة المزدوجة تساوي 1 باستمرار، وأن التفكيك شبه المنحني موجود إذا وفقط إذا كانت تساوي 0 باستمرار.
  • أثبتوا أنه بالنسبة لفضاءات جزئية محددة $S$، فإن المشتقة من الدرقة الثانية للدالة المزدولة غير ثابتة. وقد تم إثبات ذلك من خلال إظهار أن المنحنى الجبري المرتبط يحتوي على نقاط عقلانية لكل من قيم الأثر 0 و 1، باستخدام حد هاسي-ويل.
• الآثار المترتبة: لا يمكن توليد هذه الدالات بواسطة عمليات البناء الثانوية المعروفة القائمة على ربط الدالات المنحنية أو شبه المنحنية، مما يميزها عن العديد من الفئات الأخرى المعروفة.

ج. البناء الثانوي عبر المكونات المتجهية

يقدم المؤلفون بناءً ثانوياً جديداً للدالات البولينية المنحنية مشتقاً من دالات $PS_{ap}$ المتجهية المعممة.

• الآلية: يستغلون خاصية أن الدوال المزدوجة لمكونات الدالات المنحنية المتجهية الناشئة عن التقسيمات المنحنية (bent partitions) تحقق علاقة خطية محددة: $(F_\alpha)^* + (F_\beta)^* = (F_{\alpha+\beta})^*$.
• البناء: من خلال ربط المكونات $F_\alpha, F_\beta, F_\gamma, F_{\alpha+\beta+\gamma+1}$، يقومون ببناء دالة بولينية منحنية جديدة.
• التعميم: قاموا بتعميم ذلك بشكل أكبر من خلال تعريف دالة تعتمد على توزيع السوابق (preimage distribution) للانتشار الديسارجي (Desarguesian spread)، مع تعيين قيم لمجموعات التقسيم لضمان أن الدالة الناتجة منحنية.

4. الأهمية

• توسيع نطاق الدالات المنحنية: توفر الورقة أمثلة صريحة وقابلة للإثبات لدالات منحنية تقع خارج فئة MM#، مما يعالج مشكلة طويلة الأمد في تصنيف الدالات المنحنية.
• محدودية عمليات البناء الثانوية: من خلال إثبات أن دالات $PS_{ap}$ المعممة لا تسمح عموماً بتفكيكات منحنية/شبه منحنية، يوضح المؤلفون القيود المفروضة على عمليات البناء الثانوية القائمة على الربط لهذه الفئة المحددة. وهذا يسلط الضوء على الحاجة إلى عمليات بناء أولية أو طرق ثانوية جديدة.
• التقدم المنهجي: يوفر التطبيق الصارم للهندسة الجبرية (تحديداً نظرية حقول الدوال والنقاط العقلانية على المنحنيات) لدراسة مشتقات الدالات البولينية أدوات قوية للبحوث المستقبلية في تصنيف الدوال التشفيرية.
• الأهمية التشفيرية: الدالات التي تقع خارج فئة MM# مرغوبة بشدة في تطبيقات التشفير لأنها توفر مقاومة ضد بعض الهجمات الجبرية التي قد تستغل بنية دالات MM.

الخاتمة

تساهم هذه الورقة بشكل كبير في تطوير نظرية الدالات البولينية المنحنية من خلال بناء عائلات جديدة من دالات GMM خارج فئة MM# وتوصيف القيود الهيكلية لدالات $PS_{ap}$ المعممة فيما يتعلق بالتفكيك. يربط هذا العمل بين التصميم التركيبي، ونظرية الحقول المنتهية، والهندسة الجبرية لحل مشكلات التصنيف في علم التشفير.