तकनीकी सारांश: फूरियर विश्लेषण के माध्यम से परम्यूटेशन के XOR की क्वांटम सुरक्षा

1. समस्या विवरण

यह शोध पत्र XOR of Permutations (XoP) निर्माण की क्वांटम सुरक्षा को संबोधित करता है, जो स्वतंत्र रैंडम परम्यूटेशन से बना एक मौलिक छद्म यादृच्छिक फलन (PRF) है। विशेष रूप से, इस निर्माण को इस प्रकार परिभाषित किया गया है:
$$\text{XoP}[r](x) := P_1(x) \oplus \cdots \oplus P_r(x)$$
जहाँ $P_1, \dots, P_r$ $n$-बिट स्ट्रिंग्स पर स्वतंत्र रैंडम परम्यूटेशन हैं।

जबकि क्लासिकल एडवर्सरीज (classical adversaries) के विरुद्ध XoP की सुरक्षा अच्छी तरह से स्थापित है (बर्थडे बाउंड से परे सुरक्षा प्राप्त करना), क्वांटम एडवर्सरीज (जो सुपरपोजिशन क्वेरी करने में सक्षम हैं, Q2 मॉडल) के विरुद्ध इसकी सुरक्षा एक खुला प्रश्न बना हुआ है। परम्यूटेशन-आधारित क्वांटम PRFs के लिए मौजूदा परिणाम क्वांटम कोलिजन-फाइंडिंग हमलों (जैसे Brassard-Høyer-Tapp) द्वारा निर्धारित $q \approx 2^{n/3}$ की "बर्थडे बाउंड" तक ही सीमित हैं। लेखक यह निर्धारित करने का लक्ष्य रखते हैं कि क्या XoP इस बाउंड से काफी आगे जाकर सुरक्षा प्राप्त कर सकता है।

2. कार्यप्रणाली

लेखक कार्यात्मकों (functionals) के स्थान पर लागू होने वाले फूरियर-एनालिटिक वेरिएंट ऑफ द पॉलिनोमियल मेथड का उपयोग करते हैं। यह दृष्टिकोण हाल के क्लासिकल तकनीकों को क्वांटम सेटिंग में अनुकूलित करता है जहाँ कोहेरेंट क्वेरीज़ (coherent queries) के कारण पारंपरिक "रिस्पॉन्स ट्रांसक्रिप्ट" का अस्तित्व नहीं होता है।

मुख्य ढांचा (Core Framework)

1. कार्यात्मक प्रतिनिधित्व (Functional Representation): एक $q$-क्वेरी क्वांटम एल्गोरि $A$ का एक वितरण $D$ (रैंडम फंक्शन्स $F$ के सापेक्ष) के विरुद्ध डिस्टिंग्विशिंग एडवांटेज को एक इनर प्रोडक्ट के रूप में व्यक्त किया जाता है:
   $$\text{Adv} = \langle \mu_D - 1, P_A \rangle$$
   जहाँ $\mu_D$ वितरण $D$ का डेंसिटी फंक्शन है और $P_A(f) = \Pr[A^{O_f} \to 1]$ एक कार्यात्मक है जो एल्गोरिदम की स्वीकृति प्रायिकता (acceptance probability) को दर्शाता है।
2. फूरियर एक्सपेंशन (Fourier Expansion): यह दिखाया गया है कि कार्यात्मक $P_A$ का फूरियर डिग्री अधिकतम $2q$ है। डेंसिटी फंक्शन $\mu_D - 1$ को डिग्री $d$ के फूरियर घटकों में विभाजित किया जाता है। एडवांटेज को इन घटकों के इनर प्रोडक्ट्स के योग द्वारा सीमित किया जाता है:
   $$\text{Adv} \leq \sum_{d=1}^{2q} |\langle \mu_D^{=d}, P_A^{=d} \rangle|$$
3. घटक विश्लेषण (Component Analysis): लेखक XoP वितरण के फूरियर घटकों $\mu_{\text{XoP}}^{=d}$ के नॉर्म्स का विश्लेषण करते हैं।
   • उच्च डिग्री ($d \geq 5$): वे रैंडम परम्यूटेशन के गुणों से प्राप्त कॉम्बिनेटोरियल तर्क और रिकर्सिव संबंधों का उपयोग करके इन घटकों के $\ell_2$-नॉर्म्स को सीधे सीमित करते हैं।
   • निम्न डिग्री ($d \in \{2, 3, 4, 6\}$): इन पदों के लिए सीधा नॉर्म बाउंडिंग अपर्याप्त है। इसके बजाय, लेखक इन फूरियर घटकों को अन्य समस्याओं के लिए डिस्टिंग्विशिंग एडवांटेज के रूप में पुनर्व्याख्या करते हैं, जो विशेष रूप से "प्लांटेड कोलिजन" (जैसे कि एक रैंडम फंक्शन जिसे $f(x) = f(x')$ के लिए कंडीशन किया गया हो) वाले वितरणों से संबंधित हैं।

मुख्य तकनीकी उपकरण (Key Technical Tools)

• प्लांटेड कोलिजन डिस्ट्रीब्यूशन्स (Planted Collision Distributions): डिग्री-2 घटक को एक यूनिफॉर्म रैंडम फंक्शन और एक प्लांटेड कोलिजन वाले फंक्शन के बीच के अंतर के समान दिखाया गया है। इस उप-समस्या की सुरक्षा का विश्लेषण Zhandry के स्मॉल-रेंज डिस्ट्रीब्यूशन इंडिस्टिंग्विशेबिलिटी परिणामों का उपयोग करके किया गया है।
• कंप्रेस्ड ओरकल (Compressed Oracle): प्लांटेड कोलिजन समस्या के लिए अधिक सटीक बाउंड (विशेष रूप से $O(q^{1.5}/N^{1.5})$ रिजीम के लिए) प्राप्त करने के लिए, लेखक कंप्रेस्ड ओरकल तकनीक का उपयोग करते हैं। वे डिस्टिंग्विशिंग एडवांटेज को एक डेटाबेस स्टेट के एक्सपेक्टेशन के रूप में व्याख्या करते हैं, जिससे वे डेटाबेस में कोलिजन की संख्या को सीमित कर पाते हैं और प्लांटेड कोलिजन समस्या के लिए $O(q^{1.5}/N^{1.5})$ का बाउंड प्राप्त करते हैं।
• रिडक्शन (Reductions): लेखक XoP के फूरियर घटकों और रैंडम फंक्शन्स को प्लांटेड $k$-कोलिजन या प्लांटेड XOR बाधाओं वाले फंक्शन्स से अलग करने के एडवांटेज के बीच रिडक्शन स्थापित करते हैं।

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

मुख्य प्रमेय (Main Theorem)

यह शोध पत्र सिद्ध करता है कि $r \geq 2$ स्वतंत्र रैंडम परम्यूटेशन का XOR, किसी भी $q$-क्वेरी क्वांटम एल्गोरि द्वारा एक रैंडम फंक्शन से अविभेद्य (indistinguishable) है, जिसका एडवांटेज इस सीमा द्वारा बाधित है:
$$O\left( \min \left\{ \frac{q^3}{2^{rn}}, \frac{q^{1.5}}{2^{(r-0.5)n}}, \frac{1}{2^{(r-1.5)n}} \right\} \right)$$
सभी $q \leq 2^{n/57774}$ के लिए।

विशिष्ट सुरक्षा सीमाएँ (Specific Security Bounds)

परिणाम यह दर्शाता है कि XoP पूरे क्वेरी रेंज के दौरान सुरक्षित रहता है, जो $2^{n/3}$ क्वांटम बर्थडे बाउंड से कहीं अधिक है:

1. लो क्वेरी रिजीम ($q \lesssim 2^{n/2}$): एडवांटेज $O(q^3 / 2^{rn})$ द्वारा डोमिनेटेड है। यह क्वांटम कोलिजन-फाइंडिंग हमलों से मेल खाता है।
2. मिडल क्वेरी रिजीम: एडवांटेज $O(q^{1.5} / 2^{(r-0.5)n})$ द्वारा सीमित है। यह बेहतर प्लांटेड कोलिजन विश्लेषण के माध्यम से प्राप्त किया गया है।
3. हाई क्वेरी रिजीम ($q \approx 2^n$): एडवांटेज $O(2^{-(r-1.5)n})$ द्वारा सीमित है। यह सुनिश्चित करता है कि यदि $r \geq 2$ है, तो क्वेरी की संख्या डोमेन साइज के करीब होने पर भी सुरक्षा बनी रहती है।

ह्यूरिस्टिक टाइटनेस (Heuristic Tightness)

लेखक अपने बाउंड की टाइटनेस का सुझाव देने के लिए ह्यूरिस्टिक हमलों को प्रस्तुत करते हैं:

• $q \lesssim 2^{n/2}$ के लिए, क्वांटम कोलिजन-फाइंडिंग हमले $\Omega(q^3/2^{rn})$ और $\Omega(q^{1.5}/2^{(r-0.5)n})$ का एडवांटेज सुझाते हैं।
• $q \approx 2^n$ के लिए, एक ह्यूरिस्टिक कोलिजन-काउंटिंग हमला लगभग $2^{-(r-1.5)n}$ का एडवांटेज सुझाता है।

4. महत्व और दावे

• प्रथम बियॉन्ड-बर्थडे क्वांटम PRF: लेखकों की जानकारी में, यह परम्यूटेशन से बना पहला निर्माण है जो $2^{n/3}$ बर्थडे बाउंड से परे क्वांटम सुरक्षा प्राप्त करता है।
• व्यावहारिक निहितार्थ: यह परिणाम सुझाव देता है कि क्वांटम आइडियल साइफर मॉडल में ब्लॉक साइफर्स (जैसे AES-256) का उपयोग करके XoP के इंस्टेंशिएशन $q \approx 2^n$ क्वेरी तक सुरक्षित हो सकते हैं, बशर्ते की की-लेंथ पर्याप्त हो। यह परम्यूटेशन-आधारित क्रिप्टोग्राफिक प्रिमिटिव्स की क्वांटम सुरक्षा के संबंध में एक महत्वपूर्ण अनिश्चितता को हल करता है।
• मेथोडोलॉजिकल एडवांस: शोध पत्र कम-डिग्री फूरियर घटकों को प्लांटेड कोलिजन समस्याओं के डिस्टिंग्विशिंग एडवांटेज के रूप में पुनर्व्याख्या करने की एक नई तकनीक पेश करता है, जो फूरियर विश्लेषण और कंप्रेस्ड ओरकल पद्धति के बीच के अंतर को पाटता है।
• सहायक परिणाम: प्लांटेड कोलिजन के लिए $O(q^{1.5}/N^{1.5})$ बाउंड का प्रमाण बड़े-रेंज रिजीम में स्मॉल-रेंज डिस्ट्रीब्यूशन की अविभेद्यता के लिए एक नया, बेहतर बाउंड प्रदान करता है, जो स्वतंत्र रूप से महत्वपूर्ण है।

लेखक नोट करते हैं कि हालांकि उन्होंने तकनीकी विवरणों को औपचारिक बनाने और विशिष्ट लेम्मा (विशेष रूप से डिग्री-2 घटकों के लिए $O(q^3/N^r)$ बाउंड) के लिए प्रारंभिक प्रमाण उत्पन्न करने में AI टूल्स (ChatGPT 5.4/5.5 Pro) की सहायता ली है, लेकिन पेपर का मुख्य गणितीय योगदान, प्रमाणों का सरलीकरण और समग्र संरचना मानव लेखकों द्वारा विकसित की गई है।