Certified-Everlasting Quantum NIZK Proofs

यहाँ निखिल पप्पू के शोध पत्र "Certified-Everlasting Quantum NIZK Proofs" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र जटिलता वर्ग (complexity class) NP के लिए Certified-Everlasting Non-Interactive Zero-Knowledge (CE-NIZK) प्रमाणों के निर्माण को संबोधित करता है।

• संदर्भ: मानक NIZK आमतौर पर या तो सांख्यिकीय सुदृढ़ता (statistical soundness - असीमित प्रोवर के विरुद्ध सुरक्षित) या कम्प्यूटेशनल ज़ीरो-नॉलेज (computational zero-knowledge - कुशल वेरीफायर के विरुद्ध सुरक्षित) प्रदान करते हैं, लेकिन शायद ही कभी दोनों को एक साथ प्रदान करते हैं। पोस्ट-क्वांटम युग में, Statistical Soundness (सुदृढ़ता की रक्षा के लिए भविष्य के क्वांटम कंप्यूटरों से सुरक्षित) के साथ-साथ Everlasting Zero-Knowledge (भविष्य के असीमित विरोधियों से सुरक्षा के लिए जो प्रमाण ट्रांसक्रिप्ट को स्टोर कर सकते हैं) प्राप्त करने की इच्छा है।
• चुनौती: "Certified-Everlasting" (CE) गुण के लिए यह आवश्यक है कि एक वेरीिफायर अपने क्वांटम प्रमाण अवस्था (quantum proof state) को इस तरह से हटा सके (delete) जिसे प्रोवर द्वारा प्रमाणित (certified) किया जा सके। यदि विलोपन (deletion) प्रमाणित है, तो वेरीिफायर की शेष अवस्था को केवल कथन (statement) का उपयोग करके सिम्युलेट किया जाना चाहिए (गवाह/witness का नहीं), यहाँ तक कि एक असीमित विरोधी द्वारा भी।
• बाधा: इंटरैक्टिव CE-ZK प्रोटोकॉल को नॉन-इंटरैक्टिव सेटिंग (विशेष रूप से कॉमन रेफरेंस स्ट्रिंग या CRS मॉडल) में सामान्य करने के पिछले प्रयास विफल रहे। यह शोध पत्र एक बाधा की पहचान करता है: "डिलीशन-रेसिस्टेंट" (Deletion-Resistant) प्रोटोकॉल नामक प्रोटोकॉल की एक श्रेणी (जहाँ प्रमाण की अवस्था को सत्यापन योग्य भाग और विलोपन प्रमाणन योग्य भाग में विभाजित किया जा सकता है) यह संकेत देती है कि ऐसे NIZK मौजूद हैं जो सांख्यिकीय रूप से सुदृढ़ और सांख्यिकीय रूप से ज़ीरो-नॉलेज दोनों हैं। ऐसे NIZK सामान्य NP भाषाओं के लिए अस्तित्व में नहीं होने की व्यापक रूप से संभावना है।

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

शोध पत्र पहचाने गए अवरोधों को दूर करने के लिए दो अलग-अलग निर्माण प्रस्तावित करता है, जो विभिन्न सेटअप मॉडलों का उपयोग करते हैं।

A. CRS मॉडल (Common Reference String)

लेखक क्वांटम सुपरपोजिशन (superposition) का उपयोग करते हुए एक नवीन दो-स्तरीय प्रमाण संरचना (two-level proof structure) के माध्यम से CRS मॉडल में CE-NIZK का निर्माण करते हैं।

• मुख्य तंत्र:
  1. आंतरिक प्रमाण (Inner Proof): कथन $x$ के लिए एक वास्तविक NIZK प्रमाण ($\pi_{in}$) उत्पन्न किया जाता है।
  2. एन्क्रिप्शन (Encryption): $\pi_{in}$ को एक BB84 क्वांटम अवस्था ($|y\rangle_\theta$) से प्राप्त One-Time Pad (OTP) का उपयोग करके एन्क्रिप्ट किया जाता है। पैड (pad) की गणना विशिष्ट आधार विकल्पों (basis choices) के अनुरूप BB84 अवस्था के बिट्स के XOR के रूप में की जाती है।
  3. बाहरी प्रमाण (Outer Proofs): एन्क्रिप्टेड सिफरटेक्स्ट को सीधे भेजने के बजाय, प्रोवर "बाहरी" NIZK प्रमाणों का एक सुपरपोजिशन उत्पन्न करता है। प्रत्येक पद यह सिद्ध करता है कि डिक्रिप्ट किया गया सिफरटेक्स्ट (विशिष्ट BB84 आधार स्ट्रिंग $z$ का उपयोग करके) $x$ के लिए एक वैध प्रमाण है।
  4. OR-Proof रणनीति: बिना गवाह के प्रमाण के सिम्युलेशन को सक्षम करने के लिए, प्रोटोकॉल एक 2-स्लॉट तकनीक (Naor-Yung से प्रेरित) का उपयोग करता है। यह दो सिफरटेक्स्ट ($ct_0, ct_1$) बनाता है और एक OR स्टेटमेंट सिद्ध करता है: या तो $ct_0$ एक वैध प्रमाण को डिक्रिप्ट करता है, अथवा $ct_1$ एक वैध प्रमाण को डिक्रिप्ट करता है।
• सुरक्षा तर्क:
  • सुदृढ़ता (Soundness): अंतर्निहित NIZK की सांख्यिकीय एडेप्टिव सुदृढ़ता पर निर्भर करती है।
  • Certified-Everlasting ZK: वेरीिफायर को BB84 अवस्था वापस करने के लिए कहा जाता है। यदि प्रोवर विलोपन को सत्यापित करता है (Bartusek और Khurana द्वारा BB84 अवस्थाओं के लिए प्रमाणित विलोपन प्रमेय का उपयोग करके), तो OTP पैड सूचना-सैद्धांतिक रूप से छिपा हुआ (information-theoretically hidden) हो जाता है।
  • सिमुलेशन (Simulation): सिम्युलेटर अंतर्निहित NIZK के Quantum-Secure Adaptive Zero-Knowledge गुण का उपयोग करता है। वह सुपरपोजिशन के भीतर एक-एक बिट करके वास्तविक आंतरिक प्रमाण को सिम्युलेटेड प्रमाण के साथ बदल देता है। OR-प्रूफ संरचना के कारण, सिम्युलेटर पूरे गवाह-निर्भर डेटा को सिम्युलेटेड दृश्य (view) से बदलने के दौरान भी बाहरी प्रमाण की वैधता बनाए रख सकता है।

B. साझा EPR मॉडल (Shared EPR Model)

लेखक देखते हैं कि जब प्रोवर और वेरीिफायर पहले से ही EPR जोड़े (Einstein-Podolsky-Rosen pairs) साझा करते हैं, तो "डिलीशन-रेसिस्टेंट" असंभवता की बाधा लागू नहीं होती है।

• मुख्य तंत्र:
  1. हिडन बिट्स प्रतिमान (Hidden Bits Paradigm): प्रोटोकॉल क्लासिक हिडन-बिट्स जनरेटर (HBG) प्रतिमान को क्वांटम सेटिंग में अनुकूलित करता है।
  2. एंटैंगलमेंट (Entanglement): प्रोवर और वेरीिफायर EPR जोड़े साझा करते हैं। HBG कमिटमेंट एक आधार स्ट्रिंग $\theta$ को फिक्स करता है।
  3. मापन (Measurement): दोनों पक्ष $\theta$ आधार में अपने EPR आधे हिस्सों को मापते हैं। एंटैंगलमेंट के कारण, वे सहसंबद्ध परिणाम (correlated outcomes) प्राप्त करते हैं, जो प्रभावी रूप से "हिडन बिट्स" उत्पन्न करते हैं जो प्रकट होने तक वेरीिफायर के लिए अज्ञात रहते हैं।
  4. विलोपन (Deletion): विलोपन को प्रमाणित करने के लिए, वेरीिफायर अनओपन किए गए EPR जोड़ों को Hadamard आधार में मापता है। यह अवस्था को ढहा (collapse) देता है, जिससे हिडन बिट्स के बारे में जानकारी नष्ट हो जाती है।
• दक्षता (Efficiency): यह दृष्टिकोण CRS मॉडल की तुलना में काफी अधिक कुशल है। इसके लिए केवल सिंगल-क्यूबिट मापन (कंप्यूटेशनल या Hadamard आधार में) और क्लासिकल गणना की आवश्यकता होती है, जिससे NIZK प्रमाणों के जटिल सुपरपोजिशन की आवश्यकता नहीं होती।

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

1. परिभाषा और असंभवता परिणाम:

   • दोनों मॉडलों (CRS और Shared EPR) में CE-NIZKs को औपचारिक रूप से परिभाषित किया।
   • सिद्ध किया कि "डिलीशन-रेसिस्टेंट" CE-NIZKs (जहाँ प्रमाण और विलोपन अवस्थाएँ विभाज्य हैं) का अस्तित्व उन NIZKs के अस्तित्व को दर्शाता है जिनमें सांख्यिकीय सुदृढ़ता और सांख्यिकीय ज़ीरो-नॉलेज दोनों हैं, जो सामान्यतः असंभव माने जाते हैं। यह बताता है कि सरल इंटरैक्टिव प्रोटोकॉल का सामान्यीकरण क्यों विफल होता है।

2. CRS मॉडल में CE-NIZK:

   • CRS मॉडल में NP के लिए पहला CE-NIZK निर्मित किया।
   • मान्यताएँ (Assumptions): Learning With Errors (LWE) धारणा (विशेष रूप से, बहुपद कठोरता) पर आधारित है।
   • तकनीक: BB84 अवस्थाओं के साथ जुड़े NIZK प्रमाणों के क्वांटम सुपरपोजिशन का उपयोग किया, जिसमें "Two-Slot" तकनीक और Quantum-Secure Adaptive Zero-Knowledge का लाभ उठाया गया।

3. Shared EPR मॉडल में CE-NIZK:

   • प्रदर्शित किया कि Shared EPR मॉडल में असंभवता की बाधा समाप्त हो जाती है।
   • किसी भी Statistically Binding Hidden-Bits Generator (जो LWE से बनाया जा सकता है) पर आधारित एक अत्यधिक कुशल CE-NIZK का निर्माण किया।
   • दक्षता: प्रोटोकॉल के लिए केवल सिंगल-क्यूबिट मापन की आवश्यकता होती है, जो इसे CRS निर्माण की तुलना में व्यावहारिक रूप से अधिक व्यवहार्य बनाता है।

4. सुरक्षा गारंटी:

   • दोनों निर्माण Statistical Soundness (असीमित प्रोवर्स के विरुद्ध सुरक्षित) प्रदान करते हैं।
   • वे Computational Zero-Knowledge (मानक) और Certified-Everlasting Zero-Knowledge (सफल विलोपन प्रमाणन के बाद असीमित विरोधियों के विरुद्ध सुरक्षित) दोनों को पूरा करते हैं।

4. परिणाम (Results)

• Theorem 2.4: OWFs और विशिष्ट क्वांटम-सुरक्षित NIZKs के गुणों (जो LWE-आधारित निर्माणों द्वारा संतुष्ट होते हैं) को मानते हुए CRS मॉडल में NP के लिए CE-NIZKs मौजूद हैं।
• Theorem 2.6: Statistically Binding Hidden-Bits Generators के अस्तित्व को मानते हुए Shared EPR मॉडल में NP के लिए CE-NIZKs मौजूद हैं (जो LWE द्वारा संतुष्ट है)।
• Corollary 2.5 & 2.7: दोनों प्रोटोकॉल के मूर्त इंस्टेंशिएशन (concrete instantiations) केवल LWE समस्या की बहुपद कठोरता पर आधारित रूप से संभव हैं।

5. महत्व (Significance)

• अंतराल को पाटना: यह कार्य क्वांटम क्रिप्टोग्राफी के एक प्रमुख खुले प्रश्न को हल करता है: क्या हम ऐसे NIZKs प्राप्त कर सकते हैं जो सांख्यिकीय रूप से सुदृढ़ हों और प्रमाणित विलोपन के माध्यम से 'एवरलास्टिंग ज़ीरो-नॉलेज' गारंटी भी दें? उत्तर हाँ है, बशर्ते हम क्वांटम संसाधनों (BB84 अवस्था या EPR जोड़े) का उपयोग करें।
• असंभवता को पार करना: यह शोध पत्र एक गहरा सैद्धांतिक अंतर्दृष्टि प्रदान करता है कि पिछले प्रयास क्यों विफल रहे ("डिलीशन-रेसिस्टेंट" बाधा) और कैसे क्वांटम एंटैंगलमेंट और सुपरपोजिशन का उपयोग करके इसे दरकिनार किया जा सकता है।
• व्यावहारिक निहितार्थ:
  • Shared EPR मॉडल एक अत्यधिक कुशल प्रोटोकॉल प्रदान करता है जो निकट-अवधि के क्वांटम नेटवर्क के लिए उपयुक्त है जहाँ एंटैंगलमेंट वितरण संभव है।
  • CRS मॉडल निर्माण उन सेटिंग्स के लिए समाधान प्रदान करता है जहाँ पूर्व-साझा एंटैंगलमेंट उपलब्ध नहीं है, जो केवल मानक पोस्ट-क्वांटम धारणाओं (LWE) पर निर्भर करता है।
• भविष्य की दिशाएँ: यह शोध पत्र QMA (क्वांटम NP) के लिए CE-NIZKs के निर्माण और Publicly Verifiable Deletion (वर्तमान में, विलोपन का सत्यापन प्रोवर के लिए निजी है) की खोज के मार्ग खोलता है।

संक्षेप में, यह शोध पत्र Certified-Everlasting NIZKs की सैद्धांतिक व्यवहार्यता स्थापित करता है, जो क्वांटम यांत्रिकी के अद्वितीय गुणों (नो-क्लोनिंग, एंटैंगलमेंट और जेंटल मेजरमेंट) का लाभ उठाकर ऐसी सुरक्षा गारंटी प्रदान करता है जो शास्त्रीय दुनिया में असंभव है।