Asymptotically Ideal Hierarchical Secret Sharing Based on CRT for Integer Ring

यहाँ शोध पत्र "Asymptotically Ideal Hierarchical Secret Sharing Based on CRT for Integer Ring" का विस्तृत तकनीकी सारांश दिया गया है।

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

सीक्रेट शेयरिंग (SS) योजनाएँ एक गुप्त (secret) को प्रतिभागियों के बीच इस प्रकार वितरित करने की अनुमति देती हैं कि केवल अधिकृत उपसमुच्चय (authorized subsets) ही इसे पुनर्गठित (reconstruct) कर सकें। जबकि मानक $(t, n)$-थ्रेशोल्ड योजनाएँ सभी प्रतिभागियों के साथ समान व्यवहार करती हैं, वास्तविक दुनिया के परिदृश्य अक्सर पदानुक्रमित गुप्त साझाकरण (Hierarchical Secret Sharing - HSS) की मांग करते हैं, जहाँ प्रतिभागियों को अलग-अलग अधिकार थ्रेशोल्ड वाले स्तरों (levels) में विभाजित किया जाता है।

मौजूदा HSS योजनाएँ महत्वपूर्ण समझौतों (trade-offs) का सामना करती हैं:

• आदर्श योजनाएँ (Information Rate $\rho=1$): बिर्कहोफ इंटरपोलेशन या पॉलीमेट्रॉइड्स पर आधारित योजनाएँ आदर्श हैं लेकिन अक्सर डीलर के लिए घातांकीय (exponential) गणना समय या जटिल मैट्रिक्स सत्यापन की आवश्यकता होती है।
• CRT-आधारित योजनाएँ: चाइनीज रिमाइंडर थ्योरम (CRT) का उपयोग करने वाली योजनाएँ लचीले शेयर आकार और बहुपद (polynomial) जटिलता प्रदान करती हैं। हालाँकि, पिछली CRT-आधारित HSS योजनाओं में दो में से एक दोष होता है:
  • सुरक्षा संबंधी खामियाँ: कुछ प्रस्तावित योजनाएँ (जैसे, Harn et al., Tiplea et al. द्वारा) असुरक्षित सिद्ध हुई थीं।
  • कम सूचना दर (Low Information Rate): सुरक्षित CRT-आधारित योजनाओं (जैसे, Ersoy et al. द्वारा) की सूचना दर $1/2$ से काफी कम है।
  • लचीलेपन का अभाव: कुछ आदर्श योजनाएँ लचीले शेयर आकार को समायोजित नहीं कर सकती हैं।

मुख्य चुनौती: ऐसे HSS (दोनों विवोंक्त/Disjunctive और संयुग्मी/Conjunctive) निर्माण करना जो सुरक्षित हों, अनंतस्पर्शी रूप से आदर्श (asymptotically ideal, सूचना दर $\to 1$) हों, लचीले शेयर आकार का समर्थन करते हों, और डीलर के लिए बहुपद-समय जटिलता (polynomial-time complexity) बनाए रखते हों।

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

लेखक दो नई योजनाएँ प्रस्तावित करते हैं: एक विवोंक्त पदानुक्रमित गुप्त साझाकरण (Disjunctive Hierarchical Secret Sharing - DHSS) योजना और एक संयुग्मी पदानुक्रमित गुप्त साझाकरण (Conjunctive Hierarchical Secret Sharing - CHSS) योजना।

मुख्य गणितीय उपकरण

1. पूर्णांक रिंग (Integer Rings) पर CRT: मॉड्यूलर शेयरों से रहस्यों के पुनर्निर्माण के लिए चाइनीज रिमाइंडर थ्योरम (CRT) का उपयोग किया जाता है।
2. सह-अभाज्य (Co-primes) के $k$-सघन अनुक्रम (k-Compact Sequences): पूर्णांकों का एक विशिष्ट अनुक्रम $L = \{m_0, m_1, \dots, m_n\}$ जहाँ $m_0$ एक बड़ा अभाज्य संख्या है, और बाद के अभाज्य संख्याएँ $km_0 < m_i < km_0 + m_0^\theta$ (जहाँ $k \ge 1, \theta \in (0,1)$) को संतुष्ट करती हैं। यह संरचना सुनिश्चित करती है कि असमुथ-ब्लूम (Asmuth-Bloom) बाधा को अनंतस्पर्शी रूप से पूरा किया जा सके, जिससे उच्च सूचना दर प्राप्त होती है।
3. एक-तरफ़ा फलन (One-Way Functions): मध्यवर्ती मानों को मास्क करने और यह सुनिश्चित करने के लिए उपयोग किया जाता है कि अनधिकृत उपसमुच्चय (unauthorized subsets) गुप्त को प्राप्त न कर सकें, भले ही उनके पास आंशिक जानकारी हो।

योजना निर्माण (Scheme Construction)

दोनों योजनाएँ एक समान ढांचे का पालन करती हैं लेकिन उनके एक्सेस स्ट्रक्चर (access structures) भिन्न हैं:

A. विवोंक्त HSS (DHSS)

• एक्सेस स्ट्रक्चर: एक उपसमुच्चय तब अधिकृत होता है यदि वह किसी भी स्तर $\ell$ के लिए थ्रेशोल्ड $t_\ell$ को पूरा करता है (अर्थात, $\exists \ell$ ऐसा कि $|A \cap \bigcup_{w=1}^\ell P_w| \ge t_\ell$)।
• शेयर जनरेशन:
  • डीलर एक गुप्त $s \in \mathbb{Z}_{m_0}$ उत्पन्न करता है।
  • निचले स्तर के प्रतिभागियों के लिए यादृच्छिक पूर्णांक $c_i$ आवंटित किए जाते हैं।
  • प्रत्येक स्तर $\ell$ के लिए, एक मान $y_\ell = s + \alpha_\ell m_0$ की गणना की जाती है।
  • उच्च स्तरों के लिए शेयर $y_\ell \pmod{m_i}$ से व्युत्पन्न होते हैं।
  • महत्वपूर्ण चरण: डीलर $w_i^{(\ell)} = (y_\ell - h_\ell(s_i, \ell)) \pmod{m_i}$ प्रकाशित करता है, जहाँ $h_\ell$ एक सार्वजनिक एक-तरफ़ा फलन है। यह $y_\ell$ को सीधे प्रकट किए बिना शेयरों को विशिष्ट स्तर के थ्रेशोल्ड से बांधता है।
• पुनर्निर्माण (Reconstruction): अधिकृत प्रतिभागी एक-तरफ़ा फलन और सार्वजनिक मानों का उपयोग करके $s_i^{(\ell)}$ की गणना करते हैं, फिर $y_\ell$ को पुनः प्राप्त करने के लिए CRT का उपयोग करते हैं और अंततः $s = y_\ell \pmod{m_0}$ प्राप्त करते हैं।

B. संयुग्मी HSS (CHSS)

• एक्सेस स्ट्रक्चर: एक उपसमुच्चय केवल तभी अधिकृत होता है जब वह सभी स्तरों $\ell$ के लिए थ्रेशोल्ड $t_\ell$ को पूरा करता है (अर्थात, $\forall \ell, |A \cap \bigcup_{w=1}^\ell P_w| \ge t_\ell$)।
• शेयर जनरेशन:
  • गुप्त $s$ को $m$ यादृच्छिक शेयरों $\delta_1, \dots, \delta_m$ में विभाजित किया जाता है ताकि $\sum \delta_i \equiv s \pmod{m_0}$ हो।
  • प्रत्येक $\delta_\ell$ को DHSS योजना की तरह ही माना जाता है, जिससे $y_\ell = \delta_\ell + \alpha_\ell m_0$ मान उत्पन्न होते हैं।
  • शेयरों को वितरित और मास्क किया जाता है, जो DHSS योजना के समान एक-तरफ़ा फलनों का उपयोग करता है।
• पुनर्निर्माण: प्रतिभागी CRT का उपयोग करके प्रत्येक $\delta_\ell$ को स्वतंत्र रूप से पुनर्गठित करते हैं और फिर $s$ को पुनः प्राप्त करने के लिए उन्हें $\pmod{m_0}$ के तहत जोड़ते हैं।

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

1. प्रथम सुरक्षित CRT-आधारित आदर्श HSS: यह शोध पत्र पहला DHSS और CHSS निर्माण प्रस्तुत करता है जो पूर्णांक रिंग CRT पर आधारित है और जो सुरक्षित और अनंतस्पर्शी रूप से आदर्श दोनों हैं।
2. लचीले शेयर आकार: पिछली आदर्श योजनाओं (जैसे, Tassa, Cheng) के विपरीत, जो निश्चित शेयर आकार की आवश्यकता रखती हैं, प्रस्तावित योजनाएँ प्रतिभागियों को विभिन्न आकार के शेयर रखने की अनुमति देती हैं, जो CRT-आधारित दृष्टिकोण की एक अंतर्निहित विशेषता है।
3. अनंतस्पर्शी पूर्णता (Asymptotic Perfectness): यह सिद्ध किया गया है कि ये योजनाएँ अनंतस्पर्शी रूप से पूर्ण हैं। जैसे-जैसे गुप्त का आकार ($m_0$) बढ़ता है, अनधिकृत उपसमुच्चयों के लिए सूचना रिसाव शून्य के करीब पहुँच जाता है।
4. अनंतस्पर्शी सूचना दर (Asymptotic Information Rate): सूचना दर $\rho$ का मान $m_0 \to \infty$ होने पर $1$की ओर प्रवृत्त होता है। यह$k$-सघन सह-अभाज्य अनुक्रमों का उपयोग करके प्राप्त किया गया है, जो असमुथ-ब्लूम बाधा को पूरा करते हुए गुप्त स्थान और शेयर स्थान के बीच के अंतर को न्यूनतम करते हैं।
5. बहुपद जटिलता (Polynomial Complexity): डीलर की गणना जटिलता बहुपद बनी रहती है, जिससे पॉलीमेट्रॉइड्स पर आधारित पिछली आदर्श योजनाओं की घातांकीय समय आवश्यकताओं से बचा जा सकता है।

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

• सुरक्षा प्रमाण: लेखक प्रमेय 2 (Asymptotic Perfectness) और प्रमेय 4 (Correctness) को सिद्ध करते हैं। वे प्रदर्शित करते हैं कि किसी भी अनधिकृत सेट $B$ के लिए, सशर्त एंट्रॉपी (conditional entropy) $H(S|V_B)$, $m_0 \to \infty$ होने पर गुप्त की एंट्रॉपी $H(S)$ के बराबर हो जाती है।
  • प्रमाण अनधिकृत सेट के शेयरों के अनुरूप उम्मीदवार रहस्यों (candidate secrets) के सेट ($G$) की कार्डिनैलिटी के विश्लेषण पर निर्भर करता है। $k$-सघन अनुक्रमों के गुणों का उपयोग करते हुए, वे दिखाते हैं कि वैध उम्मीदवारों का अनुपात एक स्थिरांक (constant) की ओर अभिसरित होता है, जिससे सूचना हानि $\Delta$ समाप्त हो जाती है।
• सूचना दर:
  • गुप्त स्थान $S = \mathbb{Z}_{m_0}$ और अधिकतम शेयर स्थान $S_{max} = \mathbb{Z}_{m_n}$ के लिए, दर $\rho = \frac{\log_2 m_0}{\log_2 m_n}$ है।
  • चूंकि $m_n < m_0 + m_0^\theta$ (1-सघन अनुक्रमों के लिए), जैसे-जैसे $m_0 \to \infty$, $\rho \to 1$ होता है।
• तुलना:
  • Harn et al. [7] और Tiplea et al. [9] की तुलना में, प्रस्तावित योजना सुरक्षित है (उन्हें असुरक्षित दिखाया गया था)।
  • Ersoy et al. [8] की तुलना में, प्रस्तावित योजना की सूचना दर अधिक है (approaching 1 बनाम $< 1/2$)।
  • Tassa [4] और Chen et al. [5] की तुलना में, प्रस्तावित योजना लचीले शेयर आकार का समर्थन करती है और इसमें कम गणना जटिलता है।

5. महत्व (Significance)

यह कार्य पदानुक्रमित गुप्त साझाकरण (Hierarchical Secret Sharing) के संबंध में क्रिप्टोग्राफिक साहित्य के एक लंबे समय से चले आ रहे अंतराल को हल करता है। इससे पहले, शोधकर्ताओं को निम्नलिखित में से किसी एक को चुनना पड़ता था:

1. सुरक्षा/आदर्शता (लेकिन उच्च जटिलता या लचीलेपन का अभाव)।
2. लचीलापन/गति (लेकिन असुरक्षा या कम सूचना दर)।

$k$-सघन अनुक्रमों को एक एक-तरफ़ा फलन के साथ CRT ढांचे में सफलतापूर्वक एकीकृत करके, लेखक एक व्यावहारिक, कुशल और सैद्धांतिक रूप से सुदृढ़ समाधान प्रदान करते हैं। यह बड़े पैमाने के सिस्टम (जैसे, वितरित भंडारण, ब्लॉकचेन गवर्नेंस, या कॉर्पोरेट सुरक्षा) में पदानुक्रमित एक्सेस कंट्रोल को तैनात करने में सक्षम बनाता है जहाँ प्रतिभागियों के पास अलग-अलग विशेषाधिकार स्तर होते हैं, शेयर आकार को अनुकूलित किया जाना चाहिए, और सूचना रिसाव को न्यूनतम किया जाना चाहिए।