💻 computer science

The 1-Bit Barrier is Universal: k-Stage Pipeline Composition and Unified Leakage Bounds for Standard Modular Reductions in PQC Hardware

यह शोध पत्र लीन 4 (Lean 4) में एक मशीन-चेक किया गया प्रमाण प्रस्तुत करता है जो यह स्थापित करता है कि फ्रेश इंटर-स्टेज मास्किंग और PF-PINI( $\leq 2$ ) गैजेट्स के साथ अनिश्चित-गहराई वाले $k$ -स्टेज मास्क किए गए NTT पाइपलाइन्स, पूर्ववर्ती कंपोजिशन थ्योरम्स का सामान्यीकरण करके और मोंटगोमरी रिडक्शन गुणों को सत्यापित करके, पाइपलाइन गहराई से स्वतंत्र, $2/q$ का एक यूनिवर्सल प्रति-अवलोकन लीकेज बाउंड प्राप्त करते हैं।

मूल लेखक: Ray Iskander, Khaled Kirah

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

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

CC BY 4.0

मूल लेखक: Ray Iskander, Khaled Kirah

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

यहाँ "The 1-Bit Barrier is Universal" पेपर का सरल भाषा और रचनात्मक उपमाओं (analogies) के साथ विवरण दिया गया है।

बड़ी तस्वीर: एक शोर भरे कारखाने में रहस्यों की सुरक्षा

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

यह पेपर इस बारे में है कि यह मिक्सिंग प्रक्रिया काम करती है, इसकी गणितीय गारंटी बनाने के बारे में, चाहे असेंबली लाइन कितनी भी लंबी क्यों न हो।

समस्या: "लीकी" (Leaky) मशीन

पोस्ट-क्वांटम क्रिप्टोग्राफी की दुनिया में (भविष्य के क्वांटेंट कंप्यूटरों को रोकने के लिए आवश्यक नया प्रकार का गणित), कारखाना एक विशिष्ट प्रकार की मशीन का उपयोग करता है जिसे मॉड्यूलर रिडक्शन (Modular Reduction) कहा जाता है (विशेष रूप से "बैरेट" (Barrett) और "मोंटगोमरी" (Montgomery) रिडक्शन)।

इन मशीनों को विशेष कैलकुलेटर के रूप में सोचें।

पुराना दृष्टिकोण: लंबे समय तक, हम केवल यह जानते थे कि "बैरेट" कैलकुलेटर थोड़ा सा डेटा लीक करता है। हमें "मोंटगोमरी" कैलकुलेटर के बारे में पता नहीं था।
जोखिम: यदि कोई मशीन बहुत अधिक जानकारी लीक करती है, तो एक जासूस बिजली की खपत (power consumption) को सुनकर रैंडम मास्क का अनुमान लगा सकता है, और अंततः मूल ब्लूप्रिंट को फिर से बना सकता है।

खोज: "1-बिट बैरियर" (The 1-Bit Barrier)

लेखकों ने पाया कि बैरेट और मोंटगोमरी दोनों कैलकुलेटरों में एक बहुत ही विशिष्ट, सुरक्षित व्यवहार होता है। वे इसे "1-बिट बैरियर" कहते हैं।

उपमा (Analogy):
कल्पना कीजिए कि आप 1 से 1,000,000 के बीच एक नंबर का अनुमान लगाने की कोशिश कर रहे हैं।

यदि कोई मशीन खराब है, तो वह आपके अनुमान को केवल 100 नंबरों तक सीमित कर सकती है। यह एक बहुत बड़ा लीक है।
यदि कोई मशीन परफेक्ट है, तो वह आपको कोई संकेत नहीं देती; आपको अभी भी पूरे दस लाख नंबरों का अनुमान लगाना होगा।
1-बिट बैरियर का अर्थ है कि मशीन आपके अनुमान को अधिकतम 2 नंबरों तक सीमित कर देती है।

पेपर की भाषा में, इसे PF-PINI(2) कहा जाता है। इसका मतलब है कि मशीन जो भी आउटपुट देती है, उसके लिए सीक्रेट और रैंडम मास्क के केवल दो संभावित संयोजन (combinations) हो सकते हैं जो उसे बना सकते थे। यह ऐसा है जैसे मशीन कहती है, "मैंने यह परिणाम बनाया, और यह केवल सीक्रेट A या सीक्रेट B से ही आ सकता था।" चूंकि लाखों संभावनाएँ मौजूद हैं, इसलिए केवल दो तक सीमित करना अविश्वसनीय रूप से सुरक्षित है।

यह पेपर क्या जोड़ता है:

मोंटगोमरी सुरक्षित है: उन्होंने सिद्ध किया कि मोंटगोमरी कैलकुलेटर (जो कई नए मानकों में उपयोग किया जाता है) में बैरेट की तरह ही यह समान "1-बिट बैरियर" है।
चेन रिएक्शन: उन्होंने सिद्ध किया कि यदि आप इन कैलकुलेटरों को एक लंबी लाइन (पाइपलाइन) में जोड़ते हैं, तो लाइन लंबी होने से सुरक्षा कम नहीं होती है।

समाधान: "फ्रेश मास्क" रिफ्रेश स्टेशन

यह पेपर इन असेंबली लाइनों को बनाने के लिए एक महत्वपूर्ण नियम पेश करता है: आपको हर मशीन के बीच एक "फ्रेश मास्क" (Fresh Mask) डालना चाहिए।

उपमा (Analogy):
कल्पना कीजिए कि एक रिले रेस है जहाँ धावक एक बैटन (baton) पास करते हैं।

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

क्योंकि कंबल हर बार नया और रैंडम होता है, इसलिए धावक B को सुनने वाला जासूस यह नहीं जान पाता कि धावक A क्या कर रहा था। रेस के पहले हिस्से का "शोर" पूरी तरह से मिट जाता है।

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

मुख्य परिणाम: "एंड-टू-एंड" गारंटी

लेखकों ने अपने गणित की जांच करने के लिए एक शक्तिशाली कंप्यूटर प्रूफ असिस्टेंट (जिसे Lean 4 कहा जाता है) का उपयोग किया। उन्होंने इसे केवल लिखा नहीं; उन्होंने कंप्यूटर से हर कदम को सत्यापित करवाया, जिससे यह सुनिश्चित हुआ कि कोई तार्किक कमी न रहे।

उनका निष्कर्ष:
यदि आप इन कैलकुलेटरों (बैरेट या मोंटगोमरी) की एक पाइपलाइन बनाते हैं और आप हर चरण के बीच एक "फ्रेश मास्क" रखते हैं:

अंतिम आउटपुट सुरक्षित है।
एक जासूस द्वारा चुराए जाने वाली जानकारी की मात्रा उस "1-बिट बैरियर" तक सीमित है (अनुमान को लाखों में से केवल 2 संभावनाओं तक सीमित करना)।
यह सुरक्षा तब भी बनी रहती है जब आपकी पाइपलाइन में 2 चरण हों या 100 चरण। पाइपलाइन की लंबाई इसे कमजोर नहीं बनाती है।

"एडम्स ब्रिज" केस स्टडी (The "Adams Bridge" Case Study)

पेपर एक वास्तविक दुनिया के हार्डवेयर प्रोजेक्ट का उल्लेख करता है जिसे एडम्स ब्रिज (Adams Bridge) कहा जाता है।

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

एक वाक्य में सारांश

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

तकनीकी सारांश: 1-बिट बाधा सार्वभौमिक है (The 1-Bit Barrier is Universal)

समस्या विवरण
नंबर थ्योरेटिक ट्रांसफॉर्म (NTT) NIST पोस्ट-क्वांटम क्रिप्टोग्राफी (PQC) मानकों ML-DSA (FIPS 204) और ML-KEM (FIPS 203) के लिए कम्प्यूटेशनल बैकबोन के रूप में कार्य करता है। इन मानकों के हार्डवेयर कार्यान्वयन साइड-चैनल हमलों, विशेष रूप से डिफरेंशियल पावर एनालिसिस (DPA) का प्रतिरोध करने के लिए अंकगणितीय मास्किंग (arithmetic masking) पर निर्भर करते हैं। जबकि $GF(2^n)$ पर बूलियन मास्किंग ने स्थापित कंपोजेबिलिटी फ्रेमवर्क (जैसे, PINI) प्रदान किए हैं, प्राइम $q$ के लिए $\mathbb{Z}_q$ पर अंकगणितीय मास्किंग अनूठी चुनौतियाँ पेश करती है।

QANARY प्रोग्राम के पिछले कार्यों (पेपर 1–6) ने संरचनात्मक निर्भरता विश्लेषण स्थापित किया और विशिष्ट घटकों के लिए सुरक्षा मार्जिन को परिमाणित किया, विशेष रूप से यह सिद्ध किया कि बैरेट रिडक्शन (Barrett reduction) एक "1-बिट बैरियर" (PF-PINI(2)) को संतुष्ट करता है। हालाँकि, दो महत्वपूर्ण अंतराल शेष थे:

अनिश्चित पाइपलाइन गहराई (Arbitrary Pipeline Depth): पिछले कंपोजिशन प्रमेय दो चरणों तक सीमित थे। फ्रेश इंटर-स्टेज मास्किंग के साथ $k$ -चरणों वाली अनिश्चित पाइपलाइनों के लिए कोई औपचारिक गारंटी नहीं थी।
मोंटगोमरी रिडक्शन (Montgomery Reduction): जबकि बैरेट रिडक्शन का लक्षण वर्णन किया गया था, मोंटगोमरी रिडक्शन—जो NTT हार्डवेयर (ML-DSA और कुछ ML-KEM कार्यान्वयन में प्रमुख) में उपयोग किया जाने वाला दूसरा मानक मॉड्यूलर रिडक्शन है—एक औपचारिक PF-PINI लक्षण वर्णन की कमी थी।
एकीकृत एंड-टू-एंड बाउंड्स: बटरफ्लाई, बैरेट और मोंटगोमरी रिडक्शन के लिए अनिश्चित पाइपलाइनों को जोड़ने वाले परिणामों के लिए कोई एकल, मशीन-चेक्ड कार्डिनैलिटी बाउंड नहीं था।

कार्यप्रणाली (Methodology)
यह शोध पत्र Lean 4 प्रूफ असिस्टेंट का उपयोग करके औपचारिक सत्यापन (formal verification) नियोजित करता है। दृष्टिकोण पूरी तरह से रचनात्मक (constructive) है, जिसमें शून्य sorry (अप्रामाणित धारणाएं) और शून्य गैर-मानक एक्सिओम (axioms) हैं। कार्यप्रणाली निम्नलिखित पर निर्भर करती है:

PF-PINI परिभाषा: प्राइम-फील्ड प्रोब आइसोलेटिंग नॉन-इंटरफेरेंस (PF-PINI) पैरामीटर का उपयोग करना, जो एक एकल अंकगणितीय मास्क के तहत एक सिंगल-वायर गैजेट के लीकेज को परिमाणित करता है। एक गैजेट PF-PINI( $M$ ) है यदि किसी भी आउटपुट वैल्यू का प्री-इमेज कार्डिनैलिटी (preimage cardinality) $M$ से अधिक नहीं है।
पाइपलाइन मॉडलिंग: एक $k$ -स्टेज पाइपलाइन को परिभाषित करना जहाँ प्रत्येक स्टेज $G_i$ , फ्रेश रैंडम मास्क द्वारा अलग किया गया एक PF-PINI गैजेट है। पाइपलाइन आउटपुट को रिकर्सिवली (recursively) कंप्यूट किया जाता है।
कॉम्बिनेटोरियल विश्लेषण: यह सिद्ध करना कि फ्रेश इंटर-स्टेज मास्किंग मध्यवर्ती चरणों के लीकेज पैरामीटर्स को "मिटा" (erase) देती है, जिससे अंतिम बाउंड केवल अंतिम चरण के पैरामीटर पर निर्भर होता है।
हार्डवेयर-फिथफुल मॉडलिंग: हार्डवेयर रजिस्टर चौड़ाई और रैपअराउंड व्यवहार को ध्यान में रखने के लिए मोंटगोमरी रिडक्शन को मॉडल करना, विशेष रूप से कोलिजन ऑफसेट $2^{w-s}$ का विश्लेषण करना।

मुख्य योगदान
यह शोध पत्र चार प्राथमिक योगदान देता है, जो Lean 4 में औपचारिक रूप से व्यक्त किए गए हैं:

$k$ -स्टेज कंपोजिशन थ्योरम (Theorem 3.1):
यह प्रमेय पिछले 2-स्टेज कंपोजिशन परिणाम को $k \ge 1$ की अनिश्चित गहराई तक सामान्यीकृत करता है। यह सिद्ध करता है कि फ्रेश इंटर-स्टेज मास्किंग के साथ $G_0, \dots, G_{k-1}$ गैजेट्स की एक पाइपलाइन के लिए, आउटपुट के प्रीइमेज की कार्डिनैलिटी इस प्रकार सीमित है:
$| \{ (m, f) : \text{pipeline output} = v \} | \le G_{k-1}.\text{maxMult} \cdot q^{2k-2}$
महत्वपूर्ण रूप से, यह बाउंड लास्ट-स्टेज-डिटरमाइंड (अंतिम चरण द्वारा निर्धारित) है; सभी मध्यवर्ती चरणों के पैरामीटर्स फ्रेश मास्क द्वारा मिटा दिए जाते हैं।
मोंटगोमरी रिडक्शन PF-PINI(2) है (Theorem 4.3):
यह शोध पत्र औपचारिक रूप से सिद्ध करता है कि मोंटगोमरी रिडक्शन PF-PINI(2) गुण को संतुष्ट करता है, जो बैरेट रिडक्शन की संरचना को दर्शाता है। यह प्रदर्शित करता है कि हार्डवेयर-फिथफुल मोंटगोमरी मैप में एक "टू-ब्रांच" संरचना होती है (यह निर्भर करते हुए कि रैपअराउंड होता है या नहीं), जिसके परिणामस्वरूप प्रीइमेज कार्डिनैलिटी अधिकतम 2 होती है। थ्योरम 4.7 आगे इस बाउंड की टाइटनेस (tightness) को स्थापित करती है, यह दिखाते हुए कि मानक मापदंडों (ML-KEM और ML-DSA) के लिए, मल्टीप्लिसिटी ठीक 2 है।
एंड-टू-एंड मल्टीप्लिसिटी बाउंड (Theorem 5.1):
$k$ -स्टेज कंपोजिशन थ्योरम को बैरेट (पेपर 5), मोंटगोमरी (यह पेपर) और बटरफ्लाई (पेपर 4) के विशिष्ट PF-PINI(2) परिणामों के साथ जोड़कर, यह शोध पत्र एक एकीकृत बाउंड स्थापित करता है। किसी भी $k$ -स्टेज पाइपलाइन के लिए जहाँ प्रत्येक स्टेज $\text{maxMult} \le 2$ संतुष्ट करता है, आउटपुट प्रीइमेज कार्डिनैलिटी इस प्रकार सीमित है:
$2 \cdot q^{2k-2}$
यूनिफॉर्म मास्क के साथ प्रथम-क्रम (first-order) प्रोबिंग मॉडल के तहत, यह प्रति-अवलोकन सशर्त संभाव्यता बाउंड $2/q$ के बराबर है, जो पाइपलाइन की गहराई $k$ से स्वतंत्र है।
अनुभवजन्य निष्कर्षों का औपचारिक एंकरिंग (Theorem 5.4):
यह शोध पत्र एक Lean-वेरिफाइड कंडीशनल प्रदान करता है कि यदि पाइपलाइन के किसी भी चरण में $\text{maxMult} \ge 3$ (जैसे, एक अनमास्क्ड स्टेज) है, तो एंड-टू-एंड बाउंड की परिकल्पना विफल हो जाती है। यह "एडम्स ब्रिज" (Adams Bridge) PQC एक्सेलेरेटर (पेपर 1, 2 और बाहरी कार्य) के विशिष्ट अनमास्क्ड कॉन्फ़िगरेशन को गहराई-स्वतंत्र बाउंड की पर्याप्त शर्तों से बाहर होने की पुष्टि करके, पूर्व अनुभवजन्य और संरचनात्मक विश्लेषणों को औपचारिक रूप से एंकर करता है।

परिणाम

1-बिट बैरियर की सार्वभौमिकता: यह शोध पत्र पुष्टि करता है कि "1-बिट बैरियर" (2 की प्रीइमेज कार्डिनैलिटी) दोनों मानक मॉड्यूलर रिडक्शन (बैरेट और मोंटगोमरी) पर लागू होता है जिनका उपयोग NIST PQC हार्डवेयर में किया जाता है।
डेप्थ इंडिपेंडेंस (गहराई से स्वतंत्रता): औपचारिक प्रमाण प्रदर्शित करते हैं कि यदि फ्रेश इंटर-स्टेज मास्किंग का उपयोग किया जाता है और प्रत्येक स्टेज PF-PINI( $\le 2$ ) को संतुष्ट करता है, तो पाइपलाइन में चरणों को जोड़ने से प्रति-अवलोकन लीकेज बाउंड कम नहीं होता है।
सत्यापन स्थिति: संपूर्ण आर्टिफैक्ट तीन थ्योरम मॉड्यूल में 20 घोषणाओं (declarations) से बना है, जो 1,753 जॉब्स को बिना किसी त्रुटि, बिना किसी sorry, और बिना किसी नेटिव निर्णय प्रक्रिया (decision procedure) के सफलतापूर्वक पूरा करता है।

महत्व और दावे
यह शोध पत्र मास्क किए गए NTT हार्डवेयर के लिए एक औपचारिक सत्यापन कार्यक्रम के समापन के रूप में स्थित है। इसका महत्व हार्डवेयर डिजाइनरों के लिए एक मात्रात्मक, मशीन-चेक्ड कंपोजिशनल फाउंडेशन प्रदान करने में निहित है।

प्रमाणन (Certification) के लिए: व्युत्पन्न कार्डिनैलिटी बाउंड ( $2 \cdot q^{2k-2}$ ) आर्किटेक्चर स्तर पर DPA-प्रतिरोध तर्कों के लिए आवश्यक विशिष्ट साक्ष्य प्रदान करता है, जो SILVER और maskVerif जैसे गेट-लेवल टूल्स का पूरक है।
डिजाइनरों के लिए: यह एक निर्देशात्मक समाधान पथ प्रदान करता है: गहराई-स्वतंत्र बाउंड प्राप्त करने के लिए, डिजाइनरों को यह सुनिश्चित करना चाहिए कि प्रत्येक स्टेज PF-PINI( $\le 2$ ) है और चरणों के बीच फ्रेश मास्क डाले गए हैं।
दावों की विनम्रता: लेखक स्पष्ट रूप से कहते हैं कि संभाव्यता और मिन-एन्ट्रॉपी व्याख्याएँ (जैसे, $2/q$ ) कार्डिनैलिटी बाउंड्स के अनौपचारिक सिमेंटिक परिणाम हैं और उन्हें Lean में यांत्रिक रूप से औपचारिक रूप से प्रस्तुत नहीं किया गया है। इसके अलावा, एडम्स ब्रिज विश्लेषण के संबंध में, पेपर केवल यह दावा करता है कि विशिष्ट कॉन्फ़िगरेशन थ्योरम 5.1 की पर्याप्त शर्तों को विफल करते हैं; यह दावा नहीं करता कि हार्डवेयर "टूटा हुआ" या "असुरक्षित" है, यह स्वीकार करते हुए कि वैकल्पिक फ्रेमवर्क या मजबूत मॉडल अलग निष्कर्ष दे सकते हैं। इस कार्य को विशिष्ट कार्यान्वयन पर निर्णायक सुरक्षा निर्णय के बजाय कम्पोजिशनल विश्लेषण के एक उपकरण के रूप में फ्रेम किया गया है।