🔢 mathematics

Exact Bias of Linear TRNG Correctors -- Spectral Approach

यह शोध पत्र लीनियर TRNG करेक्टर्स के लिए निकट-इष्टतम (near-optimal), सटीक बायस बाउंड्स प्राप्त करने के लिए एक स्पेक्ट्रल दृष्टिकोण का उपयोग करता है, जो यह प्रकट करता है कि 10% इनपुट बायस के साथ 80-बिट सुरक्षा प्राप्त करने के लिए कोड रेट के 50% से अधिक का त्याग करना आवश्यक है और इसमें महत्वपूर्ण हार्डवेयर लागत आती है।

मूल लेखक: Maciej Skorski, Francisco-Javier Soto, Onur Günlü

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

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

CC BY 4.0

मूल लेखक: Maciej Skorski, Francisco-Javier Soto, Onur Günlü

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

कल्पना कीजिए कि आप एक ऐसी मशीन बनाने की कोशिश कर रहे हैं जो वास्तव में रैंडम नंबर (यादृच्छिक संख्याएँ) उत्पन्न करती है, जैसे कि पासवर्ड तय करने के लिए एक सिक्का उछालना। वास्तविक दुनिया में, भौतिक "सिक्के" (जैसे सर्किट में इलेक्ट्रॉनिक शोर) शायद ही कभी पूर्ण होते हैं। वे थोड़े पक्षपाती हो सकते हैं, जैसे कि "हेड्स" 55% बार और "टेल्स" 45% बार आ सकता है। इस मामूली पक्षपात को बायस (Bias) कहा जाता है।

यदि आप इन थोड़े पक्षपाती सिक्कों का उपयोग सीधे सुरक्षा (जैसे संदेशों को एन्क्रिप्ट करने) के लिए करते हैं, तो एक हैकर अंततः पैटर्न का अनुमान लगा सकता है। इसे ठीक करने के लिए, इंजीनियर एक "सुधारक" (corrector) का उपयोग करते हैं—एक विशेष मशीन जो इन पक्षपाती सिक्कों को लेती है और उन्हें आपस में मिलाकर एक एकल, पूरी तरह से निष्पक्ष सिक्का बनाती है।

यह शोध पत्र एक सर्वश्रेष्ठ संभव मिक्सिंग मशीन बनाने और यह निर्धारित करने के बारे में है कि वह वास्तव में कितनी अच्छी है।

यहाँ लेखकों द्वारा की गई खोजों का विवरण दिया गया, सरल उपमाओं का उपयोग करते हुए:

1. पुराना तरीका बनाम नया तरीका

पुराना तरीका ("सबसे खराब स्थिति" का अनुमान):
पहले, इंजीनियर यह अनुमान लगाने की कोशिश करते थे कि उनकी मिक्सिंग मशीन कितनी निष्पक्ष थी, इसके लिए वे केवल एक सबसे खराब संभव परिदृश्य को देखते थे। यह ऐसा था जैसे कहना, "यदि मेरे पास 100 सिक्कों का एक बैग है, और सबसे खराब सिक्का 10% पक्षपाती है, तो मेरा पूरा बैग बेकार है।" यह तरीका बहुत सुरक्षित था, लेकिन यह अत्यधिक निराशावादी था। इसने इंजीनियरों को बताया कि उन्हें अच्छी सुरक्षा प्राप्त करने के लिए विशाल, महंगी मशीनों की आवश्यकता है, भले ही उनकी मशीनें वास्तव में गणित के सुझाव से कहीं बेहतर काम कर रही हों।

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

उपमा: कल्पना कीजिए कि एक गायक मंडली (choir) है। पुराना तरीका पूरे समूह का निर्णय लेने के लिए केवल सबसे तेज़, बेसुरा गायक सुनता था। नया तरीका पूरे समूह की सद्भाव (harmony) को सुनता है।
परिणाम: उन्होंने पाया कि मिक्सिंग मशीनें पहले के अनुमानों की तुलना में कहीं अधिक बेहतर हैं। उनका नया गणित दिखाता है कि "पक्षपात" पुराने अनुमानों की तुलना में बहुत तेज़ी से गिरता है। वास्तव में, उनके नए अनुमान अक्सर पुराने अनुमानों की तुलना में 10 गुना अधिक सटीक (एक ऑर्डर ऑफ मैग्नीट्यूड) हैं।

2. एक आदर्श मिश्रण का "नुस्खा" (Recipe)

यह शोध पत्र वेट एन्यूमिरेटर (Weight Enumerator) पर आधारित एक विशिष्ट "नुस्खा" पेश करता है।

उपमा: मिक्सिंग मशीन को एक रेसिपी बुक के रूप में सोचें। "वेट एन्यूमिरेटर" उन तरीकों की एक सूची है जिनसे सामग्री (इनपुट बिट्स) को जोड़ा जा सकता है।
खोज: लेखकों ने सिद्ध किया कि यदि आप इस सूची (नुस्खे) को जानते हैं, तो आप बिल्कुल गणना कर सकते हैं कि आउटपुट पूर्णतः रैंडम होने के कितने करीब है। उन्होंने केवल अनुमान नहीं लगाया; उन्होंने सटीक सूत्र दिए।
"स्वीट स्पॉट": उन्होंने दो अलग-अलग प्रकार के गणितीय मापों ( $\ell_2$ और $\ell_\infty$ ) को जोड़ने का एक तरीका खोजा जिससे एक ऐसा परिणाम प्राप्त होता है जो लगभग पूरी तरह से सटीक (tight) है। यह एक 'बेस्ट-केस' और 'वर्स्ट-केस' परिदृश्य के बीच सटीक मध्य मार्ग खोजने जैसा है ताकि वास्तविक उत्तर मिल सके।

3. पूर्णता की लागत (एक समझौता)

शोध पत्र ने इन मशीनों को बनाने की वास्तविक दुनिया की लागत पर भी विचार किया।

उपमा: कल्पना कीजिए कि आप गंदे पानी की एक बाल्टी (पक्षपाती इनपुट) को शुद्ध पानी के एक गिलास (रैंडम आउटपुट) में बदलना चाहते हैं।
- शुद्ध पानी का गिलास पाने के लिए, आपको बहुत सारा गंदा पानी फेंकना होगा।
- जितना अधिक इनपुट पानी पक्षपाती होगा, उतना ही अधिक आपको फेंकना पड़ेगा।
निष्कर्ष: लेखकों ने लगभग 20,000 अलग-अलग मिक्सिंग रेसिपीज़ (कोड) का परीक्षण किया। उन्होंने पाया कि यदि आपका इनपुट थोड़ा भी पक्षपाती है (10% पक्षपात), और आप बहुत उच्च स्तर की सुरक्षा (80-बिट सुरक्षा, जो आधुनिक एन्क्रिप्शन का स्वर्ण मानक है) चाहते हैं, तो आपको अपने डेटा का आधे से अधिक हिस्सा त्यागना होगा।
- आपके पास 100 बिट्स का कच्चा डेटा हो सकता है, लेकिन वास्तव में सुरक्षित परिणाम प्राप्त करने के लिए, आपके पास केवल 40 या 50 बिट्स का उपयोगी आउटपुट हो सकता है।
- यह "बर्बादी" कोई बग नहीं है; यह रैंडमनेस को साफ करने की अंतर्निहित लागत है। आप कुछ भी मुफ्त में नहीं पा सकते।

4. हार्डवेयर वास्तविकता

अंत में, उन्होंने देखा कि कंप्यूटर चिप पर ये मशीनें कितनी जगह लेती हैं।

उपमा: एक बेहतर फिल्टर बनाने के लिए अधिक पाइप और वाल्वों की आवश्यकता होती है।
निष्कर्ष: सुरक्षा (Security), गति (Rate) और लागत (Cost) के बीच एक सीधा संबंध है।
- यदि आप उच्चतम सुरक्षा चाहते हैं, तो आपको एक बड़ी, अधिक जटिल मशीन (अधिक गेट इक्विवेलेंट्स या हार्डवेयर स्पेस) की आवश्यकता होगी।
- यदि आप स्थान बचाने के लिए मशीन को छोटा बनाने की कोशिश करते हैं, तो या तो आपको कम सुरक्षा मिलेगी या आपको अपने इनपुट डेटा का और भी अधिक हिस्सा त्यागना होगा।

सारांश

यह शोध पत्र रैंडम नंबर जनरेटर के पीछे के गणित के लिए एक "यूजर मैनुअल" है। यह इंजीनियरों को बताता है:

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

लेखकों ने एक नए प्रकार का रैंडम नंबर जनरेटर आविष्कार नहीं किया; उन्होंने बस हमारे पास मौजूद मौजूदा जनरेटरों को मापने के लिए एक बहुत अधिक सटीक और सटीक पैमाना दिया है।

तकनीकी सारांश: लीनियर TRNG करेक्टर्स का सटीक बायस (Exact Bias): स्पेक्ट्रल दृष्टिकोण

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

ट्रू रैंडम नंबर जनरेटर्स (TRNGs) भौतिक घटनाओं से एंट्रॉपी निकालते हैं, फिर भी उनके कच्चे आउटपुट में अक्सर सांख्यिकीय खामियां होती हैं, जैसे कि बायस (bias) और सहसंबंध (correlations), जो क्रिप्टोग्राफिक आवश्यकताओं का उल्लंघन करते हैं। जबकि रैंडमनेस एक्सट्रैक्टर्स इन खामियों को सुधारने के लिए एक सैद्धांतिक ढांचा प्रदान करते हैं, हार्डवेयर कार्यान्वयन सरल निर्माणों को प्राथमिकता देते हैं। लीनियर करेक्टर्स, जिन्हें $Y = GX $(जहाँ$ G $एक बाइनरी मैट्रिक्स है,$ X $कच्चा इनपुट है, और$ Y$ सुधारा गया आउटपुट है) द्वारा परिभाषित किया जाता है, व्यापक रूप से उपयोग किए जाते हैं क्योंकि वे केवल XOR गेट्स पर निर्भर करते हैं।

हालाँकि, इन लीनियर करेक्टर्स के लिए मौजूदा सुरक्षा विश्लेषण अक्सर $\ell_\infty$ बाउंड्स या व्यक्तिगत इनपुट बायस के सरल योग पर निर्भर करते हैं। लेखक तर्क देते हैं कि ये तकनीकें अक्सर ऐसी सुरक्षा अनुमान प्रदान करती हैं जो अत्यधिक रूढ़िवादी (conservative) होती हैं और यूनिफॉर्म डिस्ट्रीब्यूशन (uniform distribution) से वास्तविक टोटल वेरिएशन डिस्टेंस (total variation distance - $\ell_1$ नॉर्म) से बहुत दूर होती हैं। यह अंतर सटीक सुरक्षा मूल्यांकन में बाधा डालता है, जिससे कोड रेट (कंप्रेशन दक्षता) या हार्डवेयर जटिलता में अनावश्यक त्याग करना पड़ सकता है।

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

यह शोध पत्र बायस्ड कॉइन मॉडल (biased coin model) के तहत लीनियर करेक्टर्स के आउटपुट डिस्ट्रीबशन को चरित्रित करने के लिए एक फूरियर-एनालिटिक दृष्टिकोण (Fourier-analytic approach) का उपयोग करता है, जहाँ इनपुट बिट्स स्वतंत्र होते हुए भी बायस्ड होते हैं।

फूरियर एक्सपेंशन (Fourier Expansion): लेखक बोलियन क्यूब (boolean cube) पर फलनों के फूरियर एक्सपेंशन का उपयोग करते हैं। आउटपुट $Y$ के प्रोबेबिलिटी मास फंक्शन को फूरियर गुणांकों (Fourier coefficients) के संदर्भ में व्यक्त करके, वे डिस्ट्रीब्यूशन को मैट्रिक्स $G$ द्वारा जनरेट किए गए लीनियर कोड के वेट एन्यूमिरेटर (weight enumerator) से जोड़ते हैं।
नॉर्म कैरेक्टराइजेशन (Norm Characterization):
- $\ell_\infty$ नॉर्म: वे किसी भी आउटपुट की अधिकतम संभावना के लिए एक सटीक फॉर्मूला प्राप्त करते हैं, जो मिन-एंट्रॉपी कंडेन्सर (min-entropy condenser) के रूप में सुधारक की प्रभावशीलता को स्पष्ट करता है। इसे कोड के वेट एन्यूमिरेटर पॉलीनोमियल $W_G(\delta)$ के रूप में व्यक्त किया जाता है।
- $\ell_2$ नॉर्म: प्लैंचर के प्रमेय (Plancherel's theorem) का उपयोग करते हुए, वे यूनिफॉर्मिटी से $\ell_2$ दूरी के सटीक लक्षण वर्णन को स्थापित करते हैं। यह रेनी एंट्रॉपी (Rényi entropy) और एन्क्रिप्शन संदर्भों में अविभेदनीयता (indistinguishability) से संबंधित है।
- $\ell_1$ नॉर्म (टोटल वेरिएशन): प्राप्त $\ell_\infty$ और $\ell_2$ बाउंड्स के बीच इंटरपोलेशन (interpolation) का उपयोग करके, लेखक टोटल वेरिएशन डिस्टेंस के लिए लगभग सटीक (nearly tight) ऊपरी और निचली सीमाएं (upper and lower bounds) निर्मित करते हैं।
कोड थ्योरेटिक फ्रेमवर्क (Code Theoretic Framework): विश्लेषण यह मानता है कि इनपुट बिट्स $X_i$ स्वतंत्र हैं जिनका बायस $\delta_i = 1 - 2p_i$ है। परिणाम $W_G(x) = \sum A_w x^w$ वाले वेट एन्यूमिरेटर पॉलीनोमियल का उपयोग करके संक्षिप्त रूप में व्यक्त किए गए हैं, जहाँ $A_w$ हैमिंग वेट $w$ वाले कोडवर्ड्स की संख्या है।

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

1. सटीक फूरियर-एनालिटिक लक्षण वर्णन (Exact Fourier-Analytic Characterization)

यह शोध पत्र लीनियर करेक्टर्स के लिए यूनिफॉर्मिटी से $\ell_\infty$ और $\ell_2$ दूरियों के लिए पहले सटीक फॉर्मूले प्रदान करता है, जो सीधे कोड वेट एन्यूमिरेटर्स के माध्यम से व्यक्त किए गए हैं। यह पिछले कार्यों का विस्तार करता है जो अक्सर ढीले बाउंड्स या विशिष्ट धारणाओं पर निर्भर थे।

2. इंटरपोलेशन के माध्यम से लगभग सटीक $\ell_1$ बाउंड्स (Nearly Tight $\ell_1$ Bounds via Interpolation)

मुख्य सैद्धांतिक योगदान टोटल वेरिएशन डिस्टेंस ( $\ell_1$ नॉर्म) के लिए बाउंड्स का व्युत्पन्न है जो पिछले अनुमानों की तुलना में काफी अधिक सटीक (sharper) हैं। एक कोड के वेट एन्यूमिरेटर $W_G$ और इनपुट बाय $\delta$ के लिए, टोटल वेरिएशन डिस्टेंस इस प्रकार सीमित है:
$\frac{W_G(\delta^2) - 1}{W_G(\delta) - 1} \leq \|P_Y - P_{U_k}\|_1 \leq \sqrt{W_G(\delta^2) - 1}$
ये बाउंड्स व्यावहारिक रूप से दिलचस्प सुरक्षा स्तरों के लिए $\ell_\infty$ -आधारित पूर्व अनुमानों की तुलना में एक परिमाण (order of magnitude) बेहतर हैं।

3. ट्रेड-ऑफ का अनुभवजन्य मूल्यांकन (Empirical Evaluation of Trade-offs)

लेखकों ने लगभग 20,000 लीनियर कोड्स (Reed-Muller, BCH, और साइक्लिक कोड्स सहित) पर एक बड़े पैमाने पर अनुभवजन्य अध्ययन किया। उन्होंने निम्नलिखित के बीच मौलिक ट्रेड-ऑफ को मात्रात्मक रूप से निर्धारित किया:

कंप्रेशन एफिशिएंसी (कोड रेट): अनुपात $k/n$ ।
क्रिप्टोग्राफिक सुरक्षा: बायस रिडक्शन का स्तर।
हार्डवेयर जटिलता: गेट इक्विवेलेंट्स (Gate Equivalents - GE) में अनुमानित।

परिणाम (Results)

सुरक्षा बाउंड्स और सटीकता (Security Bounds and Tightness)

स्मॉल बायस रिजीम (Small Bias Regime): छोटे इनपुट बाय $\delta \ll 1$ के लिए, टोटल वेरिएशन डिस्टेंस $\Theta(\delta^d)$ के रूप में घटता है, जहाँ $d$ कोड का न्यूनतम दूरी (minimum distance) है। यह पूर्व $\ell_\infty$ -आधारित बाउंड्स के विपरीत है जो अक्सर $\sqrt{\delta}$ या कम अनुकूल स्केलिंग पर निर्भर होने का सुझाव देते थे।
सुधार का परिमाण (Magnitude of Improvement): Reed-Muller और BCH कोड्स के साथ तुलना दर्शाती है कि नए बाउंड्स सख्त (tighter) सुरक्षा आकलन प्रदान करते हैं, जो व्यावहारिक पैरामीटर रेंज में अक्सर एक ऑर्डर ऑफ मैग्नीट्यूड के करीब सुधार करते हैं।
सटीकता (Tightness): "अच्छे" कोड्स (जिनका वेट डिस्ट्रीब्यूशन लगभग बाइनोमियल होता है) के लिए, प्राप्त लोअर और अपर बाउंड्स के बीच का अंतर कम है, जिससे $\sqrt{W_G(\delta^2) - 1}$ सटीक टोटल वेरिएशन डिस्टेंस के लिए एक विश्वसनीय प्रॉक्सी बन जाता है।

रेट–सिक्योरिटी–कॉस्ट ट्रेड-ऑफ (Rate–Security–Cost Trade-offs)

सुरक्षा लागत (Security Cost): महत्वपूर्ण इनपुट बाय (जैसे 10%) के साथ उच्च सुरक्षा (जैसे 80-बिट सुरक्षा) प्राप्त करने के लिए आमतौर पर कोड रेट के 50% से अधिक का त्याग करना आवश्यक होता है।
हार्डवेयर लागत (Hardware Cost): उच्च सुरक्षा स्तर आम तौर पर बढ़े हुए हार्डवेयर खर्च (गेट इक्विवेलेंट्स में मापा गया) के साथ सह-संबंधित होते हैं।
पारेटो फ्रंटियर (Pareto Frontier): अध्ययन यह रेखांकित करता है कि साइक्लिक कोड्स अक्सर पारेटो फ्रंटियर पर स्थित होते हैं, जो कार्यान्वयन लागत, सुरक्षा और रेट के बीच एक अनुकूल संतुलन प्रदान करते हैं।

महत्व और दावे (Significance and Claims)

यह शोध पत्र दावा करता है कि इसने लीनियर TRNG करेक्टर्स के लिए निकट-इष्टतम (near-optimal) सुरक्षा बाउंड्स स्थापित किए हैं, जो उन अत्यधिक रूढ़िवादी अनुमानों से आगे निकल गए हैं जो ऐतिहासिक रूप से इस क्षेत्र में हावी रहे हैं। विश्लेषण को स्पेक्ट्रल (फूरियर) दृष्टिकोण में बदलकर, लेखक यह प्रदर्शित करते हैं कि टोटल वेरिएशन डिस्टेंस का इनपुट बाय पर निर्भरता कोड के पूर्ण न्यूनतम-दूरी (minimum-distance) पद के समानुपाती है, न कि इसके वर्गमूल के।

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