🔢 mathematics

Notes on the LVP and CVP in $p$ -adic Fields

यह शोधपत्र गैर-आर्किमिडियन गुणों, मैक्सिमल ऑर्डर्स और $p$ -रेडिकल्स का लाभ उठाकर ऑर्थोगोनल आधारों के कुशल निर्माण और नॉर्म्स के लक्षण वर्णन के माध्यम से $p$ -एडिक क्षेत्रों में लॉन्गएस्ट और क्लोसेस्ट वेक्टर समस्याओं को हल करने के लिए एक बहुपद-समय (polynomial-time) एल्गोरिदम प्रस्तुत करता है।

मूल लेखक: Chi Zhang, Mingqian Yao

प्रकाशित 2026-04-13

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

CC BY 4.0

मूल लेखक: Chi Zhang, Mingqian Yao

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

मुख्य चित्र: एक डिजिटल तिजोरी को तोड़ना

कल्प_ना कीजिए कि आप गुप्त संदेशों की सुरक्षा के लिए एक अटूट डिजिटल तिजोरी (एक क्रिप्टोग्राफिक सिस्टम) बनाने की कोशिश कर रहे हैं। ऐसा करने के लिए, आपको एक ऐसे गणितीय पहेली की आवश्यकता है जिसे सेटअप करना आसान हो लेकिन बिना किसी विशेष कुंजी (key) के उसे हल करना असंभव हो।

दशकों से, गणितज्ञों ने यूक्लिडियन ज्यामिति (वही ज्यामिति जो आपने स्कूल में त्रिभुजों और वृत्तों के साथ सीखी थी) पर आधारित पहेलियों का उपयोग किया है। इन पहेलियों में बिंदुओं के एक ग्रिड में "सबसे छोटा" या "सबसे निकटतम" पथ खोजना शामिल है।

हालाँकि, यह शोध पत्र p-adic क्षेत्रों (p-adic fields) पर आधारित एक नए प्रकार की पहेली पेश करता है। p-adic क्षेत्रों को एक सपाट मानचित्र के रूप में नहीं, बल्कि एक अजीब, बहु-परतीय ब्रह्मांड के रूप में सोचें जहाँ दूरी के नियम पूरी तरह से अलग हैं। इस ब्रह्मांड में, "लॉन्गेस्ट वेक्टर प्रॉब्लम" (LVP) और "क्लोजेस्ट वेक्टर प्रॉब्लम" (CVP) नई चुनौतियाँ हैं।

इस पेपर के लेखक, ची झांग और मिंगकियान याओ ने एक मास्टर की (master key) खोज ली है। उन्होंने इस अजीब ब्रह्मांड में इन पहेलियों को हल करने का एक तेज़, चरण-दर-चरण तरीका खोजा है। इसका अर्थ यह है कि इन विशिष्ट p-adic पहेलियों का उपयोग करके बनाया गया कोई भी डिजिटल सुरक्षित अब असुरक्षित माना जाता है।

परिवेश: अलग नियमों वाला एक संसार

उनकी खोज को समझने के लिए, हमें पहले उस "दुनिया" को समझना होगा जिसमें वे काम कर रहे हैं।

उपमा: प्याज बनाम रूलर (पैमाना)

सामान्य गणित (यूक्लिडियन): कल्पना कीजिए कि रूलर से दूरी माप रहे हैं। यदि आप 1 मील उत्तर की ओर और 1 मील पूर्व की ओर चलते हैं, तो आप $\sqrt{2}$ मील दूर होते हैं। दूरी लगातार बढ़ती जाती है।
p-adic गणित: कई परतों वाले एक प्याज की कल्पना करें। इस दुनिया में, दो बिंदुओं के बीच की "दूरी" इस बात से निर्धारित होती है कि वे कितने परतों को साझा करते हैं।
- यदि दो संख्याएँ एक गहरी, आंतरिक परत साझा करती हैं, तो उन्हें "बहुत करीब" माना जाता है (दूरी बहुत कम होती है)।
- यदि वे एक गहरी परत में थोड़ा भी भिन्न होती हैं, तो वे "बहुत दूर" होती हैं।
- स्वर्ण नियम: इस दुनिया में, यदि आप दो कदम उठाते हैं, तो कुल दूरी दो कदमों का योग नहीं होती है। यह केवल दोनों में से बड़ा कदम होती है। (इसे नॉन-आर्किमिडियन गुण कहा जाता है)।

चूँकि नियम इतने अलग हैं, इसलिए इस दुनिया के "ग्रिड" (लैटिस) बहुत अलग दिखते हैं। सामान्य ग्रिड में, सबसे छोटा रास्ता खोजना कठिन होता है। इन p-adic ग्रिडों में, लेखकों ने पाया कि यदि आप प्याज को सही ढंग से छीलना जानते हैं, तो रास्ता स्पष्ट हो जाता है।

समस्या: "लॉन्गेस्ट" और "क्लोजेस्ट" वेक्टर्स

यह पेपर दो विशिष्ट समस्याओं पर ध्यान केंद्रित करता है:

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

क्रिप्टोग्राफी की दुनिया में, ये समस्याएँ उन "तालों" की तरह हैं जो हैकर्स को बाहर रखती हैं। यदि आप उन्हें जल्दी से हल नहीं कर सकते, तो ताला सुरक्षित है।

खोज: "ऑर्थोगोनल" कुंजी

लेखकों की सफलता एक ग्रिड को व्यवस्थित करने का तरीका खोजने में है जिससे ये समस्याएँ सरल हो जाएँ। वे इसे ऑर्थोगोनल बेसिस (Orthogonal Basis) कहते हैं।

उपमा: उलझा हुआ ऊन बनाम सीधी रेखाएँ
उलझे हुए ऊन के गोले (एक p-adic लैटिस) की कल्पना करें।

पुराना तरीका: सबसे लंबी डोरी या सबसे करीबी गांठ खोजने के लिए, आपको पूरे उलझाव को सुलझाना पड़ता है। इसमें अनंत समय लगता है (एक्सपोनेंशियल टाइम)।
नया तरीका: लेखकों ने ऊन को पूरी तरह से सीधी, गैर-प्रतिच्छेदी रेखाओं (एक ऑर्थोगोनल बेसिस) में पुनर्गठित करने का तरीका खोज लिया है।
- एक बार जब ऊन सीधा हो जाता है, तो सबसे लंबी डोरी खोजना उसके सिरों को देखने जैसा है।
- सबसे करीबी गांठ खोजना बस एक लंबवत रेखा गिराने जैसा है।

उन्होंने बीजगणितीय संख्या सिद्धांत (algebraic number theory) के उपकरणों का उपयोग करके इसे हासिल किया:

मैक्सिमल ऑर्डर्स (Maximal Orders): उन्होंने इस क्षेत्र की संख्याओं के लिए "परफेक्ट कंटेनर" खोजा।
यूनिफॉर्मिज़र्स (Uniformizers): उन्होंने एक विशेष "माप की इकाई" (एक मानक रूलर की तरह) खोजा जो प्याज की परतों में पूरी तरह फिट बैठती है।
रेसिड्यू फील्ड्स (Residue Fields): उन्होंने संरचना को समझने के लिए प्याज की "त्वचा" का अध्ययन किया।

इन उपकरणों को जोड़कर, उन्होंने एक पॉलीनोमियल-टाइम एल्गोरिदम बनाया। सरल भाषा में: "हमने एक शॉर्टकट खोज लिया है जो बहुत बड़े ग्रिडों के लिए भी सेकंडों में पहेली को हल कर देता है, जबकि पहले इसमें लाखों साल लग जाते।"

प्रभाव: तालों को तोड़ना

इस पेपर का क्रिप्टोग्राफी के लिए बहुत गंभीर निहितार्थ है:

हमला (The Attack): क्योंकि लेखक LVP और CVP को इतनी तेज़ी से हल कर सकते हैं, इसलिए कोई भी एन्क्रिप्शन सिस्टम या डिजिटल सिग्नेचर स्कीम जो इन विशिष्ट p-adic पहेलियों पर निर्भर करती है, वह टूटी हुई (broken) है।
इतिहास: पिछले शोधकर्ताओं को लगा था कि ये पहेलियाँ कठिन हैं। 2021 में, इन्हीं पर आधारित नए स्कीम्स बनाए गए थे। यह पेपर सिद्ध करता है कि वे असुरक्षित हैं यदि अंतर्निध गणित (minimal polynomial) ज्ञात हो।
प्रति-हमला (The Counter-Attack): लेखक सुझाव देते हैं कि इन सिस्टमों को फिर से सुरक्षित बनाने के लिए, हमें दूरी के नियमों को पूरी तरह से छिपाने की आवश्यकता हो सकती है। दूरी के फॉर्मूले को देने के बजाय, हमें केवल एक "ब्लैक बॉक्स" (ओरेकल) देना चाहिए जो आपसे पूछने पर दूरी बताता है। यदि हम फॉर्मूले को नहीं देख सकते, तो हम पहेली को हल करने के लिए "सीधी रेखाएँ" (ऑर्थोगोनल बेसिस) नहीं बना सकते।

सारांश

इस पेपर को नए प्रकार के ताले में खामी खोजने वाले लॉकस्मिथ (ताले बनाने वालों) के समूह के रूप में देखें।

उन्होंने एक अजीब नई दुनिया (p-adic fields) का अध्ययन किया जहाँ दूरी अलग तरह से काम करती है।
उन्होंने महसूस किया कि इस दुनिया के "ताले" (LVP/CVP) इस बात पर निर्भर करते हैं कि ग्रिड उलझा हुआ हो।
उन्होंने एक मशीन (एल्गोरिदम) का आविष्कार किया जो तुरंत उलझे हुए ग्रिड को सीधा कर देती है।
एक बार ग्रिड सीधा हो जाने पर, ताला तुरंत खुल जाता है।

निष्कर्ष: यदि आप इन विशिष्ट p-adic पहेलियों का उपयोग करके डिजिटल तिजोरी बना रहे हैं, तो उनका उपयोग न करें। लेखकों ने दिखाया है कि "रहस्य" पर्याप्त गुप्त नहीं है। हालाँकि, उनका काम आगे का रास्ता भी दिखाता है: यदि हम खेल के नियमों को और भी बेहतर तरीके से छिपा सकें, तो हम इस अजीब गणितीय ब्रह्मांड में सुरक्षित सिस्टम बना सकते हैं।

यहाँ ची झांग और मिंगकियान याओ के शोध पत्र "Notes on the LVP and CVP in p-adic Fields" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र $p$ -adic क्षेत्रों (fields) के संदर्भ में दो मौलिक लैटिस समस्याओं की कम्प्यूटेशनल जटिलता को संबोधित करता है:

लॉन्गेस्ट वेक्टर प्रॉब्लम (LVP): एक लैटिस $L$ दिया गया है, एक ऐसा वेक्टर $v \in L$ खोजें जिसका दूसरा सबसे बड़ा नॉर्म (norm) हो (विशेष रूप से, वह सबसे बड़ा नॉर्म जो लैटिस के अधिकतम नॉर्म से सख्ती से कम हो)।
क्लोजेस्ट वेक्टर प्रॉब्लम (CVP): एक लैटिस $L$ और एक लक्ष्य वेक्टर $t$ दिया गया है, एक ऐसा लैटिस वेक्टर $v \in L$ खोजें जो दूरी $|t - v|_p$ को न्यूनतम करता हो।

संदर्भ:
जबकि यूक्लिडियन लैटिस (Euclidean lattices) में SVP और CVP, यूक्लिडियन लैटिस-आधारित क्रिप्टोग्राफी की सुरक्षा के केंद्र में हैं, उनके $p$ -adic समकक्षों (LVP और CVP) को हाल ही में नए पोस्ट-क्वांटम क्रिप्टोसिस्टम (Deng et al., 2018; 2021) के आधार के रूप में प्रस्तावित किया गया था। ये स्कीम्स इस धारणा पर टिकी हैं कि $p$ -adic लैटिस में ऑर्थोगोनल बेसिस (orthogonal bases) खोजना कम्प्यूटेशनल रूप से कठिन है। पिछले हमलों (Zhang, 2025) ने इन स्कीम्स को केवल विशिष्ट स्थितियों (टोटली रैमिफाइड फील्ड्स) के तहत तोड़ा था। यह शोध पत्र किसी भी $p$ -adic फील्ड के लिए, जो एक मिनिमल पॉलीनोमियल द्वारा परिभाषित है, एक सामान्य बहुपद समय (general polynomial-time) एल्गोरिदम प्रदान करने का लक्ष्य रखता है।

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

लेखक $p$ -adic नॉर्म्स के नॉन-आर्किमिडियन गुण (non-Archimedean property) (अल्ट्रामेट्रिक असमानता: $|x+y|_p \leq \max(|x|_p, |y|_p)$ ) का लाभ उठाते हुए एक नियत (deterministic) बहुपद समय एल्गोरिदम विकसित करते हैं। मुख्य कार्यप्रणाली में तीन मुख्य चरण शामिल हैं:

A. मैक्सिमल ऑर्डर की गणना (Computing the Maximal Order)

लैटिस समस्याओं को हल करने के लिए, पहले क्षेत्र विस्तार (field extension) $K = \mathbb{Q}_p(\theta)$ की बीजगणितीय संरचना को समझना आवश्यक है।

लेखक क्षेत्र $K$ के मैक्सिमल ऑर्डर $\mathcal{O}_K$ की गणना करने के लिए Round 2 और Round 4 एल्गोरिदम का उपयोग करते हैं।
एक ज्ञात ऑर्डर (जैसे, $\mathbb{Z}_p[\theta]$ ) से शुरू होकर, वे $p$ -रेडिकल ( $I_p = \{x \in \mathcal{O} \mid \exists m, x^m \in p\mathcal{O}\}$ ) का उपयोग करके रिंग को पुनरावृत्ति (iteratively) से विस्तारित करते हैं।
फ्रोबेनियस होमोमोर्फिज्म (Frobenius homomorphism) और $p$ -रेडिकल पर रिंग के प्रभाव से प्राप्त विशिष्ट रैखिक मानचित्रों के कर्नेल (kernel) की गणना करके, वे कुशलतापूर्वक मैक्सिमल ऑर्डर का निर्माण करते हैं।

B. एक ऑर्थोगोनल बेसिस का निर्माण (Constructing an Orthogonal Basis)

एक महत्वपूर्ण सैद्धांतिक अंतर्दृष्टि यह है कि यूक्लिडियन लैटिस के विपरीत, $p$ -adic लैटिस में हमेशा एक ऑर्थोगोनल बेसिस होती है। लेखक इस बेसिस का निर्माण निम्नलिखित का उपयोग करके करते हैं:

यूनिफॉर्माइज़र (Uniformizers): $p$ -रेडिकल से एक तत्व $\pi \in \mathcal{O}_K$ (एक यूनिफॉर्माइज़र) खोजना जिसका $p$ -adic absolute value अधिकतम हो।
रेसिड्यू फील्ड बेसिस (Residue Field Basis): $\mathbb{F}_p$ पर रेसिड्यू फील्ड $k = \mathcal{O}_K / \pi \mathcal{O}_K$ के लिए एक बेसिस $\{s_1, \dots, s_f\}$ की गणना करना।
टेन्सर प्रोडक्ट निर्माण (Tensor Product Construction): इन्हें मिलाकर $\{s_i \pi^j \mid 1 \leq i \leq f, 0 \leq j \leq e-1\}$ का सेट बनाना, जहाँ $e$ रैमिफिकेशन इंडेक्स (ramification index) है और $f$ रेसिड्यू डिग्री (residue degree) है।

Theorem 4.3 यह सिद्ध करता है कि यह सेट $\mathbb{Q}_p$ पर क्षेत्र $K$ के लिए एक ऑर्थोगोनल बेसिस बनाता है। इसका अर्थ है कि किसी भी लीनियर कॉम्बिनेशन का नॉर्म उसके घटकों के नॉर्म के अधिकतम मान के बराबर होता है।

C. LVP और CVP को हल करना (Solving LVP and CVP)

एक बार ऑर्थोगोनल बेसिस स्थापित हो जाने के बाद, LVP और CVP सरल उप-समस्याओं (subproblems) में बदल जाते हैं:

LVP एल्गोरिदम: बेसिस वेक्टर्स और लैटिस जनरेटर्स को उनके नॉर्म्स के अनुसार पुनर्व्यवस्थित करके, एल्गोरिदम बहुपद समय में दूसरे सबसे बड़े नॉर्म वाले वेक्टर की पहचान करता है।
CVP एल्गोरिदम: ऑर्थोगोनल बेसिस का उपयोग करके, एल्गोरिदम लक्ष्य $t$ के निकटतम लैटिस वेक्टर को खोजने के लिए एक ग्रीडी रिडक्शन (coordinate-wise प्रोजेक्शन के समान) करता है।
दोनों एल्गोरिदम विस्तार की डिग्री ( $n$ ) और $\log p$ के सापेक्ष नियत बहुपद समय (deterministic polynomial time) में चलते हैं।

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

सामान्य बहुपद समय एल्गोरिदम (General Polynomial-Time Algorithm): यह शोध पत्र मिनिमल पॉलीनोमियल द्वारा दिए गए $p$ -adic क्षेत्रों में LVP और CVP को हल करने वाला पहला सामान्य नियत बहुपद समय एल्गोरिदम प्रस्तुत करता है। यह उन हमलों का सामान्यीकरण करता है जो केवल टोटली रैमिफाइड फील्ड्स तक सीमित थे।
ऑर्थोगogonal बेसिस निर्माण (Orthogonal Basis Construction): लेखक मैक्सिमल ऑर्डर और रेसिड्यू फील्ड एक्सटेंशन का उपयोग करके $p$ -adic क्षेत्रों में ऑर्थोगोनल बेसिस उत्पन्न करने के लिए एक रचनात्मक प्रमाण और एल्गोरिदम प्रदान करते हैं, जो एक ऐसा गुण है जो यूक्लिडियन स्पेस में नहीं होता है।
नॉर्म्स का लक्षण वर्णन (Characterization of Norms): यह शोध पत्र Theorem 7.1 पेश करता है, जो $\mathbb{Q}_p$ पर परिमित-आयामी वेक्टर स्पेस पर सभी नॉर्म्स को परिभाषित करता है। यह दिखाता है कि ऐसे किसी भी नॉर्म को एक इन्वर्टिबल मैट्रिक्स और धनात्मक वास्तविक संख्याओं के सेट द्वारा दर्शाया जा सकता है। यह रेखांकित करता है कि यदि ट्रांसफॉर्मेशन मैट्रिक्स ज्ञात है, तो "छिपा हुआ" ऑर्थोगोनल बेसिस आसानी से प्राप्त किया जा सकता है, जिससे नॉर्म क्रिप्टोग्राफी के लिए असुरक्षित हो जाता है।
व्यावहारिक सत्यापन (Practical Validation): $\mathbb{Q}_2(\sqrt[3]{5})$ (पॉलीनोमियल $X^3 - 3X^2 + 3X - 5$ का उपयोग करके) पर एक ठोस उदाहरण मैक्सिमल ऑर्डर, यूनिफॉर्माइज़र और परिणामी ऑर्थोगोनल बेसिस की चरण-दर-चरण गणना को प्रदर्शित करता है।

4. परिणाम (Results)

जटिलता (Complexity): मैक्सिमल ऑर्डर की गणना करने, यूनिफॉर्माइज़र खोजने और LVP/CVP को हल करने के प्रस्तावित एल्गोरिदम इनपुट साइज ( $n$ और $\log p$ ) के संदर्भ में बहुपद समय (polynomial time) में हैं।
सुरक्षा निहितार्थ (Security Implication): इस कुशल एल्गोरिदम का अस्तित्व यह संकेत देता है कि यदि अंडरलाइंग फील्ड को मिनिमल पॉलीनोमियल द्वारा पूरी तरह से निर्दिष्ट किया गया है, तो $p$ -adic लैटिस पर आधारित पब्लिक-की एन्क्रिप्शन और सिग्नेचर स्कीम्स (जैसा कि Deng et al. द्वारा प्रस्तावित किया गया था) असुरक्षित हैं। इन स्कीम्स द्वारा जिस "कठोरता" (hardness) की धारणा पर भरोसा किया गया था, वह सामान्य मामले में गलत है।
पिछले सुधारों की सीमा (Limitation of Previous Patches): पेपर नोट करता है कि हालांकि पिछले कार्यों ने इन स्कीम्स को पैच करने के लिए बड़े रेसिड्यू डिग्री वाले क्षेत्रों का उपयोग करने का सुझाव दिया था, वर्तमान एल्गोरिदम रेसिड्यू डिग्री की परवाह किए बिना प्रभावी रहता है, बशर्ते कि फील्ड ज्ञात हो।

5. महत्व (Significance)

क्रिप्टोग्राफिक प्रभाव (Cryptographic Impact): यह कार्य $p$ -adic लैटिस पर आधारित पोस्ट-क्वांटम क्रिप्टोग्राफिक प्रस्तावों के एक विशिष्ट वर्ग की सुरक्षा को मौलिक रूप से कमजोर करता है। यह दर्शाता है कि नॉन-आर्किमिडियन ज्योमेट्री, अद्वितीय बीजगणितीय संरचनाएं प्रदान करने के बावजूद, यूक्लिडियन ज्योमेट्री की तरह लैटिस समस्याओं के लिए समान स्तर की कम्प्यूटेशनल कठोरता प्रदान नहीं करती है।
सैद्धांतिक प्रगति (Theoretical Advancement): यह शोध पत्र बीजगणितीय संख्या सिद्धांत (मैक्सिमल ऑर्डर, रैमिफिकेशन) और कम्प्यूटेशनल जटिलता के बीच के अंतर को पाटता है। यह यूक्लिडियन और $p$ -adic लैटिस के बीच संरचनात्मक अंतर को स्पष्ट करता है, विशेष रूप से ऑर्थोगोनल बेसिस के अस्तित्व के संबंध में।
भविष्य की दिशाएं (Future Directions): लेखक सुझाव देते हैं कि $p$ -adic क्रिप्टोग्राफी के व्यवहार्य होने के लिए, उन्हें मिनिमल पॉलीनोमियल के माध्यम से फील्ड को परिभाषित करने से दूर जाना होगा। इसके बजाय, वे नॉर्म ओरैकल्स (norm oracles) का प्रस्ताव करते हैं जहाँ नॉर्म की गणना की जा सकती है लेकिन अंडरलाइंग ऑर्थोगोनल बेसिस (ट्रैपडोर) छिपा रहता है। वे यह खुला प्रश्न पूछते हैं कि क्या ऐसे नॉर्म के मापदंडों (Theorem 7.1) को खोजना कठिन है जब बेसिस अज्ञात हो।

निष्कर्षतः, यह शोध पत्र स्थापित करता है कि $p$ -adic क्षेत्रों में LVP और CVP सुबोध (tractable) समस्याएं हैं, जो प्रभावी रूप से वर्तमान $p$ -adic लैटिस-आधारित क्रिप्टोसिस्टम्स की सुरक्षा मान्यताओं को तोड़ते हैं और भविष्य के शोध को नॉर्म ओरकल्स और हिडन बेसिस स्ट्रक्चर की ओर पुनर्निर्देशित करते हैं।