Lattice-based extended withdrawability

तकनीकी सारांश: लैटिस-आधारित विस्तारित विड्रोएबिलिटी (Lattice-based Extended Withdrawability)

समस्या विवरण
डिजिटल हस्ताक्षर पारंपरिक रूप से स्थायित्व प्रदान करते हैं: एक बार हस्ताक्षरित होने के बाद, कोई संदेश हस्ताक्षरकर्ता की सार्वजनिक कुंजी के तहत अनिश्चित काल के लिए सत्यापन योग्य रहता है। हालांकि, कई विकेंद्रीकृत अनुप्रयोगों (जैसे, सीमित समय तक पहुंच, प्रतिसंहरणीय (revocable) समझौते, विकेंद्रीकृत एस्क्रो) को एक हस्ताक्षर को बिना गुप्त कुंजी को प्रकट किए या अन्य हस्ताक्षरों को अमान्य किए वापस लेने (withdraw) की क्षमता की आवश्यकता होती है। लियू, सुसिलो और बेक ने 'विस्तारित विड्रोएबल सिग्नेचर' (EWS) पेश करने के लिए इसे संबोधित किया, जो यह अनुमति देता है कि एक हस्ताक्षर संभावित हस्ताक्षरकर्ताओं के एक सेट के बीच तब तक अस्पष्ट रहे जब तक कि वास्तविक हस्ताक्षरकर्ता उसे "पुष्टि" (confirm) न कर दे। उनका निर्माण डिस्क्रीट-लॉगारिदम प्रिमिटिव्स (श्नोर सिग्नेचर और 1-आउट-ऑफ-N सिग्नेचर) पर आधारित है।

यह शोध पत्र "पोस्ट-क्वांटम गैप" को संबोधित करता है: शोर का एल्गोरिदम (Shor's algorithm) मौजूदा EWS योजनाओं के डिस्क्रीट-लॉगारिदम आधार को तोड़ देता है। जबकि लैटिस-आधारित हस्ताक्षर (जैसे, डिलिथियम) मौजूद हैं, लियू-सुसिलो-बेक (LSB) निर्माण का एक सीधा "शाब्दिक लिप्यंतरण" (literal transcription) लैटिस में विफल रहता है क्योंकि इसमें संरचनात्मक बाधाएं हैं। विशेष रूप से, LSB योजना हस्ताक्षरकर्ता के योगदान को पुन: रैंडमाइज करने के लिए सार्वजनिक कुंजियों के मल्टीप्लिकेटिव शिफ्ट (multiplicative shifts) प्रकाशित करने पर निर्भर करती है। लैटिस सेटिंग (Fiat-Shamir with aborts) में, ऐसे शिफ्ट $As_1 s_j$ के रूप में होते हैं, जो हस्ताक्षरकर्ता की सार्वजनिक कुंजी $t_i = As_1 + s_2$ के साथ एक सामान्य कारक $As_1$ साझा करते हैं। इन शिफ्ट्स को प्रकाशित करना हस्ताक्षरकर्ता की पहचान को उजागर कर देता है, जिससे आवश्यक अस्पष्टता (ambiguity) टूट जाती है।

कार्यप्रणाली (Methodology)
लेखक EWS के लिए एक नया निर्माण प्रस्तावित करते हैं जो LSB दृष्टिकोण से हटकर इसे एक 'क्लेमेबल रिंग सिग्नेचर' (पार्क और सेलफॉन) के रूप में मानता है। स्पष्ट रूप से सार्वजनिक कुंजियों को पुन: रैंडमाइज करने के प्रयास के बजाय, यह निर्माण EWS के दो मुख्य कार्यों को अलग करता है:

1. अस्पष्टता (Ambiguity): एक अनाम 1-आउट-ऑफ-N (रिंग) सिग्नेचर द्वारा प्रदान की जाती है, जिसका उपयोग एक ब्लैक बॉक्स के रूप में किया जाता है।
2. पुष्टि (Confirmation): हस्ताक्षरकर्ता के दावे द्वारा प्रदान की जाती है, जिसमें विड्रोएबल ऑब्जेक्ट पर एक बाइंडिंग सिग्नेचर और हस्ताक्षरकर्ता के इंडेक्स के लिए एक हाइडिंग कमिटमेंट (hiding commitment) को खोलना शामिल है।

निर्माण 'फिएट-शमीर विद अबॉर्ट्स' (Fiat-Shamir with aborts) प्रतिमान पर कार्य करता है और तीन मॉड्यूलर घटकों पर निर्भर करता है:

• एक आधार सिग्नेचर स्कीम (जैसे, एक नो-हिंट, फुल-$t$ डिलिथियम-शैली की स्कीम)।
• एक अनाम 1-आउट-ऑफ-N सिग्नेचर (लैटिस वन-आउट-ऑफ-मेनी प्रूफ के माध्यम से स्थापित)।
• एक हाइडिंग-एंड-बाइंडिंग कमिटमेंट स्कीम (अजताई-शैली)।

विड्रोएबल सिग्नेचर $\sigma$ में संदेश पर एक रिंग सिग्नेचर $\sigma_r$ और हस्ताक्षरकर्ता के इंडेक्स के लिए एक कमिटमेंट $C$, और सार्वजनिक कुंजियों का सेट शामिल होता है। पुष्टि करने के लिए, हस्ताक्षरकर्ता $C$ के ओपनिंग $(i, \rho)$ को प्रकट करता है और अपने आधार गुप्त कुंजी के साथ पूरे विड्रोएबल ऑब्जेक्ट $\langle \mu, \pi, \sigma \rangle$ पर हस्ताक्षर करता है।

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

1. सुरक्षा मॉडल का परिशोधन: लेखक LSB के सुरक्षा मॉडल को परिष्कृत करते हैं।

   • वे LSB की "पूर्णता" (completeness) परिभाषा को एक 'एनोनिमिटी-अनटिल-क्लेम' (anonymity-until-claim) अविभेद्यता खेल (परिभाषा 14) से बदलते हैं, जो स्पष्ट रूप से हाइडिंग गारंटी को कैप्चर करता है।
   • वे 'क्लेमेबिलिटी साउंडनेस' (परिभाषा 16) पेश करते हैं, जो यह सुनिश्चित करता है कि एक पुष्ट हस्ताक्षर एक अद्वितीय हस्ताक्षरकर्ता इंडेक्स से बंधा हुआ है, जिससे हमलावर को एक ही हस्ताक्षर को विभिन्न रिंग सदस्यों के प्रति आरोपित करने से रोका जा सके।
   • वे एक निश्चित लक्ष्य इंडेक्स के साथ 'इनसाइडर करप्शन' के तहत अनफोर्जेबिलिटी को औपचारिक रूप देते हैं, जिससे मल्टीप्लिकेटिव $q_H$ (हैश क्वेरी) रिडक्शन लॉस से बचा जा सके जो LSB प्रमाण में मौजूद था।

2. जेनेरिक निर्माण: फिएट-शमीर विद अबॉर्ट्स प्रतिमान पर EWS का एक जेनेरिक निर्माण प्रस्तुत किया गया है। महत्वपूर्ण रूप से, यह कोई भी हस्ताक्षरकर्ता-व्युत्पन्न मान स्पष्ट रूप से प्रकाशित नहीं करता है। अस्पष्टता पूरी तरह से रिंग सिग्नेचर के ज़ीरो-नॉलेज गुणों से प्राप्त होती है, और ट्रैसेबिलिटी (traceability) कमिटमेंट के बाइंडिंग गुण से प्राप्त होती है।

3. असंभवता परिणाम (Impossibility Result): यह पेपर सिद्ध करता है (प्रपोजिशन 2) कि LSB 1-आउट-ऑफ-N सिग्नेचर (एडिटिव चैलेंज स्प्लिटिंग का उपयोग करके) का एक शाब्दिक लैटिस लिप्यंतरण असुरक्षित है। स्पार्स चुनौतियों (sparse challenges) के साथ लैटिस सेटिंग में, एक ईमानदार हस्ताक्षरकर्ता द्वारा वैध चैलेंज स्प्लिट उत्पन्न करने की संभावना नगण्य ($2^{-\Omega(n)}$) है, और यदि पूर्णता (completeness) को पैच भी कर दिया जाए, तो भी गुमनामी विफल हो जाएगी क्योंकि सिम्युलेटेड ट्रांसक्रिप्ट वास्तविक ट्रांसक्रिप्ट से अविभेद्य नहीं होगी।

4. पूर्ण सुरक्षा प्रमाण: लेखक (QROM) में निम्नलिखित के लिए स्पष्ट गेम-आधारित रिडक्शन प्रदान करते हैं:

   • सत्यता (Correctness): अंतर्निहित प्रिमिटिव्स की सत्यता तक रिडक्शन।
   • विस्तारित विड्रोएबिलिटी (Extended Withdrawability): कमिटमेंट की हाइडिंग (Decisional MLWE) और 1-आउट-ऑफ-N स्कीम की गुमनामी तक रिडक्शन।
   • अनफोर्जेबिलिटी (Unforgeability): बेस सिग्नेचर की EUF-CMA सुरक्षा तक रिडक्शन (बिना रिवाइंडिंग और बिना $q_H$ लॉस के)।
   • क्लेमेबिलिटी साउंडनेस (Claimability Soundness): कमिटमेंट के बाइंडिंग (MSIS) तक रिडक्शन।

5. इंस्टेंशिएशन (Instantiation): इस योजना को एक नो-हिंट, फुल-$t$ डिलिथियम-शैली के बेस सिग्नेचर और एक स्थापित लैटिस वन-आउट-ऑफ-मेनी प्रूफ का उपयोग करके स्थापित किया गया है। पेपर पैरामीटर चयन पर चर्चा करता है और नोट करता है कि HAETAE एक वैकल्पिक बेस के रूप में कार्य कर सकता है।

परिणाम
यह पेपर स्थापित करता है कि प्रस्तावित निर्माण है:

• सत्य (Correct): ईमानदार हस्ताक्षर अत्यधिक संभावना के साथ सत्यापित होते हैं।
• विस्तारित विड्रोएबल (Extended Withdrawable): एक हमलावर जिसके पास सभी गुप्त कुंजियाँ हैं, वह तब तक यह अंतर नहीं कर सकता कि रिंग के किस सदस्य ने विड्रोएबल सिग्नेचर बनाया है जब तक कि हस्ताक्षरकर्ता इसकी पुष्टि न कर दे।
• अनफोर्जेबल (Unforgeable): साइनिंग ऑरेकल और रिंग के सभी सदस्यों (लक्ष्य को छोड़कर) की गुप्त कुंजियों तक पहुंच के साथ भी, एक हमलावर एक नए संदेश के लिए पुष्ट हस्ताक्षर को फोर्ज नहीं कर सकता।
• साउंड (Sound): एक पुष्ट हस्ताक्षर को दो अलग-अलग हस्ताक्षरकर्ताओं के बीच आरोपित नहीं किया जा सकता है।

सुरक्षा मानक मॉड्यूल-लैटिस धारणाओं पर निर्भर करती है: Decisional MLWE, MSIS, और SelfTargetMSIS, साथ ही 1-आउट-ऑफ-N प्रूफ का ज़ीरो-नॉलेज गुण।

महत्व
यह पेपर दावा करता है कि यह विस्तारित विड्रोएबल हस्ताक्षरों का पहला सुरक्षित, पोस्ट-क्वांटम कार्यान्वयन प्रदान करता है। यह प्रदर्शित करता है कि LSB का डिस्क्रीट-लॉगारिदम निर्माण साझा मूल्यों के अभाव के कारण लैटिस में सीधे पोर्ट नहीं किया जा सकता है। समस्या को एक क्लेमेबल रिंग सिग्नेचर के रूप में पुनर्गठित करके और कमिटमेंट-आधारित पुष्टि तंत्र का उपयोग करके, लेखक एक ऐसी योजना प्राप्त करते हैं जो है:

• पोस्ट-क्वांटम सुरक्षित: लैटिस धारणाओं के माध्यम से क्वांटम हमलावरों के प्रति प्रतिरोधी।
• सार्वजनिक रूप से सत्यापन योग्य: डेसिग्नेटेड-वेरिफायर वेरिएंट के विपरीत, कोई भी पक्ष विड्रोएबल सिग्नेचर को सत्यापित कर सकता है।
• मॉड्यूलर: योजना के सुरक्षा प्रमाण केवल अंतर्निहित प्रिमिटिव्स के इंटरफेस पर निर्भर करते हैं, जिससे पूरे सिस्टम को फिर से सिद्ध किए बिना विभिन्न लैटिस-आधारित घटकों (जैसे, अलग बेस सिग्नेचर या रिंग प्रूफ) को बदलने की अनुमति मिलती है।
• मूल लक्ष्यों के प्रति वफादार: डिज़ाइन लैटिस सेटिंग में इसके संरचनात्मक दोषों को ठीक करते हुए मूल LSB योजना के कार्यात्मक लक्ष्यों और अंतर्ज्ञान को संरक्षित करता है।