🔢 mathematics

The combinatorial structure and value distributions of plateaued functions

تتقصى هذه الورقة البنية التوافقية، وتوزيعات القيم، والخصائص التشفيرية للدوال الهضبية (plateaued functions) فوق الحقول المحدودة، مؤسسةً روابط مباشرة بين تحويلات والش (Walsh transforms) الخاصة بها، والخطية، والانتظام التفاضلي، مع توصيف وجود وقيود الدوال الهضبية "شبه المتوازنة" (almost balanced) والدوال الهضبية ذات الانتشار غير التماثلي الأقصى (APN) بشكل محدد.

المؤلفون الأصليون: Lukas Kölsch, Alexandr Polujan

نُشر 2026-03-26

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

CC BY 4.0

المؤلفون الأصليون: Lukas Kölsch, Alexandr Polujan

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

تخيل أنك مهندس معماري بارع يصمم حصناً رقمياً فائقاً. لجعل هذا الحصن آمناً، تحتاج إلى بناء جدران يصعب كسرها للغاية، ومع ذلك تكون مرنة بما يكفي للسماç بمرور المستخدمين المصرح لهم. في عالم التشفير، هذه "الجدران" هي دوال رياضية.

هذه الورقة البحثية تشبه تقرير تفتيش مفصل عن نوع خاص جداً من هذه الجدران يسمى الدالة الهضبية (Plateaued Function).

إليك تفاصيل ما اكتشفه المؤلفون، مشروحة عبر تشبيهات بسيطة.

1. لبنات البناء: ما هي الدالة "الهضبية"؟

فكر في الدالة كآلة تأخذ كومة ضخمة من المدخلات (مثل مليون مفتاح مختلف) وتخرج مخرجات (مثل مليون قفل مختلف).

الدوال المتوازنة (Balanced Functions): في الحالة المثالية، تريد آلة حيث يحصل كل قفل على نفس العدد تماماً من المفاتيح. إذا كان لديك 1,000 قفل و1,000 مفتاح، فسيحصل كل قفل على مفتاح واحد بالضبط. هذا هو التوازن المثالي.
المشكلة: في العالم الحقيقي، التوازن المثالي نادر. أحياناً، يحصل قفل واحد على 10 مفاتيح، بينما لا يحصل آخر على أي شيء. هذا يخلق "عدم توازن"، وهو ما يمكن للمخترقين استغلاله.
الدوال الهضبية (Plateaued Functions): هذه هي الآلات "شبه المثالية". بدلاً من التوزيع المسطح والمتساوي، تخيل مشهداً طبيعياً به هضاب مسطحة (ومن هنا جاء الاسم). معظم الأقفال تحصل على عدد قياسي من المفاتيح، لكن القليل منها قد يحصل على كمية مختلفة قليلاً. إنها ليست مسطحة تماماً، لكنها "مسطحة بما يكفي" لتكون آمنة جداً.

لقد درس المؤلفون هذه الدوال "الهضبية" لأنها لبنات البناء للعديد من أنظمة التشفير الحديثة (مثل تلك التي تحمي بياناتك البنكية أو بيانات الإنترنت الخاصة بك).

2. أداة التحري: تحويل والش (Walsh Transform)

كيف تعرف ما إذا كانت الآلة متوازنة أم لا دون الحاجة لعد كل مفتاح؟ أنت بحاجة إلى جهاز أشعة سينية خاص.

في الرياضيات، هذا الأشعة السينية يسمى تحويل والش (Walsh Transform).

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

استخدم المؤلفون هذا "المحلل الصوتي" لمعرفة كيفية توزيع المفاتيح بين الأقفال، دون الحاجة لعدها واحداً تلو الآخر.

3. الاكتشاف الكبير: قاعدة "شبه التوازن"

ركز الفريق على مجموعة خاصة من هذه الآلات تسمى "شبه المتوازنة" (Almost Balanced).

السيناريو: تخيل حفلة بها 100 ضيف و100 كرسي. في الحفلة المتوازنة تماماً، يجلس الجميع. في الحفلة "شبه المتوازنة"، يوجد 99 كرسياً عليه شخص واحد بالضبط، لكن هناك كرسياً واحداً عليه 5 أشخاص، وكرسياً آخر فارغ. إنه أمر عادل تقريباً، لكن ليس تماماً.
النتيجة: اكتشف المؤلفون أنه بالنسبة لهذه الآلات "شبه المتوازنة"، توجد قواعد صارمة. لا يمكنك وضع أي عدد من الأشخاص على الكرسي الإضافي. الرياضيات تجبر الأرقام على أن تكون محددة جداً (مثل قوى العدد 2 أو مضاعفات محددة).

لق un أثبتوا أنه إذا كانت الآلة "شبه متوازنة"، فإن هيكلها الداخلي (تحويل والش) يجب أن يبدو بطريقة معينة. الأمر يشبه قولك: "إذا رأيت منزلاً بباب أحمر، فلا بد أن يكون سقفه أزرق".

4. لغز "الحد الواحد" (Monomial Mystery)

أحد أشهر أنواع هذه الآلات يُبنى باستخدام صيغ بسيطة تسمى "الحد الواحد" (Monomials) (فكر فيها كوصفات مكونة من حد واحد، مثل $x^3$ أو $x^5$ ).

السؤال: هل يمكن لهذه الوصفات البسيطة أن تصنع آلات "شبه متوازنة"؟
الإجابة: نعم، ولكن فقط تحت شروط صارمة للغاية. وجد المؤلفون أن هذه الوصفات البسيطة لا تعمل إلا إذا اتبع "الأس" (القدرة) نمطاً محدداً للغاية يتعلق بحجم النظام.
التشبيه: الأمر يشبه محاولة خبز كعكة باستخدام الدقيق والسكر فقط. يمكنك فعل ذلك، ولكن فقط إذا استخدمت كوبين من الدقيق وكوباً واحداً من السكر بالضبط. إذا استخدمت 3 أكواب من الدقيق، ستنهار الكعكة. الورقة البحثية تخبرنا بالضبط أي "وصفات" (أسس) تعمل وأيها تفشل.

5. دوال APN "فائقة الأمان"

أخيراً، نظر المؤلفون إلى "نخبة" هذه الدوال: دوال APN. هذه هي المعيار الذهبي للأمان، وتُستخدم في أكثر خوارزميات التشفير حرجاً.

التحدي: نحن نعلم أن هذه الدوال موجودة، لكننا لا نفهم شكلها بشكل كامل. هل لديها توزيع "مثالي" للمفاتات، أم أنها فوضوية؟
الاختراق: استخدم المؤلفون أدواتهم الجديدة لإثبات أن أنواعاً معينة من التوزيعات "الفوضوية" هي في الواقع مستحيلة لهذه الدوال النخبوية.
- مثال: أظهروا أن نوعاً معيناً من دالة APN "شبه المتوازنة" (حيث يوجد قفلان يحتوي كل منهما على مفتاحين، والبقية تحتوي على 3 مفاتيح) لا يمكن أن يوجد. الأمر يشبه إثبات أن نوعاً معيناً من المثلثات ذات الأضلاع الأربعة مستحيل هندسياً.

لماذا يهم هذا؟

فكر في التشفير كأنها لعبة "غميضة" بين صانعي الشفرات وكاسري الشفرات.

صناع الشفرات يريدون بناء دوال يصعب التنبؤ بها (لا خطية عالية) وتوزع البيانات بالتساوي (متوازنة).
كاسرو الشفرات يبحثون عن أنماط أو عدم توازن لكسر الشفرة.

من خلال فهم "البنية التوافقية" (الشكل والتوزيع) لهذه الدوال الهضبية، يعطي المؤلفون لصناع الشفرات مخططاً أفضل. إنهم يقولون:

"إليكم الأشكال الوحيدة التي تعمل."
"إليكم الأشكال المستحيلة، فلا تضيعوا وقتكم في محاولة بنائها."
"إليكم كيفية التحقق مما إذا كان تصميمكم آمناً بمجرد النظر إلى 'صوته' (تحويل والش)."

الملخص

هذه الورقة البحثية هي خريطة للمعماريين الرقميين. لقد أخذت مفهوماً رياضياً مجرداً ومعقداً (الدوال الهضبية) واستخدمت أداة قوية (تحويل والش) للكشف عن القواعد الخفية لكيفية توزيع هذه الدوال لبياناتها. لقد وجدوا أنه بينما يمكن لهذه الدوال أن تكون "شبه متوازنة"، إلا أنها مقيدة بقوانين رياضية صارمة، كما استبعدوا عدة تصميمات مستحيلة لأكثر أنظمة التشفير أماناً في العالم.

إليك ملخص تقني مفصل للورقة البحثية بعنوان "البنية التوافقية وتوزيعات القيم للدوال الهضبية (Plateaued Functions)" من إعداد لوكاش كولش وألكسندر بولوجان.

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

تعالج الورقة الفجوة في فهم توزيعات القيم (أحجام مجموعات الصورة والسابقة) للدوال الهضبية، وهي فئة واسعة من البدائيات التشفيرية التي تعمم الدوال التربيعية، ودوال "بنت" (bent)، ومعظم دوال "اللا-مثالية شبه الكاملة" (APN) المعروفة.

بينما تمت دراسة الخصائص التفاضلية واللاخطية لهذه الدوال بشكل مستفيض، إلا أن بنيتها التوافقية فيما يتعلق بكيفية ربط المدخلات بالمخرجات (تحديداً ما إذا كانت متوازنة، أو شبه متوازنة، أو دالة $d$ -إلى-1) لا تزال أقل استكشافاً. يهدف المؤلفون إلى:

إرساء اتصال صارم بين تحويل والش (Walsh transform) (الخصائص الطيفية) وتوزيع القيم (أحجام السوابق) للدوال المتجهية $F: \mathbb{F}_p^n \to \mathbb{F}_p^m$ .
توصيف الدوال شبه المتوازنة الهضبية، حيث تكون جميع السوابق لها نفس الحجم باستثناء سابقة واحدة.
تحديد شروط الوجود للدوال الهضبية $d$ -إلى-1 (بما في ذلك الدوال أحادية الحد - monomials) واستخلاص حدود على خطيتها وتوحيدها التفاضلي.
تحليل البنية التوافقية المحددة لدوال APN الهضبية، وخاصة تلك ذات أحجام مجموعات الصورة الدنيا.

2. المنهجية

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

الخطوات المنهجية الرئيسية:

تحويل والش عند الصفر: يركز المؤلفون على تحويل والش عند تقييمه عند $a=0$ ، ويُرمز له بـ $W_F(b, 0)$ . يستخدمون تعامد الخصائص (orthogonality of characters) لربط مجموع معاملات والش بأحجام السوابق.
مقياس عدم الاتزان ( $N_bF$ ): يعرّفون عدم الاتزان $N_bF$ باعتباره المجموع الموزون لمربعات معاملات والش عند الصفر لـ $b$ غير الصفر. يقيس هذا المقياس الانحراف عن الدالة المتوازنة.
التحسين عبر متباينة كوشي-شفارز: يطبقون متباينة كوشي-شفارز على النظام المكون من معادلات مجموع أحجام السوابق ( $\sum X_i = p^n$ ) ومجموع مربعات أحجام السوابق ( $\sum X_i^2 = p^{2n-m} + p^m N_bF$ ). يسمح هذا باستخلاص حدود وثيقة لأحجام مجموعات السوابق الفردية.
القيود الطيفية للدوال الهضبية: يستفيدون من تعريف الدوال الهضبية، حيث تكون معاملات والش مقيدة بمجموعة محددة من القيم $\{0, \pm p^{(n+t)/2}\}$ . هذا التقييد يفرض قيوداً قوية على التوزيعات القيمية الممكنة.
النظرية العددية الجبرية: بالنسبة للأعداد الأولية الفردية $p$ ، يستخدمون خصائص الحقول الدورية (cyclotomic fields) لإثبات أن بعض معاملات والش يجب أن تكون أعداداً صحيحة، وهي خطوة حاسمة في تحليل الدوال $d$ -إلى-1.

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

أ. الحدود العامة والدوال شبه المتوازنة

مبرهنة 3.3: يستخلص المؤلفون حدوداً عليا ودنيا صريحة لحجم أي مجموعة سابقة $|F^{-1}(\beta)|$ بدلالة حجم مجموعة الصورة وعدم الاتزان $N_bF$ .
تعريف 3.7: يعممون مفهوم الدوال شبه المتوازنة لتشمل الحالات غير الشاملة (non-surjective). تكون الدالة شبه متوازنة إذا حققت الحدود المستخلصة في المبرهنة 3.3 بالتساوي، مما يعني أن جميع السوابق لها الحجم $A$ باستثناء سابقة واحدة بحجم $B$ .
مبرهنة 4.1: بالنسبة لدالة هضبية شاملة وشبه متوازنة، يثبت المؤلفون أن جميع معاملات والش غير الصفرية عند الصفر يجب أن يكون لها نفس المقدار وأن تكون أعداداً صحيحة. يؤدي هذا إلى توصيف دقيق لأحجام السوابق.

ب. الدوال الهضبية $d$ -إلى-1 والدوال أحادية الحد

مبرهنة 5.2: نتيجة رئيسية تثبت أن الدالة الهضبية $d$ $d$ -إلى-1 (حيث $d > 2$ $d > 2$ ) لا يمكن أن توجد إلا إذا كان $d = p^t + 1$ لعدد صحيح $t$ $t$ ما، و $n$ يجب أن يكون زوجياً.
- يجب أن تمتلك الدالة مزيجاً محدداً من مكونات "بنت" ومكونات ذات سعة $p^{n/2+t}$ .
- تتحدد الخطية كـ $L(F) = p^{n/2+t}$ .
نتيجة 5.4: بتطبيق ذلك على الدوال أحادية الحد $F(x) = x^d$ ، فإن هذا يعني أن الدوال أحادية الحد الهضبية هي إما تبديلات ( $d=1$ ) أو دوال $d$ -إلى-1 حيث $d = p^t + 1$ .
مبرهنات 5.5 و5.6: يستخلصون حدوداً على التوحيد التفاضلي (differential uniformity). الدالة الهضبية $(p^t+1)$ -إلى-1 تمتلك توحيداً تفاضلياً لا يقل عن $p^t$ . وهي تحقق $p^t$ بالضبط إذا وفقط إذا كانت ثنائية القيم تفاضلياً (أي أن المعادلة $F(x+a)-F(x)=b$ لها إما 0 أو $p^t$ من الحلول).

ج. إنشاء الدوال شبه المتوازنة

تقدم الورقة إنشاءات صريحة للدوال الهضبية الشاملة وشبه المتوازنة:

الدوال أحادية الحد (مبرهنة 5.8): يُظهر أن الدوال من الشكل $F(x) = \text{Tr}_{n/2}^n(x^{2r+1})$ تكون شبه متوازنة تحت شروط محددة على $r$ و $n$ .
دوال مايورانا-ماكفارلاند (المقترح 5.9 و 5.10): يحلل المؤلفون إنشاءات مايورانا-ماكفارلاند المعممة، موضحين كيف تؤدي اختيارات محددة للتبديل $\pi$ والدالة $\phi$ إلى إنتاج دوال هضبية متوازنة أو شبه متوازنة بتوزيعات قيم يمكن التنبؤ بها.

د. دوال APN الهضبية

حدود عدم الاتزان (مقترح 6.3): بالنسبة لدوال APN الهضبية، يقع عدم الاتزان $N_bF$ $N_{b} F$ بين $(2^{n+1}-2)/3$ $(2^{n + 1} - 2) /3$ و $2^{n+1}-2$ $2^{n + 1} - 2$ .
- الحد الأدنى يقابل الدوال ذات أكبر عدد من مكونات "بنت".
- الحد الأعلى يقابل الدوال التي لا تحتوي على مكونات متوازنة.
تكافؤ مكونات "بنت" (مقترح 6.5): يجب أن يكون عدد مكونات "بنت" في دالة APN هضبية متوافقاً مع $2 \pmod 4$ .
استبعاد توزيعات القيم (مبرهنة 6.7): يثبت المؤلفون أن دوال APN الهضبية ذات أصغر حجم لمجموعة الصورة لا يمكن أن تمتلك ثاني توزيع قيم ممكن مذكور في الأدبيات السابقة (تحديداً التوزيع الذي يحتوي على سابقتين بحجم 2 والباقي بحجم 3).
مبرهنة 6.8: دوال APN الهضبية ذات أصغر حجم لمجموعة الصورة لا يمكن أن تحتوي على أي دالة مكونة متوازنة.

4. الأهمية

إطار موحد: توفر الورقة إطاراً طيفياً موحداً لتحليل توزيعات القيم لمجموعة واسعة من الدوال التشفيرية، متجاوزة الحالة الخاصة لدوال "بنت" أو APN.
قيود الوجود: تفرض قيوداً جبرية صارمة على وجود الدوال الهضبية $d$ -إلى-1، مما يستبعد العديد من المرشحين المحتملين للبدائيات التشفيرية بناءً على خصائصها الطيفية.
الآثار التشفيرية:
- النتائج المتعلقة بـ التوحيد التفاضلي تساعد في تقييم مقاومة الدوال الهضبية ضد الهجوم التفاضلي.
- توصيف الدوال شبه المتوازنة أمر بالغ الأهمية لفهم الخصائص الإحصائية لصناديق الاستبدال (S-boxes) ودوال التجزئة (مثل الأنظمة المستخدمة في إثباتات المعرفة الصفرية مثل Poseidon و Rescue-Prime، والتي تستخدم الدوال أحادية الحد).
- استبعاد توزيعات قيم محددة لدوال APN يضيق نطاق البحث في مشكلة "APN الكبيرة" (إيجاد تبديلات APN في الأبعاد الزوجية).
إنشاءات جديدة: تقدم الورقة إنشاءات نظرية جديدة (عبر نماذج مايورانا-ماكفارلاند والدوال أحادية الحد من نوع Trace) تضمن توزيعات قيم محددة، مما يساعد في تصميم بدائيات ذات خصائص توازن ولاخطية مرغوبة.

باختصار، يجسّر هذا العمل الفجوة بين النظرية الطيفية (تحويل والش) والبنية التوافقية (توزيع القيم) للدوال الهضبية، مما يوفر شروطاً ضرورية وإنشاءات صريحة حيوية للتشفير المتماثل الحديث.