On the Walsh spectra of quadratic APN functions

तकनीकी सारांश: द्विघात APN फलनों के वॉल्श स्पेक्ट्रा पर

समस्या विवरण
लगभग पूर्ण गैर-रैखिकता (Almost Perfect Nonlinear - APN) फलन सममित क्रिप्टोसिस्टम में महत्वपूर्ण घटक हैं, जो विभेदात्मक हमलों (differential attacks) के विरुद्ध इष्टतम प्रतिरोध प्रदान करते हैं। इन फलनों का एक मौलिक गुण उनकी रैखिकता है, जो उनके वॉल्श स्पेक्ट्रम द्वारा निर्धारित होती है। जबकि विषम आयामों $n$ के लिए द्विघात APN फलनों का आयाम वितरण (और इस प्रकार वॉल्श स्पेक्ट्रम) पूरी तरह से अभिलक्षित है, सम $n$ का मामला काफी हद तक खुला बना हुआ है। सम $n$ के लिए ज्ञात एकमात्र सामान्य बाधा वॉल्श ट्रांसफॉर्म के चौथे क्षण (fourth moment) से प्राप्त की जाती है। यह शोध पत्र द्विघात APN फलनों $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ के संभावित वॉल्श स्पेक्ट्रा को समझने के अंतराल को संबोधित करता है, जहाँ $n$ सम है, विशेष रूप से उनके आयाम वितरणों पर मजबूत स्थितियाँ प्राप्त करने का प्रयास करता है।

कार्यप्रणाली
लेखक द्विघात APN फलनों और परिमित ज्यामिति (finite geometry) के बीच दो नवीन ज्यामितीय संबंधों को स्थापित करते हैं:

1. सदिश स्थान विभाजन (Vector Space Partitions): शोध पत्र प्रदर्शित करता है कि एक द्विघात APN फलन का आयाम वितरण परिवेशी स्थान $\mathbb{F}_2^n$ के सदिश स्थान विभाजन के साथ विशिष्ट रूप से सहसंबद्ध होता है। विशेष रूप से, $F$ के गैर-तुच्छ गैर-बेंट घटक फलन (non-trivial non-bent component functions) एक विभाजन में उप-स्थानों (subspaces) से जुड़े होते हैं जहाँ प्रत्येक उप-स्थान का आयाम सीधे संबंधित घटक फलन के आयाम से जुड़ा होता है।
2. ब्लॉकिंग सेट (Blocking Sets): गैर-तुच्छ गैर-बेंट घटकों के सेट को, $N_F$ के रूप में नामित किया गया है, $PG(n-1, 2)$में एक विशिष्ट प्रकार के ब्लॉकिंग सेट के रूप में दिखाया गया है। महत्वपूर्ण रूप से, लेखक सिद्ध करते हैं कि$N_F$का किसी भी$n/2$ आयाम वाले उप-स्थान के साथ प्रतिच्छेदन में विषम संख्या में बिंदु होने चाहिए।

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

प्रमुख योगदान और परिणाम

• सदिश स्थान विभाजन के साथ संबंध (अनुभाग II):

  • प्रमेय II.4 स्थापित करता है कि यदि एक घटक फलन $F_b$ का आयाम $2^{(n+k)/2}$ है, तो यह $\mathbb{F}_2^n$ के एक सदिश स्थान विभाजन में आयाम $k$ के एक उप-स्थान के अनुरूप होता है।
  • यह संबंध विभाजन सिद्धांत से पैकिंग स्थितियों और आयाम सीमाओं को लागू करने की अनुमति देता है।
  • प्रमेय II.10: एक द्विघात APN फलन में अधिकतम एक घटक फलन हो सकता जिसका आयाम $2^{3n/4}$ से अधिक हो। यदि ऐसा कोई घटक मौजूद है, तो अन्य सभी का आयाम $2^{(2n-l)/2}$ से कम होना चाहिए, जहाँ $l$ अधिकतम आयाम का घातांक है।
  • प्रस्ताव II.14–II.16: रैखिकता और विशिष्ट आयामों की उपस्थिति के आधार पर गैर-बेंट घटकों की संख्या ($|N_F|$) पर नए निम्नतम मान (lower bounds) प्राप्त किए गए हैं।

• ब्लॉकिंग सेट के साथ संबंध (अनुभाग III):

  • उपप्रमेय III.3: सेट $N_F$, $(n/2)$-स्थानों के संबंध में $PG(n-1, 2)$में एक ब्लॉकिंग सेट है, जिसमें अतिरिक्त गुण यह है कि प्रत्येक ऐसा स्थान$N_F$ को विषम संख्या में बिंदुओं के साथ प्रतिच्छेद करता है।
  • प्रमेय III.9: यह द्विघात APN फलन के बेंट घटक फलनों की संख्या पर पहला गैर-तुच्छ, सामान्य ऊपरी सीमा (upper bound) है। विशेष रूप से, $n \ge 6$ के लिए, गैर-बेंट घटकों की संख्या $|N_F| \ge 2^{n/2} + 2^{n/2-2} + 2^{n/2-3} - 1$ है। समानता केवल तभी संभव है जब $n=8$ हो। फलस्वरूप, बेंट घटकों की संख्या $2^n - 2^{n/2} - 2^{n/2-2} - 2^{n/2-3}$ से अधिक नहीं हो सकती।

• संश्लेषण और आयामी विश्लेषण (अनुभाग IV):

  • विभाजन और ब्लॉकिंग सेट बाधाओं को जोड़कर, लेखक कई सैद्धांतिक रूप से संभावित आयाम वितरणों को हटा देते हैं।
  • प्रमेय IV.1: प्रकार $[(n/2)^{2^{n/2+1}}]$ के सदिश स्थान विभाजन (एक $(n/2)$-स्प्रेड) किसी भी द्विघात APN फलन के अनुरूप नहीं होते हैं।
  • प्रमेय IV.5: $n=8$ के लिए, शोध पत्र आयाम वितरणों को एक विशिष्ट सूची तक सीमित करता है (तुच्छ विभाजन और 4-स्प्रेड को छोड़कर), जिससे संभावित विस्तारित वॉल्श स्पेक्ट्रा के प्रकारों की संख्या घटकर अधिकतम 18 विशिष्ट प्रकार रह जाती है।
  • प्रस्ताव IV.4: शोध पत्र विभिन्न पैरामीटर श्रेणियों में $|N_F|$ के प्राप्त निम्नतम मानों की मजबूती की तुलना करता है, जिससे यह पहचान की जाती है कि फलन की रैखिकता के आधार पर कौन सा बाउंड प्रभावी है।

• तुल्यता और क्रमपरिवर्तन (अनुभाग V):

  • यह शोध पत्र विश्लेषण करता है कि ये संरचनाएं EA-तुल्यता और CCZ-तुल्यता के तहत कैसे व्यवहार करती हैं।
  • उपप्रमेय V.6: यदि एक द्विघात APN फलन एक क्रमपरिवर्तन (permutation) के CCZ-तुल्य है, तो इसमें कम गैर-बेंट घटक नहीं हो सकते; विशेष रूप से, $|N_F| \ge 3(2^{n/2}-1)$, और $N_F$ को एक 3-गुना ब्लॉकिंग सेट होना चाहिए।

महत्व और दावे
शोध पत्र का दावा है कि यह प्रसिद्ध चौथे-क्षण (fourth-moment) बाउंड के बाद द्विघात APN फलनों के वॉल्श स्पेक्ट्रा पर प्रदान किए गए पहले सामान्य प्रतिबंधों में से एक है। द्विघात APN फलनों के बीजगणितीय गुणों को सदिश स्थान विभाजन और ब्लॉकिंग सेट जैसी संयोजी संरचनाओं से जोड़कर, लेखक आयाम वितरणों पर मजबूत बाधाएं प्राप्त करते हैं।

लेखक स्पष्ट रूप से कहते हैं कि उनके परिणाम:

1. यह सिद्ध करते हैं कि एक द्विघात APN फलन में अधिकतम एक घटक हो सकता जिसका आयाम $2^{3n/4}$ से अधिक हो।
2. बेंट घटकों की संख्या पर पहला गैर-तुच्छ ऊपरी बाउंड प्रदान करते हैं।
3. यह निर्धारित करने के लिए स्थितियाँ प्रदान करते हैं कि क्या कोई फलन अपने बेंट घटकों की संख्या के आधार पर एक क्रमपरवर्तन के CCZ-तुल्य है।
4. छोटे सम आयामों (विशेष रूप से $n=6, 8, 10$) के लिए सभी संभावित आयाम वितरणों को व्यवस्थित रूप से सूचीबद्ध करते हैं, यह उजागर करते हुए कि कौन से साकार (realized) हैं और कौन से खुले प्रश्न बने हुए हैं।

शोध पत्र खुले प्रश्नों की सूची के साथ समाप्त होता है, जिसमें आयाम 8 में विशिष्ट आयाम वितरणों वाले APN फलनों का अस्तित्व और गैर-शास्त्रीय वॉल्श स्पेक्ट्रा वाले द्विघात APN फलनों के अनंत परिवारों की खोज शामिल है। लेखक एक विनम्र स्वर बनाए रखते हैं, यह नोट करते हुए कि हालांकि उन्होंने कई संभावनाओं को बाहर कर दिया है, द्विघात APN फलनों के पूर्ण वर्गीकरण का कार्य अभी भी एक खुला विषय बना हुआ है।