💻 computer science

Explicit cost analysis of Toom-4 multiplication for incomplete NTT in lattice-based cryptography

यह शोध पत्र एक ठोस Toom-4 कार्यान्वयन को स्पष्ट ऑपरेशन गणनाओं के साथ प्रस्तुत करता है ताकि इनकम्प्लीट (incomplete) NTT के लिए एक लागत मॉडल व्युत्पन्न किया जा सके, जिससे उन विशिष्ट पैरामीटर श्रेणियों की पहचान की जा सके जहाँ Toom-4, Karatsuba और इनकम्प्लीट NTT को संयोजित करने वाली हाइब्रिड रणनीतियाँ लैटिस-आधारित क्रिप्टोग्राफी में मौजूदा विधियों से बेहतर प्रदर्शन करती हैं।

मूल लेखक: Sakura Oku, Momonari Kudo

प्रकाशित 2026-05-19

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

CC BY 4.0

मूल लेखक: Sakura Oku, Momonari Kudo

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

कल्पना कीजिए कि आप एक बहुत बड़ी जिग्सॉ पहेली (jigsaw puzzle) को हल करने की कोशिश कर रहे हैं, लेकिन आपकी मेज बहुत छोटी है। आधुनिक डिजिटल सुरक्षा की दुनिया में (विशेष रूप से "लैटिस-आधारित क्रिप्टोग्राफी" में), यह "पहेली" विशाल बहुपदों (polynomials) से जुड़ी एक जटिल गणितीय समस्या है, और "मेज" एक विशिष्ट गणितीय नियम है जिसे मोडुलस (modulus) कहा जाता है।

आमतौर पर, इन पहेलियों को तेज़ी से हल करने के लिए, विशेषज्ञ एक सुपर-फास्ट शॉर्टकट का उपयोग करते हैं जिसे NTT कहा जाता है। सोचिए कि NTT एक जादुई कन्वेयर बेल्ट है जो पहेली के टुकड़ों को तुरंत छाँट देती है। हालांकि, यह कन्वेयर बेल्ट केवल तभी काम करती है जब मेज (मोडुलस) एक बहुत ही विशिष्ट आकार की हो। यदि मेज गलत आकार की है, तो कन्वेयर बेल्ट टूट जाती है, और आपको टुकड़ों को हाथों से छाँटना पड़ता है, जो कि बहुत धीमा है।

हाल ही में, शोधकर्ताओं ने एक "आंशिक" कन्वेयर बेल्ट (जिसे Incomplete NTT कहा जाता है) का उपयोग करने का तरीका खोजा है जो लगभग किसी भी मेज के आकार पर काम कर सकता है, लेकिन यह छोटे ढेरों को छोड़ देता है जिन्हें अभी भी हाथों से छाँटने की आवश्यकता होती है।

समस्या: छोटे ढेरों को कैसे छाँटें?

जब कन्वेयर बेल्ट जल्दी रुक जाती है, तो आपके पास छोटे उप-पहेली (sub-puzzles) बच जाते हैं। उन्हें पूरा करने के लिए, आपको एक रणनीति की आवश्यकता होती है।

करत्सुबा (Karatsuba): यह इन छोटे ढेरों को छाँटने का एक जाना-माना, कुशल तरीका है। यह एक मानक, भरोसेमंद फोल्डिंग तकनीक की तरह है।
टूम-4 (Toom-4): यह एक अधिक उन्नत, जटिल फोल्डिंग तकनीक है। सैद्धांतिक रूप से, यह बहुत बड़े ढेरों के लिए तेज़ है, लेकिन इसे सेटअप करना जटिल है।

इस शोध पत्र के लेखकों ने एक सरल प्रश्न पूछा: "यदि हमें 'आंशिक कन्वेयर बेल्ट' (Incomplete NTT) का उपयोग करने के लिए मजबूर किया जाता है, तो क्या शेष छोटे ढेरों के लिए जटिल 'टूम-4' तकनीक का उपयोग करना सार्थक है, या हमें मानक 'करत्सुबा' पर टिके रहना चाहिए?"

चुनौती: चरणों की गिनती करना

समस्या यह है कि जबकि हम जानते हैं कि टूम-4 सैद्धांतिक रूप से तेज़ है, लेकिन इस विशिष्ट "आंशिक कन्वेयर बेल्ट" परिदृश्य में इसका उपयोग करने के लिए आवश्यक चरणों (जोड़ और गुणा) की सटीक संख्या किसी ने लिखी नहीं थी। यह ऐसा ही है जैसे यह जानना कि एक कार साइकिल से तेज़ है, लेकिन यह न जानना कि एक विशिष्ट, ऊबड़-खाबड़ सड़क पर वह वास्तव में कितने गैलन ईंधन बचाएगी।

लेखकों ने टूम-4 के लिए एक सटीक "चरण-दर-चरण रेसिपी" बनाने का कठिन कार्य किया। उन्होंने हर एक गणितीय ऑपरेशन (जोड़ और गुणा) को गिना, उन्हें अलग-अलग किया ताकि वे देख सकें कि प्रत्येक विधि कितना "ईंधन" (कंप्यूटेशनल पावर) खर्च करती है।

खोज: एक हाइब्रिड रणनीति

अपनी नई, सटीक रेसिपी का उपयोग करते हुए, उन्होंने विभिन्न परिदृश्यों का परीक्षण किया। उन्होंने पाया कि:

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

उन्होंने एक "हाइब्रिड रणनीति" की खोज की: जितना संभव हो सके आंशिक कन्वेयर बेल्ट का उपयोग करें, फिर मध्यम आकार के ढेरों के लिए टूम-4 पर स्विच करें, और अंत में सबसे छोटे टुकड़ों के लिए करत्सुबा पर स्विच करें।

परिणाम

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

सरल शब्दों में:
कल्पना कीजिए कि आप फर्नीचर हटा रहे हैं।

Full NTT एक बड़ा ट्रक है जो आपके पूरे घर में समा जाता है।
Incomplete NTT एक ट्रक है जो केवल आपके घर के आधे हिस्से में फिट होता है, इसलिए आपको बाकी हिस्सा खुद हटाना पड़ता है।
Karatsuba एक-एक करके बक्से ले जाना है।
Toom-4 पुली (pulleys) और लीवर की एक जटिल प्रणाली है।

शोध पत्र कहता है: "यदि आपके पास एक बहुत बड़ा घर है, तो ट्रक सब कुछ करता है। लेकिन यदि आपके पास एक अजीब आकार का घर है जहाँ ट्रक केवल आधा ही अंदर जा सकता है, तो केवल बक्से एक-एक करके उठाने के बजाय, बीच के हिस्से के लिए पुली सिस्टम (Toom-4) का उपयोग करें, और फिर अंतिम कुछ बक्सों को हाथों से उठाएं।"

यह क्यों महत्वपूर्ण है

लेखकों ने किसी नए प्रकार के गणित का आविष्कार नहीं किया है; उन्होंने बस मौजूदा उपकरणों को बहुत सटीकता से मापा है। उनका काम इंजीनियरों को तेज़, अधिक सुरक्षित डिजिटल लॉक (क्रिप्टोसिस्टम) बनाने में मदद करता है, उन्हें यह बताकर कि जटिल "पुली" का उपयोग कब करना है और कब साधारण "बक्सों" पर टिके रहना है। उन्होंने कंप्यूटर सिमुलेशन चलाकर अपने गणित की पुष्टि की, जिससे यह सिद्ध हुआ कि जब "ट्रक" (NTT) सीमित होता है, तो उनकी हाइब्रिड रणनीति समय बचाती है।

तकनीकी सारांश: इनकम्प्लीट (अपूर्ण) NTT के लिए टूम-4 (Toom-4) गुणन का स्पष्ट लागत विश्लेषण

समस्या विवरण
बहुपद गुणन (Polynomial multiplication) लैटिस-आधारित क्रिप्टोसिस्टम जैसे कि Kyber (ML-KEM) और Dilithium (ML-DSA) में एक मौलिक ऑपरेशन है, जिसे आमतौर पर अवशेष रिंगों $R_q = \mathbb{F}_q[x]/\langle x^n + 1 \rangle$ पर किया जाता है। जबकि नंबर थ्योरेटिक ट्रांसफॉर्म (NTT) $O(n \log n)$ गुणन गति प्रदान करता है, यह कड़ाई से शर्त $2n \mid (q-1)$ की आवश्यकता रखता है। यह प्रतिबंध पैरामीटर चयन को सीमित कर सकता है और सुरक्षा या दक्षता लक्ष्यों से समझौता कर सकता है।

इस समस्या के समाधान के लिए, हाफिज एवं अन्य (2025) ने "इनकम्प्लीट NTT" पेश किया, जो गहराई $\ell$ (जहाँ $2^{\ell+1} \mid (q-1)$ ) के ट्रंकेटेड NTT को निष्पादित करके और शेष उप-समस्याओं के लिए पारंपरिक बहुपद गुणन के साथ जोड़कर मॉडुलस प्रतिबंध को शिथिल करता है। जबकि करात्सुबा (Karatsuba) गुणन इस ढांचे के भीतर अच्छी तरह से समझा गया है, टूम-4 गुणन की सटीक लागत—विशेष रूप से जोड़ने (additions) और गुणा (multiplications) के संबंध में इसके स्थिरांक (constant factors)—को इनकम्प्लीट NTT लागत मॉडल के अनुकूल रूप में व्यक्त नहीं किया गया है। मौजूदा टूम-कुक (Toom-Cook) विश्लेषण (जैसे बोद्राटो और ज़ानोनी) सामान्य अनुकूलन पर ध्यान केंद्रित करते हैं लेकिन इनकम्प्लीट NTT के लिए आवश्यक विशिष्ट हाइब्रिड ढांचे के साथ सीधे एकीकृत नहीं हैं।

कार्यप्रणाली (Methodology)
लेखक इनकम्प्लीट NTT ढांचे के अनुरूप तैयार किए गए टूम-4 गुणन का एक मूर्त कार्यान्वयन प्रस्तुत करते हैं और एक स्पष्ट ऑपरेशन काउंट मॉडल व्युत्पन्न करते हैं।

कार्यान्वयन रणनीति: लेखक भिन्नात्मक स्थिरांकों से बचने के लिए पूर्णांक मूल्यांकन बिंदुओं $\{0, \pm 1, \pm 2, 3, \infty\}$ को अपनाते हैं। सभी विभाजनों को अंतिम स्केलिंग चरण तक स्थगित कर दिया जाता है।
एडिशन चेन ऑप्टिमाइज़ेशन: कार्यप्रणाली का एक महत्वपूर्ण घटक आवश्यक स्केलर मल्टीपल्स को कंप्यूट करने के लिए एडिशन चेन का उपयोग करना है। व्यक्तिगत स्केलर गुणन करने के बजाय, लेखक वांछित गुणांकों के लिए न्यूनतम एडिशन चेन का निर्माण करते हैं जो इनवर्स वेंडरमंड मैट्रिक्स (inverse Vandermonde matrix) के लिए आवश्यक हैं। यह लक्षित गुणांकों के लिए आवश्यक जोड़ और घटाव की सटीक संख्या के व्यवस्थित निर्धारण की अनुमति देता है।
लागत व्युत्पत्ति (Cost Derivation): लेखक ऑपरेशन काउंट को $\mathbb{F}_q$ के ऊपर जोड़/घटाव ( $A$ ) और गुणा ( $M$ ) में अलग करते हैं। वे टूम-4 चरणों (स्प्लिटिंग, इवैल्यूएशन, रिकर्सिव मल्टीप्लिकेशन, इंटरपोलेशन, और री-कंपोज़िशन) के लिए रिकर्सिव फॉर्मूले व्युत्पन्न करते हैं और उन्हें हाफिज एवं अन्य द्वारा स्थापित इनकम्प्लीट NTT के वेटेड कॉस्ट मॉडल में एकीकृत करते हैं।
हाइब्रिड विश्लेषण: अध्ययन उन हाइब्रिड रणनीतियों का विश्लेषण करता है जो टूम-4, करात्सुबा और इनकम्प्लीट NTT को मिलाती हैं। $C_w(n; \ell, L)$ (जहाँ $w$ गुणा को जोड़ने का सापेक्ष लागत है) के वेटेड कॉस्ट फंक्शन को न्यूनतम करके, लेखक विभिन्न उप-समस्या आकारों के लिए इष्टतम रिकर्सन डेप्थ $L$ निर्धारित करते हैं।

मुख्य योगदान

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

परिणाम
विश्लेषण से पता चलता है कि इस संदर्भ में टूम-4 की प्रभावशीलता स्वीकार्य NTT गहराई ( $\ell$ ) और परिणामी उप-समस्या आकार ( $d = n/2^\ell$ ) पर अत्यधिक निर्भर है:

सीमित गहराई शासन (Limited Depth Regime): जब स्वीकार्य NTT गहराई कम होती है (जैसे, $\ell=0$ या $\ell=1$ ), तो उप-समस्याएं इतनी बड़ी होती हैं कि टूम-4 महत्वपूर्ण लाभ प्रदान करता है। उदाहरण के लिए, $n=256$ और $\ell=0$ के साथ, हाइब्रिड विधि ने शुद्ध करात्सुबा की तुलना में वेटेड लागत को लगभग 5% कम कर दिया और शुद्ध टूम-4 की तुलना में काफी बेहतर प्रदर्शन किया।
इष्टतम रिकर्सन: इष्टतम रिकर्सन डेप्थ $L$ , $d$ के साथ बदलता है। $d \le 128$ के लिए, इष्टतम रणनीति $L=0$ (शुद्ध करात्सुबा) है। $d=256$ के लिए, $L=1$ इष्टतम है, और $d \ge 512$ के लिए, $L=2$ इष्टतम है।
प्रायोगिक पुष्टि: प्रतिबंधित 2-adic वैल्यूएशन वाले प्राइम्स पर प्रयोगों ने सैद्धांतिक मॉडल की पुष्टि की। जब अधिकतम स्वीकार्य गहराई न्यूनतम थी ( $\ell_{max}=0$ ), तो हाइब्रिड विधि ने करात्सुबा की तुलना में काफी बेहतर प्रदर्शन किया (उदाहरण के लिए, $n=256$ के लिए 14.182 ms बनाम 16.722 ms)। जैसे-जैसे स्वीकार्य गहराई बढ़ी, हाइब्रिड विधि का प्रदर्शन लाभ कम होता गया, और जब उप-समस्याएं बहुत छोटी हो गईं तो यह करात्सुबा के साथ अभिसरित (converge) हो गया।

महत्व और दावे
लेखक विनम्रतापूर्वक दावा करते हैं कि उनका प्राथमिक योगदान एक नया गुणन एल्गोरिदम नहीं है, बल्कि इनकम्प्लीट NTT ढांचे के लिए विशेष रूप से तैयार किया गया टूम-4 का सटीक निरंतर-स्तर (constant-level) विश्लेषण है। वे तर्क देते हैं कि यह स्पष्ट लागत मॉडल साहित्य में मौजूद अंतर को पाटता है, जिससे पूर्ण रूप से उपलब्ध न होने वाली स्थितियों में हाइब्रिड रणनीतियों का व्यवस्थित मूल्यांकन संभव होता है।

लेख निष्कर्ष निकालते हैं कि टूम-4 इनकम्प्लीट NTT के "सीमित-डेप्थ शासन" में सबसे अधिक फायदेमंद है, विशेष रूप से तब जब $q-1$ का 2-adic वैल्यूएशन ट्रांसफॉर्म की गहराई को प्रतिबंधित करता है। ऐसे मामलों में, प्रस्तावित हाइब्रिड रणनीति मानक करात्सा-आधारित दृष्टिकोणों की तुलना में मापने योग्य प्रदर्शन सुधार प्रदान करती है। लेखक उल्लेख करते हैं कि उनका वर्तमान कार्यान्वयन पायथन में है और भविष्य के कार्यों में लो-लेवल कार्यान्वयन (जैसे C/C++) को अनुकूलित करना और ठोस लैटिस-आधारित स्कीमों में और अधिक मूल्यांकन शामिल है।

समस्या: छोटे ढेरों को कैसे छाँटें?

चुनौती: चरणों की गिनती करना

खोज: एक हाइब्रिड रणनीति

परिणाम

यह क्यों महत्वपूर्ण है

इसी तरह के और पेपर