💻 computer science

Machine-Checked Cardinality Bounds for Masked Barrett Reduction: A 1-Bit Side-Channel Leakage Barrier in Post-Quantum Cryptographic Hardware

यह शोध पत्र पोस्ट-क्वांटम क्रिप्टोग्राफी में मास्क्ड बैरेट रिडक्शन (masked Barrett reduction) के लिए एक सार्वभौमिक "1-बिट बैरियर" (1-Bit Barrier) स्थापित करने हेतु लीन 4 (Lean 4) में एक मशीन-चेक्ड प्रमाण प्रस्तुत करता है, जो यह प्रदर्शित करता है कि इसके आंतरिक वायर मैप्स (internal wire maps) का प्रीइमेज कार्डिनैलिटी (preimage cardinality) अधिकतम दो है, जिससे अधिकतम एक बिट का मिन-एन्ट्रॉपी लॉस (min-entropy loss) सुनिश्चित होता है और ML-KEM एवं ML-DSA के लिए सुरक्षित प्राइम-फील्ड PINI कंपोजिशन (Prime-Field PINI compositions) के निर्माण को सक्षम बनाया जाता है।

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

प्रकाशित 2026-04-28

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

CC BY 4.0

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

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

मुख्य चित्र: डिजिटल रहस्यों की सुरक्षा

कल्पना कीजिए कि आप डिजिटल रहस्यों को सुरक्षित रखने के लिए एक उच्च-सुरक्षा तिजोरी (एक कंप्यूटर चिप) बना रहे हैं। यह सुनिश्चित करने के लिए कि कोई भी बिजली की खपत या इलेक्ट्रोमैग्नेटिक तरंगों (एक "साइड-चैनल अटैक") को सुनकर आपके रहस्यों को चुरा न सके, आप मास्किंग (masking) नामक तकनीक का उपयोग करते हैं।

मास्किंग को अपने गुप्त नंबर को एक बॉक्स के अंदर रखने जैसा समझें, और फिर दुनिया को दिखाने से पहले उसमें एक रैंडम, बदलती हुई संख्या जोड़ दें। यदि आप इसे पूरी तरह से करते हैं, तो जासूस को केवल रैंडम शोर दिखाई देगा और उसे आपके रहस्य के बारे में कुछ भी पता नहीं चलेगा।

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

समस्या: "दो-दरवाजों" वाला जाल

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

हालाँकि, बैरेट रिडक्शन अलग है। इसमें एक "कंडीशनल" (सशर्त) चरण होता है। एक ऐसे गलियारे की कल्पना करें जिसमें सड़क का एक दोराहा है:

दरवाजा A: यदि गुप्त नंबर छोटा है, तो आप बाईं ओर जाते हैं।
दरजा B: यदि गुप्त नंबर बड़ा है, तो आप दाईं ओर जाते हैं।

लेखकों ने पाया कि इस दोराहे के कारण, तार (wire) पर एक एकल आउटपुट वैल्यू दो अलग-अलग रैंडम मास्क द्वारा बनाई जा सकती है, न कि केवल एक द्वारा।

डर: यदि कोई हमलावर आउटपुट देखता है, तो वह सोच सकता है, "आहा! यह मास्क A या मास्क B से आ सकता है। मैंने क्षेत्र को सीमित कर दिया है!"
वास्तविकता: लेखकों ने सिद्ध किया कि यह कभी भी दो से अधिक नहीं हो सकता। यह तीन, चार या सौ कभी नहीं होगा। यह सख्ती से 0, 1, या 2 है।

"1-बिट बैरियर" (1-Bit Barrier)

शोध पत्र इस खोज को 1-बिट बैरियर कहता है।

यहाँ उपमा दी गई है:
कल्पना कीजिए कि आप एक पासवर्ड का अनुमान लगा रहे हैं।

परफेक्ट सुरक्षा: आपके पास 1,000,000 संभावित पासवर्ड हैं, और हमलावर को पता ही नहीं है कि वह कौन सा है।
बैरेट लीक: "दो-दरवाजों" वाले प्रभाव के कारण, हमलावर को यह एहसास हो सकता है कि, "यह या तो पासवर्ड A है या पासवर्ड B।" उन्होंने क्षेत्र को 1,000,000 से घटाकर केवल 2 कर दिया है।

गणितीय शब्दों में, क्षेत्र को 2 संभावनाओं तक सीमित करने से आपकी सुरक्षा में ठीक 1 बिट की कमी आती है (क्योंकि $2^1 = 2$ )।

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

"मशीन-चेक्ड" (Machine-Checked) का वादा

हम इस पर भरोसा क्यों करें? आमतौर पर, सुरक्षा प्रमाण कागज पर लिखे जाते हैं और मनुष्यों द्वारा जांचे जाते हैं, जो गलतियाँ कर सकते हैं।

शोध पत्र का दृष्टिकोण: लेखकों ने प्रमाण लिखने के लिए Lean 4 नामक एक कंप्यूटर प्रोग्राम का उपयोग किया।
उपमा: एक इंसान द्वारा यह कहने के बजाय कि "मुझे लगता है कि यह पुल सुरक्षित है," उन्होंने एक रोबोट बनाया जिसने पुल के डिज़ाइन लॉजिक के हर एक बोल्ट, बीम और पेंच की जांच की। रोबोट ने "जीरो एरर्स" (या कंप्यूटर के शब्दों में "जीरो सॉरी") रिपोर्ट किया।
परिणाम: यह केवल एक सिद्धांत नहीं है; यह एक गणितीय रूप से सत्यापित प्रमाण है जो ML-KEM और ML-DSA जैसे वर्तमान मानकों में उपयोग किए जाने वाले किसी भी मॉड्यूल (किसी भी आकार के गुप्त नंबर) के लिए काम करता है।

"एडम्स ब्रिज" चिप क्यों विफल हुआ

यह पेपर यह भी समझाता है कि एडम्स ब्रिज (Adams Bridge) नामक एक विशिष्ट चिप डिज़ाइन को पिछले अध्ययनों में असुरक्षित क्यों पाया गया था।

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

निष्कर्षों का सारांश

त्रिरूपता (Trichotomy): बैरेट रिडक्शन के पीछे का गणित आश्चर्यजनक रूप से सरल है। किसी भी आउटपुट के लिए, वहां पहुँचने के तरीकों की संख्या हमेशा 0, 1, या 2 होती है। कभी अधिक नहीं।
1-बिट सीमा: इसका अर्थ है कि इस प्रक्रिया में एक एकल तार से हमलावर अधिकतम कितनी जानकारी चुरा सकता है, वह 1 बिट है।
प्रमाण: इसे एक कंप्यूटर प्रूफ असिस्टेंट (Lean 4) द्वारा शून्य त्रुटियों के साथ सत्यापित किया गया है, जो हार्डवेयर डिजाइनरों के लिए एक स्वर्ण-मानक गारंटी है।
समाधान: पूरे सिस्टम को सुरक्षित रखने के लिए, हार्डवेयर डिजाइनरों को गणना के प्रत्येक चरण के बीच रैंडम मास्क को रिफ्रेश करना सुनिश्चित करना चाहिए। यदि वे ऐसा करते हैं, तो 1-बिट बैरियर पूरे पाइपलाइन की रक्षा करता है।

संक्षेप में: लेखों ने एक विशिष्ट एन्क्रिप्शन चरण के गणित में एक छोटी, अपरिहार्य दरार पाई, यह सिद्ध किया कि वह दरार कितनी बड़ी है (1 बिट से अधिक नहीं), और यह दिखाया कि बाकी की तिजोरी को कैसे सील किया जाए ताकि वह दरार मायने न रखे।

यहाँ शोध पत्र "Machine-Checked Cardinality Bounds for Masked Barrett Reduction: A 1-Bit Side-Channel Leakage Barrier in Post-Quantum Cryptographic Hardware" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

ML-KEM (FIPS 203) और ML-DSA (FIPS 204) जैसे पोस्ट-क्वांटम क्रिप्टोग्राफी (PQC) मानक भारी रूप से नंबर थ्योरेटिक ट्रांसफॉर्म (NTT) पाइपलाइनों पर निर्भर करते हैं। ये पाइपलाइनें रैखिक "बटरफ्लाई" चरणों और गैर-रैखिक मॉड्यूलर रिडक्शन चरणों से बनी होती हैं, जिन्हें आमतौर पर बैरेट रिडक्शन (Barrett reduction) का उपयोग करके लागू किया जाता है।

जबकि मौजूदा औपचारिक सत्यापन ढाँचे (ISW, t-SNI, PINI, DOM) $GF(2) $पर बूलियन मास्किंग के लिए मजबूत गारंटी प्रदान करते हैं, वे **प्राइम फील्ड्स ($ \mathbb{Z}_q$) पर अरिथमेटिक मास्किंग** के लिए, विशेष रूप से बैरेट रिडक्शन के लिए, मशीन-चेक्ड लक्षण वर्णन (characterizations) की कमी रखते हैं।

अंतराल (The Gap): हार्डवेयर कार्यान्वयन (जैसे, "एडम्स ब्रिज" डिज़ाइन) अक्सर साइड-चैनल कमजोरियों से ग्रस्त होते हैं क्योंकि बैरेट रिडक्शन में गैर-रैखिक कंडीशनल सबट्रैक्शन उस अफ़ाइन संरचना (affine structure) को तोड़ देता है जिसे मानक कंपोजिशन थ्योरम द्वारा माना जाता है।
प्रश्न: प्रथम-क्रम (first-order) अरिथमेटिक मास्किंग के तहत, बैरेट रिडक्शन सर्किट के आंतरिक तारों (internal wires) का सटीक लीकेज बाउंड क्या है? पिछले उपकरण एक सार्वभौमिक, मशीन-चेक्ड उत्तर प्रदान करने में सक्षम नहीं थे, जिससे FIPS 140-3 प्रमाणन में अनिश्चितता बनी हुई थी।

2. कार्यप्रणाली (Methodology)

लेखक Lean 4 प्रूफ असिस्टेंट और Mathlib लाइब्रेरी का उपयोग करके एक औपचारिक सत्यापन दृष्टिकोण (formal verification approach) अपनाते हैं।

औपचारिकीकरण (Formalization): वे $\mathbb{Z}_q$ (जहाँ $q$ मॉडुलस है) पर बीजगणितीय रूप से बैरेट इंटरनल वायर मैप को परिभाषित करते हैं। मैप $f_x(m)$ एक गुप्त $x$ और एक रैंडम मास्क $m$ को लेता है, और एक कंडीशनल सबट्रैक्शन द्वारा निर्धारित दो-शाखा (two-branch) संरचना के आधार पर आउटपुट उत्पन्न करता है।
प्रूफ रणनीति: विशिष्ट उदाहरणों का अनुकरण करने के बजाय, वे सार्वभौमिक प्रमेय सिद्ध करते हैं जो सभी $q > 0$ और शिफ्ट पैरामीटर $s$ के लिए मान्य हैं।
मुख्य अवधारणा: वे प्रीइमेज कार्डिनैलिटी (preimage cardinality) का विश्लेषण करते हैं: एक निश्चित गुप्त $x$ और एक विशिष्ट आउटपुट मान $v$ के लिए, कितने अलग-अलग मास्क $m$ ने $v$ उत्पन्न किया होगा?
टूलचेन: इस आर्टिफैक्ट में 12 सिद्ध परिणाम शामिल हैं जिनमें शून्य sorry (कोई अपूर्ण प्रमाण नहीं) है, यह सुनिश्चित करता है कि प्रत्येक चरण Lean द्वारा कर्नेल-वेरिफाइड है।

3. मुख्य योगदान (Key Contributions)

A. ट्राइकोटॉमी थ्योरम (The Trichotomy Theorem)

यह शोध पत्र सिद्ध करता है कि बैरेट इंटरनल वायर मैप एक तीन-मूल्य प्रीइमेज संरचना (three-valued preimage structure) प्रदर्शित करता है। किसी भी गुप्त $x$ और किसी भी आउटपुट $v$ के लिए, मास्क $m$ की संख्या जिससे $f_x(m) = v$ होता है, ठीक 0, 1, या 2 है।

तंत्र (Mechanism): कंडीशनल सबट्रैक्शन दो अफ़ाइन शाखाओं (translations in $\mathbb{Z}_q$ ) का निर्माण करता है। किसी भी मान का प्रीइमेज अधिकतम दो उम्मीदवारों का उपसमुच्चय है: $\{x - v, x - v + r\}$ , जहाँ $r = 2^s \mod q$ ।
सार्वभौमिकता: यह किसी भी मॉडुलस $q$ और शिफ्ट $s$ के लिए सत्य है, जो विशिष्ट PQC मापदंडों से स्वतंत्र है।

B. 1-बिट बैरियर (The 1-Bit Barrier)

ट्राइकोटॉमी के आधार पर, लेखक एक सार्वभौमिक लीकेज बाउंड स्थापित करते हैं:

मैक्स-मल्टीप्लिसिटी (Max-Multiplicity): चूंकि एक एकल आउटपुट उत्पन्न करने वाले मास्क की अधिकतम संख्या 2 है, इसलिए एक विशिष्ट आउटपुट मान को देखने की अधिकतम संभावना $2/q$ है।
मिन-एन्ट्रॉपी बाउंड (Min-Entropy Bound): $H_\infty(\text{output} \mid x)$ का कंडीशनल मिन-एन्ट्रॉपी बाउंड $\log_2(q) - 1$ है।
व्याख्या: बैरेट रिडक्शन प्रथम-क्रम प्रोबिंग के तहत प्रति आंतरिक तार अधिकतम 1 बिट की मिन-एन्ट्रॉपी लीक करता है। यह एक "रूढ़िवादी" (conservative) बाउंड है क्योंकि कई आउटपुट मान अप्राप्य (preimage count = 0) हैं, जिसका अर्थ है कि वास्तविक लीकेज अक्सर 1 बिट से काफी कम होता है।

C. PF-PINI फ्रेमवर्क

लेखक $\mathbb{Z}_q$ पर अरिथमेटिक गैजेट्स के लिए एक नया सुरक्षा मीट्रिक, प्राइम-फील्ड PINI (PF-PINI) पेश करते हैं:

परिभाषा: एक गैजेट PF-PINI( $k$ ) है यदि प्रीइमेज कार्डिनैलिटी $k$ द्वारा सीमित है।
इंस्टेंशिएशन (Instantiations):
- बटरफ्लाई स्टेज: PF-PINI(1) को संतुष्ट करते हैं (परफेक्ट बायजेक्शन, मास्क के अलावा शून्य लीकेज)।
- बैरेट रिडक्शन: PF-PINI(2) को संतुष्ट करता है (1-बिट बैरियर)।
कंपोजिशन अवलोकन: वे देखते हैं (हालांकि अभी तक औपचारिक रूप से सिद्ध नहीं किया गया है) कि यदि पाइपलाइन चरणों को ताज़ा इंटर-स्टेज मास्किंग (fresh inter-stage masking) द्वारा अलग किया जाता है, तो कंपोज्ड पाइपलाइन का मैक्स-मल्टीप्लिसिटी $\max(k_1, k_2)$ होता है। यह दर्शाता है कि 1-बिट बैरियर पूरे NTT पाइपलाइन में प्रसारित होता है।

4. परिणाम और विश्लेषण (Results and Analysis)

मशीन-चेक्ड प्रूफ: आर्टिफैक्ट में 12 सत्यापित प्रमेय शामिल हैं, जिसमें ट्राइकोटॉमी, टाइटनेस प्रूफ (यह दिखाने के लिए कि count=2 प्राप्त किया जा सकता है), और PF-PINI इंस्टेंशिएशन शामिल हैं।
सपोर्ट गैप की खोज: विश्लेषण "अप्राप्य" (unreachable) आउटपुट मानों को प्रकट करता है (प्रीइमेज काउंट = 0)। यह एक सुरक्षा विशेषता है, बग नहीं, क्योंकि यह हमलावर की प्रभावी जानकारी को कम करता है।
एडम्स ब्रिज केस स्टडी: शोध पत्र "एडम्स ब्रिज" हार्डवेयर कार्यान्वयन का विश्लेषण करता है:
- इंट्रा-स्टेज विफलता: पिछले कार्यों (पेपर 1 और 2) ने मध्यवर्ती मास्किंग के बिना शेयर इंटरेक्शन के कारण कमजोरियों को दिखाया था।
- इंटर-स्टेज विफलता: यह पेपर पहचानता है कि एडम्स ब्रिज चरणों के बीच ताज़ा मास्किंग लगाने में विफल रहता है। फलस्वरूप, PF-PINI कंपोजिशन बाउंड लागू नहीं होता है, जिससे लीकेज $\max(k_1, k_2)$ के बजाय $k_1 \times k_2$ तक बढ़ सकता है। यह समझाता है कि क्यों व्यक्तिगत बैरेट गेट्स के लिए 1-बिट बैरियर मौजूद होने के बावजूद यह डिज़ाइन असुरक्षित है।
मात्रात्मक प्रभाव (Quantitative Impact):
- ML-KEM ( $q=3329$ ) के लिए: लीकेज $\le 1$ बिट (मिन-एन्ट्रॉपी $\ge 10.70$ बिट्स)।
- ML-DSA ( $q=8,380,417$ ) के लिए: लीकेज $\le 1$ बिट (मिन-एन्ट्रॉपी $\ge 21.99$ बिट्स)।

5. महत्व (Significance)

प्रमाणन तत्परता (Certification Readiness): 1-बिट बैरियर हार्डवेयर डिजाइनरों के लिए एक सार्वभौमिक, मशीन-चेक्ड प्रमाण प्रदान करता है। यह मूल्यांकनकर्ताओं को विशिष्ट पैरामीटर सेटों को पुन: सत्यापित किए बिना बैरेट-आधारित कार्यान्वयन को FIPS 140-3 के लिए प्रमाणित करने की अनुमति देता है।
डिज़ाइन मार्गदर्शन: यह स्पष्ट करता है कि सुरक्षा के लिए प्राथमिक वास्तुशिल्प (architectural) आवश्यकता ताज़ा इंटर-स्टेज मास्किंग है। यदि इसे लागू किया जाता है, तो बैरेट रिडक्शन की गैर-रैखिक प्रकृति पूरे NTT पाइपलाइन की सुरक्षा को नगण्य 1-बिट हानि से अधिक खतरे में नहीं डालती है।
पद्धतिगत बदलाव (Methodological Shift): यह शोध पत्र साइड-चैनल विश्लेषण को अनुभवजन्य सिमुलेशन और SAT-आधारित चेकिंग से हटाकर कर्नेल-वेरिफाइड बीजगणितीय प्रमाणों की ओर ले जाता है, जो PQC हार्डवेयर सत्यापन के लिए एक नया मानक स्थापित करता है।
फाइव-पेपर प्रोग्राम को पूरा करना: यह कार्य श्रृंखला के पिछले शोध पत्रों के अंतराल को भरता है, जो टूल निर्माण (पेपर 1) और हमले के परिमाणीकरण (पेपर 2) से आगे बढ़कर, बीजगणितीय आधार (पेपर 3), रैखिक संरचना (पेपर 4), और अंततः गैर-रैखिक लक्षण वर्णन (पेपर 5) तक पहुँचता है।

6. सीमाएँ और भविष्य का कार्य (Limitations and Future Work)

कंपोजिशन प्रूफ: यह दावा कि ताज़ा मास्किंग के साथ $\max(k_1, k_2)$ लागू होता है, वर्तमान में एक अवलोकन है, एक औपचारिक प्रमेय नहीं।
उच्च-क्रम मास्किंग (Higher-Order Masking): परिणाम प्रथम-क्रम मास्किंग ( $t=1$ ) तक सीमित हैं। उच्च-क्रम सुरक्षा के लिए कई तारों (wires) के संयुक्त प्रीइमेज का विश्लेषण करने की आवश्यकता है।
एन्ट्रॉपी औपचारिकीकरण: जबकि बीजगणितीय बाउंड सिद्ध है, सूचना-सैद्धांतिक मिन-एन्ट्रॉपी बाउंड अभी भी Mathlib में पूरी तरह से शामिल नहीं हुए मानक परिभाषाओं पर निर्भर है।
अन्य रिडक्शन: परिणाम बैरेट रिडक्शन के लिए विशिष्ट हैं; मोंटगोमरी और स्कूलबुक रिडक्शन के लिए अलग विश्लेषण की आवश्यकता होगी।

संक्षेप में, यह शोध पत्र स्थापित करता है कि बैरेट रिडक्शन प्रथम-क्रम अरिथमेटिक मास्किंग के तहत मौलिक रूप से सुरक्षित है, जो प्रति तार 1 बिट से अधिक जानकारी लीक नहीं करता है, बशर्ते पाइपलाइन चरणों के बीच ताज़ा मास्किंग लागू की जाए। यह अगली पीढ़ी के PQC हार्डवेयर को सुरक्षित करने के लिए एक कठोर गणितीय आधार प्रदान करता है।