तकनीकी सारांश: तीव्र सीमाबद्ध-स्वतंत्रता फलन और उनके द्वैत (Duals)

समस्या विवरण

यह शोध पत्र उन क्रिप्टोग्राफिक प्रिमिटिव्स (primitives) के निर्माण की चुनौती को संबोधित करता है जो यादृच्छिक फलनों (random functions) और यादृच्छिक रैखिक कोडों (random linear codes) के सांख्यिकीय गुणों की नकल करते हैं, जबकि स्थिर कम्प्यूटेशनल ओवरहेड बनाए रखते हैं। विशेष रूप से, लेखक "तीव्र" कार्यान्वयन (implementations) चाहते हैं—जिन्हें रैखिक-आकार के अंकगणितीय सर्किट (आकार $O(n)$) द्वारा गणनीय माना जाता है—जो निम्नलिखित को संतुष्ट करते हैं:

1. सीमाबद्ध स्वतंत्रता (Bounded Independence): ऐसे हैश फलन जो किसी भी स्थिर $t$ के लिए $t$-wise स्वतंत्र हैं।
2. तीव्र द्वैत कोड (Fast Dual Codes): रैखिक कोडों के ऐसे परिवार जहाँ कोड और उसका द्वैत (dual) दोनों ही तीव्र, व्यवस्थित एन्कोडिंग (systematic encoding) को स्वीकार करते हैं और जिनका अंतर (distance) गिल्बर्ट-वरसामो (GV) बाउंड के करीब पहुँचता है।
3. मजबूत यादृच्छिक-समान गुण (Stronger Random-Like Properties): केवल दूरी से आगे बढ़कर सूची-डिकोडेबिलिटी (list-decodability) जैसे गुणों तक विस्तार करना, यह सुनिश्चित करना कि कोड स्थानीय बाधाओं (स्थानीय समानता) के तहत भी यादृच्छिक रैखिक कोडों की तरह व्यवहार करें।

पूर्ववर्ती कार्यों, जैसे कि [IKOS08] और [DI14] ने तीव्र युग्म-स्वतंत्र (pairwise independent) हैश फलन और GV बाउंड के करीब पहुँचने वाले तीव्र कोड स्थापित किए, लेकिन अक्सर स्वतंत्रता पैरामीटर $t$, संचालन के क्षेत्र (field of operation), या कोड और उसके द्वैत को एक साथ अनुकूलित करने की क्षमता के संबंध में सीमाएँ थीं। [BR26] द्वारा एक हालिया निर्माण ने तीव्र द्वैत कोडों में सुधार किया, लेकिन वह बाइनरी क्षेत्रों तक सीमित था, उसे 1/2 का निश्चित दर (rate) चाहिए था, उसमें गैर-नगण्य विफलता की संभावना थी, और उसमें व्यवस्थित एन्कोडिंग का अभाव था।

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

लेखक "IKOS निर्माण" (इशाई, कुशिलेविट्ज़, ओस्ट्रोवस्की, साहई) और "DI निर्माण" (ड्रुक, इशाई) पर आधारित हैं, और उन्हें उच्च स्वतंत्रता मापदंडों के लिए सामान्यीकृत करते हैं।

1. हैश फलनों का सामान्यीकरण

हैश फलनों के लिए मुख्य निर्माण एक तीन-चरणीय पाइपलाइन का अनुसरण करता है:

1. बाहरी एन्कोडिंग (Outer Encoding): इनपुट पर एक बड़े (लेकिन स्थिर) वर्णमाला (alphabet) के ऊपर एक तीव्र रैखिक कोड लागू करें।
2. आंतरिक हैशिंग (Inner Hashing): एनकोडेड वेक्टर के प्रत्येक निर्देशांक (coordinate) पर स्थिर-आकार के, $t$-wise स्वतंत्र हैश फलन लागू करें।
3. निष्कर्षण (Extraction): परिणाम पर एक अच्छे कोड के जनरेटर मैट्रिक्स के ट्रांसपोज़ (transpose) को लागू करें (जो एक एक्सट्रैक्टर के रूप में कार्य करता है)।

$t$-wise स्वतंत्रता प्राप्त करने के लिए, लेखक आंतरिक चरण में स्थिर-आकार के युग्म-स्वतंत्र हैश फलनों को स्थिर-आकार के $t$-wise स्वतंत्र हैश फलनों से बदलते हैं। वे सिद्ध करते हैं कि यदि बाहरी कोड का अंतर पर्याप्त रूप से बड़ा है (विशेष रूप से $> 1 - 1/t^2$), तो $t$ इनपुट्स की विशिष्टता पर्याप्त अंश के निर्देशांकों में संरक्षित रहती है, जिससे आंतरिक हैश फलन स्वतंत्र, समान (uniform) आउटपुट उत्पन्न करने में सक्षम होते हैं जिसे अंतिम निष्कर्षण चरण सुरक्षित रखता है।

2. रैखिक समान आउटपुट परिवार (Linear Uniform Output Families - LUOF)

कोडों का निर्माण करने के लिए, लेखक रैखिक समान आउटपुट परिवार (LUOF) की अवधारणा का उपयोग करते हैं। एक यादृच्छिक मैट्रिक्स $A$ एक LUOF है यदि, किसी भी गैर-शून्य इनपुट $x$ के लिए, आउटपुट $xA$ समान रूप से वितरित होता है।

• तीव्र LUOF: लेखक [DI14] के निर्माण को एक तीव्र $t$-LUF बनाने के लिए सामान्यीकृत करते हैं। एक मैट्रिक्स $A$ एक $t$-LUF है यदि, $t$ रैखिक रूप से स्वतंत्र इनपुट्स $x_1, \dots, x_t$ के सेट के लिए, आउटपुट $x_1A, \dots, x_tA$ समान रूप से और स्टोकेस्टिक रूप से स्वतंत्र हैं।
• निर्माण: निर्माण के समान, इसमें एक बाहरी कोड, यादृच्छिक स्थिर-आकार के मैट्रिसेस की एक परत (जो "आंतरिक" फलन के रूप में कार्य करती है), और एक निष्कर्षण चरण शामिल है। लेखक सिद्ध करते हैं कि यदि बाहरी कोड का पर्याप्त अंतर है, तो आंतरिक यादृच्छिक मैट्रिसेस रैखिक रूप से स्वतंत्र इनपुट्स को स्वतंत्र समान आउटपुट में मैप करते हैं।

3. तीव्र द्वैत कोडों का निर्माण

$t$-LUOF मैट्रिक्स $A \in \mathbb{F}_q^{k \times r}$ का उपयोग करके, लेखक एक कोड $C$ को परिभाषित करते हैं जिसका व्यवस्थित एन्कोडिंग मैप $x \mapsto (x, xA)$ है।

• द्वैत (Duality): द्वैत कोड $C^\perp$ को मैप $y \mapsto (-yA^\top, y)$ द्वारा जनरेट किया जाता है।
• ट्रांसपोज़ेशन सिद्धांत (Transposition Principle): ट्रांसपोज़ेशन सिद्धांत (लेम्मा 3.4) का हवाला देते हुए, वे तर्क देते हैं कि यदि $xA$की गणना करना तीव्र (रैखिक आकार) है, तो$yA^\top$ की गणना करना भी तीव्र होगा।
• द्वैत की स्वतंत्रता: एक महत्वपूर्ण तकनीकी योगदान यह सिद्ध करना है कि यदि $A$ एक $t$-LUF है, तो $A^\top$ भी एक $t$-LUF है (लेम्मा 3.9)। यह वज़िरानी के XOR लेम्मा (Vazirani's XOR Lemma) पर निर्भर करता है और यह सुनिश्चित करता है कि द्वैत कोड प्राथमिक कोड के मजबूत यादृच्छिकता गुणों को विरासत में प्राप्त करता है।

मुख्य योगदान और परिणाम

1. तीव्र $t$-Wise स्वतंत्र हैश फलन

• परिणाम: किसी भी स्थिर $t$ के लिए, लेखक $t$-wise स्वतंत्र हैश फलनों का एक परिवार निर्मित करते हैं जो रैखिक-आकार के सर्किट द्वारा गणनीय है।
• अनुकूलन (Optimization): बाइनरी क्षेत्र ($\mathbb{F}_2$) के लिए, बीजगणितीय घात (algebraic degree) को $\log_2 t$ तक अनुकूलित किया गया है। यह लगभग इष्टतम है, क्योंकि कम घात $t$-wise स्वतंत्रता का समर्थन करने में विफल रहेगी।
• दक्षता: सर्किट का आकार $O(k+r)$ है, जहाँ $k$ इनपुट लंबाई और $r$ आउटपुट लंबाई है। छिपा हुआ स्थिरांक $t$ पर निर्भर करता है (लगभग $\Theta(t^7)$), लेकिन स्थिर $t$ के लिए यह स्थिर रहता है।

2. तीव्र द्वैत के साथ तीव्र कोड (GV-Bound)

• परिणाम: लेखक किसी भी परिमित क्षेत्र $\mathbb{F}_q$ पर कोड $C$ और उनके द्वैत $C^\perp$ का एक परिवार निर्मित करते हैं जिसकी दर $R \in (0, 1)$ अनिश्चित है।
• गुण:
  • दोनों $C$ और $C^\perp$ तीव्र, व्यवस्थित एन्कोडिंग (रैखिक आकार) को स्वीकार करते हैं।
  • दोनों संभाव्यता $1 - 2q^{-\varepsilon n}$ के साथ गिल्बर्ट-वरसामो बाउंड के $\varepsilon$-करीब अंतर प्राप्त करते हैं।
  • इस निर्माण में नगण्य विफलता की संभावना है (जैसा कि [BR26] में थी)।
  • यह एन्कोडिंग के लिए एक रैखिक-आकार के यूनिवर्सल सर्किट का समर्थन करता है।

3. तीव्र द्वैत के साथ तीव्र सूची-डिकोडेबल (List-Decodable) कोड

• परिणाम: $t$-LUF गुण का उपयोग करके, लेखक निर्माण को कोड जो $t$-स्थानीय रूप से समान (t-locally similar) हैं, तक विस्तारित करते हैं।
• सूची-डिकोडिंग (List-Decoding): वे सिद्ध करते हैं कि किसी भी स्थिर $t$ के लिए, निर्मित कोड (और उनके द्वैत) सूची-डिकोडिंग क्षमता तक $(\rho, L)$-सूची-डिकोडेबल हैं, जहाँ सूची का आकार $L = O(1/\varepsilon)$ है।
• नवीनता: यह पहला निर्माण (लेखकों के ज्ञान के अनुसार) है जो एक साथ तीव्र एन्कोडिंग, तीव्र द्वैत एन्कोडिंग और दोनों कोड और उनके द्वैत के लिए इष्टतम सूची-डिकोडेबिलिटी प्राप्त करता है।

महत्व और क्रिप्टोग्राफिक अनुप्रयोग

यह शोध पत्र प्रदर्शित करता है कि ये निर्माण शक्तिशाली बिल्डिंग ब्लॉक्स के रूप में कार्य करते हैं, विशेष रूप से उन परिदृश्यों में जिनमें उच्च दक्षता और मजबूत सुरक्षा गारंटी की आवश्यकता होती है।

1. पूर्णतः सुरक्षित मल्टी-पार्टी कम्प्यूटेशन (MPC)

लेखक पूर्णतः सुरक्षित MPC के लिए पहले गैर-तुच्छ प्रोटोकॉल प्रस्तुत करते हैं जहाँ सर्किट जटिलता पार्टियों की संख्या ($n$) के साथ रैखिक रूप से स्केल करती है ($O(n)$)।

• संदर्भ: बीजगणितीय कोड (जैसे रीड-सोलोमन) का उपयोग करने वाले पिछले प्रोटोकॉल अक्सर क्वाज़ी-लीनियर ओवरहेड का सामना करते थे।
• अनुप्रयोग: तीव्र द्वैत कोडों का उपयोग करके, वे एक ओब्लिवियस लीनियर इवैल्यूएशन (OLE) प्रोटोकॉल का निर्माण करते हैं और इसे सामान्य स्थिर-आकार के फलनों तक विस्तारित करते हैं। प्रोटोकॉल निष्क्रिय विरोधियों (passive adversaries) के विरुद्ध सुरक्षा थ्रेशोल्ड $t = (1/2 - \varepsilon)n$ प्राप्त करता है।

2. एन्क्रिप्टेड मैट्रिक्स-वेक्टर उत्पाद (EMVP)

जटिलता-आधारित क्रिप्टोग्राफी के संदर्भ में, लेखक अपने तीव्र द्वैत कोडों को एन्क्रिप्टेड मैट्रिक्स-वेक्टर उत्पादों पर लागू करते हैं।

• सुधार: उनका निर्माण [BR26] के दृष्टिकोण की सीमाओं को दूर करता है (जो $\mathbb{F}_2$ तक सीमित था और जिसमें गैर-नगण्य विफलता की संभावना थी)।
• लाभ: यह EMVP प्रोटोकॉल को सक्षम बनाता है जहाँ मैट्रिक्स एन्कोडिंग और क्वेरी एन्कोडिंग दोनों का एसिम्प्टोटिक रूप से इष्टतम सर्किट जटिलता होता है।

3. यादृच्छिक रैखिक कोड के रूढ़िवादी विकल्प (Conservative Substitutes)

$t$-LUF निर्माण यादृच्छिक रैखिक कोड के लिए एक "रूढ़िवादी" विकल्प प्रदान करता है, जो उन अनुप्रयोगों में उपयोगी है जो शोर वाले रैखिक बीजगणित (जैसे LPN) की कठिनाई पर निर्भर करते हैं।

• लाभ: जबकि पिछले निर्माण केवल न्यूनतम अंतर (1-स्थानीय समानता) पर निर्भर थे, $t$-LUF $t$-स्थानीय समानता सुनिश्चित करता है, जो सूची-डिकोडेबिलिटी जैसी मजबूत कॉम्बिनेटरियल विशेषताओं की गारंटी देता है। यह स्थानीय संरचनाओं का लाभ उठाने वाले हमलों के खिलाफ अधिक मजबूत सुरक्षा धारणा प्रदान करता है।

4. MPC-अनुकूल हैशिंग

कम बीजगणितीय घात वाले तीव्र $t$-wise स्वतंत्र हैश फलन सीधे उन MPC प्रोटोकॉल के लिए लागू होते हैं जहाँ सर्किट आकार और बीजगणितीय घात दोनों संचार और राउंड जटिलता को प्रभावित करते हैं। यह निर्माण दोनों को एक साथ अनुकूलित करता है।

निष्कर्ष

यह शोध पत्र पिछले रैखिक-आकार के निर्माणों को उच्च स्वतंत्रता मापदंडों और मजबूत यादृच्छिक-समान गुणों का समर्थन करने के लिए सफलतापूर्वक सामान्यीकृत करता है। तीव्र $t$-LUF और उनके द्वैत गुणों को सिद्ध करके, लेखक ऐसे कोड और हैश फलन बनाने के लिए एक एकीकृत ढांचा प्रदान करते हैं जो एक साथ तीव्र, व्यवस्थित और सांख्यिकीय रूप से सुदृढ़ हैं। ये परिणाम नए क्रिप्टोग्राफिक प्रोटोकॉल को इष्टतम एसिम्प्टोटिक जटिलता के साथ सक्षम करते हैं, विशेष रूप से सूचना-सैद्धांतिक (information-theoretic) MPC और एन्क्रिप्टेड कंप्यूटेशन में।