💻 computer science

Attacks on Sparse LWE and Sparse LPN with new Sample-Time tradeoffs

यह शोध पत्र किकुची पद्धति (Kikuchi method) का विस्तार करते हुए उच्च माड्यूली $q$ वाले स्पार्स लर्निंग विद एरर्स (LWE) और लर्निंग पैरिटी विद नॉइज़ (LPN) समस्याओं पर दो नए हमलों का प्रस्ताव देता है, जो नमूना और समय जटिलता के बीच बेहतर ट्रेड-ऑफ स्थापित करने के लिए स्पेक्ट्रल नॉर्म्स और किकुची ग्राफों पर क्लोज्ड वॉक (closed walks) का उपयोग करते हैं।

मूल लेखक: Shashwat Agrawal, Amitabha Bagchi, Rajendra Kumar

प्रकाशित 2026-03-31

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

CC BY 4.0

मूल लेखक: Shashwat Agrawal, Amitabha Bagchi, Rajendra Kumar

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

कल्पना कीजिए कि आप एक जासूस हैं जो एक रहस्य को सुलझाने की कोशिश कर रहे हैं। वह रहस्य एक विशाल, अराजक स्प्रेडशीट के भीतर छिपा एक गुप्त कोड है। इस स्प्रेडशीट में हजारों पंक्तियाँ हैं, लेकिन ट्विस्ट यह है कि अधिकांश सेल खाली हैं। केवल कुछ ही सेल्स में वास्तविक संख्याएँ मौजूद हैं।

यह Sparse LWE और Sparse LPN की दुनिया है। क्रिप्टोग्राफी (वह गणित जो आपके बैंक खातों और संदेशों को सुरक्षित रखता है) की दुनिया में, ये वे "कठिन समस्याएँ" हैं जो डेटा की रक्षा करती हैं। यदि कोई उन्हें आसानी से हल कर सके, तो वे एन्क्रिप्शन को तोड़ सकते हैं।

लंबे समय से, गणितज्ञों को पता था कि ये समस्याएँ कठिन हैं यदि स्प्रेडशीट यादृच्छिक संख्याओं (random numbers) से पूरी तरह भरी हो। लेकिन क्या होगा अगर स्प्रेडशीट ज्यादातर खाली (sparse) हो? क्या यह अभी भी कठिन है? या क्या यह खालीपन इसे क्रैक करना आसान बना देता है?

शश्वत अग्रवाल, अभितभा भगची और राजेंद्र कुमार का यह शोध पत्र एक नए जासूसी मैनुअल की तरह है। वे इन "स्पार्स" रहस्यों को हल करने के दो नए, चतुर तरीके पेश करते हैं, भले ही संख्याएँ जटिल हों (केवल साधारण 0 या 1 न हों)।

यहाँ बताया गया है कि वे इन "स्पार्स" रहस्यों को कैसे हल करते हैं, रोजमर्रा के उदाहरणों के साथ समझाया गया है।

सेटअप: "स्पार्स" स्प्रेडशीट

कल्पना कीजिए कि आपके पास $n$ कॉलम का एक विशाल ग्रिड है। एक गुप्त संदेश कुछ विशिष्ट कॉलमों में छिपा है (मान लीजिए कि $k$ कॉलम)। बाकी सब शून्य हैं।

समस्या: आपको समीकरणों (पंक्तियों) की एक सूची दी जाती है जो इन कॉलमों को शोर (static/noise) के साथ मिलाती हैं। आपको यह पता लगाना है: क्या समीकरणों की यह सूची एक गुप्त पैटर्न (Planted) द्वारा बनाई गई है, या यह केवल रैंडम कचरा (Random) है?
चुनौती: यदि आपके पास बहुत कम समीकरण हैं, तो अंतर बताना असंभव है। यदि आपके पास बहुत अधिक हैं, तो यह आसान है। यह शोध पत्र पूछता है: वह सटीक टिपिंग पॉइंट (tipping point) क्या है जहाँ यह आसान हो जाता है?

नया उपकरण: "किकुची ग्राफ" (Kikuchi Graph)

इसे हल करने के लिए, लेखक एक विशाल मानचित्र बनाते हैं जिसे किकुची ग्राफ कहा जाता है।

उपमा: कल्पना कीजिए कि आपके पास $n$ मेहमानों के साथ एक बड़ी पार्टी है। मेहमानों को सीधे देखने के बजाय, आप एक ऐसा मानचित्र बनाते हैं जहाँ मेहमानों का हर संभावित समूह एक "कमरा" है।
यदि मेहमानों के दो समूह आपके स्प्रेडशीट के समीकरणों के आधार पर एक विशिष्ट संबंध साझा करते हैं, तो आप उनके कमरों के बीच एक दरवाजा (एक किनारा/edge) खींचते हैं।
यह समीकरणों की एक अव्यवस्थित सूची को कमरों और दरवाजों के एक संरचित नेटवर्क में बदल देता है।

लेखक इस मानचित्र का उपयोग दो अलग-अलग तरीकों से इस "गुप्त पैटर्न" को पकड़ने के लिए करते हैं।

हमला #1: "स्पेक्ट्रल" विधि (कंपन परीक्षण - The Vibration Test)

अवधारणा: कल्पना कीजिए कि आपका किकुची ग्राफ तारों (edges) से बना एक विशाल, जटिल वाद्य यंत्र है।

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

हमला #2: "क्लोज्ड वॉक" विधि (खजाने की खोज - The Treasure Hunt)

अवधारणा: यह तरीका मानचित्र पर खजाने की खोज जैसा है।

रणनीति: लेखक ग्राफ पर एक विशिष्ट प्रकार के पथ की तलाश करते हैं जिसे "क्लोज्ड वॉक" (Closed Walk) कहा जाता है। यह एक ऐसा पथ है जो एक कमरे से शुरू होता है, अन्य कमरों से होकर गुजरता है, और अंततः वापस शुरुआती बिंदु पर लौट आता है।
ट्रिक: एक रैंडम ग्राफ में, ये लूप दुर्लभ और अव्यवस्थित होते हैं। एक गुप्त पैटर्न वाले ग्राफ में, ये लूप प्रचुर मात्रा में होते हैं और एक विशिष्ट लय का पालन करते हैं।
गणितीय जादू: वे उन दरवाजों से गुजरते हुए जो नंबर (लेबल) उन्होंने लिए, उन्हें आपस में गुणा करते हैं।
- रैंडम केस: नंबर एक-दूसरे को रद्द कर देते हैं, जिससे परिणाम शून्य के करीब आता है।
- गुप्त केस: नंबर एक-दूसरे को सुदृढ़ करते हैं, जिससे एक बड़ा मान प्राप्त होता है।
हमला: वे ऐसे कई लूप ढूंढते हैं, गणित करते हैं, और जांचते हैं कि परिणाम बड़ा है या छोटा।
- लाभ: यदि आपके पास पर्याप्त डेटा है, तो यह "वाइब्रेशन टेस्ट" की तुलना में बहुत तेज़ (क्वाड्रेटिक स्पीडअप) है। यह तब भी काम करता है जब समीकरण पूरी तरह से यादृच्छिक न हों।
- हानि: यह बहुत चयनात्मक है। यह केवल तभी काम करता है जब संख्याएँ "प्राइम" (एक विशिष्ट प्रकार के पूर्णांक) हों और शोर कम हो।

यह क्यों मायने रखता है? ("ट्रेड-ऑफ")

इस शोध पत्र का सबसे बड़ा योगदान "स्वीट स्पॉट" (Sweet Spot) को खोजना है।

इसे एक ट्रेड-ऑफ के रूप में सोचें: समय (पहेली सुलझाने में लगने वाला समय) और सैंपल्स (सुरागों/समीकरणों की संख्या जो आपको चाहिए)।

पुराना तरीका: इसे जल्दी हल करने के लिए आपको बहुत अधिक सुरागों की आवश्यकता थी, या बहुत कम सुरागों के साथ इसे हल करने के लिए आपको सुपरकंप्यूटर की आवश्यकता थी।
नया तरीका: लेखक दिखाते हैं कि आप एक "डायल" (पैरामीटर $l$ $l$ ) को ट्यून कर सकते हैं।
- यदि आपके पास बहुत सारे सुराग हैं, तो आप इसे बहुत तेज़ी से हल कर सकते हैं।
- यदि आपके पास कम सुराग हैं, तो इसमें अधिक समय लगता है, लेकिन वे यह भी सिद्ध करते हैं कि इसमें वास्तव में कितना समय लगता है।

"बड़ी तस्वीर" का निष्कर्ष

शोध पत्र यह निष्कर्ष निकालता है कि कुछ प्रकार की स्पार्स समस्याओं के लिए, "गुप्त पैटर्न" को खोजना वास्तव में हमारी सोच से अधिक आसान है, बशर्ते आपके पास पर्याप्त डेटा हो।

हालाँकि, वे एक सुरक्षा कवच की भी पुष्टि करते हैं: यदि "स्पैरसिटी" (खाली सेल्स की संख्या) पर्याप्त रूप से अधिक है, तो समस्या अविश्वसनीय रूप से कठिन बनी रहती है, यहाँ तक कि इन नई विधियों के लिए भी। यह सुझाव देता है कि इन स्पार्स समस्याओं का उपयोग करने वाली वर्तमान एन्क्रिप्शन प्रणालियाँ अभी भी सुरक्षित हैं, लेकिन अब हमारे पास एक बेहतर मानचित्र है कि वे वास्तव में कितनी सुरक्षित हैं।

संक्षेप में:
लेखकों ने स्पार्स डेटा में छिपे पैटर्न को खोजने के लिए दो नए "जासूसी उपकरण" (एक कंपन परीक्षण और एक खजाने की खोज) बनाए हैं। उन्होंने सिद्ध किया कि हालांकि ये पैटर्न पहले की तुलना में तेजी से पाए जा सकते हैं, लेकिन अंतर्निहित गणित अभी भी हमारे डिजिटल जगत को सुरक्षित रखने के लिए पर्याप्त मजबूत है, बशर्ते हम अपने मापदंडों (parameters) का चयन बुद्धिमानी से करें।

यहाँ शश्वत अग्रवाल, अमितभा बागची और राजेंद्र कुमार के शोध पत्र "Attacks on Sparse LWE and Sparse LPN with new Sample-Time tradeoffs" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र उच्च माड्यूली (moduli) $q$ पर स्पार्स लर्निंग विद एरर्स (Sparse LWE) और स्पार्स लर्निंग पारिटी विद नॉइज़ (Sparse LPN) की कम्प्यूटेशनल हार्डनेस (computational hardness) को संबोधित करता है।

संदर्भ: मानक LWE और LPN आधारभूत लैटिस-आधारित क्रिप्टोग्राफी (lattice-based cryptography) के स्तंभ हैं। स्पैरसिटी बाधाओं (जहाँ गुणांक सदिशों में केवल $k \ll n$ गैर-शून्य प्रविष्टियाँ होती हैं) वाले वेरिएंट का उपयोग क्रिप्टोग्राफिक प्रिमिटिव्स (जैसे, तेज़ की जनरेशन, छोटे सिफरटेक्स्ट) की दक्षता में सुधार के लिए किया जाता है।
अंतराल (The Gap): जबकि $\mathbb{Z}_2$ (बाइनरी) पर Sparse LWE/LPN का व्यापक अध्ययन किया गया है, बड़े माड्यूली $q$ (जहाँ $q$ सुरक्षा पैरामीटर के बहुपद/polynomial के रूप में है) पर इन समस्याओं की हार्डनेस अभी भी कम खोजी गई है।
उद्देश्य: $k$ -स्पार्स LWE/LPN के लिए 'प्लांटेड' (noisy) इंस्टेंस को 'रैंडम' इंस्टेंस से अलग करने के लिए सैंपल कॉम्प्लेक्सिटी ( $m$ , नमूनों की संख्या) और टाइम कॉम्प्लेक्सिटी के बीच एक सूक्ष्म विश्लेषण (fine-grained analysis) प्रदान करना।

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

लेखक किकुची विधि (Kikuchi Method) का सामान्यीकरण करते हैं, जिसे पहले $k$ -XOR ( $\mathbb{Z}_2$ पर Sparse LPN) पर लागू किया गया था, ताकि उच्च माड्यूली $q$ को संभाला जा सके। मुख्य दृष्टिकोण एक किकुची ग्राफ (Kikuchi Graph) का निर्माण करना है ताकि रैखिक समीकरणों को अलग करने की समस्या को एक ग्राफ-थ्योरेटिक समस्या में बदला जा सके।

A. किकुची ग्राफ का सामान्यीकरण

$q=2$ के लिए, रैखिक समीकरणों को $\{\pm 1\}$ पर उत्पाद समीकरणों (product equations) में परिवर्तित किया जाता है। $q > 2$ के लिए, लेखक विशिष्ट संशोधन पेश करते हैं:

रूट्स ऑफ यूनिटी (Roots of Unity) पर उत्पाद समीकरण: $\mathbb{Z}_q$ पर रैखिक समीकरणों को $q$ -वें रूट्स ऑफ यूनिटी, $\Omega_q = \{1, \omega_q, \dots, \omega_q^{q-1}\}$ के समूह पर उत्पाद समीकरणों के रूप में फिर से लिखा जाता है।
उच्च-आयामी लिफ्टिंग (High-Dimensional Lifting): $[n]$ से आकार $l$ के उपसमुच्चयों (subsets) में लिफ्ट करने के बजाय, ग्राफ के वर्टिक्स को उपसमुच्चयों और गुणांकों के युग्मों $\binom{[n]}{l} \times [q]^l$ में लिफ्ट किया जाता है। यह स्पार्स वेक्टर्स के इंडेक्स और गुणांक दोनों को एनकोड करता है।
निर्देशित ग्राफ निर्माण (Directed Graph Construction): सामान्यीकृत सिमेट्रिक डिफरेंस एक निर्देशित (directed) ग्राफ बनाता है (जो $q=2$ के लिए अनडिरेक्टेड ग्राफ के विपरीत है)। स्पेक्ट्रल विश्लेषण को सुगम बनाने के लिए, लेखक ग्राफ को हर्मिटियन (Hermitian) बनाने हेतु संयुग्मी भार (conjugate weights) के साथ रिवर्स एडजेस (reverse edges) जोड़ते हैं।

B. दो अलग-अलग हमले की रणनीतियाँ (Two Distinct Attack Strategies)

लेखक इस ग्राफ संरचना पर आधारित दो एल्गोरिदम प्रस्तावित करते हैं, जो अलग-अलग ट्रेड-ऑफ प्रदान करते हैं:

1. स्पेक्ट्रल विधि (Wein et al. [WEAM19 का सामान्यीकरण)

तंत्र (Mechanism): किकुची ग्राफ के एडजेसेंसी मैट्रिक्स (adjacency matrix) के स्पेक्ट्रल नॉर्म (spectral norm) (सबसे बड़ा आइजनवैल्यू) की गणना करता है।
तर्क (Logic):
- एक रैंडम इंस्टेंस में, अपेक्षित स्पेक्ट्रल नॉर्म कम होता है (0 के आसपास केंद्रित)।
- एक प्लांटेड इंस्टेंस में, नॉइज़ वितरण एक बायस (bias) पैदा करता है, जिससे स्पेक्ट्रल नॉर्म काफी अधिक हो जाता है (औसत डिग्री $\Delta$ और नॉइज़ सहसंबंध $\rho$ के समानुपाती)।
विश्लेषण: रैंडम और प्लांटेड दोनों मामलों के लिए स्पेक्ट्रल नॉर्म की टेल प्रोबेबिलिटी को बाउंड करने के लिए मैट्रिक्स बर्नस्टीन इनइक्वेलिटी (Matrix Bernstein inequality) का उपयोग करता है।
उपयोगिता: यह किसी भी नॉइज़ वितरण के लिए काम करता है (बशर्ते कि वह सममित हो और 0 के पास केंद्रित हो) और इसके लिए $q$ का प्राइम होना आवश्यक नहीं है।

2. q-ary कवर विधि (Gupta et al. [GHOS26 का सामान्यीकरण)

तंत्र (Mechanism): किकुची ग्राफ में गैर-तुच्छ बंद पथों (non-trivial closed walks) को खोजता है, जो $q$ -ary कवर्स (constraints के मल्टीसेट्स जहाँ प्रत्येक वेरिएबल के गुणांकों का योग $0 \mod q$ होता है) के अनुरूप होते हैं।
तर्क (Logic):
- वॉक (walk) के एज लेबल्स (दाहिने हाथ के पक्ष) से एक बहुपद (polynomial) का निर्माण करता है।
- रैंडम केस में, इस बहुपद का अपेक्षित मान 0 होता है और यह 0 के करीब केंद्रित होता है।
- प्लांटेड केस में, बहुपद नॉइज़ की विशिष्ट संरचना के कारण एंटी-कंसंट्रेशन (anti-concentration) प्रदर्शित करता है (0 से काफी विचलित होता है)।
विश्लेषण: मल्टीलिनियर बहुपदों के एंटी-कंसंट्रेशन परिणामों पर निर्भर करता है।
उपयोगिता: इसके लिए $q$ का प्राइम (अभाज्य) होना आवश्यक है। यह बाउंडेड-एरर डिस्ट्रीब्यूशन (जैसे डिस्क्रीट गॉसियन) और विशिष्ट LPN नॉइज़ डिस्ट्रीब्यूशन के लिए प्रभावी है। यह बड़े $l$ के लिए स्पीडअप प्रदान करता है।

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

A. नए एल्गोरिदम और ट्रेड-ऑफ

लेखक एल्गोरिदम स्थापित करते हैं जो $\tilde{O}((\binom{n}{l} q^l))$ की टाइम कॉम्प्लेक्सिटी और $m \ge \tilde{O}((\frac{n}{l})^k)$ की सैंपल कॉम्प्लेक्सिटी के साथ निर्णायक $k$ -स्पार्स LWE/LPN समस्याओं को हल करते हैं।

थ्योरम 1.1 (स्पार्स LWE):
- स्पेक्ट्रल विधि: टाइम $\tilde{O}(\binom{n}{l} q^l)$ । सामान्य $q$ और नॉइज़ के लिए काम करता है।
- q-ary कवर विधि: टाइम $\tilde{O}(\sqrt{\binom{n}{l} q^l} \cdot (n/l)^k)$ । इसके लिए $q$ का प्राइम होना और पर्याप्त रूप से बड़ा होना ( $q \gg r(l \log n)^{3/2}$ ) आवश्यक है।
थ्योरम 1.2 (स्पार्स LPN):
- समान ट्रेड-ऑफ, जिसमें $l \gg k$ होने पर q-ary कवर विधि समान सैंपल कॉम्प्लेक्सिटी के लिए स्पेक्ट्रल विधि की तुलना में लगभग द्विघातीय (quadratic) स्पीडअप प्रदान करती है।

B. हार्डनेस कंजैक्चर की टाइटनेस (Tightness of the Hardness Conjecture)

यह शोध पत्र जैन, लिन और साहा (JLS24) द्वारा स्पार्स LWE की हार्डनेस के संबंध में दिए गए एक अनुमान (conjecture) को संबोधित करता है।

JLS24 कंजैक्चर: स्पार्स LWE जिसमें स्पैरसिटी $k = \Omega(\log n)$ और बहुपद सैंपल्स $m = \text{poly}(n)$ है, वह मानक LWE जितना ही कठिन है।
शोध पत्र का निष्कर्ष: लेखक दिखाते हैं कि यदि $k = O(\log n / \log \log n)$ या यदि $m = n^{\Omega(\log \log n)}$ , तो टाइम कॉम्प्लेक्सिटी को किसी भी $\delta > 0$ के लिए $\exp(\delta n)$ तक कम किया जा सकता है।
निहितार्थ: यह JLS24 कंजैचर की टाइटनेस (tightness) स्थापित करता है। ये हमले स्पार्सिटी या सैंपल काउंट के थोड़े से शिथिल (relax) होने पर सब-एक्सपोनेंशियल समय में समस्या को तोड़ देते हैं, जिससे पुष्टि होती है कि अनुमानित हार्डनेस मानक पैरामीटर व्यवस्थाओं में बनी रहती है।

C. पूर्व कार्य के साथ तुलना

बनाम JLS24: लेखकों के हमले अधिक कुशल हैं। JLS24 द्वारा प्रस्तावित "स्पार्स वेक्टर्स इन द कर्नेल" हमले को यह दिखाया गया है कि वह अनिवार्य रूप से q-ary कवर विधि का एक विशेष मामला है, लेकिन किकुची ग्राफ निर्माण लेखकों को बेहतर सैंपल-टाइम ट्रेड-ऑफ के साथ आवश्यक वेक्टर्स को कुशलतापूर्वक खोजने की अनुमति देता है।
बनाम मनोहर [Man24]: लेखक उल्लेख करते हैं कि उनका किकुची ग्राफ निर्माण और स्पेक्ट्रल नॉर्म विश्लेषण पीटर मनोहर के हालिया पीएचडी थीसिस की तुलना में अधिक सामान्य है। विशेष रूप से, लेखकों का ग्राफ निर्माण अधिक एडजेस (edges) की अनुमति देता है, जिससे बड़े $q$ के लिए बेहतर सैंपल कॉम्प्लेक्सिटी बाउंड प्राप्त होते हैं।

4. महत्व (Significance)

अंतराल को भरना: यह कार्य उच्च माड्यूली $q$ पर स्पार्स LWE/LPN के लिए व्यवस्थित, सूक्ष्म विश्लेषण प्रदान करने वाला पहला कार्य है, जो शक्तिशाली किकुची विधि को बाइनरी केस से आगे बढ़ाता है।
क्रिप्टोग्राफिक सुरक्षा: ये परिणाम उन क्रिप्टोग्राफिक स्कीमों के लिए सुरक्षा पैरामीटर्स को परिष्कृत करते हैं जो स्पार्स LWE/LPN पर निर्भर करती हैं। वे दर्शाते हैं कि हालांकि ये समस्याएं कठिन हैं, फिर भी विशिष्ट शासन (regimes) मौजूद हैं (जो $l$ द्वारा पैरामीटराइज्ड हैं) जहाँ हार्डनेस सब-एक्सपोनेंशियल समय में गिर जाती है, जो सुरक्षित पैरामीटर चयन में मार्गदर्शन करती है।
मेथोडोलॉजिकल प्रगति: शोध पत्र स्पेक्ट्रल और कॉम्बिनेटरियल तकनीकों (क्लोज्ड वॉक्स) को गैर-बाइनरी फील्ड्स तक सफलतापूर्वक सामान्यीकृत करता है, जिसमें निर्देशित ग्राफ और गैर-यूनिफॉर्म नॉइज़ डिस्ट्रीब्यूशन की जटिलताओं को संभालने के लिए $q$ -ary कवर्स की अवधारणा पेश की गई है।
क्वांटम स्पीडअप क्षमता: स्पेक्ट्रल विधि को एक संभावित क्वांटम स्पीडअप (द्विघातीय से चतुर्थांश तक) के लिए नोट किया गया है, जो यह सुझाव देता है कि क्वांटम एल्गोरिदम इन समस्याओं के लिए टाइम कॉम्प्लेक्सिटी को और कम कर सकते हैं, जो पोस्ट-क्वांटम क्रिप्टोग्राफी के लिए एक महत्वपूर्ण विचार है।

संक्षेप में, यह शोध पत्र सामान्य माड्यूली पर स्पार्स LWE/LPN पर हमला करने के लिए एक व्यापक ढांचा प्रदान करता है, दो अलग-अलग एल्गोरिदम प्रस्तुत करता है जिनके पूरक गुण हैं, और मानक LWE के सापेक्ष उनकी हार्डनेस की सटीक सीमा स्थापित करता है।