Partial Derandomization for Leakage-Resilient Shamir's Secret Sharing over Composite Order Fields

तकनीकी सारांश: सम्मिश्र क्रम वाले क्षेत्रों (Composite Order Fields) पर लीकेज-रेज़िलिएंट शमीर सीक्रेट शेयरिंग के लिए आंशिक रैंडमाइजेशन (Partial Derandomization)

1. समस्या विवरण

यह शोध पत्र सम्मिश्र क्रम वाले क्षेत्रों ($\mathbb{F}_{p^d}$ जहाँ $d \ge 2$) पर फिजिकल-बिट लीकेज (physical-bit leakage) के विरुद्ध लचीले शमीर सीक्रेट शेयरिंग (SSS) योजनाओं के लिए स्पष्ट मूल्यांकन स्थानों (explicit evaluation places) के निर्माण को संबोधित करता है।

मानक SSS में, एक गुप्त (secret) को $n$ पक्षों के बीच साझा किया जाता है ताकि कि कोई भी $k$ इसे पुनर्गठित कर सके। जबकि यादृच्छिक निर्माण (रैंडम मूल्यांकन स्थानों को समान रूप से चुनना) स्थानीय लीकेज के विरुद्ध सांख्यिकीय रूप से सुरक्षित ज्ञात हैं, वे विश्वसनीय सार्वजनिक यादृच्छिकता (trusted public randomness) की आवश्यकता रखते हैं। व्यवहार में, हमलावर रैंडम सीड को प्रभावित कर सकते हैं, जिससे योजना को असुरक्षित मूल्यांकन स्थानों की ओर मोड़ा जा सकता है।

पिछले कार्यों ने स्थापित किया कि:

• प्राइम क्षेत्रों ($\mathbb{F}_p$) पर, रैंडम मूल्यांकन स्थान उच्च संभावना के साथ लीकेज रेजिलिएंस प्रदान करते हैं।
• सम्मिश्र क्षेत्रों ($\mathbb{F}_{p^d}$) पर, न्गुयेन (EUROCRYPT 2025) ने एक पूर्ण द्विशाखता (perfect dichotomy) स्थापित की: कोई भी लीनियर कोड-आधारित सीक्रेट शेयरिंग योजना या तो पूर्णतः सुरक्षित (सांख्यिकीय दूरी 0) है या फिजिकल-बिट लीकेज के विरुद्ध पूरी तरह से असुरक्षित है।
• हालाँकि, सम्मिश्र क्षेत्रों के लिए, $k > 2$ या सामान्य ब्लॉक-लीकेज व्यवस्था के लिए कोई स्पष्ट, नियत (deterministic) मूल्यांकन स्थानों का परिवार ज्ञात नहीं था। प्राइम क्षेत्रों के लिए मौजूदा स्पष्ट निर्माण गैर-रेखीय बिट-एक्सट्रैक्शन गुणों पर निर्भर थे जो सम्मिश्र क्षेत्रों के लीनियर कोऑर्डिनेट मैप्स पर लागू नहीं होते हैं।

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

2. कार्यप्रणाली और निर्माण

लेखक एक आंशिक डिरैंडमाइजेशन (partial derandomization) रणनीति का प्रस्ताव करते हैं। $n$ स्वतंत्र रैंडम मूल्यांकन बिंदुओं के बजाय, वे एक यादृच्छिक चुने गए बेस पॉइंट $x_0$ पर एक एकल रैशनल फंक्शन $\Phi$ के इटरेट्स (iterates) के रूप में मूल्यांकन स्थानों का निर्माण करते हैं।

निर्माण:

• फील्ड सेटअप: मान लीजिए $\mathbb{F} = \mathbb{F}_{p^d}$ जिसमें एक प्रिमिटिव एलिमेंट $\alpha$ है।
• स्टेप ऑपरेटर: मोबियस ट्रांसफॉर्मेशन $\Phi(x) = \frac{\alpha x}{x + 1}$ को परिभाषित करें।
• मूल्यांकन स्थान: $n$ मूल्यांकन स्थान $x_j = \Phi^j(x_0)$ के रूप में परिभाषित हैं, जहाँ $j = 0, \dots, n-1$ और $x_0 \in \mathbb{F}^*$ एक यादृच्छिक चुना गया बेस पॉइंट है।
• एंट्रॉपी में कमी: इस योजना को निर्दिष्ट करने के लिए केवल $d \log p$ बिट्स की आवश्यकता होती है ( $x_0$ चुनने के लिए), जो $n$ स्वतंत्र रैंडम बिंदुओं के लिए आवश्यक $nd \log p$ बिट्स की तुलना में एक महत्वपूर्ण कमी है।

मुख्य संरचनात्मक अंतर्दृष्टि:
सुरक्षा विश्लेषण $\Phi$ के विशिष्ट पोल्स (distinct poles) पर निर्भर करता है।

• $\Phi^0(x) = x$ का एक पोल $\infty$ पर है।
• $j \ge 1$ के लिए, $\Phi^j(x)$ का एक विशिष्ट परिमित बिंदु $\mathbb{F}^*$ पर एक पोल है।
• यह "पोल-विशिष्टता" (pole-distinctness) अत्यंत महत्वपूर्ण है। लेखक एक संभावित उम्मीदवार $\Psi(x) = \alpha x$ (शुद्ध डाइलेशन) के विपरीत देखते हैं, जहाँ सभी इटरेट्स का $\infty$ पर एक ही पोल होता है, जिससे सुरक्षा तर्क विफल हो जाता है।

3. तकनीकी दृष्टिकोण

प्रमाण तीन चरणों में आगे बढ़ता है, जो न्गुयेन (2025) द्वारा स्थापित पूर्ण द्विशाखता (perfect dichotomy) का लाभ उठाता है:

1. पूर्ण द्विशाखता (चरण 1):
   यह शोध पत्र इस तथ्य का उपयोग करता है कि $\mathbb{F}_{p^d}$ में कोऑर्डिनेट एक्सट्रैक्शन $\mathbb{F}_p$-लीनियर है। फलस्वरूप, लीकेज मैप लीनियर है। इसका अर्थ है कि विभिन्न सीक्रेट्स के लिए लीकेज डिस्ट्रीब्यूशन के बीच सांख्यिकीय दूरी या तो 0 या 1 होती है। पूर्ण सुरक्षा तब प्राप्त होती है जब लीकेज मैप सर्जेक्टिव (surjective) होता है। यह स्थिति एक टेस्ट मैट्रिक्स $\Theta_{\vec{i}}$ (मूल्यांकन स्थानों और लीकेज पैटर्न से व्युत्पन्न) के $\mathbb{F}_p$ पर फुल कॉलम रैंक होने के समतुल्य है।

2. पार्शियल फ्रैक्शन नॉनडेजेनरेसी (चरण 2):
   टेस्ट मैट्रिक्स के फुल रैंक होने को सिद्ध करने के लिए, लेखक को यह दिखाना होगा कि मूल्यांकन स्थान की घातों (powers) का कोई गैर-तुच्छ लीनियर कॉम्बिनेशन शून्य नहीं होता है। वे एक रैशनल फंक्शन $G_\ell(x) = \sum c_j \eta(i_j) (\Phi^j(x))^\ell$ को परिभाषित करते हैं।
   पार्शियल फ्रैक्शन डिकंपोजिशन का उपयोग करते हुए, वे $\Phi^j$ के विशिष्ट पोल्स का लाभ उठाते हैं। क्योंकि पोल्स विशिष्ट हैं, इसलिए किसी विशिष्ट पोल पर $G_\ell$ का रेसिड्यू (residue) योग के एक एकल पद द्वारा निर्धारित होता है। यदि $G_\ell$ सर्वथा शून्य होता, तो सभी गुणांकों को शून्य होना पड़ता। यह "नॉनडेजेनरेसी" तर्क उन "बुरे" बेस पॉइंट्स $x_0$ की संख्या को सीमित करता है जो रैंक की स्थिति को विफल करते हैं।

3. मल्टी-ब्लॉक विस्तार (चरण 3):
   तर्क को मल्टी-ब्लॉक लीकेज (जहाँ प्रत्येक शेयर के प्रति कई कोऑर्डिनेट्स लीक होते हैं) तक विस्तारित किया गया है। लेखक शेयरों के भीतर लीनियर कॉम्बिनेशन से उत्पन्न होने वाले फील्ड कोएफिशिएंट्स को संभालते हैं, यह दिखाते हुए कि पार्शियल फ्रैक्शन तर्क तब तक मान्य रहता है जब तक कि लीकेज पैटर्न "एडमिसिबल" (प्रत्येक शेयर के लिए विशिष्ट ब्लॉक पोजीशन) हो।

4. मुख्य परिणाम

प्रमेय 1.1 (सिंगल-ब्लॉक लीकेज के विरुद्ध पूर्ण सुरक्षा):
पैरामीटर्स $n = O(d / \log_p d)$ और किसी भी थ्रेशोल्ड $k \ge 2$ के लिए, "बुरे" बेस पॉइंट्स का एक सेट $Bad \subset \mathbb{F}^*$ मौजूद है जिसका आकार $|Bad| \le n + n(dp)^n$ है। किसी भी $x_0 \notin Bad$ के लिए, $\Phi^j(x_0)$ वाले मूल्यांकन स्थानों का उपयोग करने वाली योजना किसी भी सिंगल-ब्लॉक लीकेज पैटर्न के विरुद्ध पूर्णतः सुरक्षित (सांख्यिकीय दूरी ठीक 0) है।

• यह किसी भी प्राइम $p$ के लिए सिंगल फिजिकल-बिट लीकेज प्रति शेयर के विरुद्ध पूर्ण सुरक्षा को दर्शाता है।
• एक अच्छा $x_0$ गारंटीकृत रूप से मौजूद है जब $d > n(1 + \log_p d) + \log_p(2n)$ हो।

प्रमेय 1.2 (मल्टी-ब्लॉक लीकेज):
एक निश्चित एडमिसिबल लीकेज पैटर्न के लिए जिसमें $M$ कुल ब्लॉक्स लीक होते हैं, बुरे सेट का आकार $n + n \cdot p^M$ द्वारा सीमित है। एक अच्छा $x_0$ तब मौजूद होता है जब $M < d - \log_p(2n)$ हो।

• $\le M$ ब्लॉक्स वाले सभी पैटर्न के विरुद्ध सार्वभौमिक सुरक्षा के लिए, $|Bad| \le n + n(dpe)^M$ है, और अस्तित्व $d > M(\frac{5}{2} + \log_p d) + \log_p(2n)$ होने पर गारंटीकृत है।

वर्गीकारक (Classifier):
शोध पत्र एक स्पष्ट वर्गीकारक (एल्गोरिदम 1) प्रदान करता है जो, किसी भी संभावित $x_0$ को दिए जाने पर, सभी लीकेज पैटर्न के लिए फुल-रैंक स्थिति को सत्यापित करता है। यह संरचित निर्माण की सुरक्षा को प्रमाणित करने के लिए एक सुदृढ़ परीक्षण के रूप में कार्य करता है।

5. महत्व और तुलना

यह शोध पत्र निम्नलिखित योगदानों और अंतरों का दावा करता है:

• पूर्ण सुरक्षा बनाम सांख्यिकीय सुरक्षा: सम्मिश्र क्षेत्रों पर पिछले रैंडमाइज्ड निर्माणों के विपरीत, जो सांख्यिकीय सुरक्षा ($\epsilon = 2^{-\Omega(d)}$) प्रदान करते थे, यह निर्माण एक प्रतिबंधित पैरामीटर व्यवस्था के लिए पूर्ण सुरक्षा (सांख्यिकीय दूरी 0) प्राप्त करता है।
• डिरैंडमाइजेशन: यह $nd \log p$ बिट्स से $d \log p$ बिट्स तक योजना को निर्दिष्ट करने के लिए आवश्यक रैंडमनेस को कम करता है, जो कि मूल्यांकन स्थानों को एक-पैरामीटर परिवार ( $\Phi$ के ऑर्बिट) तक सीमित करके किया जाता है।
• स्पष्ट निर्माण: यह $k > 2$ के लिए सम्मिश्र क्षेत्रों पर फिजिकल-बिट लीकेज का प्रतिरोध करने वाला पहला स्पष्ट मूल्यांकन स्थानों का परिवार प्रदान करता है, जो "रैंडम प्लेसेस" प्रतिमान से आगे बढ़ता है।
• सीमाएँ और ट्रेड-ऑफ:
  • $n$ की संख्या $O(d / \log_p d)$ तक सीमित है, जबकि रैंडमाइज्ड निर्माण $O(dk / \log_p d)$ का समर्थन करते हैं। लेखक का अनुमान है कि यह फैक्टर-$k$ की हानि सिंगल-पैरामीटर निर्माणों के लिए स्वाभाविक है।
  • मल्टी-ब्लॉक सार्वभौमिकता वर्तमान में पैटर्न एन्यूमरेशन बॉटलनैक (bottleneck) द्वारा सीमित है, जिसके परिणामस्वरूप $M$ में एक्सपोनेंशियल बैड-सेट बाउंड प्राप्त होता है।
  • निर्माण मोबियस ट्रांसफॉर्मेशन $\Phi(x) = \alpha x / (x+1)$ की विशिष्ट बीजगणितीय संरचना पर निर्भर करता है; वैकल्पिक डाइलेशन $\alpha x$ सुरक्षा प्रदान करने में विफल रहता है।

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