2025-11-15T00:04:11.828858

On the Walsh spectra of quadratic APN functions

BÃ©nÃ©teau, Goluboff, KÃ¶lsch et al.

APN functions play a central role as building blocks in the design of many block ciphers, serving as optimal functions to resist differential attacks. One of the most important properties of APN functions is their linearity, which is directly related to the Walsh spectrum of the function. In this paper, we establish two novel connections that allow us to derive strong conditions on the Walsh spectra of quadratic APN functions. We prove that the Walsh transform of a quadratic APN function $F$ operating on $n=2k$ bits is uniquely associated with a vector space partition of $\mathbb{F}_2^n$ and a specific blocking set in the corresponding projective space $PG(n-1,2)$. These connections allow us to prove a variety of results on the Walsh spectrum of $F$. We prove for instance that $F$ can have at most one component function of amplitude larger than $2^{\frac{3}{4}n}$. We also find the first nontrivial upper bound on the number of bent component functions of a quadratic APN function, and and provide conditions for a function to be CCZ-equivalent to a permutation, based on its number of bent components.

academic

حول أطياف والش للدوال APN التربيعية

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

معرّف البحث: 2510.12008
العنوان: On the Walsh spectra of quadratic APN functions
المؤلفون: Sophie Hannah Bénéteau (جامعة فلوريدا)، Nicolas Goluboff (جامعة ماساتشوستس أمهيرست)، Lukas Kölsch (جامعة جنوب فلوريدا)، Divyesh Vaghasiya (جامعة جنوب فلوريدا)
التصنيف: math.CO cs.IT math.IT
تاريخ النشر: 15 أكتوبر 2025 (نسخة arXiv التمهيدية)
رابط البحث: https://arxiv.org/abs/2510.12008

الملخص

تلعب دوال APN (شبه مثالية غير خطية) دوراً أساسياً في تصميم أنظمة التشفير الكتلية، وتمثل الدوال المثلى للدفاع ضد الهجمات التفاضلية. تتمثل إحدى أهم خصائص دوال APN في درجة خطيتها، والتي ترتبط ارتباطاً مباشراً بطيف والش للدالة. يؤسس هذا البحث ارتباطات جديدة مبتكرة تمكننا من استخلاص شروط قوية لطيف والش للدوال APN التربيعية. يثبت البحث أن تحويل والش للدالة APN التربيعية $F$ التي تعمل على $n=2k$ بت يرتبط بشكل فريد بتقسيمات الفضاء المتجه لـ $\mathbb{F}_2^n$ وبمجموعات حجب معينة في فضاء الإسقاط المقابل $PG(n-1,2)$ . تمكننا هذه الارتباطات من إثبات عدة نتائج متعلقة بطيف والش للدالة $F$ ، مثل إثبات أن $F$ يمكن أن يحتوي على مكون دالة واحد فقط بسعة أكبر من $2^{\frac{3}{4}n}$ ، وإيجاد أول حد أعلى غير تافه لعدد مكونات الدوال المنحنية في دوال APN التربيعية.

خلفية البحث والدافع

أهمية المشكلة

التطبيقات التشفيرية: دوال APN هي لبنات بناء أساسية في تصميم أنظمة التشفير المتماثلة، خاصة في شبكات الاستبدال والتبديل (SPN) للأنظمة الكتلية، مما يوفر مقاومة مثلى ضد الهجمات التفاضلية.
التحديات النظرية: بينما تم تحديد توزيع السعة بشكل كامل للدوال APN التربيعية في الحالات ذات البعد الفردي (جميع المكونات غير التافهة لها سعة $2^{\frac{n+1}{2}}$ )، تبقى حالة البعد الزوجي مشكلة مفتوحة.
القيود الحالية:
- بالنسبة للـ $n$ الزوجية، القيد الوحيد المعروف حالياً على السعة يأتي من توصيف اللحظة الرابعة لتحويل والش
- نقص في الحدود غير التافهة لعدد مكونات الدوال المنحنية في دوال APN التربيعية
- فهم ناقص للخصائص الهيكلية لطيف والش

دافع البحث

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

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

إنشاء ارتباطات تقسيم الفضاء المتجه: إثبات وجود مراسلة فريدة بين توزيع السعة للدالة APN التربيعية $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ (حيث $n$ زوجية) وتقسيمات الفضاء المتجه لـ $\mathbb{F}_2^n$ .
بناء نظرية مجموعات الحجب: إثبات أن مجموعة المكونات غير التافهة وغير المنحنية $N_F$ تشكل مجموعات حجب خاصة في فضاء الإسقاط $PG(n-1,2)$ .
استخلاص شروط جديدة:
- إثبات أن $F$ يمكن أن يحتوي على مكون دالة واحد فقط بسعة أكبر من $2^{\frac{3}{4}n}$
- إنشاء أول حد أعلى غير تافه لعدد مكونات الدوال المنحنية
- توفير شروط ضرورية لأن تكون الدالة مكافئة CCZ لتبديل
إكمال تحليل الأبعاد الصغيرة: إجراء تحليل شامل للأبعاد 6 و8 و10، وتحديد جميع توزيعات السعة الممكنة.

شرح الطريقة

تعريف المهمة

دراسة هيكل طيف والش للدالة APN التربيعية $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ (حيث $n$ زوجية)، حيث:

الإدخال: دالة APN تربيعية $F$
الإخراج: شروط وخصائص هيكلية لطيف والش
الهدف: فهم الإمكانيات والقيود على توزيع السعة

الإطار النظري الأساسي

1. نظرية تقسيم الفضاء المتجه

تعريف الدالة التفاضلية: بالنسبة لـ $a \in \mathbb{F}_2^n$ غير صفري، نعرّف $D_{F,a}(x) = F(x) + F(x+a)$ .

بناء الفضاء المتجه: نعرّف

$T_b = \{a \in \mathbb{F}_2^n : \text{Im}(D_{F,a}) = H_b\} \cup \{0\}$
$\overline{T_b} = \{a \in \mathbb{F}_2^n : \text{Im}(D_{F,a}) = \overline{H_b}\}$
$V_b = T_b \cup \overline{T_b}$

حيث $H_b = \{x \in \mathbb{F}_2^n : \langle b,x \rangle = 0\}$ .

النظرية الرئيسية (النظرية 2.4): سعة $F_b$ تساوي $2^{\frac{n+\dim(V_b)}{2}}$ .

2. نظرية مجموعات الحجب

خصائص مجموعات الحجب: مجموعة المكونات غير التافهة وغير المنحنية $N_F$ تشكل مجموعات حجب بشأن الفضاءات ذات البعد $(n/2)$ في $PG(n-1,2)$ ، وحجم التقاطع مع كل فضاء ذي بعد $(n/2)$ فردي.

النتيجة الرئيسية: باستخدام نظرية Govaerts-Storme بشأن حجم مجموعات الحجب غير التافهة الدنيا، نحصل على حد أعلى لعدد مكونات الدوال المنحنية.

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

الطريقة الهندسية: تحويل مشكلة طيف والش لدوال APN التربيعية إلى مشكلة هندسية تتعلق بتقسيمات الفضاء المتجه ومجموعات الحجب للمرة الأولى.
التوصيف الهيكلي: تحديد سعة المكون الدالي $F_b$ مباشرة من خلال $\dim(V_b)$ ، مما يؤسس ارتباطاً مباشراً بين الهيكل الجبري والخصائص الطيفية.
التطبيق متعدد التخصصات: التطبيق الماهر للنظريات العميقة لتقسيمات الفضاء المتجه ومجموعات الحجب في الهندسة المحدودة.

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

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

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

التحليل الشامل للأبعاد الصغيرة:
- البعد 6: التحقق من أن جميع أنواع تقسيمات الفضاء المتجه الممكنة تتوافق مع دوال APN التربيعية المعروفة
- البعد 8: تحديد 18 توزيع سعة ممكن
- البعد 10: تحليل جميع الحالات الممكنة نظرياً
التحقق من الدوال المعروفة:
- التحقق من دوال طيف والش الكلاسيكية
- تحليل الدوال ذات الخطية القصوى
- التحقق من خصائص مجموعات الحجب لدالة $x^3$

الأدوات الحسابية

يستخدم البحث التحقق المدعوم بالحاسوب لـ:

تعداد جميع تقسيمات الفضاء المتجه الممكنة في حالات البعد الصغير
التحقق من توافق النتائج النظرية مع دوال APN المعروفة

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

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

1. قيود السعة (النظرية 2.10)

النتيجة: لتكن $n$ زوجية، و $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ دالة APN تربيعية بخطية $L(F) = 2^{\frac{n+l}{2}}$ حيث $l > n/2$ ، إذاً:

لدى $F$ مكون دالة واحد بالضبط بسعة $2^{\frac{n+l}{2}}$
جميع المكونات الأخرى لها سعة على الأكثر $2^{\frac{2n-l}{2}}$
على وجه الخصوص، أي دالة APN تربيعية لها على الأكثر مكون دالة واحد بسعة أكبر من $2^{\frac{3n}{4}}$

2. الحد الأعلى لمكونات الدوال المنحنية (النظرية 3.9)

النتيجة: لتكن $n \geq 6$ زوجية، و $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ دالة APN تربيعية، إذاً: $|N_F| \geq 2^{n/2} + 2^{n/2-2} + 2^{n/2-3} - 1$ حيث تتحقق المساواة فقط عندما $n=8$ .

3. التصنيف الكامل للبعد 8 (النظرية 4.5)

بالنسبة لـ $F: \mathbb{F}_2^8 \to \mathbb{F}_2^8$ دالة APN تربيعية، توزيعات السعة الممكنة هي:

$[0^{190}, 2^{64}, 6^1]$
$[0^{238-4i}, 2^{5i}, 4^{17-i}]$ ، حيث $1 \leq i \leq 17$

تحليل الاستبعاد

1. مقارنة الحدود (القضية 4.4)

مقارنة ثلاثة حدود دنيا مختلفة لـ $|N_F|$ :

حد تقسيم الفضاء المتجه: الأقوى عندما $k < n/2$
حد مجموعة الحجب: الأقوى عندما $k = n/2$
حد البعد: الأقوى عندما $k > n/2$

2. تحليل التكافؤ

إثبات أنه تحت التكافؤ EA:

تقسيمات الفضاء المتجه تحافظ على التكافؤ (النظرية 5.2)
مجموعات الحجب تحافظ على التكافؤ (النظرية 5.1)

النتائج المهمة

القيود الهيكلية: طيف والش لدوال APN التربيعية يخضع لقيود هندسية صارمة وليس تعسفياً.
تأثير البعد: مع زيادة البعد، توزيعات السعة الممكنة تتناقص بشكل حاد.
شروط التكافؤ CCZ: إذا كانت دالة تربيعية مكافئة CCZ لتبديل، فإن $|N_F| \geq 3(2^{n/2} - 1)$ .

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

الاتجاهات البحثية الرئيسية

تصنيف دوال APN: أعمال Carlet و Charpin و Zinoviev وآخرين
نظرية طيف والش: طريقة اللحظة الرابعة وحدود الخطية
تقسيمات الفضاء المتجه: نظرية البناء لـ Heden و Bu وآخرين
نظرية مجموعات الحجب: الحدود المثلى لـ Govaerts-Storme

مزايا هذا البحث

إنشاء ارتباط مباشر للمرة الأولى بين طيف والش والأشياء الهندسية
توفير شروط أقوى من طريقة اللحظة الرابعة الكلاسيكية
توحيد وجهات النظر الجبرية والهندسية

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

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

طيف والش لدوال APN التربيعية يمتلك هيكلاً هندسياً عميقاً
تقسيمات الفضاء المتجه ومجموعات الحجب توفر أدوات قوية لفهم طيف والش
معظم توزيعات السعة الممكنة نظرياً لا يمكن تحقيقها عملياً

القيود

المشاكل البنائية: النظرية تستبعد العديد من الإمكانيات، لكنها لا توفر طرق بناء جديدة
قيود البعد: النتائج الرئيسية تركز على الأبعاد الزوجية
التعقيد الحسابي: التحليل الشامل للحالات عالية البعد لا يزال صعباً

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

يطرح البحث 6 مشاكل مفتوحة، بما فيها:

البحث عن أمثلة لتوزيعات السعة المفقودة في البعد 8
تحسين حدود $|N_F|$
إيجاد المزيد من أنواع تقسيمات الفضاء المتجه غير القابلة للتحقق

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

المزايا

الابتكار النظري: إنشاء منظور هندسي جديد تماماً لفهم طيف والش
منهجية النظام: دراسة منظمة من زاويتي تقسيمات الفضاء المتجه ومجموعات الحجب
عمق النتائج: الحصول على عدة حدود غير تافهة للمرة الأولى
اكتمال التحليل: تحليل شامل للحالات ذات الأبعاد الصغيرة

أوجه القصور

غياب البناء: النتائج استبعادية بشكل أساسي، تفتقر إلى بناء دوال APN جديدة
التحقق الحسابي: بعض النتائج تعتمد على التحقق بالحاسوب، والإثبات النظري ليس كاملاً
القيود التطبيقية: مساهمات نظرية بشكل أساسي، القيمة العملية في التشفير تحتاج إلى التحقق

التأثير

القيمة الأكاديمية: توفير أدوات ومنظور بحثي جديد لنظرية دوال APN
مساهمة المنهجية: قد تلهم الطريقة الهندسية دراسة مشاكل تشفيرية أخرى
المشاكل المفتوحة: المشاكل المطروحة توجه الأبحاث المستقبلية

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

التحليل النظري لدوال APN التربيعية
تصميم وتحليل صناديق الاستبدال (S-boxes) في التشفير
دراسة تطبيقات الهندسة المحدودة في التشفير
البحث في الخصائص الهيكلية لطيف والش للدوال البوليانية

المراجع

يستشهد البحث بـ 25 مرجعاً مهماً، يغطي نظرية دوال APN وتقسيمات الفضاء المتجه ونظرية مجموعات الحجب وغيرها من المجالات، مما يعكس طبيعة البحث متعدد التخصصات. تشمل المراجع الرئيسية كتاب Carlet عن الدوال البوليانية وأعمال Govaerts-Storme حول مجموعات الحجب وأبحاث Heden وآخرين حول تقسيمات الفضاء المتجه.