💻 computer science

Time-Complexity Characterization of NIST Lightweight Cryptography Finalists

यह शोधपत्र एक प्रतीकात्मक मॉडल प्रस्तुत करता है ताकि सभी दस NIST हल्के क्रिप्टोग्राफी (lightweight cryptography) फाइनलिस्टों को इनिशियलाइज़ेशन (initialization), डेटा-प्रोसेसिंग (data-processing) और फाइनलाइजेशन (finalization) चरणों में विभाजित करके उनकी समय जटिलता (time complexity) को औपचारिक रूप से व्युत्पन्न किया जा सके, जिससे संसाधन-सीमित वातावरण के लिए कुशल प्रिमिटिव्स (primitives) के चयन के मार्गदर्शन हेतु एक एकीकृत सैद्धांतिक ढांचा प्रदान किया जा सके।

मूल लेखक: Najmul Hasan, Prashanth BusiReddyGari

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

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

CC BY 4.0

मूल लेखक: Najmul Hasan, Prashanth BusiReddyGari

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

कल्पना कीजिए कि आपके पास नन्हे, बैटरी से चलने वाले रोबोटों (जैसे स्मार्ट सेंसर या IoT डिवाइस) का एक बेड़ा है जिन्हें गुप्त संदेश भेजने की आवश्यकता है। ये रोबोट बहुत छोटे हैं और उनमें ऊर्जा बहुत कम है, इसलिए वे भारी बैकपैक नहीं उठा सकते या जटिल मैराथन नहीं दौड़ सकते। उन्हें एक "ताले और चाबी" वाली प्रणाली (क्रिप्टोग्राफी) की आवश्यकता है जो अत्यंत सुरक्षित हो लेकिन साथ ही अविश्वसनीय रूप से हल्की और तेज़ भी हो।

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

नजमुल हसन और प्रशांत बुसीरेड्डीगारी का यह शोध पत्र इस कमी को पूरा करता है। उन्होंने क्या किया, इसे सरल शब्दों में यहाँ समझाया गया है:

1. समस्या: एक ताले का "वजन" मापना

सोचिए कि 10 फाइनलिस्ट 10 अलग-अलग प्रकार के बैकपैक हैं। कुछ फोम के बने हैं, तो कुछ भारी स्टील के। NIST ने पहले ही उन्हें तराजू पर तौल लिया था (अनुभवजन्य परीक्षण), लेकिन लेखक एक नुस्खा (recipe) लिखना चाहते थे जो यह भविष्यवाणी कर सके कि एक बैकपैक कितना भारी होगा, यदि उसमें कुछ सामान डाला जाए, और इसके लिए हर बार उसे वास्तव में पैक करने की आवश्यकता न पड़े।

वे एक "टाइम कॉम्प्लेक्सिटी" (समय जटिलता) मानचित्र बनाना चाहते थे। सरल शब्दों में, यह एक सूत्र है जो बताता है: "यदि आपका संदेश छोटा है, तो ताला कितना तेज़ है? यदि आपका संदेश लंबा है, तो यह कितना धीमा हो जाता है?"

2. समाधान: तीन-चरणीय असेंबली लाइन

लेखकों ने प्रत्येक 10 क्रिप्टोग्राफिक एल्गोरिदम को तीन सरल चरणों में तोड़ दिया, जैसे कि एक फैक्ट्री की असेंबली लाइन:

चरण 1: इनिशियलाइजेशन (सेटअप): कुछ भी पैक करने से पहले, आपको मशीन सेट करनी होती है। आप चाबी और "नॉन्स" (सेशन के लिए एक अद्वितीय संख्या) लगाते हैं। इसमें एक निश्चित समय लगता है, चाहे आपका संदेश कितना भी बड़ा क्यों न हो। यह कार के इंजन को गर्म करने जैसा है; चाहे आप 1 मील चलें या 100 मील, इसमें उतना ही समय लगता है।
चरण 2: डेटा प्रोसेसिंग (पैकिंग): यहीं पर वास्तविक संदेश और अतिरिक्त डेटा को एन्क्रिप्ट किया जाता है। यह मुख्य काम है। इसमें लगने वाला समय पूरी तरह से इस बात पर निर्भर करता है कि आपके पास कितना डेटा है। लेखकों ने गणना करने के लिए सूत्र बनाए कि डेटा के प्रत्येक ब्लॉक के लिए कितने "कदम" (गणितीय संचालन) की आवश्यकता होती है।
चरण 3: फाइनलाइजेशन (सील करना): एक बार सब कुछ पैक हो जाने के बाद, आपको बॉक्स को सील करना होता है और यह साबित करने के लिए एक सुरक्षा टैग लगाना होता है कि इसके साथ छेड़छाड़ नहीं की गई है। यह एक निश्चित मात्रा में काम है, जैसे किसी पैकेज पर अंतिम स्टिकर लगाना।

3. परिणाम: सबसे हल्का कौन है?

इन सभी 10 फाइनलिस्टों पर इस तीन-चरणीय मॉडल को लागू करके, लेखकों ने सूत्रों का एक "मेन्यू" (Table I में दिखाया गया है) तैयार किया है जो प्रत्येक एल्गोरिदम के "वजन" का वर्णन करता है।

यहाँ उनके नए सूत्रों का उपयोग करके पता चले कुछ दिलचस्प निष्कर्ष दिए गए हैं:

"सिंपल लीनियर" धावक: GIFT-COFB, Grain-128AEAD, और ISAP जैसे एल्गोरिदम एक सीधे हाईवे की तरह हैं। उनका समय संदेश के आकार के साथ बिल्कुल तालमेल बिठाते हुए बढ़ता है। यदि आप संदेश को दोगुना करते हैं, तो समय भी दोगुना हो जाता है। उनमें कोई अतिरिक्त "टैक्स" या जटिल गुणक नहीं हैं। GIFT-COFB विशेष रूप से सरल है, जो बड़े संदेशों के लिए इसे बहुत कुशल बनाता है।
"ब्लॉक" धावक: TinyJambu और Romulus जैसे एल्गोरिदम एक कन्वेयर बेल्ट की तरह काम करते हैं जो केवल विशिष्ट आकार के बक्सों में वस्तुओं को स्वीकार करता है। यदि आपका संदेश पूरी तरह से एक बॉक्स में फिट नहीं होता है, तो उन्हें खाली स्थान भरने के लिए "पैडिंग" (खाली जगह) जोड़नी पड़ती है। यह विशेष रूप से छोटे संदेशों के लिए थोड़ा अतिरिक्त बोझ डालता है, लेकिन वे बहुत व्यवस्थित हैं।
"परम्यूटेशन" धावक: ASCON (जिसे अंततः NIST ने विजेता चुना) और Xoodyak जैसे एल्गोरिदम एक "शफलिंग" (क्रम बदलने) की विधि का उपयोग करते हैं। वे डेटा लेते हैं और उसे एक विशिष्ट पैटर्न में मिला देते हैं। उनके सूत्र दिखाते हैं कि वे बहुत कुशल हैं, और समय की लागत मुख्य रूप से इस बात से आती है कि उन्हें डेटा को कितनी बार शफल करना पड़ता है।
"हाइब्रिड" धावक: ISAP विभिन्न तकनीकों का मिश्रण है। यह प्रत्येक सेशन के लिए एक अस्थायी कुंजी बनाता है, जिससे सेटअप का थोड़ा समय लगता है लेकिन यह कुछ प्रकार के हैकिंग के विरुद्ध बहुत सुरक्षित बनाता है।

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

यह शोध पत्र केवल यह नहीं कहता कि "एल्गोरिदम A तेज़ है।" यह यह देखकर समझाता है कि ऐसा क्यों है।

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

निचोड़

यह शोध पत्र क्रिप्टोग्राफिक प्रदर्शन के लिए एक "यूनिवर्सल ट्रांसलेटर" प्रदान करता है। अंतहीन परीक्षण करने या अनुमान लगाने के बजाय, इंजीनियर अब इन प्रतीकात्मक सूत्रों का उपयोग अपने विशिष्ट रोबोट के लिए सही "ताला" चुनने के लिए कर सकते हैं।

यदि आपको बड़े संदेशों के लिए बिल्कुल सरल और सबसे हल्का रास्ता चाहिए, तो गणित GIFT-COFB की ओर संकेत करता है।
यदि आपको सामान्य उपयोग के लिए सुरक्षा और गति का संतुलन चाहिए, तो गणित ASCON को उजागर करता है।
यदि आपको डेटा को पूर्ण ब्लॉक्स के लिए प्रतीक्षा किए बिना बिट-दर-बिट प्रोसेस करना है, तो Grain-128AEAD स्पष्ट विकल्प है।

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

तकनीकी सारांश: NIST लाइटवेट क्रिप्टोग्राफी फाइनलिस्ट्स का समय-जटिलता लक्षण वर्णन

समस्या विवरण
जैसे-जैसे डिजिटल पहचान प्रणालियों और इंटरनेट ऑफ थिंग्स (IoT) में उभरती प्रौद्योगिकियां सीमित प्रसंस्करण शक्ति, मेमोरी और ऊर्जा वाले उपकरणों पर अधिक निर्भर होती जा रही हैं, लाइटवेट क्रिप्टोग्राफी (LWC) की मांग महत्वपूर्ण हो गई है। जबकि नेशनल इंस्टीट्यूट ऑफ स्टैंडर्ड्स एंड टेक्नोलॉजी (NIST) ने दस फाइनलिस्ट एल्गोरिदम का मूल्यांकन करने वाली एक मानकीकरण प्रक्रिया पूरी की है, मौजूदा साहित्य कार्यात्मक बेंचमार्क (निष्पादन समय और थ्रूपुट) पर अधिक निर्भर करता है, न कि एक एकीकृत सैद्धांतिक समझ पर। Ascon, ISAP और TinyJAMBU जैसे फाइनलिस्ट्स के लिए वर्तमान दस्तावेजीकरण कार्यान्वयन अनुकूलन पर केंद्रित है, लेकिन इसमें औपचारिक समय-जटिलता अभिव्यक्तियों का अभाव है। यह सैद्धांतिक ढांचे का अभाव विविध सीमित वातावरणों में एल्गोरिदम की दक्षता को व्यवस्थित रूप से अलग करने और प्रदर्शन स्केलिंग की भविष्यवाणी करने की क्षमता में बाधा डालता है।

कार्यप्रणाली
लेखक एक प्रतीकात्मक मॉडल प्रस्तावित करते हैं जो क्रिप्टोग्राफिक योजनाओं की समय जटिलता को तीन अलग-अलग चरणों में विभाजित करता है: इनिशियलाइजेशन (आरंभिकरण), डेटा प्रोसेसिंग (डेटा प्रसंस्करण), और फाइनलाइजेशन (समापन)। यह ढांचा विशिष्ट हार्डवेयर प्लेटफॉर्म से स्वतंत्र होकर औपचारिक समय-जटिलता अभिव्यक्तियों को व्युत्पन्न करने की अनुमति देता है।

कुल समय जटिलता ( $T_{total}$ ) को निम्नलिखित के योग के रूप में मॉडल किया गया है:

इनिशियलाइजेशन ( $T_{init}$ ): कुंजी (key) और नॉन्स (nonce) सेटअप के लिए निश्चित लागत ($ck + cn$), जो इनपुट आकार से स्वतंत्र है।
डेटा प्रोसेसिंग ( $T_{process}$ ): एसोसिएटेड डेटा ( $A$ ) और मैसेज ब्लॉक्स ( $M$ ) को संसाधित करने से जुड़ी लागत। इसे $T_A$ और $T_M$ में विभाजित किया गया है, जिसे ब्लॉक काउंट, परम्यूटेशन समय ( $T_p$ ) और ऑपरेशन ओवरहेड्स के आधार पर गणना किया जाता है।
फाइनलाइजेशन ( $T_{finalize}$ ): ऑथेंटिकेशन टैग जनरेशन या वैलिडेशन के लिए स्थिर समय लागत ( $c_f$ )।

इस तीन-चरणीय अपघटन का उपयोग करते हुए, लेखक सभी दस NIST फाइनलिस्ट्स (Ascon, Elephant, GIFT-COFB, Grain-128AEAD, ISAP, PHOTON-Beetle, Romulus, SPARKLE, TinyJAMBU, और Xoodyak) के लिए उनके एल्गोरिदम विनिर्देशों, जिसमें स्टेट साइज, परम्यूटेशन डिजाइन और ऑपरेशन मोड शामिल हैं, के आधार पर प्रतीकात्मक जटिलता अभिव्यक्तियाँ व्युत्पन्न करते हैं।

प्रमुख योगदान और परिणाम
यह शोध पत्र दस फाइनलिस्ट्स के कम्प्यूटेशनल स्केलिंग का तुलनात्मक विश्लेषण प्रदान करता है, उन्हें उनकी अंतर्निहित वास्तुशिल्प रणनीतियों के आधार पर वर्गीकृत करता है:

परम्यूटेशन-आधारित एल्गोरिदम: पांच फाइनलिस्ट्स (Ascon, Elephant, PHOTON-Beetle, SPARKLE, Xoodyak) स्पंज-आधारित या परम्यूटेशन-केंद्रित निर्माणों का उपयोग करते हैं। उनकी जटिलता आम तौर पर परम्यूटेशन लागत ( $b$ ) और संसाधित ब्लॉकों की संख्या द्वारा संचालित होती है। उदाहरण के लिए, Ascon एक सुव्यवस्थित 12-राउंड इनिशियलाइजेशन के माध्यम से कुशल स्केलिंग ( $O(l_A \cdot b + l_P \cdot b)$ ) प्राप्त करता है, जबकि SPARKLE एन्क्रिप्शन और हैशिंग दोनों कार्यात्मकताओं को समर्थन देने के लिए अतिरिक्त स्थिर पद (constant terms) शामिल करता है।
ब्लॉक साइफर-आधारित एल्गोरिदम: तीन फाइनलिस्ट्स (GIFT-COFB, Romulus-N, TinyJAMBU) ब्लॉक साइफर या रजिस्टर-आधारित निर्माणों का उपयोग करते हैं। GIFT-COFB को इसके उल्लेखनीय रूप से सरल रैखिक स्केलिंग ( $O(\ell_A + \ell_M)$ ) के लिए हाइलाइट किया गया है, जिसमें कोई मल्टीप्लिकेटिव फैक्टर्स नहीं हैं, जो इसे बड़े संदेशों के लिए अत्यधिक कुशल बनाता है। TinyJAMBU विभिन्न चरणों के लिए दोहरे परम्यूटेशन ( $P_{640}$ और $P_{1024}$ ) का उपयोग करता है, जो विशिष्ट निश्चित इनिशियलाइजेशन लागत और एसोसिएटेड डेटा तथा संदेशों के लिए अलग प्रसंस्करण लागत पेश करता है।
स्ट्रीम साइफर और हाइब्रिड एल्गोरिदम: Grain-128AEAD एकमात्र स्ट्रीम साइफर फाइनलिस्ट है, जो सीधे बिट काउंट के साथ स्केल करने वाली जटिलता ($O(|M| + |AD|)$) प्रदान करता है, जिससे पैडिंग ओवरहेड समाप्त हो जाता है। ISAP सेशन की (session key) व्युत्पत्ति के साथ स्पंज-आधारित एन्क्रिप्शन को जोड़ता है, जो की सेपरेशन (key separation) के माध्यम से साइड-चैनल हमलों के खिलाफ प्रतिरोध प्रदान करते हुए रैखिक स्केलिंग ( $O(|A| + |M|)$ ) प्राप्त करता है।

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

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

1. समस्या: एक ताले का "वजन" मापना

2. समाधान: तीन-चरणीय असेंबली लाइन

3. परिणाम: सबसे हल्का कौन है?

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

निचोड़

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