🔢 mathematics

Quadratic APN Functions in Dimension 8 via Gröbner Basis Search in a Self-Equivalence Subspace

यह शोध पत्र 8 आयामों में 566 द्विघात (quadratic) APN फलनों की खोज करने के लिए एक विशिष्ट 40-आयामी स्व-तुल्यता उपसमष्टि (self-equivalence subspace) के भीतर रैंडम सैंपलिंग और ग्रोबनर बेसिस एन्यूमरेशन (Gröbner basis enumeration) को संयोजित करने वाले एक हाइब्रिड कम्प्यूटेशनल सर्च को प्रस्तुत करता है, जिसमें तीन पूर्व अज्ञात CCZ-तुल्यता वर्ग भी शामिल हैं जिन्हें पिछले व्यापक डेटाबेस द्वारा छोड़ दिया गया था।

मूल लेखक: Oleksandr Kuznetsov

प्रकाशित 2026-06-11

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Oleksandr Kuznetsov

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

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

यह शोध पत्र इन दुर्लभ लॉकपिक्स को खोजने के लिए एक चतुर नई रणनीति का वर्णन करता है, जिसमें एक "टॉर्च" और एक "चुंबक" का उपयोग करके गोदाम के एक विशिष्ट, छोटे हिस्से में नेविगेट किया गया है जिसे पहले खाली माना जाता था।

यहाँ उनकी खोज का सरल उपमाओं (analogies) का उपयोग करके विवरण दिया गया है:

1. समस्या: ब्रह्मांडीय घास के ढेर में सुई (The Needle in the Cosmic Haystack)

क्रिप्टोग्राफी (गुप्त कोड का विज्ञान) की दुनिया में, ये "लॉकपिक्स" विशेष गणितीय उपकरण हैं जिनका उपयोग डेटा को सुरक्षित रूप से उलझाने (scramble) के लिए किया जाता है ताकि इसे हैकर्स द्वारा क्रैक न किया जा सके। लंबे समय से, गणितज्ञ डेटा के एक विशिष्ट आकार (8 बिट्स) के लिए नए, बेहतर लॉकपिक्स खोजने की कोशिश कर रहे हैं।

पुराना तरीका: पिछले शोधकर्ताओं ने इन लॉकपिक्स को खोजने के लिए संभावनाओं का एक विशाल पेड़ (tree) बनाने और उसकी हर शाखा की जांच करने का प्रयास किया। उन्होंने गोदाम के एक विशिष्ट, व्यवस्थित खंड (एक "सेल्फ-इक्विवेलेंस सबस्पेस") को देखा और निष्कर्ष निकाला, "यहाँ कुछ भी नहीं है।" उन्होंने देखना बंद कर दिया।
वास्तविकता: इस शोध पत्र के लेखक कहते हैं, "रुकिए। वह खंड खाली नहीं है। आपने उन वस्तुओं को केवल इसलिए मिस कर दिया क्योंकि आपकी 'पेड़ पर चढ़ने वाली' विधि बहुत कठोर थी।"

2. नई रणनीति: टॉर्च और चुंबक (The Flashlight and the Magnet)

लेखकों ने इन छिपे हुए लॉकपिक्स को खोजने के लिए दो-चरणीय प्रक्रिया विकसित की:

चरण 1: टॉर्च (एक संरचित क्षेत्र में रैंडम सैंपलिंग)
पूरे ब्रह्मांड को खोजने के बजाय, उन्होंने गोदाम के भीतर एक विशिष्ट, व्यवस्थित 40-आयामी (40-dimensional) "कमरे" पर ध्यान केंद्रित किया। उन्होंने महसूस किया कि हालांकि यह कमरा पूरे गोदाम की तुलना में बहुत छोटा है, लेकिन इस विशिष्ट कमरे के भीतर "लॉकपिक्स" कहीं और की तुलना में बहुत अधिक सामान्य हैं।
उन्होंने इस कमरे में बेतरतीब ढंग से घूमने के लिए एक विशेष मानचित्र (जिसे RREF पैरामीट्राइजेशन कहा जाता है) का उपयोग किया। उन्होंने सैकड़ों "सेंटर" लॉकपिक्स खोजे जो वहीं पड़े थे, बस खोजे जाने की प्रतीक्षा कर रहे थे।
चरण 2: चुंबक (ग्रोबनर बेसिस सर्च)
यही असली जादू है। एक बार जब उन्हें एक "सेंटर" लॉकपिक मिल गया, तो वे केवल रुके नहीं। उन्होंने उस केंद्र के आसपास के तत्काल पड़ोस को स्कैन करने के लिए एक शक्तिशाली गणितीय उपकरण जिसका नाम ग्रोबनर बेसिस (एक सुपर-मैग्नेट की तरह सोचें) का उपयोग किया।
यहाँ आश्चर्यजनक बात यह है: चुंबक ने न केवल उसी कमरे में अधिक लॉकपिक्स खोजे। इसने उन नए लॉकपिक्स को भी बाहर निकाला जो पड़ोसी कमरों में छिपे हुए थे, जो उनके शुरुआती व्यवस्थित खंड के बाहर थे।
- उपमा: कल्पना कीजिए कि आपको एक विशिष्ट दराज में एक दुर्लभ सिक्का मिलता है। आप दराज को स्कैन करने के लिए चुंबक का उपयोग करते हैं, और अचानक, चुंबक तीन अन्य दुर्लभ सिक्कों को खींच लेता है जो दराज के नीचे चिपके हुए थे, भले ही वे सिक्के तकनीकी रूप रूप से एक अलग दराज के belonged (संबंधी) हों।

3. खोज: नए खजाने वर्ग (New Treasure Classes)

इस पद्धति का उपयोग करते हुए, टीम ने 566 नए लॉकपिक्स खोजे। उन्होंने उन्हें छह समूहों (वर्गों) में वर्गीकृत किया:

दो समूह "ज्ञात" प्रकार के थे (जैसे प्रसिद्ध गोल्ड फंक्शन्स)। इन्होंने "गेटवे" के रूप में कार्य किया। जब लेखकों ने इन ज्ञात प्रकारों को अपने शुरुआती बिंदु के रूप में उपयोग किया, तो "चुंबक" ने नए, अज्ञात प्रकारों को बाहर निकाला।
चार समूह पूरी तरह से नए थे। वे पहले कभी नहीं देखे गए थे।
- एक समूह (वर्ग A) सीधे व्यवस्थित कमरे के अंदर पाया गया।
- तीन समूह (वर्ग B, C, और D) कमरे के बाहर पाए गए, लेकिन वे केवल तभी खोजे जा सके जब "चुंबक" को कमरे के भीतर मौजूद ज्ञात "गेटवे" लॉकपिक्स से जोड़ा गया था।

4. प्रमाण: यह क्यों मायने रखता है

लेखकों ने केवल अनुमान नहीं लगाया कि ये नए हैं। उन्होंने अपने निष्कर्षों की जांच करने के लिए एक "फिंगरप्रिंट" प्रणाली (जिसे ऑर्थो-डेरिवेटिव इनवेरिएंट कहा जाता है) का उपयोग किया, जो दुनिया के सबसे बड़े डेटाबेस के विरुद्ध काम करती है, जिसमें लाखों ज्ञात लॉकपिक्स शामिल हैं।

परिणाम: उनके चार नए समूहों का मौजूदा लाखों प्रविष्टियों में से किसी से भी मिलान नहीं हुआ। वे वास्तव में नए हैं।
"खाली कमरा" का मिथक: उन्होंने साबित किया कि पिछले शोधकर्ता इस बारे में गलत थे कि कमरा खाली है। कमरा खाली नहीं था; पिछला खोज तरीका बस उन वस्तुओं को देख नहीं पा रहा था क्योंकि वह उन्हें एक-एक करके देख रहा था, जबकि यह नई विधि एक साथ पूरे पड़ोस को देखती है।

5. बड़ा सबक: "गेटवे" घटना (The "Gateway" Phenomenon)

सबसे महत्वपूर्ण बात जो मिली वह केवल नए लॉकपिक्स नहीं हैं, बल्कि यह है कि उन्हें कैसे खोजा गया।
लेखकों ने पाया कि आप किसी भी यादृच्छिक (random) लॉकपिक को चुनकर नए लॉकपिक्स मिलने की उम्मीद नहीं कर सकते। आपको एक बहुत ही विशिष्ट, संरचित प्रकार (व्यवस्थित कमरे के भीतर "गोल्ड" फंक्शन्स) के साथ शुरुआत करनी होगी।

उपमा: यदि आप गोदाम में किसी यादृच्छिक कचरे पर चुंबक का उपयोग करने की कोशिश करते हैं, तो कुछ नहीं होता है। लेकिन यदि आप एक विशिष्ट "गेटवे" वस्तु पर चुंबक का उपयोग करते हैं, तो यह नए छिपे हुए संसार को प्रकट करता है जो पहले अदृश्य था।

सारांश

यह शोध पत्र उन छिपे हुए गणितीय खजानों को खोजने के बारे में है जिन्हें हर कोई खाली मानता था। एक शुरुआती बिंदु खोजने के लिए एक स्मार्ट मानचित्र का उपयोग करके और परिवेश को स्कैन करने के लिए एक शक्तिशाली गणितीय "चुंबक" का उपयोग करके, लेखकों ने 566 नए क्रिप्टोग्राफिक उपकरण खोजे, जिनमें चार पूरी तरह से नए परिवार शामिल हैं जिन्हें पहले कभी नहीं देखा गया था। उन्होंने साबित किया कि कभी-कभी, नए को खोजने के लिए, आपको ज्ञात के कंधों पर खड़ा होना पड़ता है, लेकिन आपको यह देखने के लिए सही उपकरणों की आवश्यकता होती है कि किनारे के ठीक परे क्या छिपा है।

तकनीकी सारांश: स्व-तुल्यता उप-स्थान (Self-Equivalence Subspace) में ग्रोबनर बेसिस खोज के माध्यम से आयाम 8 में द्विघाती APN फलन

समस्या विवरण
$\mathbb{F}_{2^n}$ पर लगभग पूर्ण गैर-रैखिक (Almost Perfect Nonlinear - APN) फलनों का CCZ-तुल्यता (CCZ-equivalence) तक वर्गीकरण, विशेष रूप से $n=8$ के लिए, क्रिप्टोग्राफी में एक केंद्रीय समस्या है। जबकि $n \leq 6$ के लिए वर्गीकरण पूर्ण है, $n=8$ के लिए यह आंशिक है। द्विघाती APN फलनों के लिए खोज क्षेत्र विशाल है ( $2^{224}$ संभावित गुणांक सदिश), जिससे अनुमानित APN घनत्व $\approx 2^{-n}$ के कारण वैश्विक यादृच्छिक खोज (global random search) अव्यवहार्य हो जाता है। पिछले व्यवस्थित प्रयासों, जैसे कि बीयरले, ब्रिंकमैन और लींडर (BBL2021) द्वारा की गई पुनरावर्ती ट्री सर्च (recursive tree search) ने एक रैखिक ऑटोमॉर्फिज्म $A$ (क्लास इंडेक्स 22) से जुड़े 40-आयामी स्व-तुल्यता उप-स्थान $V_A$ द्वारा परिभाषित संरचित बीजगणितीय उप-स्थानों का अन्वेषण किया। BBL2021 ने रिपोर्ट किया कि इस $V_A$ उप-स्थान के भीतर शून्य APN फलन मिले। यह शोध पत्र जांच करता है कि क्या इस उप-स्थान में वास्तव में कोई APN फलन नहीं है या पिछला खोज तरीका उन्हें खोजने में विफल रहा।

कार्यप्रणाली
लेखक एक दो-चरणीय कम्प्यूटेशनल पाइपलाइन प्रस्तावित करते हैं जो पिछले ट्री सर्च की तुलना में $V_A$ का अधिक प्रभावी ढंग से अन्वेषण करने के लिए यादृच्छिक नमूनाकरण (random sampling) को बीजगणितीय गणना (algebraic enumeration) के साथ जोड़ती है।

चरण 1: RREF पैरामीट्राइजेशन के माध्यम से यादृच्छिक नमूनाकरण
लेखक 40-आयामी उप-स्थान $V_A = \{F : F \circ A = A \circ F\}$ का एक स्पष्ट रिड्यूस्ड रो एचेलोन फॉर्म (RREF) पैरामीट्राइजेशन का निर्माण करते हैं। यह खोज क्षेत्र को $2^{224}$ से घटाकर $2^{40}$ कर देता है। इस उप-स्थान के भीतर, APN फलनों का अनुभवजन्य घनत्व लगभग $10^{-4}$ पाया गया है (लगभग 11,000 यादृच्छिक नमूनों में 1 APN फलन), जिससे लक्षित नमूनाकरण संभव हो जाता है। लेखक "APN केंद्रों" (वे फलन जो $V_A$ में APN हैं) की पहचान करने के लिए यादृच्छिक नमूनाकरण करते हैं।
चरण 2: ग्रोबनर बेसिस स्लाइस गणना
प्रत्येक APN केंद्र (जो चरण 1 में मिला) के लिए, लेखक एक 24-आयामी एफाइन हाइपरप्लेन (एक "NL=4 स्लाइस") को परिभाषित करते हैं जो उस केंद्र से होकर गुजरता है। यह 224 के बीजगणितीय सामान्य रूप (ANF) गुणांकों में से 200 गुणांकों (विशेष रूप से उन सूचकांकों के संगत जिनमें $p \leq 4$ है) को केंद्र के मानों पर स्थिर करके प्राप्त किया जाता है, जिससे 24 गुणांक अज्ञात रह जाते हैं।
APN की स्थिति को 255 गैर-शून्य अंतरों के लिए बूलियन रिंग पर बहुपदीय समीकरणों के एक निकाय के रूप में एनकोड किया जाता है। लेखक इस निकाय के लिए ग्रोबनर बेसिस की गणना करने के लिए मैग्मा (Magma) कंप्यूटर अलजेब्रा सिस्टम का उपयोग करते हैं।

यदि निकाय अप्राप्य (infeasible) है, तो स्लाइस में अन्य कोई APN फलन नहीं है।
यदि निकाय के समाधान हैं, तो ग्रोबनर बेसिस गणना उस विशिष्ट 24-आयामी हाइपरप्लेन के भीतर सभी APN फलनों को खोज लेती है।
महत्वपूर्ण रूप से, जबकि केंद्र $V_A$ में होने की गारंटी है, ग्रोबनर बेसिस द्वारा खोजे गए समाधान $V_A$ के प्रति प्रतिबंधित नहीं हैं; वे स्व-तुल्यता उप-स्थान के बाहर हो सकते हैं।

वर्गीकरण और सत्यापन
पाए गए फलनों को ऑर्थो-डेरिवेटिव इनवेरिएंट $\sigma(F)$ का उपयोग करके वर्गीकृत किया जाता है, जो योशिआरा के प्रमेय और कैंटेऑट एट अल. के परिणामों द्वारा द्विघाती APN फलनों के लिए एक पूर्ण CCZ-इनवेरिएंट के रूप में सिद्ध है। लेखक अपने हस्ताक्षरों (signatures) की तुलना तीन प्रमुख डेटाबेस के साथ करते हैं: BBL2021 (पूर्व-2020 संकलन), बीयरले एट अल. 2025 डेटाबेस (जिसमें $\approx 3.8$ मिलियन फलन हैं), और शास्त्रीय गोल्ड (Gold) फलन।

मुख्य परिणाम
लेखकों ने 428 विशिष्ट 24-आयामी स्लाइसों (कुल $2^{16}$ संभावित स्लाइसों का 0.65%) पर पाइपलाइन का निष्पादन किया।

नए वर्गों की खोज: खोज ने छह CCZ-तुल्यता वर्गों में गिरने वाले 566 अद्वितीय द्विघाती APN फलन दिए।
- चार नए वर्ग (A, B, C, D): ये 500 फलन (वर्ग A में 362, B में 72, C में 36, D में 30) Beierle 2025 डेटाबेस, BBL2021 पूर्व-2020 डेटाबेस, या शास्त्रीय गोल्ड परिवारों में मौजूद नहीं हैं।
- दो ज्ञात वर्ग (E, F): ये गोल्ड फलनों $x^3$ और $x^9$ (और उनके फ्रोबेनियस ऑर्बिट्स) के अनुरूप हैं, जो सत्यापन के लिए नियंत्रण (controls) के रूप में कार्य करते हैं।
संरचनात्मक निष्कर्ष:
- उप-स्थान सदस्यता: एक सदस्यता परीक्षण ( $F \circ A = A \circ F$ ) ने खुलासा किया कि वर्ग A, E, और F पूरी तरह से $V_A$ के भीतर स्थित हैं। हालांकि, वर्ग B, C, और D पूरी तरह से $V_A$ के बाहर स्थित हैं।
- "गेटवे" घटना: नए बाहरी वर्गों (B, C, D) के 138 फलन विशेष रूप से उन गोल्ड फलनों (वर्ग E और F) पर केंद्रित स्लाइसों में पाए गए जो $V_A$ के भीतर रहते हैं। वर्ग A के फलनों पर केंद्रित स्लाइसों ने $V_A$ के बाहर कोई पड़ोसी नहीं दिया।
- वैकल्पिक सीड (Seed) की विफलता: Beierle 2025 डेटाबेस से 532 APN फलनों का उपयोग करके किए गए तुलनात्मक प्रयोगों (जो $V_A$ के बाहर हैं) के परिणामस्वरूप शून्य APN पड़ोसी मिले। यह सुझाव देता है कि ग्रोबनर बेसिस स्लाइसिंग के माध्यम से नए वर्गों को खोजने की "गेटवे" क्षमता, सभी APN फलनों का एक जेनेरिक गुण नहीं है, बल्कि यह स्व-तुल्यता उप-स्थान के भीतर रहने वाले फलनों के प्रति विशिष्ट है।

महत्व और दावे
यह शोध पत्र APN फलन वर्गीकरण के क्षेत्र में निम्नलिखित महत्वपूर्ण योगदानों का दावा करता है:

पिछले परिणामों का सुधार: लेखक यह प्रदर्शित करते हैं कि स्व-तुल्यता उप-स्थान $V_A$ (क्लास इंडेक्स 22), जिसे BBL2021 द्वारा शून्य APN फलनों वाला बताया गया था, वास्तव में कम से कम चार CCZ-वर्गों के द्विघाती APN फलनों को समाहित करता है। BBL2021 की ट्री सर्च की विफलता का कारण इसकी ब्रांच-प्रूनिंग रणनीति को माना गया है, जो इस संरचित उप-स्थान में वैध समाधानों को हटा सकती थी, जबकि ग्रोबनर बेसिस दृष्टिकोण प्रत्येक स्लाइस के भीतर पूर्ण गणना करता है।
नए फलनों की खोज: यह शोध $\approx 3.8$ मिलियन फलनों के सबसे बड़े ज्ञात डेटाबेस से अलग, $n=8$ के लिए चार नए CCZ-वर्गों के अस्तित्व का कठोर प्रमाण (ऑर्थो-डेरिवेटिव इनवेरिएंट के माध्यम से) प्रदान करता है।
पद्धतिगत नवाचार: यह "GB-नेविगेशन" तंत्र पेश करता है। यह तर्क देता है कि जबकि वैश्विक खोज असंभव है, एक "सीड" फलन खोजने के लिए उच्च APN घनत्व वाले संरचित उप-स्थानों का लाभ उठाया जा सकता है। ग्रोबनर बेसिस चरण फिर एक स्थानीय गणक (enumerator) के रूप में कार्य करता है, जो नए वर्गों को खोजने के लिए उप-स्थान से बाहर कदम रखने में सक्षम है। लेखक इस बात पर जोर देते हैं कि यह तंत्र जेनेरिक नहीं है; यह स्व-तुल्यता उप-स्थान की विशिष्ट बीजगणितीय संरचना पर निर्भर करता है, जैसा कि गैर-उप-स्थान वाले फलनों के उत्पादक सीड के रूप में विफल होने से सिद्ध होता है।
ऑर्थो-डेरिवेटिव की पूर्णता: यह कार्य द्विघाती फलनों के लिए एक सटीक CCZ-इनवेरिएंट के रूप में ऑर्थो-डेरिवेटिव सिग्नेचर की उपयोगिता को सुदृढ़ करता है, जिससे थकाऊ युग्म-परीक्षण (pairwise testing) के बिना कठोर वर्गीकरण संभव होता है।

लेखक निष्कर्ष निकालते हैं कि उनका दृष्टिकोण BBL2021 के अन्य क्लास इंडेक्सों का अन्वेषण करके और ग्रोबनर बेसिस स्लाइसिंग तकनीक का उपयोग करके APN परिदृश्य में नेविगेट करके, द्विघाती APN फलनों के वर्गीकरण को विस्तारित करने के लिए एक व्यवस्थित कार्यक्रम प्रदान करता है।