🔢 mathematics

Simultaneous Approximation for Lattice-Based Cryptography

यह शोध पत्र दो नई लैटिस समस्याओं, SIAP और CAP को प्रस्तुत करता है और यह प्रदर्शित करता है कि उन्हें हल करना मानक SVP, SIVP और CVP समस्याओं के समान ही कठिन है, जो इष्टतम, आयाम- और गैप-संरक्षण वाले नियतात्मक बहुपद-समय न्यूनीकरण (deterministic polynomial-time reductions) के माध्यम से स्थापित किया गया है, जिससे क्रिप्टोग्राफिक अनुप्रयोगों के लिए उनकी उपयुक्तता सिद्ध होती है।

मूल लेखक: Julia VanLandingham

प्रकाशित 2026-02-27

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

CC BY 4.0

मूल लेखक: Julia VanLandingham

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

बड़ी तस्वीर: हमें इसकी परवाह क्यों है?

कल्पना कीजिए कि आप एक अत्यंत सुरक्षित डिजिटल ताला (क्रिप्टोग्राफी) बनाने की कोशिश कर रहे हैं जिसे क्वांटम कंप्यूटर भी नहीं खोल सके। पिछले 20 वर्षों से, गणितज्ञ इसके लिए लैटिस (Lattices) का उपयोग कर रहे हैं।

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

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

पिछला प्रयास: "आइडियल" (Ideal) लैटिस

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

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

नया विचार: "सिमल्टेनियस एप्रोक्सिमेशन" (SA) लैटिस

यह पेपर एक नए प्रकार के ग्रिड को पेश करता है जिसे SA लैटिस कहा जाता है।

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

मुख्य कार्य: "अनुवादक" (The Translator)

इस पेपर की मुख्य उपलब्धि एक अनुवादक (Translator) बनाना है।

कल्पना कीजिए कि आपके पास एक अव्यवस्थित कमरे (General Lattice) में एक कठिन पहेली है। आप इसे हल करना चाहते हैं, लेकिन आपके पास केवल एक विशेष प्रकार के साफ-सुथरे कमरे (SA Lattice) पर काम करने वाला टूल है।

चुनौती: यदि आप बस अव्यवस्थित कमरे को साफ-सुथरे कमरे में कॉपी कर देते हैं, तो संख्याएँ इतनी बड़ी हो सकती हैं कि साफ-सुथरा कमरा फट जाए (इसे "इंटीजर इन्फ्लेशन" कहा जाता है)।
समाधान: लेखिका, जूलिया वैनलैंडिंगहैम (Julia VanLandingham) ने एक विशिष्ट एल्गोरिदम (निर्देशों का एक सेट) लिखा है जो अव्यवस्थित कमरे को साफ-सुथरे कमरे में अनुवादित करता है बिना संख्याओं को विस्फोट किए।
- रूपक: इसे अंग्रेजी से फ्रेंच में एक पुस्तक अनुवाद करने जैसा समझें। यदि आप शब्द-दर-शब्द अनुवाद करते हैं, तो फ्रेंच संस्करण 10 गुना लंबा हो सकता है। जूलिया ने एक ऐसा तरीका खोजा जिससे अनुवाद करने पर फ्रेंच संस्करण अंग्रेजी संस्करण के लगभग समान लंबाई का ही रहे।
परिणाम: क्योंकि अनुवाद कुशल है, हम जानते हैं कि यदि कोई "साफ-सुथरे कमरे" (SA Lattice) को तोड़ सकता है, तो वे "अव्यवस्थित कमरे" (General Lattice) को भी तोड़ सकते हैं। चूंकि अव्यवस्थित कमरे को तोड़ना लगभग असंभव माना जाता है, इसलिए साफ-सुथरा कमरा भी सुरक्षित है।

तीन नई पहेलियाँ

यह पेपर इन नए ग्रिडों के लिए "सबसे छोटे रास्ते" की पहेली के तीन विशिष्ट संस्करणों को परिभाषित करता है:

SAP (Shortest Vector): सबसे छोटा रास्ता खोजें।
SIAP (Shortest Independent Vectors): सबसे छोटे रास्तों का एक पूरा सेट खोजें जो एक दूसरे के ऊपर न चढ़ते हों (overlap न करें)।
CAP (Closest Vector): ग्रिड पर उस बिंदु को खोजें जो हवा में तैरते एक विशिष्ट लक्ष्य बिंदु के सबसे करीब है।

पेपर यह सिद्ध करता है कि इन नए "SA" ग्रिडों पर इन तीन पहेलियों को हल करना सामान्य ग्रिडों पर प्रसिद्ध, कठिन संस्करणों को हल करने जितना ही कठिन है।

भविष्य के लिए यह क्यों महत्वपूर्ण है

छोटी चाबियाँ: क्योंकि इन ग्रिडों को वर्णित करना आसान है, हम बहुत छोटी चाबियों के साथ एन्क्रिप्शन सिस्टम बना सकते हैं। इसका अर्थ है तेज़ इंटरनेट, कम स्टोरेज की आवश्यकता, और फोन जैसे उपकरणों पर बेहतर प्रदर्शन।
सिद्ध सुरक्षा: आइडियल लैटिस (Ideal Lattices) के पिछले प्रयासों के विपरीत, यह पेपर गणितीय रूप से सिद्ध करता है कि ये छोटी चाबियाँ सुरक्षा से समझौता नहीं करती हैं।
इष्टतमता (Optimality): लेखिका ने यह भी सिद्ध किया कि ग्रिडों को अनुवादित करने का उनका तरीका सबसे अच्छा संभव तरीका है। आप सुरक्षा को तोड़े बिना संख्याओं को और छोटा नहीं कर सकते।

एक वाक्य में सारांश

यह पेपर डिजिटल ताले बनाने का एक नया, संक्षिप्त तरीका पेश करता है जो इतना छोटा है कि आपकी जेब में समा सके, लेकिन गणितीय रूप से उतना ही अटूट सिद्ध है जितने कि आज के विशाल, भारी ताले हैं।

यहाँ जूलिया वैनलैंडिंगहैम (Julia Vanlandingham) के शोध पत्र "Simultaneous Approximation for Lattice-Based Cryptography" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या का विवरण और प्रेरणा

संदर्भ: औसत-मामले से लेकर सबसे खराब-मामले की कठोरता (average-case to worst-case hardness) के रिडक्शन और होमोमोर्फिक एन्क्रिप्शन क्षमताओं के कारण, लैटिस-आधारित क्रिप्टोग्राफी पोस्ट-क्वांटम सुरक्षा के लिए एक प्रमुख दावेदार है। हालाँकि, मानक लैटिस स्कीम्स अक्सर बड़े सार्वजनिक कुंजी (public key) आकार से ग्रस्त होती हैं।
अंतराल (The Gap):

आइडियल लैटिसेस (Ideal Lattices): इन्हें कुंजी के आकार को कम करने के लिए पेश किया गया था, लेकिन हालिया क्रिप्टोएनालिसिस सुझाव देता है कि इनके उदाहरण सामान्य लैटिस उदाहरणों की तुलना में उतने कठिन नहीं हो सकते (कमजोर सुरक्षा गारंटी)।
सिमल्टेनियस एप्रोक्सिमेशन (SA) लैटिसेस: एक विशिष्ट वर्ग के लैटिसेस जो $n+1$ पूर्णांकों द्वारा परिभाषित होते हैं (सामान्य लैटिसेस के लिए $n^2$ के बजाय), जो स्वाभाविक रूप से 'सिमल्टेनियस डायोफेंटाइन एप्रोक्सिमेशन' समस्या से उत्पन्न होते हैं।
चुनौती: जबकि पिछले कार्य (मार्टिन, 2020) ने दिखाया था कि SA लैटिसेस में शॉर्टेस्ट वेक्टर प्रॉब्लम (SVP) को हल करना सामान्य SVP के समान है, उपयोग किए गए रिडक्शन के परिणामस्वरूप महत्वपूर्ण "इंटीजर इन्फ्लेशन" (संख्याओं की बिट-लंबाई में वृद्धि) हुई। यह इन्फ्लेशन SA लैटिसेस को क्रिप्टोग्राफी के लिए अव्यावहारिक बनाने के लिए खतरा पैदा करता है क्योंकि यह सुरक्षा बनाए रखने के लिए बड़े पैरामीटर्स को अनिवार्य बनाता है, जिससे कुंजी-आकार के लाभ समाप्त हो जाते हैं।

लक्ष्य: इस शोध पत्र का लक्ष्य SIVP (शॉर्टेस्ट इंडिपेंडेंट वेक्टर प्रॉब्लम) और CVP (क्लोजेस्ट वेक्टर प्रॉब्लम) से संबंधित नए SA लैटिस समस्याओं को परिभाषित करना है, और सामान्य लैटिस समस्याओं से इन SA समस्याओं तक इष्टतम, डाइमेंशन-और-गैप-प्रिजर्विंग (dimension- and gap-preserving) रिडक्शन प्रदान करना है, जिसमें काफी कम इंटीजर इन्फ्लेशन हो।

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

2.1 नई समस्या परिभाषाएँ

लेखक SA लैटिस ढांचे के भीतर दो नई समस्याओं को परिभाषित करते हैं:

SIAP (Shortest Independent Approximation Problem): SIVP का SA-लैटिस समकक्ष। $x \in \mathbb{Q}^n$ दिया गया है, ऐसे पूर्णांक $b_1, \dots, b_n$ खोजें ताकि $\{b_i x\}$ के भिन्नात्मक भाग (fractional parts) रैखिक रूप से स्वतंत्र हों और $\gamma \lambda_n$ द्वारा सीमित हों।
CAP (Closest Approximation Problem): CVP का SA-लैटिस समकक्ष। $x \in \mathbb{Q}^n$ और एक लक्ष्य $t$ दिया गया है, एक पूर्णांक $b_0$ खोजें ताकि $\{b_0 x - t\}$ लक्ष्य के भीतर $\gamma$ कारक के भीतर हो।

2.2 मुख्य एल्गोरिदम: सामान्य लैटिसेस को SA लैटिसेस के साथ एप्रोक्सिमेट करना

मुख्य तकनीकी योगदान एल्गोरिदम 1 है, जो एक सामान्य लैटिस $L = M\mathbb{Z}^n$ को एक SA लैटिस में परिवर्तित करता है जो इसका अनुमान (approximate) लगाता है।

तंत्र (Mechanism): यह एल्गोरिदम एक मैट्रिक्स $\tilde{M} = c \cdot \text{adj}(M) + A$ का निर्माण करता है, जहाँ $A$ छोटे पूर्णांक प्रविष्टियों वाला एक परटर्बेशन (perturbation) मैट्रिक्स है।
निर्माण तर्क (Construction Logic):
- यह सुनिश्चित करता है कि $\tilde{M}$ के कॉलम (एक विशिष्ट वेक्टर $b$ के साथ) $\mathbb{Z}^n$ उत्पन्न करते हैं।
- यह सब-मैट्रिक्स के डायगोनल एंट्रियों को पुनरावृत्ति (iteratively) से समायोजित करके प्राप्त किया जाता है ताकि उनके डिटर्मिनेंट्स सह-अभाज्य (coprime) हों (बेज़ौट पहचान (Bézout's identity) और जैकोबस्टाल के फलन (Jacobsthal's function) से संबंधित गुणों का उपयोग करके)।
- परिणामी SA लैटिस आइडेंटिटी मैट्रिक्स $I_n$ और एक वेक्टर $x = \tilde{M}^{-1} M b$ द्वारा उत्पन्न होता है।
प्रमुख नवाचार: मार्टिन के पिछले कार्य के विपरीत, जो बहुपद रिंग्स (polynomial rings) का उपयोग करता था (जिससे $O(n^4 \log(nk))$ इन्फ्लेशन होता था), यह एल्गोरिदम पूर्णांक अंकगणित का उपयोग करता है और जैकोबस्टाल के फलन ( $j(n) = O(\log^2 n)$ ) का उपयोग करके परटर्बेशन के आकार को सावधानीपूर्वक सीमित करता है।

2.3 रिडक्शन (Reductions)

शोध पत्र तीन नियतात्मक बहुपद-समय (deterministic polynomial-time) रिडक्शन प्रस्तुत करता है:

SVP $\to$ SAP: सामान्य SVP को सिमल्टेनियस एप्रोक्सिमेशन प्रॉब्लम (SAP) में बदलना।
SIVP $\to$ SIAP: सामान्य SIVP को नई SIAP समस्या में बदलना।
CVP $\to$ CAP: सामान्य CVP को नई CAP समस्या में बदलना (लक्ष्य वेक्टर के रूपांतरण के साथ)।

सभी रिडक्शन सामान्य लैटिस इंस्टेंस को SA इंस्टेंस में मैप करने, SA समस्या को हल करने और समाधान को वापस मैप करने के लिए एल्गोरिदम 1 के आउटपुट पर निर्भर करते हैं।

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

3.1 बेहतर इंटीजर इन्फ्लेशन बाउंड्स

सबसे महत्वपूर्ण मात्रात्मक परिणाम SA लैटिस के लिए आवश्यक इनपुट संख्याओं की बिट-लंबाई में सुधार है।

पिछला बाउंड (मार्टिन): $O(n^4 \log(nk))$ ।
नया बाउंड (वैनलैंडिंगहैम): $O(n^2 \log(nk))$ ।
महत्व: "इंटीजर इन्फ्लेशन" में यह कमी महत्वपूर्ण है। लैटिस क्रिप्टोग्राफी में, सार्वजनिक कुंजी का आकार लैटिस पैरामीटर्स की बिट-लंबाई से सीधे संबंधित होता है। कम इन्फ्लेशन कारक का अर्थ है कि SA लैटिसेस पिछले निर्माणों की तुलना में समान सुरक्षा स्तर के लिए छोटे कुंजी आकार प्रदान कर सकते हैं।

3.2 कठोरता प्रमाण (NP-Hardness)

यह शोध पत्र सिद्ध करता है कि नई SA समस्याएँ अपने सामान्य समकक्षों जितनी ही कठिन हैं:

थ्योरम 1.2:
- SIAP और CAP किसी भी स्थिरांक एप्रोक्सिमेशन फैक्टर $\gamma$ के लिए $\ell_1, \ell_2,$ और $\ell_\infty$ नॉर्म्स के तहत NP-hard हैं।
- SAP $\ell_\infty$ के तहत किसी भी स्थिरांक $\gamma$ के लिए NP-hard है। $\ell_1$ और $\ell_2$ के तहत, यह $\gamma < 2$ और $\gamma < 2^{1/2}$ के लिए रैंडमाइज्ड रिडक्शन के तहत NP-hard है।
निहितार्थ: यह पुष्टि करता है कि SA लैटिसेस उन "कमजोरियों" से ग्रस्त नहीं हैं जो कभी-कभी आइडियल लैटिसेस से जुड़ी होती हैं; SA लैटिसेस में समस्याओं को हल करना सामान्य लैटिसेस को हल करने जितना ही कठिन है।

3.3 रिडक्शन की इष्टतमता (Optimality)

लेखक सिद्ध करते हैं कि गैप को संरक्षित करने वाले बहुपद-समय रिडक्शन के लिए इंटीजर इन्फ्लेशन पर $O(n^2 \log(nk))$ का बाउंड इष्टतम (optimal) है।

थ्योरम 3.14: यदि उप-द्विघातीय (sub-quadratic) इंटीजर इन्फ्लेशन (जैसे, $O(n^{2-\epsilon})$ ) के साथ कोई रिडक्शन मौजूद होता, तो यह SVP के लिए एक उप-घातांकीय (sub-exponential) एप्रोक्सिमेशन एल्गोरिदम को इंगित करता, जो वर्तमान में असंभव माना जाता है। अतः, प्रस्तावित एल्गोरिदम वर्तमान जटिलता परिदृश्य के भीतर सर्वोत्तम संभव है।

3.4 जटिलता विश्लेषण (Complexity Analysis)

रिडक्शन नियतात्मक (deterministic) हैं और बहुपद समय और स्थान (polynomial time and space) में चलते हैं।
रिडक्शन के लिए समय जटिलता (एल्गोरिदम 2, 3, और 4) $O(n^5 \log^3(nk))$ है, जो एल्गोरिदम 1 में पूर्णांक ऑपरेशन्स द्वारा संचालित है।

4. महत्व और प्रभाव

SA लैटिसेस की क्रिप्टोग्राफिक व्यवहार्यता: यह शोध पत्र SA लैटिसेस को लैटिस-आधारित क्रिप्टोग्राफी के लिए एक मजबूत आधार के रूप में स्थापित करता है। वे सामान्य लैटिसेस में पाई जाने वाली 'वर्स्ट-केस हार्डनेस' की गारंटी से समझौता किए बिना, छोटे कुंजी आकार ( $n+1$ पूर्णांक विवरण के कारण) प्रदान करने की क्षमता रखते हैं।
"आइडियल लैटिस" ट्रेड-ऑफ का समाधान: यह आइडियल लैटिसेस की विशिष्ट कमजोरी (संभावित संरचनात्मक कमजोरियां) को संबोधित करता है, एक ऐसा वर्ग (SA) प्रदान करके जो प्रमाणित रूप से सामान्य लैटिसेस जितना कठिन है, फिर भी इसमें ऐसी संरचनात्मक विशेषताएं हैं जो दक्षता लाभ की ओर ले जा सकती हैं।
पैरामीटर्स का अनुकूलन: यह सिद्ध करके कि इंटीजर इन्फ्लेशन बाउंड इष्टतम है, यह शोध पत्र इस विशिष्ट रिडक्शन तकनीक का उपयोग करके कुंजी आकार को कितना संकुचित किया जा सकता है, इसके लिए एक सैद्धांतिक सीमा निर्धारित करता है, जो भविष्य के क्रिप्टोसिस्टम डिजाइन का मार्गदर्शन करता है।
नए हार्डनेस लक्ष्य: SIAP और CAP की शुरूआत लैटिस समस्याओं के परिदृश्य का विस्तार करती है, जो प्रतिबंधित लैटिस सेटिंग्स में SIVP और CVP पर आधारित नए स्कीम्स को सक्षम बना सकती है।

संक्षेप में, वैनलैंडिंगहैम का कार्य लैटिस क्रिप्टोग्राफी में सैद्धांतिक कठोरता और व्यावहारिक दक्षता के बीच के अंतर को पाटता है। यह प्रदर्शित करता है कि सिमल्टेनियस एप्रोक्सिमेशन लैटिसेस, अनुकूलित मापदंडों के साथ, सामान्य लैटिसेस के एक सुरक्षित, कठिन-से-हल होने वाले विकल्प के रूप में उभर रहे हैं, जो उन्हें अगली पीढ़ी के क्रिप्टोग्राफिक मानकों के लिए एक आशाजनक उम्मीदवार बनाते हैं।