Non-Trivial Zero-Knowledge Implies One-Way Functions

यहाँ चक्रमोरती, हुलेट, खुराना और तोमर के शोध पत्र "Non-Trivial Zero-Knowledge Implies One-Way Functions" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र क्रिप्टोग्राफी और जटिलता सिद्धांत (complexity theory) के एक मौलिक प्रश्न को संबोधित करता है: जीरो-नॉलेज (ZK) प्रूफ सिस्टम बनाने के लिए न्यूनतम धारणाएँ (assumptions) क्या हैं?

ऐतिहासिक रूप से, यह ज्ञात था कि यदि NP औसत रूप से कठिन (hard on average) है, तो ZK के लिए NP का अस्तित्व वन-वे फंक्शन्स (OWFs) की उपस्थिति को दर्शाता है। हाल ही में, हिराहारा और नानाशिमा (HN24) ने दिखाया कि NP की वर्स्ट-केस कठिनाई (विशेष रूप से $NP \not\subseteq ioP/poly$) भी OWFs को व्युत्पन्न करने के लिए पर्याप्त है, बशर्ते ZK सिस्टम में त्रुटियाँ नगण्य (negligible) हों।

हालाँकि, गैर-नगण्य (non-negligible) त्रुटियों वाले गैर-तुच्छ (non-trivial) ZK सिस्टम के संबंध में एक महत्वपूर्ण अंतराल बना हुआ था।

• अंतराल (The Gap): एक ZK सिस्टम को "तुच्छ" (trivial) माना जाता है यदि इसकी पूर्णता त्रुटि (completeness error $\epsilon_c$), साउंडनेस त्रुटि (soundness error $\epsilon_s$), और जीरो-नॉलेज त्रुटि (zero-knowledge error $\epsilon_{zk}$) का योग $\ge 1$ हो। ऐसे सिस्टम बिना किसी क्रिप्टोग्राफिक धारणा के बनाए जा सकते हैं (जैसे, हमेशा स्वीकार करने, हमेशा अस्वीकार करने, या साक्ष्य (witness) प्रकट करने का चयन करके)।
• प्रश्न: यदि एक ZK सिस्टम गैर-तुच्छ (non-trivial) है (अर्थात $\epsilon_c + \epsilon_s + \epsilon_{zk} < 1$), तो क्या यह अभी भी वन-वे फंक्शन्स के अस्तित्व को दर्शाता है? पिछले तकनीकें भारी रूप से कम (नगण्य) त्रुटियों पर निर्भर थीं और तब विफल हो गईं जब त्रुटियाँ बड़ी (जैसे, $\epsilon_s + \epsilon_{zk} \approx 1$) थीं।

2. कार्यप्रणाली और तकनीकी दृष्टिकोण (Methodology and Technical Approach)

लेखक "यूनिवर्सल एक्सट्रपोलेशन" (UE) और "यूनिवर्सल एप्रोक्सिमेशन" (UA) तकनीकों की सीमाओं से आगे बढ़ते हुए, गैर-तुच्छ ZK और OWFs के बीच के अंतर को पाटने के लिए एक नया ढांचा विकसित करते हैं।

A. मुख्य अंतर्दृष्टि: पुनरावृत्ति और "अच्छे" कॉमन रेफरेंस स्ट्रिंग्स (CRS)

पिछली कृतियों (ओस्ट्रोवस्की-विगडरसन, चक्रवर्ती आदि) में उच्च-त्रुटि शासन (high-error regime) में विफल होने का कारण यह था कि वे सिम्युलेटर के आउटपुट को एक एकल वितरण (single distribution) के रूप में देखते थे। लेखक देखते हैं कि उच्च-त्रुटि शासन में, सिम्युलेटर उच्च संभावना के साथ "बुरे" प्रमाण (जो वास्तविक प्रमाणों से दूर हैं) आउटपुट कर सकता है, जिससे वास्तविक और सिम्युलेटेड ट्रांसक्रिप्ट के बीच का अंतर छिप जाता है।

इससे निपटने के लिए, वे एक पुनरावृत्ति रणनीति (repetition strategy) पेश करते हैं:

1. नमूनाकरण (Sampling): एक एकल सिम्युलेटेड प्रमाण के नमूने लेने के बजाय, एल्गोरिदम एक ही कॉमन रेफरेंस स्ट्रिंग (CRS) के लिए कई प्रमाणों का नमूना लेता है।
2. वर्गीकरण (Classification): वे CRS को "अच्छे" (Good) या "बुरे" (Bad) के रूप में वर्गीकृत करते हैं:
   • अच्छा CRS: सिम्युलेटर, इस CRS पर आधारित होकर, एक स्वीकार्य प्रमाण उत्पन्न करने की गैर-नगण्य संभावना रखता है।
   • बुरा CRS: सिम्युलेटर लगभग कभी भी स्वीकार्य प्रमाण उत्पन्न नहीं करता है।
3. तर्क: यदि भाषा $L$ कठिन है, तो वास्तविक प्रूवर (prover) हमेशा स्वीकार करता है। यदि सिम्युलेटर उच्च संभावना के साथ एक "बुरा" CRS आउटपुट करता है, तो जीरो-नॉलेज गुण का उल्लंघन होता है क्योंकि वास्तविक प्रूवर (एक बुरे CRS पर) स्वीकार करेगा जबकि सिम्युलेटर नहीं करेगा।
4. संवर्धन (Amplification): नमूनाकरण प्रक्रिया को बहुपद (polynomially) रूप से दोहराकर, एल्गोरिदम उच्च विश्वास के साथ $x \in L$ और $x \notin L$ के बीच अंतर कर सकता है, बशर्ते $\epsilon_c + \epsilon_s + \epsilon_{zk} < 1$ हो।

B. इंटरैक्टिव प्रोटोकॉल तक विस्तार (Extension to Interactive Protocols)

इसे इंटरैक्टिव (बहु-चरण) ZK तक विस्तारित करना काफी कठिन है क्योंकि प्रूवर यह जांच नहीं सकता कि क्या कोई संदेश स्वीकृति की ओर ले जाएगा, जब तक कि उसे भविष्य के वेरीफायर रैंडमनेस का ज्ञान न हो।

• दुर्भावनापूर्ण प्रूवर ($\tilde{P}$): लेखक एक अकुशल "दुर्भावनापूर्ण प्रूवर" को परिभाषित करते हैं जो, एक आंशिक ट्रांसक्रिप्ट दिए जाने पर, सिम्युलेटर से कई संभावित अगले संदेशों का नमूना लेता है और उस संदेश को चुनता है जो वेरीफायर के स्वीकार करने की संभावना को अधिकतम करता है।
• अनुमान के माध्यम से दक्षता (Efficiency via Estimation): इसे कुशल बनाने के लिए, वे उम्मीदवार संदेशों का नमूना लेने के लिए यूनिवर्सल एक्सट्रपोलेशन (UE) का उपयोग करते हैं और सिम्यूलेशन के माध्यम से उनकी सफलता की संभावना का अनुमान लगाते हैं (चूंकि वेरीफायर पब्लिक-कॉइन (public-coin) और स्टेटलेस है)।
• प्राइवेट कॉइन को संभालना (Handling Private Coins): प्राइवेट-कॉइन प्रोटोकॉल के लिए, वे दिखाते हैं कि जब तक सहायक-इनपुट (auxiliary-input) OWFs मौजूद नहीं हैं, तब तक किसी भी निरंतर-चरण (constant-round) वाले प्राइवेट-कॉइन प्रोटोकॉल को पब्लिक-कॉइन में परिवर्तित किया जा सकता है। अतः, गैर-तुच्छ प्राइवेट-कॉइन ZK, सहायक-इनपुट OWFs की उपस्थिति को दर्शाता है।

C. डिसीजन-टू-इवर्जन रिडक्शन (Decision-to-Inversion Reduction)

मुख्य प्रमाण एक डिसीजन-टू-इवर्जन रिडक्शन का निर्माण करता है।

1. वे मानते हैं कि OWFs मौजूद नहीं हैं।
2. इसका तात्पर्य एक यूनिवर्सल एक्सट्रपोलेशन (UE) मशीन की उपस्थिति से है।
3. UE का उपयोग करके, वे भाषा $L$ (जिसे माना जाता है कि $L \notin ioP/poly$ है) को तय करने वाला एक एल्गोरिदम $A$ निर्मित करते हैं।
4. एल्गोरिदम $A$, वास्तविक और सिम्युलेटेड ट्रांसक्रिप्ट के बीच अंतर करने के लिए ZK प्रोटोकॉल और UE मशीन का उपयोग करता है।
5. यदि $A$ सफल होता है, तो यह $L \notin ioP/poly$ की धारणा का खंडन करता है, जिससे सिद्ध होता है कि OWFs का अस्तित्व होना चाहिए।

3. प्रमुख योगदान और परिणाम (Key Contributions and Results)

यह शोध पत्र निम्नलिखित मुख्य प्रमेय (अनौपचारिक रूप से) स्थापित करता है:

1. गैर-तुच्छ NIZK $\implies$ OWF:
   यदि $NP \not\subseteq ioP/poly$ और NP के लिए एक गैर-तुच्छ नॉन-इंटरैक्टिव जीरो-नॉलेज (NIZK) तर्क मौजूद है (जहाँ $\epsilon_c + \epsilon_s + \epsilon_{zk} < 1$), तो वन-वे फंक्शन्स (OWF) मौजूद हैं।

   • महत्व: यह पिछली कृति (CHK25) में सुधार करता है जिसमें $\epsilon_{zk} + \sqrt{\epsilon_s} < 1$ जैसी सख्त सीमाओं की आवश्यकता थी। नया परिणाम किसी भी गैर-तुच्छ त्रुटि शासन के लिए मान्य है।

2. गैर-तुच्छ पब्लिक-कॉइन ZK $\implies$ सहायक-इनपुट OWF:
   यदि $NP \not\subseteq ioP/poly$ और NP के लिए एक गैर-तुच्छ, निरंतर-चरण (constant-round), पब्लिक-कॉइन ZK तर्क मौजूद है, तो सहायक-इनपुट (auxiliary-input) वन-वे फंक्शन्स मौजूद हैं।

   • महत्व: यह उच्च त्रुटियों वाले इंटरैक्टिव ZK के लिए वर्स्ट-केस हार्डनेस से OWFs का पहला लक्षण वर्णन है।

3. गैर-तुच्छ प्राइवेट-कॉइन ZK $\implies$ सहायक-इनपुट OWF:
   यदि $NP \not\subseteq ioP/poly$ और एक गैर-तुच्छ, निरंतर-चरण, प्राइवेट-कॉइन ZK तर्क मौजूद है, तो सहायक-इनपुट OWFs मौजूद हैं।

   • तंत्र: यह एक रिडक्शन पर निर्भर करता है जो दिखाता है कि यदि सहायक-इनपुट OWFs मौजूद नहीं हैं, तो प्राइवेट-कॉइन प्रोटोकॉल को पब्लिक-कॉइन में बदला जा सकता है।

4. ZK का संवर्धन (Amplification of ZK):
   परिणाम यह भी दर्शाते हैं कि गैर-तुच्छ ZK प्रमाणों को लगभग बिना किसी शर्त के मानक (नगण्य त्रुटि) ZK में बढ़ाया जा सकता है।

   • यदि $NP \subseteq BPP$, तो तुच्छ ZK मौजूद है।
   • यदि $NP \not\subseteq ioP/poly$, तो गैर-तुच्छ ZK की उपस्थिति OWFs की उपस्थिति को दर्शाती है। चूंकि OWFs + वीक ZK $\implies$ स्टैंडर्ड ZK (ज्ञात संवर्धन प्रमेयों के माध्यम से), इसलिए गैर-तुच्छ ZK, मानक ZK की ओर ले जाता है।

4. महत्व और प्रभाव (Significance and Impact)

• चरित्रण की पूर्णता (Completeness of Characterization): यह शोध पत्र ZK के जटिलता के पूर्ण लक्षण वर्णन को प्रदान करता है। यह सिद्ध करता है कि कोई भी गैर-तुच्छ ZK सिस्टम (भले ही उसमें बड़ी त्रुटियां हों) क्रिप्टोग्राफिक रूप से उतना ही मजबूत है जितना कि वन-वे फंक्शन्स, यह मानते हुए कि NP की वर्स्ट-केस कठिनाई मौजूद है। कोई भी "कमजोर" ZK नहीं है जिसे बनाने के लिए OWFs से कम कठिन हो।
• संवर्धन के लिए धारणाओं को हटाना: पहले, कमजोर NIZKs को मजबूत NIZKs में बढ़ाने के लिए पब्लिक-की एन्क्रिप्शन या विशिष्ट त्रुटि सीमाओं जैसी धारणाओं की आवश्यकता होती थी। यह कार्य दिखाता है कि हल्की जटिलता धारणा ($NP \not\subseteq ioP/poly$) के तहत, गैर-तुच्छ NIZKs को केवल निहित OWFs का उपयोग करके मानक NIZKs में बढ़ाया जा सकता है।
• उच्च-त्रुटि शासन के लिए नई तकनीकें: "गुड/बैड CRS" वर्गीकरण और पुनरावृत्ति-आधारित विश्लेषण का परिचय गैर-नगण्य त्रुटियों वाले क्रिप्टोग्राफिक प्रोटोकॉल के विश्लेषण के लिए एक नया टूलकिट प्रदान करता है, जिसका उपयोग ZK के परे भी किया जा सकता है।
• त्रुटियों की भूमिका को स्पष्ट करना: यह कार्य निर्णायक रूप से दिखाता है कि OWFs के निर्माण में बाधा त्रुटि का आकार नहीं है, बल्कि यह कि क्या सिस्टम तुच्छ (त्रुटियों का योग $\ge 1$) है या गैर-तुच्छ।

संक्षेप में, यह कार्य ZK की नींव के बारे में हमारी समझ के एक बड़े अंतराल को भरता है, यह सिद्ध करते हुए कि NP के लिए किसी भी गैर-तुच्छ जीरो-नॉलेज प्रूफ सिस्टम का अस्तित्व, वन-वे फंक्शन्स के मौलिक आधार को बनाने के लिए पर्याप्त है।