💻 computer science

Towards Worst-case Hardness for Low-Noise LPN

यह शोध पत्र लर्निंग पेरिटी विद नॉइज़ (LPN) समस्या के लिए एक नया वर्स्ट-केस-टू-एवरेज-केस रिडक्शन प्रस्तुत करता है जो, सांख्यिकीय स्मूथिंग से कंप्यूटेशनल इंडिस्टिंग्विशेबिलिटी की ओर स्थानांतरित होकर, इन्वर्स-पॉलीनोमियल नॉइज़ रेट्स के लिए हार्डनेस प्राप्त करता है जो पब्लिक-की एनक्रिप्शन के लिए पर्याप्त है, एक ऐसा क्षेत्र जो पहले वर्स्ट-केस रिडक्शन के माध्यम से अप्राप्य था।

मूल लेखक: Divesh Aggarwal, Rishav Gupta, Hai Hoang Nguyen, Kel Zin Tan, Prashant Nalini Vasudevan

प्रकाशित 2026-06-05

📖 7 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Divesh Aggarwal, Rishav Gupta, Hai Hoang Nguyen, Kel Zin Tan, Prashant Nalini Vasudevan

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

यहाँ "Towards Worst-case Hardness for Low-Noise LPN" पेपर की व्याख्या सरल भाषा और रोज़मर्रा के उदाहरणों के साथ दी गई है।

बड़ी तस्वीर: एक ताला, एक चाबी और एक शोर भरा संकेत

कल्पना कीजिए कि आप एक सुपर-सुरक्षित डिजिटल लॉक (क्रिप्टोग्राफी) बनाने की कोशिश कर रहे हैं। इस ताले को अटूट बनाने के लिए, आप एक गणितीय पहेली पर भरोसा करते हैं जिसे LPN (Learning Parity with Noise) कहा जाता है।

LPN को इस तरह समझें:

आपके पास एक गुप्त कोड है (0 और 1 की एक स्ट्रिंग)।
आप उस कोड के आधार पर कई संदेश भेजते हैं।
लेकिन, एक शरारती 'ग्रेमलिन' (gremlin) उन संदेशों में रैंडम "शोर" (noise) जोड़ देता है (कुछ 0 को 1 में और कुछ 1 को 0 में बदल देता है)।
चुनौती: क्या एक हैकर केवल उन शोर वाले संदेशों को देखकर मूल गुप्त कोड का पता लगा सकता है?

यदि शोर बहुत अधिक है (50% बिट्स बदल दिए गए हैं), तो संदेश पूरी तरह से निरर्थक (gibberish) दिखेंगे, और गुप्त कोड सुरक्षित रहेगा। यदि शोर बहुत कम है, तो गुप्त कोड का पता लगाना आसान है। क्रिप्टोग्राफर्स को "गोल्डिलॉक्स" ज़ोन (Goldilocks zone) की आवश्यकता होती है: इतना शोर कि गुप्त कोड छिप सके, लेकिन इतना भी नहीं कि सिस्टम बेकार हो जाए।

समस्या: "सांख्यिकीय" दीवार (The "Statistical" Wall)

लंबे समय तक, क्रिप्टोग्राफर्स को एक बड़ा सिरदर्द रहा। वे जानते थे कि LPN पहेली को औसतन (average case) हल करना कठिन है (शोर के रैंडम मिश्रण के लिए)। लेकिन वे यह साबित नहीं कर पा रहे थे कि यह सबसे कठिन स्थिति (worst-case scenario) में भी कठिन है।

यह क्यों मायने रखता है?

LWE (इसका यूक्लिडियन चचेरा भाई): LWE नामक एक समान समस्या के लिए, गणितज्ञों ने सिद्ध किया कि यदि आप पहेली के सबसे आसान संस्करण को हल कर सकते हैं, तो आप इसके सबसे कठिन संस्करण को भी हल कर सकते हैं। इसने उन्हें एक सुरक्षा कवच दिया: "यदि सबसे कठिन स्थिति कठिन है, तो हमारा ताला सुरक्षित है।"
LPN (इसका बाइनरी चचेरा भाई): LPN के लिए, इसी तरह का संबंध बनाने के पिछले प्रयासों ने "स्टैटिस्टिकल स्मूदनिंग" (Statistical Smoothing) नामक तकनीक का उपयोग किया।

स्मूदनिंग का उदाहरण:
कल्पना कीजिए कि आप पानी की एक बाल्टी (शोर) में लाल रंग की एक बूंद (गुप्त कोड) को इतनी अच्छी तरह मिलाने की कोशिश कर रहे हैं कि आप बता न सकें कि लाल रंग कहाँ है।

पुराना तरीका (Statistical Smoothing): पिछले शोधकर्ताओं ने डाई (रंग) को इतना पूरी तरह मिलाने की कोशिश की कि पानी सांख्यिकीय रूप से (statistically) सादे पानी जैसा दिखने लगे।
दोष: पानी को पूरी तरह से एकसमान दिखाने के लिए, उन्हें इतना अधिक पानी (शोर) उपयोग करना पड़ा कि लाल रंग बहुत अधिक पतला हो गया। परिणामी पहेली इतनी शोर भरी थी (लगभग 50% शोर) कि वह पब्लिक-की एन्क्रिप्शन जैसे सुरक्षित ताले बनाने के लिए बेकार थी। वे एक दीवार से टकरा गए: वे सिद्ध तो कर सकते थे कि पहेली कठिन है, लेकिन केवल उस शोर के स्तर पर जो ताले को बहुत कमजोर बना देता था।

नया विचार: "कंप्यूटेशनल" स्मूदनिंग (Computational Smoothing)

इस पेपर के लेखकों (अग्रवाल, गुप्ता, आदि) ने खेल के नियम बदलने का फैसला किया। यह माँगने के बजाय कि पानी सांख्यिकीय रूप से सादे पानी जैसा दिखना चाहिए, उन्होंने पूछा: "क्या पानी एक कंप्यूटर के लिए रैंडम दिखता है?"

यह एक सूक्ष्म लेकिन शक्तिशाली बदलाव है।

सांख्यिकीय अविभेद्यता (Statistical Indistinguishability): यहाँ तक कि अनंत समय लेने वाले एक सुपर-स्मार्ट एलियन भी अंतर नहीं बता पाएगा।
कंप्यूटेशनल अविभेद्यता (Computational Indistinguishability): एक कंप्यूटर (भले ही वह बहुत तेज़ हो) उचित समय में अंतर नहीं बता पाएगा।

नया उदाहरण:
कल्पना कीजिए कि एक जादूगर (कंप्यूटर) यह पता लगाने की कोशिश कर रहा है कि लाल रंग की बूंद कहाँ है।

पुराने तरीके के लिए यह आवश्यक था कि डाई सूक्ष्मदर्शी (microscope) से भी अदृश्य हो।
नए तरीके के लिए केवल यह आवश्यक है कि डाई जादूगर की आँखों के लिए अदृश्य हो।

"पूरी तरह अदृश्य" से "कंप्यूटर के लिए अदृश्य" होने की शर्त को कम करके, लेखकों ने शोर के स्तर को इतना कम रखने का तरीका खोज लिया जो वास्तविक दुनिया के एन्क्रिप्शन के लिए उपयोगी हो।

"विन-विन" संरचना (The "Win-Win" Structure)

यह पेपर एक चतुर "विन-विन" परिदृश्य पेश करता है। वे कहते हैं: "यदि कोई हैकर हमारे LPN पहेली को हल कर सकता है, तो अंतर्निहित गणित के बारे में दो में से एक बात सत्य होनी चाहिए:"

विकल्प A (डिकोडर): हैकर एक मास्टर डिकोडर बन गया है जो कोड-तोड़ने वाली पहेली (रैंडम शोर से कोड को डिकोड करना) के सबसे कठिन संस्करण को हल कर सकता है।
विकल्प B (डिस्टिंग्विशर): हैकर एक मास्टर डिटेक्टिव बन गया है जो "शोर वाले कोड" और "शुद्ध रैंडम शोर" के बीच अंतर पहचान सकता है (dual code को पहचानना)।

जादू:
लेखक यह सिद्ध करते हैं कि आप ऐसा हैकर नहीं रख सकते जो इन दो अन्य कठिन कार्यों में से एक में कुशल हुए बिना LPN पहेली को हल कर सके।

यदि "Dual Code" को पहचानना कठिन है, तो LPN पहेली सुरक्षित है।
यदि "Dual Code" को पहचानना आसान है, तो भी LPN पहेली सुरक्षित है (क्योंकि हैकर को एक मास्टर डिकोडर होना होगा, जो कि स्वयं कठिन माना जाता है)।

यह कहने जैसा है: "यदि आप इस तिजोरी को तोड़ सकते हैं, तो आपको या तो एक मास्टर लॉकस्मिथ (ताला बनाने वाला) होना होगा या एक मास्टर फिंगरप्रिंट एनालिस्ट। चूंकि हम मानते हैं कि ये दोनों ही काम अविश्वसनीय रूप से कठिन हैं, इसलिए तिजोरी सुरक्षित है।"

परिणाम: पब्लिक-की एन्क्रिप्शन को अनलॉक करना

इस पेपर का सबसे रोमांचक हिस्सा वह है जो होता है जब वे इस नई विधि को लागू करते हैं।

पिछली सीमा: पुराने तरीके केवल बहुत उच्च शोर (high noise) के साथ सुरक्षा सिद्ध कर सकते थे (जो पब्लिक-की एन्क्रिप्शन के लिए बेकार था)।
नई उपलब्धि: यह नया तरीका कम शोर (low noise) (विशेष रूप से, शोर जो सिस्टम के बड़े होने के साथ घटता है, जैसे $1/\sqrt{n}$ ) के साथ सुरक्षा सिद्ध करता है।

यह एक बड़ी बात क्यों है?
यह विशिष्ट लो-नॉइज़ रिजीम (low-noise regime) ठीक वही है जो पब्लिक-की एन्क्रिप्शन (वह प्रकार का एन्क्रिप्शन जो आपको बिना पहले से पासवर्ड साझा किए सुरक्षित ईमेल भेजने की अनुमति देता है) बनाने के लिए आवश्यक है।

पेपर दिखाता है कि यदि हम यह मान लें कि "Dual Code" की समस्याएं कठिन हैं, तो हम अंततः एक ठोस सैद्धांतिक आधार के साथ LPN पर आधारित पब्लिक-की एन्क्रिप्शन बना सकते। यह एक ऐसा क्षेत्र था जो पहले "वर्स्ट-केस" प्रमाणों के लिए अप्राप्य था।

संक्षेप में सारांश

लक्ष्य: LPN क्रिप्टोग्राफी पहेली को सबसे कठिन संभव संस्करण से जोड़कर यह सिद्ध करना कि यह अटूट है।
पुरानी समस्या: पिछले प्रमाणों के लिए शोर का स्तर इतना अधिक होना आवश्यक था कि एन्क्रिप्शन बेकार हो जाता था।
नया तरीका: पूर्ण यादृच्छिकता (randomness) की मांग करने के बजाय, वे केवल "कंप्यूटर-प्रूफ" यादृच्छिकता की मांग करते हैं।
विन-विन: वे दिखाते हैं कि पहेली को तोड़ने का अर्थ है दो अन्य कठिन गणितीय समस्याओं में से एक को तोड़ना।
परिणाम: यह उन्हें कम शोर के स्तर पर LPN की सुरक्षा सिद्ध करने की अनुमति देता है, जिससे अंततः सुरक्षित पब्लिक-की एन्क्रिप्शन सिस्टम का निर्माण संभव होता है।

यह पेपर यह दावा नहीं करता कि उन्होंने आज एक नया एन्क्रिप्शन सिस्टम बनाया है; बल्कि, यह एक सैद्धांतिक सुरक्षा प्रमाण पत्र (theoretical safety certificate) प्रदान करता है जो कहता है, "हाँ, इन विशिष्ट मापदंडों का उपयोग करके इन प्रणालियों को बनाना गणितीय रूप से सुरक्षित है।"

तकनीकी सारांश: लो-नॉइज़ LPN के लिए वर्स्ट-केस हार्डनेस की ओर

समस्या विवरण

लर्निंग परिटी विद नॉइज़ (LPN) समस्या क्रिप्टोग्राफी में एक मौलिक धारणा है, जो सिमेट्रिक-की प्रिमिटिव्स और पब्लिक-की एन्क्रिप्शन (PKE) का आधार है। जबकि एनालॉगस लर्निंग विद एरर्स (LWE) समस्या की एवरेज-केस हार्डनेस को वर्स्ट-केस लैटिस धारणाओं द्वारा समर्थित किया जाता है, LPN के लिए इसी तरह की वर्स्ट-केस-टू-एवरेज-केस रिडक्शन स्थापित करना एक केंद्रीय खुला प्रश्न बना हुआ है।

LPN के मौजूदा रिडक्शन, विशेष रूप से ब्रेकर्सकी एट अल. [BLVW19] और यू और झांग [YZ21] द्वारा, लीनियर कोड्स के सांख्यिकीय स्मूथिंग (statistical smoothing) पर निर्भर करते हैं। इन विधियों के लिए यह आवश्यक है कि जनरेटर मैट्रिक्स की पंक्तियों के रैंडम स्पार्स कॉम्बिनेशन सांख्यिकीय रूप से यूनिफॉर्म के करीब हों। यह आवश्यकता परिणामी एवरेज-केस हार्डनेस को $1/2 - 1/\text{poly}(n)$ जैसे उच्च नॉइज़ रेट तक सीमित कर देती है। इतने उच्च नॉइज़ रेट पब्लिक-की अनुप्रयोगों के लिए अपर्याप्त हैं, जिन्हें आमतौर पर इनवर्स-पॉलीनोमियल नॉइज़ रेट (जैसे, $n^{-1/2}$ ) या सब-एक्स्पोनेंशियल टाइम एल्गोरिदम के विरुद्ध निरंतर नॉइज़ रेट की आवश्यकता होती है। इसके अलावा, मौजूदा रिडक्शन के लिए आवश्यक वर्स्ट-केस धारणाएं (जैसे, बहुत कम नॉइज़ रेट के साथ नियरएस्ट कोडवर्ड प्रॉब्लम की हार्डनेस) या तो कमजोर हैं या उनके लिए अवास्तविक प्री-प्रोसेसिंग धारणाओं की आवश्यकता है।

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

लेखक एक नया दृष्टिकोण प्रस्तावित करते हैं जो सांख्यिकीय स्मूथिंग की आवश्यकता को कंप्यूटेशनल इंडिस्टिंगुइशेबिलिटी (computational indistinguishability) में बदलकर शिथिल करता है। यह मांग करने के बजाय कि कोड की पंक्तियों के रैंडम स्पार्स कॉम्बिनेशन सांख्यिकीय रूप से यूनिफॉर्म के करीब हों, लेखक केवल यह मांग करते हैं कि वे यूनिफॉर्म से कंप्यूटेशनल रूप से इंडिस्टिंगुइशेबल हों।

यह बदलाव एक दी गई मैट्रिक्स $A \in \mathbb{F}_2^{m \times n}$ के गुणों पर आधारित एक "विन-विन" (win-win) संरचना की ओर ले जाता है:

कोड को डिकोड करना: यदि रैंडम कॉम्बिनेशन यूनिफॉर्म से कंप्यूटेशनल रूप से इंडिस्टिंगुइशेबल हैं, तो $A$ द्वारा जनरेट किए गए कोड को रैंडम नॉइज़ से डिकोड करने के लिए एक कुशल LPN सॉल्वर का उपयोग किया जा सकता है।
ड्यूल को डिस्टिंग्विश करना: यदि रैंडम कॉम्बिनेशन यूनिफॉर्म से कंप्यूटेशनल रूप से इंडिस्टिंगुइशेबल नहीं हैं, तो डिस्टिंग्विशर प्रभावी रूप से $A$ के ड्यूल कोड के लिए एक डिकोडिंग समस्या के डिसीजन वर्जन को हल करता है (विशेष रूप से, फिक्स्ड-वेट सिंड्रोम्स को यूनिफॉर्म से डिस्टिंग्विश करना)।

रिडक्शन इस अवलोकन पर निर्भर करता है कि यदि $A$ को एक जनरेटर मैट्रिक्स के रूप में देखा जाए, तो $A^T$ ड्यूल कोड के पैरिटी-चेक मैट्रिक्स के रूप में कार्य करता है। $r^T A$ दिए जाने पर वेक्टर $r$ को रिकवर करना ड्यूल कोड को $r$ को नॉइज़ वेक्टर के रूप में उपयोग करके डिकोड करने के समान है।

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

1. मुख्य रिडक्शन थ्योरम

पेपर एक रिडक्शन (थ्योरम 3.1) प्रस्तुत करता है जो यह दर्शाता है कि LPN की हार्डनेस दो समस्याओं की वर्स्ट-केस सिमल्टेनियस हार्डनेस (worst-case simultaneous hardness) से प्राप्त की जा सकती है:

एक मैट्रिक्स $A$ द्वारा जनरेट किए गए कोड को रैंडम नॉइज़ से डिकोड करना।
$A$ के ड्यूल कोड के रैंडम नॉइजी कोडवर्ड्स (सिंड्रोम्स) को यूनिफॉर्म से डिस्टिंग्विश करना।

थ्योरम 1.1 (अनौपचारिक): मान लीजिए कि $n$ वेरिएबल्स, $t$ सैंपल्स और नॉइज़ रेट $n^{-\alpha}$ के साथ सर्च LPN को हल करने में एक कुशल एल्गोरिदम के पास गैर-नगण्य एडवांटेज है। तो, किसी भी कांस्टेंट $\beta > 0$ के लिए जहाँ $\alpha + \beta < 1$ , ऐसे कुशल एल्गोरिदम $S$ और $D$ मौजूद हैं कि किसी भी मैट्रिक्स $A$ के लिए:

या तो $S$ मैट्रिक्स $A$ द्वारा जनरेट किए गए कोड को $n^{-(\alpha+\beta)}$ की दर वाले रैंडम नॉइज़ से डिकोड कर सकता है।
या $D$ $n^{\beta}/m$ नॉइज़ रेट के लिए $A$ के ड्यूल के नॉइजी कोडवर्ड्स को यूनिफॉर्म से डिस्टिंग्विश कर सकता है।

2. पब्लिक-की क्रिप्टोग्राफी के लिए इंस्टेंशिएशन

विशिष्ट पैरामीटर्स सेट करके, लेखक प्रदर्शित करते हैं कि उनका रिडक्शन एलेखनविच के पब्लिक-की एन्क्रिप्शन कंस्ट्रक्शन [Ale03] के लिए आवश्यक रिजीम में LPN हार्डनेस प्रदान करता है।

पैरामीटर्स: $\alpha = 0.5$ (लक्ष्य नॉइज़ रेट $n^{-0.5}$ ), $\beta = 0.45$ , और $m = O(n^{2.9})$ सेट करना।
परिणाम: यह इमप्लाइज करता है कि $t=2n$ सैंपल्स और $n^{-0.5}$ नॉइज़ रेट के साथ LPN की हार्डनेस, एक कोड और उसके ड्यूल की सिमल्टेनियस वर्स्ट-केस हार्डनेस को मानते हुए।
महत्व: यह पैरामीटर रिजीम पहले सांख्यिकीय स्मूथिंग का उपयोग करके वर्स्ट-केस रिडक्शन के माध्यम से अप्राप्य था।

3. तकनीकी चुनौतियाँ और समाधान

लेखक सांख्यिकीय से कंप्यूटेशनल स्मूथिंग की ओर बढ़ने की कठिनाई को संबोधित करते हैं। सांख्यिकीय सेटिंग में, फूरियर एनालिसिस स्मूथड मैट्रिक्स और नॉइज़ के जॉइंट डिस्ट्रीब्यूशन को आसानी से हैंडल करता है। कंप्यूटेशनल सेटिंग में, लेखक दिखाते हैं कि भले ही $r^T A$ स्यूडो-रैंडम हो, लीकेज $r^T e$ संभावित रूप से जॉइंट डिस्ट्रीब्यूशन को डिस्टिंग्विशेबल बना सकता है।

समाधान: रिडक्शन एक एल्गोरिदम $S$ का निर्माण करता है जो रैंडम बर्नौली नॉइज़ (random Bernoulli noise) से डिकोड करता है, न कि वर्स्ट-केस नॉइज़ से। लेखक सिद्ध करते हैं कि $r$ के अधिकांश चॉइस के लिए, बिट्स $r^T e$ स्वतंत्र बर्नौली वेरिएबल्स की तरह व्यवहार करते हैं, भले ही $r$ को फिक्स किया गया हो। यह रिडक्शन को आगे बढ़ने की अनुमति देता है बिना इस शर्त की आवश्यकता के कि $r^T e$ सभी वर्स्ट-केस एरर वेक्टर्स के लिए अनबायस्ड हो, जो कि पहले एक बाधा थी।

महत्व और दावे

पेपर दावा करता है कि यह वर्स्ट-केस धारणाओं पर आधारित इनवर्स-पॉलीनोमियल नॉइज़ रेट्स (विशेष रूप से $n^{-1/2}$ ) के साथ LPN हार्डनेस स्थापित करने के लिए एक मार्ग प्रदान करता है। यह वर्स्ट-केस हार्डनेस धारणाओं से पब्लिक-की एन्क्रिप्शन बनाने के लक्ष्य की दिशा में एक महत्वपूर्ण कदम है, जो LWE की तुलना में LPN के लिए मायावी रहा है।

लेखक स्पष्ट रूप से अपनी सीमाओं और मामूली दावों को नोट करते हैं:

गैर-मानक धारणा: रिडक्शन एक कोड और उसके ड्यूल को डिकोड करने की सिमल्टेनियस हार्डनेस पर निर्भर करता है। यह धारणा गैर-मानक है और स्वतंत्र रूप से अध्ययन नहीं की गई है। लेखक यह दावा नहीं करते हैं कि यह धारणा मौजूदा धारणाओं से कमजोर है, बल्कि यह उनके विशिष्ट दृष्टिकोण के लिए एक आवश्यक स्थिति है ताकि सांख्यिकीय स्मूथिंग बाधा को पार किया जा सके।
रैंडम बनाम वर्स्ट-केस नॉइज़: परिणामी डिकोडर $S$ रैंडम बर्नौली नॉइज़ के विरुद्ध काम करता है, जबकि पिछले रिडक्शन (जैसे, [BLVW19]) वर्स्ट-केस बाउंडेड-वेट नॉइज़ के लिए डिकोडर बनाते थे। लेखक स्वीकार करते हैं कि उनके दृष्टिकोण को वर्स्ट-केस नॉइज़ तक विस्तारित करना उनके परिणाम को महत्वपूर्ण रूप से मजबूत करेगा लेकिन इसके लिए कंप्यूटेशनल एंट्रॉपी के बारे में तर्क देने के लिए नए टूल्स की आवश्यकता होगी।
सब-एक्स्पोनेंशियल टाइम: प्रमेय में निर्दिष्ट वर्स्ट-केस समस्याओं (एक जेनेरिक कोड और उसके ड्यूल को डिकोड करना) के लिए सबसे अच्छे ज्ञात एल्गोरिदम सब-एक्स्पोनेंशियल समय में चलते हैं। इस प्रकार, रिडक्शन सब-एक्स्पोनेंशियल वर्स्ट-केस हार्डनेस धारणाओं के आधार पर पॉलीनोमियल-टाइम एल्गोरिदम के विरुद्ध LPN हार्डनेस स्थापित करता है।

संक्षेप में, पेपर एक "क्लीन विन-विन" रिडक्शन प्रदान करता है जो सांख्यिकीय आवश्यकता को कंप्यूटेशनल आवश्यकता में बदलकर, LPN हार्डनेस को पब्लिक-की एन्क्रिप्शन के लिए पर्याप्त नॉइज़ रेट पर सक्षम बनाता है, बशर्ते कि एक कोड को डिकोड करने और उसके ड्यूल की सिमल्टेनियस हार्डनेस को स्वीकार किया जाए।