🔢 الرياضيات

Constructing Complete Permutations via the D-Class of Locally Crooked Permutations

تقدم هذه الورقة فئة $D$ من التباديل فوق $\mathbb{F}_{2^{n+1}}$ لتوصيف وبناء التباديل الكاملة عبر الترافقات المحلية، وتأسيس خصائصها الجبرية، وحدودها التشفيرية، وعدم تكافؤ CCZ، مع تقديم خوارزميات نجحت في تعداد تباديل كاملة جديدة بـ $\delta=4$ .

المؤلفون الأصليون: Li Shuai

نُشر 2026-10-16

📖 5 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Li Shuai

البحث الأصلي مرخَّص بموجب CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

في البنية الخفية للأمن الرقمي الحديث، توجد فئة من الكائنات الرياضية تُعرف بالتبديلات الكاملة (complete permutations). هذه ليست مجرد عمليات خلط عشوائية للأرقام؛ بل هي إعادة ترتيبات عالية الهيكلية حيث تؤدي عملية نقل عنصر إلى موضع جديد وعملية نقله إلى موضع يمثل مجموع موضعه القديم والجديد إلى ترتيب مثالي غير متداخل في كلتا الحالتين. هذا المتطلب المزدوج أمر بالغ الأهمية لتصميم صناديق الاستبدال، أو ما يُعرف بـ (S-boxes)، وهي المكونات الأساسية في أنظمة التشفير التي تقوم بتشويش البيانات لإخفاء معناها. فإذا كانت هذه المكونات قابلة للتنبؤ بشكل كبير، يمكن كسر التشفير؛ وإذا كانت فوضوية للغاية، تصبح غير فعالة. لطالما كان التحدي الذي يواجه علماء التشفير هو إيجاد النقطة المثالية: تبديلات معقدة بما يكفي لمقاومة الهجمات المتطورة، وفي الوقت نفسه منظمة بما يكفي ليتم تنفيذها بسرعة.

تتناول دراسة حديثة أجراها "لي شواي" من جامعة نينغشيا هذا التحدي من خلال استكشاف عائلة محددة من هذه التبديلات عبر عدسة التناظر الهندسي. يركز البحث على خاصية تسمى "الاعوجاج المحلي" (local crookedness)، والتي تصف كيفية سلوك التبديل عندما يتم إزاحة مدخلاته بمقدار معين. يقدم المؤلف فئة جديدة من هذه الدوال، محددة بنمط معين في كيفية تغير مخرجاتها. ومن خلال معاملة هذه الدوال كعناصر في مجموعة أكبر يمكن تحويلها عن طريق الإزاحة، أو الدوران، أو تبديل أجزاء معينة من البيانات، ترسم الدراسة خارطة لآفاق الاحتمالات. كان الهدف هو معرفة ما إذا كان التحرك داخل هذه الآفاق يمكن أن يولد تبديلات جديدة وأفضل توفر حماية أقوى ضد تحليل التشفير التفاضلي (differential cryptanalysis)، وهي طريقة يدرس فيها المهاجمون كيف تؤثر التغييرات الصغيرة في المدخلات على المخرجات لاستنتاج المفتاح السري.

يتضمن جوهر العمل سلسلة بناء تبدأ بتبديل معروف ومنضبط، ثم تطبق سلسلة من العمليات الجبرية الدقيقة لإنشاء تبديلات جديدة. يحدد المؤلف مجموعة محددة من القواعد، أو "فئة D"، التي يجب أن تتبعها هذه التبديلات لتبقى صالحة. وضمن هذه المجموعة، يثبت الباحث أن مجموعة التبديلات "المرفوعة" (lifted permutations) — تلك التي تم تمديدها من مساحة أصغر إلى مساحة أكبر — تمتلك صلابة فريدة. فإذا حاول المرء تغيير تبديل واحد باستخدام نوع واحد فقط من العمليات، مثل الإزاحة البسيطة أو الدوران الخطي، فإن النتيجة عادة ما تفشل في الببقاء كبديل كامل صالح. ومع ذلك، تُظهر الدراسة أن الجمع بين عمليتين مختلفتين في تسلسل محدد يكسر هذه الصلابة. هذا الجمع يسمح للباحث بالتنقل في مساحة الاحتمالات، والانتقال من تبديل صالح إلى آخر دون فقدان الخصائص الجوهرية المطلوبة للأمن.

ولجعل هذا الإطار النظري عمليًا، طورت الورقة خوارزميتين متمايزتين. الأولى هي بحث "التراجع" (backtracking search) الذي يبني تبديلاً كاملاً من الصفر، مع ضمان استيفاء متطلبات الترتيب المزدوج في كل خطوة. والثانية هي بحث محلي جشع (greedy local search) يبدأ بتبديل موجود ويحاول تحسينه من خلال تطبيق العمليات المجمعة الموصوفة سابقًا. تعمل هذه الخوارزمية الثانية مثل متسلق يبحث عن قمة أعلى: فهي تختبر تعديلات صغيرة متنوعة، لكنها لا تقبل أي تغيير إلا إذا كان يحسن الجودة التشفيرية للتبديل بشكل صارم. وتُقاس الجودة بمؤشرين رئيسيين: التوحيد التفاضلي (differential uniformity)، الذي يحصي التكرار الأسوأ لأنماط المخرات، واللاخطية (nonlinearity)، التي تقيس مدى ابتعاد الدالة عن كونها معادلة خطية بسيطة. وتعتبر قيم التوحيد التفاضلي الأقل واللاخطية الأعلى أفضل عمومًا للأمن.

اختبر الباحثون هذه الطرق على مساحة رياضية بحجم 32، وهو ما يتوافق مع نظام 5 بت. وبالبدء من تبديل خطي بسيط كان معروفًا بضعفه، تم تشغيل خوارزمية البحث الجشع مائة مرة. أسفرت التجارب عن عدة تبديلات ذات توحيد تفاضلي قدره 4، وهو تحسن ملحوظ عن القيمة الابتدائية البالغة 32. كما بدأت الدراسة بمائة تبديل تم إنشاؤها عشوائيًا وطبقت نفس عملية البحث. ومرة أخرى، وجدت الخوارزمية باستمرار تبديلات ذات توحيد تفاضلي قدره 4. لم تكن النتائج تتعلق فقط بإيجاد أرقام أفضل، بل امتلكت التبديلات الجديدة "أطيافًا" (spectra) مميزة، أو أنماطًا من ترددات المخرجات، كانت مختلفة عن بعضها البعض وعن نقطة البداية. وهذا يثبت أن الطريقة لا تنتج مجرد تنويعات لنفس الكائن، بل تكتشف حقًا فئات جديدة ومتميزة من التبديلات الآمنة.

تتعلق واحدة من أكثر النتائج إثارة للاهتمام بالعلاقة بين هذه التبديلات الجديدة وفئة شهيرة من الدوال تُعرف بدوال APN (اللاخطية شبه المثالية). تاريخيًا، اعتمدت العديد من عمليات بناء التبديلات الآمنة على البدء بهذه الدوال. ومع ذلك، وجدت الدراسة أن التبديلات التي تم توليدها بواسطة طريقة "الاقتران المحلي" الجديدة هذه، رغم امتلاكها لنفس التوحيد التفاضلي الممتاز البالغ 4، إلا أنها غير متكافئة وفق معيار CCZ مع تلك المشتقة من مناهج APN الكلاسيكية. في الواقع، أدى تبديل مرجعي يعتمد على دالة APN معروفة أداءً أسوأ في هذا الاختبار المحدد، بتوحيد تفاضلي قدره 8. يشير هذا إلى أن الطريقة الجديدة تستكشف منطقة مختلفة من المشهد الرياضي، وتكشف عن تبديلات عالية الجودة كانت غير قابلة للوصول سابقًا باستخدام تقنيات البناء القياسية.

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

ملخص تقني: بناء التبديلات الكاملة عبر الفئة D للتبديلات الملتوية محلياً

بيان المشكلة

تتناول الورقة البحثية بناء التبديلات الكاملة (CPs) فوق الحقول المنتهية $\mathbb{F}_{2^n}$ . يُعد التبديل $f$ تبديلاً كاملاً (CP) إذا كان كل من $f$ والدالة $x \mapsto f(x) + x$ تبديلين أيضاً. وتعتبر التبديلات الكاملة بالغة الأهمية في التشفير، وتحديداً كأجزاء بناء لـ S-boxes في إطار Lai–Massey ولتوليد المربعات اللاتينية المتعامدة.

بينما ترتبط التبديلات الكاملة بـ التبديلات الملتوية محلياً (LCPs) فوق $\mathbb{F}_{2^{n+1}}$ عبر مراسلة Shuai–Li، اعتمدت الطرق السابقة على مسار "دالة ملتوية $\leftarrow$ LCP $\leftarrow$ CP". وكان هذا النهج مقيداً، لأنه لم يسمح بالحركة الحرة أو توليد LCPs جديدة داخل الفئة نفسها. تسعى الورقة إلى التغلب على ذلك من خلال العمل مباشرة داخل فئة LCP لتوليد CPs جديدة عبر تأثيرات المجموعات الداخلية، مما يؤدي إلى توسيع حيز البحث عن التبديلات القوية تشفيرياً.

المنهجية

1. الفئة D والثبات

يقدم المؤلف الفئة D، المعرفة بأنها مجموعة التبديلات $f$ فوق $\mathbb{F}_{2^{n+1}}$ بحيث يكون مشتقها في اتجاه ثابت $q_1 = 2^n$ له صورة تساوي متمم مستوي (hyperplane) ثابت $H = \{x : x_n = 0\}$ .
$D = \{f \in S_q : \text{Im } \Delta_{q_1}f = K\}$
حيث $K = \mathbb{F}_{2^{n+1}} \setminus H$ .

تثبت الورقة أن $D$ مغلقة تحت ثلاثة تأثيرات مجموعات محددة:

الترجمة اليسارية: $t_a \circ f$ لأي $a \in \mathbb{F}_q$ .
الضرب اليساري: $g \circ f$ لأي $g$ في المجموعة الخطية العامة التي تحافظ على $H$ ( $GL_H$ ).
الضرب اليميني: $f \circ h$ لأي $h$ في المركز (centralizer) الخاص بالتبديل الذي يعكس $H$ و $K$ .

بالإضافة إلى ذلك، الفئة مغلقة تحت ترجمات محلية محددة $t_{a,X}$ (ترجمات مقيدة لمجموعة جزئية $X$ ) بشرط أن تكون $X$ اتحاد مدارات لمجموعة ثنائية (dihedral group) محددة ناتجة عن الترجمة والتبديل الملحق.

2. الصلابة وسلسلة البناء

يقدم المؤلف فئة التبديلات الكاملة المرفوعة $D^\uparrow \subset D$ ، وهي تتكون من التبديلات في $D$ التي تعمل كدالة محايدة على متمم $K$ .

الصلابة (Rigidity): تثبت الورقة أن $D^\uparrow$ "صلبة" تحت أي عملية منفردة من خصائص الإغلاق المذكورة أعلاه (الترجمة، الضرب الخطي، أو ضرب المركز). لا يمكن لعملية واحدة أن تنقل CP مرفوعاً إلى CP مرفوع آخر ما لم تكن هي العملية المحايدة.
سلسلة البناء: لتوليد CPs جديدة، يبني المؤلف سلسلة تتضمن حاصل ضرب من العمليات:
$CP \xrightarrow{\text{lift}} LCP \xrightarrow{\text{local translation}} LCP' \xrightarrow{\text{centralizer correction}} LCP'' \xrightarrow{\text{restriction}} \text{New } CP$
تستخدم هذه السلسلة عناصر مركز محلية ( $g_{a,X_1}$ و $g_{a,X_2}$ ) لإصلاح العيب الناتج عن الترجمة المحلية، مما يضمن بقاء النتيجة ضمن $D^\uparrow$ .

3. الترافقات المحلية

ينتج عن البناء نوعان محددان من الترافقات المحلية، $f_1$ و $f_2$ ، معرفان على الحقل الأساسي $\mathbb{F}_{2^n}$ :

$f_1$ : تعديل لـ $f$ على مجموعة جزئية $X_1 \subset H$ حيث $X_1$ ثابتة تحت مجموعة ثنائية.
$f_2$ : تعديل يتضمن معكوس $f$ على مجموعة جزئية $X_2$ حيث $X_2$ ثابتة تحت مجموعة دورية (cyclic group).
تقدم الورقة شروطاً ضرورية وكافية لكي تظل هذه الخرائط المعدلة تبديلاً كاملاً (CPs).

4. الخوارزميات

تم تقديم خوارزميتين لتنفيذ النظرية:

البحث بالرجوع للخلف العشوائي (Random Backtracking Search): يولد CPs عشوائية من الصفر من خلال الحفاظ على القيود على $f(x)$ و $f(x)+x$ .
البحث المحلي الجشع (Greedy Local Search): يطبق الترافقات المحلية ( $f_1, f_2$ ) بشكل متكرر على "بذرة" (seed) لـ CP. ولا يقبل التحركات إلا إذا كانت تحسن بشكل صارم دالة الجودة القائمة على الطيف التفاضلي الكامل (DDT) وطيف والش (Walsh spectrum).

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

المساهمات النظرية

إثبات الثبات: أثبت أن الفئة D ثابتة تحت تأثيرات المجموعات المحددة والترجمات المحلية.
مبرهنة الصلابة: أثبتت أن فئة $D^\uparrow$ المرفوعة لا يمكن توليدها بعمليات منفردة، مما يستلزم استخدام سلسلة بناء مركبة.
معايير عدم التكافؤ CCZ: استُخلصت معايير لتحديد متى تكون الـ CPs المستحدثة غير متكافئة بنمط CCZ مقارنة بالبذرة. ويعتمد ذلك على التحقق مما إذا كان جدول التوزيع التفاضلي (DDT) أو مجموعة معاملات والش المطلقة قد تغيرت.
الحدود التشفيرية: استُخلصت حدود للانتشار التفاضلي ( $\delta$ )، واللاخطية ($nl $)، والدرجة الجبرية ($ \deg $) تحت التعديلات المحلية. على سبيل المثال، يتغير$ \delta $بمقدار$ 2m $كحد أقصى حيث$ m$ هو حجم المجموعة المعدلة.

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

أُجريت التجارب على $H \cong \mathbb{F}_{2^5}$ (32 عنصراً):

توليد CPs بـ $\delta=4$ : بدءاً من بذرة خطية ( $\delta=32$ ) وبذور عشوائية، نجح البحث الجشع في إيجاد عدة تبديلات كاملة ذات انتشار تفاضلي $\delta=4$ .
أطياف متميزة: أظهرت الـ CPs المولدة أطيافاً تفاضلية متميزة عن بعضها البعض وعن الـ CP المرجعي القائم على Dillon (الذي كان $\delta=8$ ).
عدم التكافؤ CCZ: تؤكد الأطياف التفاضلية المتميزة أن البناء ينتج فئات عدم تكافؤ CCZ جديدة، وليس مجرد متغيرات تآلفية (affine variants) للبذرة.
أدلة الاتصال: يوفر التقارب المتكرر نحو توزيعات مؤشرات متشابهة من بذور عشوائية مختلفة دليلاً أولياً على أن مجموعة الـ CPs المرفوعة $D^\uparrow$ قد تكون متصلة تحت تحركات الترافق المحلي.

الأهمية والادعاءات

تدعي الورقة أنها توفر إطاراً جبرياً منهجياً لتوليد تبديلات كاملة جديدة من خلال استغلال البنية الداخلية لفئة LCP.

ما وراء الدوال الملتوية: بخلاف الطرق السابقة التي تعتمد على البدء بدالة ملتوية، يسمح هذا النهج باستكشاف فضاء LCP نفسه للعثور على CPs.
الفائدة التشفيرية: نجحت الطريقة في إنتاج CPs ذات انتشار تفاضلي منخفض ( $\delta=4$ )، وهي خاصية مرغوبة لـ S-boxes، والتي كان من الصعب بناؤها سابقاً عبر المراسلة القياسية للدوال الملتوية.
الرؤية الهيكلية: إن تحديد "صلابة" $D^\uparrow$ والدور المحدد للمركز في "إصلاح" الترجمات المحلية يقدم فهماً نظرياً أعمق للعلاقة بين LCPs و CPs.
المسائل المفتوحة: تضع الورقة مسألة اتصال $D^\uparrow$ ووجود دوال APN ضمن هذه الفئة كمسائل مفتوحة، مما يشير إلى أنه بينما تدعم التجارب فكرة الاتصال، فإن إثباتاً رسمياً لا يزال مطلوباً. كما تشير إلى أنه بينما توحي النتائج بوجود صلة محتملة بتبديلات APN، إلا أنه لم يتم إثبات وجود تبديلات APN صراحة في هذا العمل.