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 फलनों के Walsh स्पेक्ट्रा पर

मूल जानकारी

  • पेपर ID: 2510.12008
  • शीर्षक: द्विघात APN फलनों के Walsh स्पेक्ट्रा पर
  • लेखक: 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 फलनों का सबसे महत्वपूर्ण गुण इसकी रैखिकता है, जो फलन के Walsh स्पेक्ट्रम से सीधे संबंधित है। यह पेपर दो नए संबंध स्थापित करता है जो हमें द्विघात APN फलनों के Walsh स्पेक्ट्रम के लिए मजबूत शर्तें प्राप्त करने में सक्षम बनाते हैं। पेपर यह साबित करता है कि n=2kn=2k बिट्स पर संचालित द्विघात APN फलन FF का Walsh रूपांतरण F2n\mathbb{F}_2^n के सदिश स्पेस विभाजन और संबंधित प्रक्षेपी स्पेस PG(n−1,2)PG(n-1,2) में विशिष्ट अवरोधक समुच्चय से विशिष्ट रूप से जुड़ा है। ये संबंध हमें FF के Walsh स्पेक्ट्रम के बारे में कई परिणाम साबित करने में सक्षम बनाते हैं, जैसे यह साबित करना कि FF के पास 234n2^{\frac{3}{4}n} से अधिक परिमाण वाले अधिकतम एक घटक फलन हो सकता है, और द्विघात APN फलनों के मुड़े हुए घटक फलनों की संख्या के लिए पहली गैर-तुच्छ ऊपरी सीमा मिली है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या का महत्व

  1. क्रिप्टोग्राफिक अनुप्रयोग: APN फलन सममित क्रिप्टोग्राफी प्रणाली डिजाइन में मूल निर्माण खंड हैं, विशेष रूप से ब्लॉक सिफर के प्रतिस्थापन-क्रमचय नेटवर्क (SPN) में, अंतर हमलों के विरुद्ध इष्टतम प्रतिरोध प्रदान करते हैं।
  2. सैद्धांतिक चुनौती: हालांकि विषम आयाम स्थिति में द्विघात APN फलनों का परिमाण वितरण पूरी तरह से निर्धारित किया गया है (सभी गैर-तुच्छ घटकों का परिमाण 2n+122^{\frac{n+1}{2}} है), सम आयाम स्थिति अभी भी एक खुली समस्या है।
  3. मौजूदा सीमाएं:
    • सम nn के लिए, परिमाण पर वर्तमान में ज्ञात एकमात्र बाधा Walsh रूपांतरण की चतुर्थ-क्षण विशेषता से आती है
    • द्विघात APN फलनों के मुड़े हुए घटक फलनों की संख्या पर गैर-तुच्छ सीमाओं की कमी
    • Walsh स्पेक्ट्रम संरचना की गहरी समझ की कमी

अनुसंधान प्रेरणा

यह पेपर द्विघात APN फलनों और ज्यामितीय वस्तुओं (सदिश स्पेस विभाजन और अवरोधक समुच्चय) के बीच नए संबंध स्थापित करके इसके Walsh स्पेक्ट्रम के संरचनात्मक गुणों को गहराई से समझने और मजबूत बाधा शर्तें प्राप्त करने का लक्ष्य रखता है।

मूल योगदान

  1. सदिश स्पेस विभाजन संबंध स्थापित किया: द्विघात APN फलन F:F2n→F2nF: \mathbb{F}_2^n \to \mathbb{F}_2^n (nn सम) के परिमाण वितरण और F2n\mathbb{F}_2^n के सदिश स्पेस विभाजन के बीच विशिष्ट पत्राचार साबित किया।
  2. अवरोधक समुच्चय सिद्धांत निर्मित किया: गैर-तुच्छ गैर-मुड़े हुए घटक फलनों के समुच्चय NFN_F को प्रक्षेपी स्पेस PG(n−1,2)PG(n-1,2) में विशेष अवरोधक समुच्चय बनाते हैं साबित किया।
  3. नई बाधा शर्तें प्राप्त कीं:
    • साबित किया कि FF के पास 234n2^{\frac{3}{4}n} से अधिक परिमाण वाले अधिकतम एक घटक फलन हो सकता है
    • मुड़े हुए घटक फलनों की संख्या के लिए पहली गैर-तुच्छ ऊपरी सीमा स्थापित की
    • फलन के CCZ समतुल्य होने के लिए क्रमचय के आवश्यक शर्तें प्रदान कीं
  4. छोटे आयामों का पूर्ण विश्लेषण पूरा किया: आयाम 6, 8, 10 के मामलों का पूर्ण विश्लेषण किया, सभी संभावित परिमाण वितरण निर्धारित किए।

विधि विवरण

कार्य परिभाषा

द्विघात APN फलन F:F2n→F2nF: \mathbb{F}_2^n \to \mathbb{F}_2^n (nn सम) के Walsh स्पेक्ट्रम संरचना का अध्ययन करें, जहां:

  • इनपुट: द्विघात APN फलन FF
  • आउटपुट: Walsh स्पेक्ट्रम की बाधा शर्तें और संरचनात्मक गुण
  • लक्ष्य: परिमाण वितरण की संभावनाओं और सीमाओं को समझना

मूल सैद्धांतिक ढांचा

1. सदिश स्पेस विभाजन सिद्धांत

अंतर फलन परिभाषा: गैर-शून्य a∈F2na \in \mathbb{F}_2^n के लिए, DF,a(x)=F(x)+F(x+a)D_{F,a}(x) = F(x) + F(x+a) परिभाषित करें।

सदिश स्पेस निर्माण: निम्नलिखित परिभाषित करें

  • Tb={a∈F2n:Im(DF,a)=Hb}∪{0}T_b = \{a \in \mathbb{F}_2^n : \text{Im}(D_{F,a}) = H_b\} \cup \{0\}
  • Tb‾={a∈F2n:Im(DF,a)=Hb‾}\overline{T_b} = \{a \in \mathbb{F}_2^n : \text{Im}(D_{F,a}) = \overline{H_b}\}
  • Vb=Tb∪Tb‾V_b = T_b \cup \overline{T_b}

जहां Hb={x∈F2n:⟨b,x⟩=0}H_b = \{x \in \mathbb{F}_2^n : \langle b,x \rangle = 0\}।

मुख्य प्रमेय (प्रमेय 2.4): FbF_b का परिमाण 2n+dim⁡(Vb)22^{\frac{n+\dim(V_b)}{2}} है।

2. अवरोधक समुच्चय सिद्धांत

अवरोधक समुच्चय गुण: गैर-तुच्छ गैर-मुड़े हुए घटक फलनों का समुच्चय NFN_F PG(n−1,2)PG(n-1,2) में (n/2)(n/2)-स्पेस के संबंध में अवरोधक समुच्चय बनाता है, और प्रत्येक (n/2)(n/2)-स्पेस के साथ प्रतिच्छेदन का आकार विषम है।

मुख्य परिणाम: Govaerts-Storme प्रमेय को न्यूनतम गैर-तुच्छ अवरोधक समुच्चय के आकार के बारे में लागू करके, मुड़े हुए घटक फलनों की संख्या पर ऊपरी सीमा प्राप्त करें।

तकनीकी नवाचार बिंदु

  1. ज्यामितीकरण विधि: पहली बार द्विघात APN फलनों की Walsh स्पेक्ट्रम समस्या को सदिश स्पेस विभाजन और अवरोधक समुच्चय की ज्यामितीय समस्या में परिवर्तित किया।
  2. संरचनात्मक विशेषता: dim⁡(Vb)\dim(V_b) के माध्यम से सीधे घटक फलन FbF_b का परिमाण निर्धारित करके, बीजगणितीय संरचना और आवृत्ति गुणों के बीच सीधा संबंध स्थापित किया।
  3. अंतःविषय अनुप्रयोग: परिमित ज्यामिति में सदिश स्पेस विभाजन और अवरोधक समुच्चय के गहन सिद्धांत को कुशलतापूर्वक लागू किया।

प्रायोगिक सेटअप

सैद्धांतिक सत्यापन विधि

यह पेपर मुख्य रूप से सैद्धांतिक अनुसंधान है, निम्नलिखित तरीकों से परिणामों को सत्यापित करता है:

  1. छोटे आयामों का पूर्ण विश्लेषण:
    • आयाम 6: सभी संभावित सदिश स्पेस विभाजन प्रकारों को सत्यापित किया कि वे ज्ञात द्विघात APN फलनों के अनुरूप हैं
    • आयाम 8: 18 संभावित परिमाण वितरण निर्धारित किए
    • आयाम 10: सभी सैद्धांतिक रूप से संभावित मामलों का विश्लेषण किया
  2. ज्ञात फलनों का सत्यापन:
    • शास्त्रीय Walsh स्पेक्ट्रम फलनों का सत्यापन
    • अधिकतम रैखिकता फलनों का विश्लेषण
    • x3x^3 फलन के अवरोधक समुच्चय गुणों का सत्यापन

कम्प्यूटेशनल उपकरण

पेपर कम्प्यूटर-सहायक सत्यापन का उपयोग करता है:

  • छोटे आयामों में सभी संभावित सदिश स्पेस विभाजनों की गणना करना
  • सैद्धांतिक परिणामों और ज्ञात APN फलनों की सामंजस्यता को सत्यापित करना

प्रायोगिक परिणाम

मुख्य सैद्धांतिक परिणाम

1. परिमाण बाधा (प्रमेय 2.10)

परिणाम: मान लीजिए nn सम है, F:F2n→F2nF: \mathbb{F}_2^n \to \mathbb{F}_2^n द्विघात APN फलन है, रैखिकता L(F)=2n+l2L(F) = 2^{\frac{n+l}{2}} और l>n/2l > n/2, तब:

  • FF के पास परिमाण 2n+l22^{\frac{n+l}{2}} वाला बिल्कुल एक घटक फलन है
  • सभी अन्य घटकों का परिमाण अधिकतम 22n−l22^{\frac{2n-l}{2}} है
  • विशेष रूप से, किसी भी द्विघात APN फलन के पास 23n42^{\frac{3n}{4}} से अधिक परिमाण वाले अधिकतम एक घटक फलन हो सकता है

2. मुड़े हुए घटक फलनों की ऊपरी सीमा (प्रमेय 3.9)

परिणाम: मान लीजिए n≥6n \geq 6 सम है, F:F2n→F2nF: \mathbb{F}_2^n \to \mathbb{F}_2^n द्विघात APN फलन है, तब: ∣NF∣≥2n/2+2n/2−2+2n/2−3−1|N_F| \geq 2^{n/2} + 2^{n/2-2} + 2^{n/2-3} - 1 जहां समानता केवल n=8n=8 होने पर संभव है।

3. आयाम 8 का पूर्ण वर्गीकरण (प्रमेय 4.5)

F:F28→F28F: \mathbb{F}_2^8 \to \mathbb{F}_2^8 के द्विघात APN फलनों के लिए, संभावित परिमाण वितरण हैं:

  • [0190,264,61][0^{190}, 2^{64}, 6^1]
  • [0238−4i,25i,417−i][0^{238-4i}, 2^{5i}, 4^{17-i}], जहां 1≤i≤171 \leq i \leq 17

विलोपन विश्लेषण

1. सीमा तुलना (प्रस्ताव 4.4)

∣NF∣|N_F| की तीन अलग-अलग निचली सीमाओं की तुलना:

  • सदिश स्पेस विभाजन सीमा: k<n/2k < n/2 होने पर सबसे मजबूत
  • अवरोधक समुच्चय सीमा: k=n/2k = n/2 होने पर सबसे मजबूत
  • आयाम सीमा: k>n/2k > n/2 होने पर सबसे मजबूत

2. समतुल्यता विश्लेषण

EA समतुल्यता के तहत साबित किया:

  • सदिश स्पेस विभाजन समतुल्यता को संरक्षित करते हैं (प्रमेय 5.2)
  • अवरोधक समुच्चय समतुल्यता को संरक्षित करते हैं (प्रमेय 5.1)

महत्वपूर्ण निष्कर्ष

  1. संरचनात्मक बाधाएं: द्विघात APN फलनों का Walsh स्पेक्ट्रम कठोर ज्यामितीय बाधाओं के अधीन है, यह मनमाना नहीं है।
  2. आयाम प्रभाव: आयाम बढ़ने के साथ, संभावित परिमाण वितरण में तेजी से कमी आती है।
  3. CCZ समतुल्यता शर्त: यदि द्विघात फलन CCZ समतुल्य है क्रमचय के लिए, तब ∣NF∣≥3(2n/2−1)|N_F| \geq 3(2^{n/2} - 1)।

संबंधित कार्य

मुख्य अनुसंधान दिशाएं

  1. APN फलनों का वर्गीकरण: Carlet, Charpin, Zinoviev आदि का कार्य
  2. Walsh स्पेक्ट्रम सिद्धांत: चतुर्थ-क्षण विधि और रैखिकता सीमाएं
  3. सदिश स्पेस विभाजन: Heden, Bu आदि का निर्माण सिद्धांत
  4. अवरोधक समुच्चय सिद्धांत: Govaerts-Storme की इष्टतम सीमाएं

इस पेपर के लाभ

  • पहली बार Walsh स्पेक्ट्रम और ज्यामितीय वस्तुओं के बीच सीधा संबंध स्थापित किया
  • शास्त्रीय चतुर्थ-क्षण से अधिक मजबूत बाधा शर्तें प्रदान कीं
  • बीजगणितीय और ज्यामितीय दृष्टिकोण को एकीकृत किया

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. द्विघात APN फलनों के Walsh स्पेक्ट्रम में गहरी ज्यामितीय संरचना है
  2. सदिश स्पेस विभाजन और अवरोधक समुच्चय Walsh स्पेक्ट्रम को समझने के लिए शक्तिशाली उपकरण प्रदान करते हैं
  3. अधिकांश सैद्धांतिक रूप से संभावित परिमाण वितरण व्यावहारिक रूप से महसूस नहीं किए जा सकते

सीमाएं

  1. निर्माणात्मक समस्या: सिद्धांत कई संभावनाओं को बाहर करता है, लेकिन नई निर्माण विधि प्रदान नहीं करता
  2. आयाम प्रतिबंध: मुख्य परिणाम सम आयामों पर केंद्रित हैं
  3. कम्प्यूटेशनल जटिलता: उच्च आयामों में पूर्ण विश्लेषण अभी भी कठिन है

भविष्य की दिशाएं

पेपर 6 खुली समस्याएं प्रस्तावित करता है, जिनमें शामिल हैं:

  1. आयाम 8 में लापता परिमाण वितरण के उदाहरण खोजना
  2. ∣NF∣|N_F| की सीमाओं में सुधार करना
  3. अधिक अप्राप्य सदिश स्पेस विभाजन प्रकार खोजना

गहन मूल्यांकन

शक्तियां

  1. सैद्धांतिक नवाचार: Walsh स्पेक्ट्रम को समझने के लिए पूरी तरह से नया ज्यामितीय दृष्टिकोण स्थापित किया
  2. विधि व्यवस्थितता: सदिश स्पेस विभाजन और अवरोधक समुच्चय दोनों कोणों से व्यवस्थित अनुसंधान
  3. परिणाम गहनता: कई पहली गैर-तुच्छ सीमाएं प्राप्त कीं
  4. विश्लेषण पूर्णता: छोटे आयामों के मामलों का विस्तृत विश्लेषण

कमियां

  1. निर्माण की कमी: मुख्य रूप से बहिष्करण परिणाम, नई APN फलन निर्माण की कमी
  2. कम्प्यूटेशनल सत्यापन: कुछ परिणाम कम्प्यूटर सत्यापन पर निर्भर हैं, सैद्धांतिक प्रमाण पूर्ण नहीं
  3. अनुप्रयोग सीमा: मुख्य रूप से सैद्धांतिक योगदान, व्यावहारिक क्रिप्टोग्राफी अनुप्रयोग मूल्य सत्यापन के लिए प्रतीक्षा करता है

प्रभाव

  1. शैक्षणिक मूल्य: APN फलन सिद्धांत के लिए नई अनुसंधान उपकरण और दृष्टिकोण प्रदान करता है
  2. पद्धति योगदान: ज्यामितीकरण विधि अन्य क्रिप्टोग्राफी समस्याओं के अनुसंधान को प्रेरित कर सकती है
  3. खुली समस्याएं: प्रस्तावित समस्याएं बाद के अनुसंधान के लिए दिशा निर्दिष्ट करती हैं

उपयुक्त परिदृश्य

  • द्विघात APN फलनों का सैद्धांतिक विश्लेषण
  • क्रिप्टोग्राफी में S-बॉक्स डिजाइन और विश्लेषण
  • परिमित ज्यामिति का क्रिप्टोग्राफी में अनुप्रयोग अनुसंधान
  • बूलियन फलनों के Walsh स्पेक्ट्रम की संरचना अनुसंधान

संदर्भ

पेपर 25 महत्वपूर्ण संदर्भों का हवाला देता है, जो APN फलन सिद्धांत, सदिश स्पेस विभाजन, अवरोधक समुच्चय सिद्धांत आदि कई क्षेत्रों के शास्त्रीय कार्य को शामिल करता है, अंतःविषय अनुसंधान की विशेषता को प्रदर्शित करता है। मुख्य संदर्भ साहित्य में Carlet की बूलियन फलन मोनोग्राफ, अवरोधक समुच्चय पर Govaerts-Storme का कार्य, और सदिश स्पेस विभाजन पर Heden आदि का अनुसंधान शामिल है।