रिंग लर्निंग विद एरर्स: Difference between revisions

Revision as of 14:30, 16 May 2023

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

आरएलडब्ल्यूई को रिंग्स पर त्रुटियों के साथ सीखना अधिक उचित रूप से कहा जाता है और परिमित क्षेत्रों पर बहुपद रिंगों के लिए विशेष रूप से त्रुटियों (एलडब्ल्यूई) के साथ सीखने की समस्या है।^[1] क्वांटम कंप्यूटर पर भी आरएलडब्ल्यूई समस्या को हल करने में अनुमानित कठिनाई के कारण, आरएलडब्ल्यूई-आधारित क्रिप्टोग्राफी भविष्य में सार्वजनिक-कुंजी क्रिप्टोग्राफी के लिए मौलिक आधार बना सकती है, ठीक उसी तरह जैसे पूर्णांक गुणनखंड और असतत लघुगणक समस्या ने 1980 के दशक की प्रारम्भ से सार्वजनिक-कुंजी क्रिप्टोग्राफी के लिए आधार के रूप में काम किया है।^[2] रिंग लर्निंग विद एरर प्रॉब्लम पर आधारित क्रिप्टोग्राफी की एक महत्वपूर्ण विशेषता यह तथ्य है कि आरएलडब्ल्यूई समस्या के समाधान का उपयोग सबसे छोटी वेक्टर समस्या (एसवीपी) के संस्करण को हल करने के लिए किया जा सकता है। जाली में (इस एसवीपी समस्या से आरएलडब्ल्यूई समस्या में बहुपद-समय की कमी को प्रस्तुत किया गया है ^[1]।

पृष्ठभूमि

आधुनिक क्रिप्टोग्राफी की सुरक्षा, विशेष रूप से सार्वजनिक-कुंजी क्रिप्टोग्राफी में, कुछ कम्प्यूटेशनल समस्याओं को हल करने की अनुमानित अस्थिरता पर आधारित है, यदि समस्या का आकार काफी बड़ा है और हल की जाने वाली समस्या का उदाहरण यादृच्छिक रूप से चुना जाता है। 1970 के दशक के बाद से उपयोग किया जाने वाला क्लासिक उदाहरण पूर्णांक गुणनखंडन समस्या है। यह माना जाता है कि दो अभाज्य संख्याओं के गुणनफल को कम्प्यूटेशनल रूप से अट्रैक्टिव है यदि वे अभाज्य संख्याएँ काफी बड़ी हैं और यादृच्छिक रूप से चुनी जाती हैं।^[3] 2015 के शोध के अनुसार दो 384-बिट प्राइम्स के उत्पाद का गुणनखंडन किया गया है, लेकिन दो 512-बिट प्राइम्स के उत्पाद का नहीं। पूर्णांक गुणनखंड व्यापक रूप से उपयोग किए जाने वाले आरएसए क्रिप्टोग्राफ़िक एल्गोरिथम का आधार बनाता है।

रिंग लर्निंग विथ एरर्स (आरएलडब्ल्यूई) समस्या परिमित क्षेत्र से गुणांक वाले बहुपदों के अंकगणित पर निर्मित है।^[1] प्रारूपिक बहुपद ${\textstyle a(x)}$ को इस प्रकार व्यक्त किया जाता है:

a(x)=a_{0}+a_{1}x+a_{2}x^{2}+\ldots +a_{n-2}x^{n-2}+a_{n-1}x^{n-1}

बहुपदों को सामान्य ढंग से जोड़ा और गुणा किया जा सकता है। आरएलडब्ल्यूई संदर्भ में बहुपदों के गुणांक और उन गुणांकों को सम्मिलित करने वाले सभी संचालन परिमित क्षेत्र में किए जाएंगे, विशेष रूप से अभाज्य पूर्णांक ${\textstyle q}$ के लिए फ़ील्ड ${\textstyle \mathbf {Z} /q\mathbf {Z} =\mathbf {F} _{q}}$ जोड़ और गुणा के संचालन के साथ परिमित क्षेत्र पर बहुपदों का सेट अनंत बहुपद वलय ${\textstyle \mathbf {F} _{q}[x]}$ बनाता है। आरएलडब्ल्यूई प्रसंग इस अनंत वलय के परिमित भागफल वलय के साथ काम करता है। भागफल वलय सामान्यतः परिमित भागफल (कारक) वलय होता है जो ${\textstyle \mathbf {F} _{q}[x]}$ मॉडुलो अलघुकरणीय बहुपद ${\textstyle \Phi (x)}$ में सभी बहुपदों को कम करके बनता है। इस परिमित भागफल वलय को $\mathbf {F} _{q}[x]/\Phi (x)$ के रूप में लिखा जा सकता है, हालांकि कई लेखक $\mathbf {Z} _{q}[x]/\Phi (x)$ लिखते हैं।^[1]

यदि बहुपद $\Phi (x)$ की डिग्री है, तो भागफल वलय, $F_{q}$ के गुणांकों के साथ ${\textstyle n}$ सापेक्ष $\Phi (x)$ से कम डिग्री वाले बहुपदों का वलय बन जाता है। मान ${\textstyle n}$ , ${\textstyle q}$ , बहुपद $\Phi (x)$ के साथ आरएलडब्ल्यूई समस्या के लिए आंशिक रूप से गणितीय संदर्भ को परिभाषित करते हैं।

आरएलडब्ल्यूई समस्या के लिए आवश्यक अन्य अवधारणा कुछ आदर्श के संबंध में "छोटे" बहुपदों का विचार है। आरएलडब्ल्यूई समस्या में उपयोग किए जाने वाले विशिष्ट मानदंड को इन्फिनिटी मानदंड के रूप में जाना जाता है (जिसे एकसमान मानदंड भी कहा जाता है)। जब इन गुणांकों को पूर्णांकों के रूप में देखा जाता है, तो बहुपद का अनन्तता मान बहुपद का सबसे बड़ा गुणांक होता है। अत: $||a(x)||_{\infty }=b$ बताता है कि बहुपद $a(x)$ का अनन्तता मान $b$ है। अतः $b$ $a(x)$ का सबसे बड़ा गुणांक है।

आरएलडब्ल्यूई समस्या को समझने के लिए आवश्यक अंतिम अवधारणा $\mathbf {F} _{q}[x]/\Phi (x)$ में यादृच्छिक बहुपदों की उत्पत्ति और "छोटे" बहुपदों की उत्पत्ति है। यादृच्छिक बहुपद आसानी से यादृच्छिक रूप से $\mathbf {F} _{q}$ से बहुपद के $n$ गुणांकों का नमूना लेकर उत्पन्न होता है, जहाँ $\mathbf {F} _{q}$ को विशेष रूप से सेट $\{-(q-1)/2,...,-1,0,1,...,(q-1)/2\}$ के रूप में दर्शाया जाता है।

बेतरतीब ढंग से एक "छोटा" बहुपद उत्पन्न करना $\mathbf {F} _{q}$ से बहुपद के गुणांक उत्पन्न करके किया जाता है जो या तो गारंटी देता है या बहुत कम गुणांक बनाता है। जब $q$ एक अभाज्य पूर्णांक होता है, तो इसे करने के दो सामान्य तरीके हैं:

यूनिफ़ॉर्म सैंपलिंग का उपयोग करना - छोटे बहुपद के गुणांकों को छोटे गुणांकों के सेट से समान रूप से नमूना लिया जाता है। मान लें कि ${\textstyle b}$ एक पूर्णांक है जो ${\textstyle q}$ से बहुत कम है। यदि हम यादृच्छिक रूप से समुच्चय से गुणांक चुनते हैं: ${\textstyle \{-b,-b+1,-b+2,\ldots ,-2,-1,0,1,2,\ldots ,b-2,b-1,b\}}$ बहुपद बाउंड ( ${\textstyle b}$ ) के संबंध में छोटा होगा।
असतत गॉसियन नमूनाकरण का उपयोग करना - ${\textstyle q}$ के लिए विषम मान के लिए, बहुपद के गुणांकों को बेतरतीब ढंग से चुना जाता है माध्य $0$ और वितरण पैरामीटर ${\textstyle \sigma }$ के साथ असतत गॉसियन वितरण के अनुसार सेट ${\textstyle \{-(q-1)/2,\ldots ,(q-1)/2\}}$ से नमूनाकरण। संदर्भों में विस्तार से बताया गया है कि यह कैसे पूरा किया जा सकता है। यह एकसमान प्रतिचयन की तुलना में अधिक जटिल है लेकिन यह एल्गोरिथ्म की सुरक्षा के प्रमाण की अनुमति देता है। द्वारकानाथ और गालब्रेथ द्वारा लिखित पेपर "सैम्पलिंग फ्रॉम डिस्क्रीट गॉसियन्स फॉर लैटिस-बेस्ड क्रिप्टोग्राफी ऑन अ कन्स्ट्रेन्ड डिवाइस" इस समस्या का अवलोकन प्रदान करता है।^[4]

आरएलडब्ल्यूई समस्या

आरएलडब्ल्यूई समस्या को दो अलग-अलग तरीकों से कहा जा सकता है: "खोज" संस्करण और "निर्णय" संस्करण। दोनों एक ही रचना से प्रारंभ होते हैं। मान लें

$a_{i}(x)$ $\mathbf {F} _{q}[x]/\Phi (x)$ से सभी $\mathbf {F} _{q}$ के गुणांकों के साथ यादृच्छिक लेकिन ज्ञात बहुपदों का समूह है।
$e_{i}(x)$ रिंग $\mathbf {F} _{q}[x]/\Phi (x)$ में बाउंड $b$ के सापेक्ष छोटे यादृच्छिक और अज्ञात बहुपदों का सेट है।
$s(x)$ रिंग $\mathbf {F} _{q}[x]/\Phi (x)$ में बंधे $b$ के सापेक्ष छोटा अज्ञात बहुपद हो।
$b_{i}(x)=(a_{i}(x)\cdot s(x))+e_{i}(x)$ .

खोज संस्करण में बहुपद जोड़े $(a_{i}(x),b_{i}(x))$ सूची दिए जाने पर अज्ञात बहुपद $s(x)$ को खोजने पर जोर देता है।

समस्या का निर्णय संस्करण इस प्रकार बताया जा सकता है। बहुपद जोड़े $(a_{i}(x),b_{i}(x))$ की सूची दी गई है, यह निर्धारित करें कि क्या $b_{i}(x)$ बहुपद $b_{i}(x)=(a_{i}(x)\cdot s(x))+e_{i}(x)$ के रूप में बनाए गए थे या सभी $\mathbf {F} _{q}$ के गुणांकों के साथ $\mathbf {F} _{q}[x]/\Phi (x)$ से यादृच्छिक रूप से उत्पन्न किए गए थे।

इस समस्या की कठिनाई भागफल बहुपद $\Phi (x)$ इसकी डिग्री ( $n$ ), क्षेत्र ( $\mathbf {F} _{q}$ ), और छोटेपन की सीमा ( $b$ ) के विकल्प द्वारा निर्धारित की जाती है। कई आरएलडब्ल्यूई-आधारित सार्वजनिक कुंजी एल्गोरिदम में, निजी कुंजी छोटे बहुपदों $s(x)$ और $e(x)$ की जोड़ी होगी। संबंधित सार्वजनिक कुंजी बहुपद $a(x)$ की जोड़ी होगी, जिसे $\mathbf {F} _{q}[x]/\Phi (x)$ और बहुपद $t(x)=(a(x)\cdot s(x))+e(x)$ से यादृच्छिक रूप से चुना गया है। $a(x)$ और $t(x)$ दिया हुआ है, यह बहुपद $s(x)$ को पुनर्प्राप्त करने के लिए कम्प्यूटेशनल रूप से अक्षम होना चाहिए।

सुरक्षा में कमी

ऐसे मामलों में जहां बहुपद $\Phi (x)$ चक्रीय बहुपद है, आरएलडब्ल्यूई समस्या के खोज संस्करण को हल करने में कठिनाई लघु सदिश खोजने के बराबर है (लेकिन जरूरी नहीं कि सबसे छोटा वेक्टर) $\mathbf {Z} [x]/\Phi (x)$ के तत्वों से बने आदर्श जाली में पूर्णांक वैक्टर के रूप में दर्शाया गया है।^[1] इस समस्या को सामान्यतः अनुमानित सबसे छोटी वेक्टर समस्या (α-SVP) के रूप में जाना जाता है और यह वेक्टर को खोजने की समस्या है जो सबसे छोटे वेक्टर के α गुना से कम है। इस तुल्यता के प्रमाण के लेखक लिखते हैं:

"... हम रिंग-एलडब्ल्यूई के खोज संस्करण में

\mathbf {R}

में आदर्श जाली पर अनुमानित एसवीपी (सबसे खराब स्थिति में) से एक मात्रा में कमी देते हैं, जहां लक्ष्य याच्छिक ढंग से कई शोर उत्पादों से सीक्रेट

s\in \mathbf {R} _{q}

(किसी भी

s

के लिए उच्च संभावना के साथ) को पुनर्प्राप्त करना है।" ^[1]

उक्त उद्धरण में, वलय $\mathbf {R}$ , $\mathbf {Z} [x]/\Phi (x)$ और वलय $\mathbf {R} _{q}$ , $\mathbf {F} _{q}[x]/\Phi (x)$ है।

2001 में डेनियल मिकिसियो द्वारा किए गए कार्य के कारण नियमित जाली में α-SVP को NP-हार्ड के रूप में जाना जाता है, हालांकि त्रुटियों की समस्या के साथ सामान्य सीखने में कमी के लिए आवश्यक α के मूल्यों के लिए नहीं।^[5] हालांकि, यह दिखाने के लिए अभी तक कोई सबूत नहीं है कि आदर्श लैटिस के लिए α-SVP की कठिनाई औसत α-SVP के बराबर है। बल्कि हमारे पास इस बात का प्रमाण है कि यदि कोई α-SVP उदाहरण हैं जो आदर्श जाली में हल करना कठिन है तो आरएलडब्ल्यूई समस्या यादृच्छिक उदाहरणों में कठिन होगी।^[1]

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

पिकर्ट का मानना है कि ये सुरक्षा समानताएं आरएलडब्ल्यूई समस्या को भविष्य की क्रिप्टोग्राफी के लिए एक अच्छा आधार बनाती हैं। वह लिखते हैं: गणितीय प्रमाण है कि क्रिप्टोसिस्टम (कुछ औपचारिक हमले के मॉडल के भीतर) को उसके यादृच्छिक उदाहरणों पर तोड़ने का एकमात्र तरीका सबसे खराब स्थिति (मूल में जोर) में अंतर्निहित जाली समस्या को हल करने में सक्षम होना है।^[8]

आरएलडब्ल्यूई क्रिप्टोग्राफी

आरएलडब्ल्यूई-आधारित क्रिप्टोग्राफी का एक बड़ा फायदा यह है कि मूल लर्निंग विद एरर (एलडब्ल्यूई) आधारित क्रिप्टोग्राफी सार्वजनिक और निजी कुंजी के आकार में पाई जाती है। आरएलडब्ल्यूई कुंजियाँ मोटे तौर पर एलडब्ल्यूई में चाबियों का वर्गमूल होती हैं।^[1] 128 बिट्स की सुरक्षा के लिए, आरएलडब्ल्यूई क्रिप्टोग्राफ़िक एल्गोरिथम लंबाई में लगभग 7000 बिट्स की सार्वजनिक कुंजी का उपयोग करेगा।^[9] संबंधित वामपंथी उग्रवादी योजना के लिए समान स्तर की सुरक्षा के लिए 49 मिलियन बिट की सार्वजनिक कुंजी की आवश्यकता होगी।^[1] दूसरी ओर, आरएलडब्ल्यूई कुंजियाँ आरएसए और एलिप्टिक कर्व डिफी-हेलमैन जैसे वर्तमान में उपयोग किए जाने वाले सार्वजनिक कुंजी एल्गोरिदम के लिए कुंजियों के आकार से बड़ी होती हैं, जिन्हें 128-बिट स्तर की सुरक्षा प्राप्त करने के लिए क्रमशः 3072 बिट और 256 बिट के सार्वजनिक कुंजी आकार की आवश्यकता होती है। हालांकि, कम्प्यूटेशनल दृष्टिकोण से, आरएलडब्ल्यूई एल्गोरिदम को मौजूदा सार्वजनिक कुंजी सिस्टम के बराबर या उससे बेहतर दिखाया गया है।^[10]

आरएलडब्ल्यूई क्रिप्टोग्राफिक एल्गोरिदम के तीन समूह उपस्थित हैं:

त्रुटियों के साथ रिंग लर्निंग प्रमुख आदान-प्रदान (आरएलडब्ल्यूई-केईएक्स)

प्रमुख विनिमय के लिए वामपंथी उग्रवाद और वामपंथी उग्रवाद का उपयोग करने का मौलिक विचार प्रस्तावित किया गया था और जिंताई डिंग द्वारा 2011 में सिनसिनाटी विश्वविद्यालय में दाखिल किया गया था। मूल विचार मैट्रिक्स गुणन की संबद्धता से आता है, और त्रुटियों का उपयोग सुरक्षा प्रदान करने के लिए किया जाता है। 2012 में अनंतिम पेटेंट आवेदन दायर करने के बाद 2012 में पेपर ^[11] दिखाई दिया।

2014 में, पिकर्ट^[12] डिंग के समान मूल विचार के बाद एक प्रमुख परिवहन योजना प्रस्तुत की, जहां डिंग के निर्माण में गोलाई के लिए अतिरिक्त 1 बिट सिग्नल भेजने का नया विचार भी उपयोग किया जाता है। डिफी-हेलमैन कुंजी एक्सचेंज के क्लासिक एमक्यूवी संस्करण का एक आरएलडब्ल्यूई संस्करण बाद में झांग एट अल द्वारा प्रकाशित किया गया था।^[13] दोनों प्रमुख एक्सचेंजों की सुरक्षा सीधे एक आदर्श जाली में लगभग छोटे वैक्टर खोजने की समस्या से संबंधित है।

त्रुटि हस्ताक्षर के साथ रिंग लर्निंग (आरएलडब्ल्यूई-एसआईजी)

चिरसम्मत फीज-फिएट-शमीर आइडेंटिफिकेशन प्रोटोकॉल का आरएलडब्ल्यूई संस्करण बनाया गया था और 2011 में हुबाशेवस्की द्वारा डिजिटल हस्ताक्षर में परिवर्तित किया गया था।^[14] इस हस्ताक्षर का विवरण 2012 में गुनेसू, ल्युबाशेवस्की और पोप्पलमैन द्वारा 2012 में विस्तारित किया गया था और उनके पेपर "प्रैक्टिकल लैटिस बेस्ड क्रिप्टोग्राफी - ए सिग्नेचर स्कीम फॉर एंबेडेड सिस्टम्स" में प्रकाशित किया गया था।^[15] इन पेपर्स ने हाल ही के सिग्नेचर एल्गोरिदम वर्ग के लिए आधार तैयार किया, कुछ सीधे रिंग लर्निंग विद एरर प्रॉब्लम पर आधारित थे और कुछ जो समान कठिन आरएलडब्ल्यूई समस्याओं से बंधे नहीं थे।^[16]

त्रुटियों के साथ रिंग लर्निंग होमोमोर्फिक एन्क्रिप्शन (आरएलडब्ल्यूई-HOM)

होमोमोर्फिक एन्क्रिप्शन का उद्देश्य संवेदनशील डेटा की संगणनाओं को उन कंप्यूटिंग उपकरणों पर होने देना है जिन पर डेटा के साथ भरोसा नहीं किया जाना चाहिए। इन कंप्यूटिंग डिवाइसों को सिफरटेक्स्ट को प्रोसेस करने की अनुमति है जो होमोमोर्फिक एन्क्रिप्शन से आउटपुट है। 2011 में, ब्रैकर्सकी और वैकुंठनाथन ने "रिंग-एलडब्ल्यूई से पूरी तरह से होमोमोर्फिक एन्क्रिप्शन और कुंजी निर्भर संदेशों के लिए सुरक्षा" प्रकाशित की, जो सीधे आरएलडब्ल्यूई समस्या पर होमोमोर्फिक एन्क्रिप्शन योजना बनाता है।^[17]

संदर्भ

↑ ^1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 ^1.6 ^1.7 ^1.8 Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (2012). "आइडियल लैटिस और लर्निंग विद एरर्स ओवर रिंग्स पर". Cryptology ePrint Archive.
↑ Peikert, Chris (2014). "Lattice Cryptography for the Internet". In Mosca, Michele (ed.). पोस्ट-क्वांटम क्रिप्टोग्राफी. Lecture Notes in Computer Science. Vol. 8772. Springer International Publishing. pp. 197–219. CiteSeerX 10.1.1.800.4743. doi:10.1007/978-3-319-11659-4_12. ISBN 978-3-319-11658-7. S2CID 8123895.
↑ Shor, Peter (20 November 1994). Algorithms for quantum computation: discrete logarithms and factoring. 35th Annual Symposium on Foundations of Computer Science. Santa Fe: IEEE. doi:10.1109/SFCS.1994.365700. ISBN 0-8186-6580-7. This paper gives Las Vegas algorithms for finding discrete logarithms and factoring integers on a quantum computer that take a number of steps which is polynomial in the input size, e.g., the number of digits of the integer to be factored. These two problems are generally considered hard on a classical computer and have been used as the basis of several proposed cryptosystems.
↑ Dwarakanath, Nagarjun C.; Galbraith, Steven D. (2014-03-18). "विवश डिवाइस पर जाली-आधारित क्रिप्टोग्राफी के लिए असतत गॉसियन से नमूनाकरण". Applicable Algebra in Engineering, Communication and Computing. 25 (3): 159–180. doi:10.1007/s00200-014-0218-3. ISSN 0938-1279. S2CID 13718364.
↑ ^5.0 ^5.1 Micciancio, D. (January 1, 2001). "एक जाली में सबसे छोटा वेक्टर कुछ स्थिरांक के भीतर अनुमानित करना कठिन है". SIAM Journal on Computing. 30 (6): 2008–2035. CiteSeerX 10.1.1.93.6646. doi:10.1137/S0097539700373039. ISSN 0097-5397.
↑ Schneider, Michael (2011). "आदर्श जालक में लघुतम सदिशों की छानबीन करना". Cryptology ePrint Archive.
↑ "cr.yp.to: 2014.02.13: A subfield-logarithm attack against ideal lattices". blog.cr.yp.to. Retrieved 2015-07-03.
↑ "What does GCHQ's "cautionary tale" mean for lattice cryptography?". www.eecs.umich.edu. Archived from the original on 2016-03-17. Retrieved 2016-01-05.
↑ Singh, Vikram (2015). "जाली क्रिप्टोग्राफी का उपयोग कर इंटरनेट के लिए एक व्यावहारिक कुंजी एक्सचेंज". Cryptology ePrint Archive.
↑ Verbauwhede, Ruan de Clercq, Sujoy Sinha Roy, Frederik Vercauteren, Ingrid (2014). "रिंग-एलडब्ल्यूई एन्क्रिप्शन का कुशल सॉफ्टवेयर कार्यान्वयन". Cryptology ePrint Archive.{{cite journal}}: CS1 maint: multiple names: authors list (link)
↑ Ding, Jintai; Xie, Xiang; Lin, Xiaodong (2012-01-01). "त्रुटियों के साथ सीखने की समस्या पर आधारित एक सरल प्रमाणित सुरक्षित कुंजी विनिमय योजना". Cryptology ePrint Archive.
↑ Peikert, Chris (2014-01-01). "इंटरनेट के लिए जाली क्रिप्टोग्राफी". Cryptology ePrint Archive.
↑ Zhang, Jiang; Zhang, Zhenfeng; Ding, Jintai; Snook, Michael; Dagdelen, Özgür (2014). "आइडियल लैटिस से ऑथेंटिकेटेड की एक्सचेंज". Cryptology ePrint Archive.
↑ Lyubashevsky, Vadim (2011). "ट्रैपडोर के बिना जाली हस्ताक्षर". Cryptology ePrint Archive.
↑ Güneysu, Tim; Lyubashevsky, Vadim; Pöppelmann, Thomas (2012). Prouff, Emmanuel; Schaumont, Patrick (eds.). Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 530–547. doi:10.1007/978-3-642-33027-8_31. ISBN 978-3-642-33026-1.
↑ "ब्लिस हस्ताक्षर योजना". bliss.di.ens.fr. Retrieved 2015-07-04.
↑ Brakerski, Zvika; Vaikuntanathan, Vinod (2011). Rogaway, Phillip (ed.). रिंग-एलडब्ल्यूई से पूरी तरह से होमोमोर्फिक एन्क्रिप्शन और प्रमुख आश्रित संदेशों के लिए सुरक्षा. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 505–524. doi:10.1007/978-3-642-22792-9_29. ISBN 978-3-642-22791-2.

[:0-1] 1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 ^1.6 ^1.7 ^1.8 Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (2012). "आइडियल लैटिस और लर्निंग विद एरर्स ओवर रिंग्स पर". Cryptology ePrint Archive.

[:2-2] Peikert, Chris (2014). "Lattice Cryptography for the Internet". In Mosca, Michele (ed.). पोस्ट-क्वांटम क्रिप्टोग्राफी. Lecture Notes in Computer Science. Vol. 8772. Springer International Publishing. pp. 197–219. CiteSeerX 10.1.1.800.4743. doi:10.1007/978-3-319-11659-4_12. ISBN 978-3-319-11658-7. S2CID 8123895.

[3] Shor, Peter (20 November 1994). Algorithms for quantum computation: discrete logarithms and factoring. 35th Annual Symposium on Foundations of Computer Science. Santa Fe: IEEE. doi:10.1109/SFCS.1994.365700. ISBN 0-8186-6580-7. This paper gives Las Vegas algorithms for finding discrete logarithms and factoring integers on a quantum computer that take a number of steps which is polynomial in the input size, e.g., the number of digits of the integer to be factored. These two problems are generally considered hard on a classical computer and have been used as the basis of several proposed cryptosystems.

[4] Dwarakanath, Nagarjun C.; Galbraith, Steven D. (2014-03-18). "विवश डिवाइस पर जाली-आधारित क्रिप्टोग्राफी के लिए असतत गॉसियन से नमूनाकरण". Applicable Algebra in Engineering, Communication and Computing. 25 (3): 159–180. doi:10.1007/s00200-014-0218-3. ISSN 0938-1279. S2CID 13718364.

[:1-5] 5.0 ^5.1 Micciancio, D. (January 1, 2001). "एक जाली में सबसे छोटा वेक्टर कुछ स्थिरांक के भीतर अनुमानित करना कठिन है". SIAM Journal on Computing. 30 (6): 2008–2035. CiteSeerX 10.1.1.93.6646. doi:10.1137/S0097539700373039. ISSN 0097-5397.

[6] Schneider, Michael (2011). "आदर्श जालक में लघुतम सदिशों की छानबीन करना". Cryptology ePrint Archive.

[7] "cr.yp.to: 2014.02.13: A subfield-logarithm attack against ideal lattices". blog.cr.yp.to. Retrieved 2015-07-03.

[8] "What does GCHQ's "cautionary tale" mean for lattice cryptography?". www.eecs.umich.edu. Archived from the original on 2016-03-17. Retrieved 2016-01-05.

[9] Singh, Vikram (2015). "जाली क्रिप्टोग्राफी का उपयोग कर इंटरनेट के लिए एक व्यावहारिक कुंजी एक्सचेंज". Cryptology ePrint Archive.

[10] Verbauwhede, Ruan de Clercq, Sujoy Sinha Roy, Frederik Vercauteren, Ingrid (2014). "रिंग-एलडब्ल्यूई एन्क्रिप्शन का कुशल सॉफ्टवेयर कार्यान्वयन". Cryptology ePrint Archive.{{cite journal}}: CS1 maint: multiple names: authors list (link)

[11] Ding, Jintai; Xie, Xiang; Lin, Xiaodong (2012-01-01). "त्रुटियों के साथ सीखने की समस्या पर आधारित एक सरल प्रमाणित सुरक्षित कुंजी विनिमय योजना". Cryptology ePrint Archive.

[12] Peikert, Chris (2014-01-01). "इंटरनेट के लिए जाली क्रिप्टोग्राफी". Cryptology ePrint Archive.

[13] Zhang, Jiang; Zhang, Zhenfeng; Ding, Jintai; Snook, Michael; Dagdelen, Özgür (2014). "आइडियल लैटिस से ऑथेंटिकेटेड की एक्सचेंज". Cryptology ePrint Archive.

[14] Lyubashevsky, Vadim (2011). "ट्रैपडोर के बिना जाली हस्ताक्षर". Cryptology ePrint Archive.

[15] Güneysu, Tim; Lyubashevsky, Vadim; Pöppelmann, Thomas (2012). Prouff, Emmanuel; Schaumont, Patrick (eds.). Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 530–547. doi:10.1007/978-3-642-33027-8_31. ISBN 978-3-642-33026-1.

[16] "ब्लिस हस्ताक्षर योजना". bliss.di.ens.fr. Retrieved 2015-07-04.

[17] Brakerski, Zvika; Vaikuntanathan, Vinod (2011). Rogaway, Phillip (ed.). रिंग-एलडब्ल्यूई से पूरी तरह से होमोमोर्फिक एन्क्रिप्शन और प्रमुख आश्रित संदेशों के लिए सुरक्षा. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 505–524. doi:10.1007/978-3-642-22792-9_29. ISBN 978-3-642-22791-2.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

@@ Line 1: / Line 1: @@
 {{short description|Computational problem possibly useful for post-quantum cryptography}}
-[[पोस्ट-क्वांटम क्रिप्टोग्राफी]] में, रिंग लर्निंग विद एरर्स (आरएलडब्ल्यूई) एक [[कम्प्यूटेशनल समस्या]] है जो नए क्रिप्टोग्राफ़िक एल्गोरिदम ([[कलन विधि]]) की नींव के रूप में कार्य करती है, जैसे न्यूहोप, जिसे क्वांटम कंप्यूटरों द्वारा क्रिप्टैनालिसिस से बचाने के लिए डिज़ाइन किया गया है और [[होमोमोर्फिक एन्क्रिप्शन]] के लिए आधार भी प्रदान करता है। [[सार्वजनिक कुंजी क्रिप्टोग्राफी|सार्वजनिक की क्रिप्टोग्राफी]] (पब्लिक की क्रिप्टोग्राफी) गणितीय समस्याओं के निर्माण पर निर्भर करती है, जिनके बारे में माना जाता है कि यदि कोई और जानकारी उपलब्ध नहीं है, तो उन्हें हल करना कठिन है, लेकिन यदि समस्या निर्माण में उपयोग की गई कुछ जानकारी ज्ञात है, तो उन्हें हल करना आसान है। इस प्रकार की कुछ समस्याएं जो वर्तमान में क्रिप्टोग्राफी में उपयोग की जाती हैं, यदि पर्याप्त मात्रा में बड़े क्वांटम कंप्यूटर कभी भी बनाए जा सकते हैं, तो हमले का खतरा होता है, इसलिए प्रतिरोधी समस्याओं की मांग की जाती है।होमोमोर्फिक एन्क्रिप्शन एन्क्रिप्शन का एक रूप है जो सिफरटेक्स्ट पर गणना की अनुमति देता है, जैसे कि एन्क्रिप्टेड डेटाबेस में संग्रहीत संख्यात्मक मानों पर अंकगणित।
+[[पोस्ट-क्वांटम क्रिप्टोग्राफी]] में, रिंग लर्निंग विद एरर्स (आरएलडब्ल्यूई) [[कम्प्यूटेशनल समस्या]] है जो नए क्रिप्टोग्राफ़िक एल्गोरिदम ([[कलन विधि]]) की नींव के रूप में कार्य करती है, जैसे न्यूहोप, जिसे क्वांटम कंप्यूटरों द्वारा क्रिप्टैनालिसिस से बचाने के लिए डिज़ाइन किया गया है और [[होमोमोर्फिक एन्क्रिप्शन]] के लिए आधार भी प्रदान करता है। [[सार्वजनिक कुंजी क्रिप्टोग्राफी|सार्वजनिक की क्रिप्टोग्राफी]] (पब्लिक की क्रिप्टोग्राफी) गणितीय समस्याओं के निर्माण पर निर्भर करती है, जिनके बारे में माना जाता है कि यदि कोई और जानकारी उपलब्ध नहीं है, तो उन्हें हल करना कठिन है, लेकिन यदि समस्या निर्माण में उपयोग की गई कुछ जानकारी ज्ञात है, तो उन्हें हल करना आसान है। इस प्रकार की कुछ समस्याएं जो वर्तमान में क्रिप्टोग्राफी में उपयोग की जाती हैं, यदि पर्याप्त मात्रा में बड़े क्वांटम कंप्यूटर कभी भी बनाए जा सकते हैं, तो हमले का खतरा होता है, इसलिए प्रतिरोधी समस्याओं की मांग की जाती है।होमोमोर्फिक एन्क्रिप्शन एन्क्रिप्शन का एक रूप है जो सिफरटेक्स्ट पर गणना की अनुमति देता है, जैसे कि एन्क्रिप्टेड डेटाबेस में संग्रहीत संख्यात्मक मानों पर अंकगणित।
-आरएलडब्ल्यूई को रिंग्स पर त्रुटियों के साथ सीखना अधिक उचित रूप से कहा जाता है और परिमित क्षेत्रों पर बहुपद रिंगों के लिए विशेष रूप से त्रुटियों (एलडब्ल्यूई) के साथ सीखने की समस्या है।<ref name=":0" /> एक क्वांटम कंप्यूटर पर भी आरएलडब्ल्यूई समस्या को हल करने में अनुमानित कठिनाई के कारण, आरएलडब्ल्यूई-आधारित क्रिप्टोग्राफी भविष्य में सार्वजनिक-कुंजी क्रिप्टोग्राफी के लिए मौलिक आधार बना सकती है, ठीक उसी तरह जैसे पूर्णांक गुणनखंड और [[असतत लघुगणक]] समस्या ने 1980 के दशक की शुरुआत से सार्वजनिक-कुंजी क्रिप्टोग्राफी के लिए आधार के रूप में काम किया है।<ref name=":2">{{Cite book|publisher = Springer International Publishing|isbn = 978-3-319-11658-7|pages = 197–219|series = Lecture Notes in Computer Science|first = Chris|last = Peikert|editor-first = Michele|editor-last = Mosca|doi = 10.1007/978-3-319-11659-4_12|title = पोस्ट-क्वांटम क्रिप्टोग्राफी|volume = 8772|year = 2014|chapter = Lattice Cryptography for the Internet|citeseerx = 10.1.1.800.4743| s2cid=8123895 }}</ref> रिंग लर्निंग विद एरर प्रॉब्लम पर आधारित क्रिप्टोग्राफी की एक महत्वपूर्ण विशेषता यह तथ्य है कि आरएलडब्ल्यूई समस्या के समाधान का उपयोग सबसे छोटी वेक्टर समस्या (एसवीपी) के संस्करण को हल करने के लिए किया जा सकता है। एक जाली में (इस एसवीपी समस्या से आरएलडब्ल्यूई समस्या में एक बहुपद-समय की कमी को प्रस्तुत किया गया है <ref name=":0" />।
+आरएलडब्ल्यूई को रिंग्स पर त्रुटियों के साथ सीखना अधिक उचित रूप से कहा जाता है और परिमित क्षेत्रों पर बहुपद रिंगों के लिए विशेष रूप से त्रुटियों (एलडब्ल्यूई) के साथ सीखने की समस्या है।<ref name=":0" /> क्वांटम कंप्यूटर पर भी आरएलडब्ल्यूई समस्या को हल करने में अनुमानित कठिनाई के कारण, आरएलडब्ल्यूई-आधारित क्रिप्टोग्राफी भविष्य में सार्वजनिक-कुंजी क्रिप्टोग्राफी के लिए मौलिक आधार बना सकती है, ठीक उसी तरह जैसे पूर्णांक गुणनखंड और [[असतत लघुगणक]] समस्या ने 1980 के दशक की प्रारम्भ से सार्वजनिक-कुंजी क्रिप्टोग्राफी के लिए आधार के रूप में काम किया है।<ref name=":2">{{Cite book|publisher = Springer International Publishing|isbn = 978-3-319-11658-7|pages = 197–219|series = Lecture Notes in Computer Science|first = Chris|last = Peikert|editor-first = Michele|editor-last = Mosca|doi = 10.1007/978-3-319-11659-4_12|title = पोस्ट-क्वांटम क्रिप्टोग्राफी|volume = 8772|year = 2014|chapter = Lattice Cryptography for the Internet|citeseerx = 10.1.1.800.4743| s2cid=8123895 }}</ref> रिंग लर्निंग विद एरर प्रॉब्लम पर आधारित क्रिप्टोग्राफी की एक महत्वपूर्ण विशेषता यह तथ्य है कि आरएलडब्ल्यूई समस्या के समाधान का उपयोग सबसे छोटी वेक्टर समस्या (एसवीपी) के संस्करण को हल करने के लिए किया जा सकता है। जाली में (इस एसवीपी समस्या से आरएलडब्ल्यूई समस्या में बहुपद-समय की कमी को प्रस्तुत किया गया है <ref name=":0" />।
 == पृष्ठभूमि ==
 आधुनिक क्रिप्टोग्राफी की सुरक्षा, विशेष रूप से सार्वजनिक-कुंजी क्रिप्टोग्राफी में, कुछ कम्प्यूटेशनल समस्याओं को हल करने की अनुमानित अस्थिरता पर आधारित है, यदि समस्या का आकार काफी बड़ा है और हल की जाने वाली समस्या का उदाहरण यादृच्छिक रूप से चुना जाता है। 1970 के दशक के बाद से उपयोग किया जाने वाला क्लासिक उदाहरण पूर्णांक गुणनखंडन समस्या है। यह माना जाता है कि दो अभाज्य संख्याओं के गुणनफल को कम्प्यूटेशनल रूप से अट्रैक्टिव है यदि वे अभाज्य संख्याएँ काफी बड़ी हैं और यादृच्छिक रूप से चुनी जाती हैं।<ref>{{cite conference |title=Algorithms for quantum computation: discrete logarithms and factoring |first=Peter |last=Shor |date=20 November 1994 |conference=35th Annual Symposium on Foundations of Computer Science |publisher=IEEE |location=Santa Fe |isbn=0-8186-6580-7 |doi=10.1109/SFCS.1994.365700 |quote=This paper gives Las Vegas algorithms for finding discrete logarithms and factoring integers on a quantum computer that take a number of steps which is polynomial in the input size, e.g., the number of digits of the integer to be factored. These two problems are generally considered hard on a classical computer and have been used as the basis of several proposed cryptosystems.}}</ref> 2015 के शोध के अनुसार दो 384-बिट प्राइम्स के उत्पाद का गुणनखंडन किया गया है, लेकिन दो 512-बिट प्राइम्स के उत्पाद का नहीं। पूर्णांक गुणनखंड व्यापक रूप से उपयोग किए जाने वाले आरएसए क्रिप्टोग्राफ़िक एल्गोरिथम का आधार बनाता है।
-रिंग लर्निंग विथ एरर्स (आरएलडब्ल्यूई) समस्या एक [[परिमित क्षेत्र]] से गुणांक वाले बहुपदों के अंकगणित पर निर्मित है।<ref name=":0" /> एक प्रारूपिक बहुपद <math display="inline">a(x)</math> को इस प्रकार व्यक्त किया जाता है:
+रिंग लर्निंग विथ एरर्स (आरएलडब्ल्यूई) समस्या [[परिमित क्षेत्र]] से गुणांक वाले बहुपदों के अंकगणित पर निर्मित है।<ref name=":0" /> प्रारूपिक बहुपद <math display="inline">a(x)</math> को इस प्रकार व्यक्त किया जाता है:
 :<math>a(x) = a_0 + a_1x + a_2x^2 + \ldots + a_{n-2}x^{n-2} + a_{n-1}x^{n-1}</math>
-बहुपदों को सामान्य ढंग से जोड़ा और गुणा किया जा सकता है। RLWE संदर्भ में बहुपदों के गुणांक और उन गुणांकों को शामिल करने वाले सभी संचालन एक परिमित क्षेत्र में किए जाएंगे, विशेष रूप से एक अभाज्य पूर्णांक <math display="inline">q</math> के लिए फ़ील्ड <math display="inline">\mathbf{Z}/q\mathbf{Z} = \mathbf{F}_q</math> जोड़ और गुणा के संचालन के साथ परिमित क्षेत्र पर बहुपदों का सेट एक अनंत बहुपद वलय <math display="inline">\mathbf{F}_q[x]</math> बनाता है। RLWE प्रसंग इस अनंत वलय के परिमित भागफल वलय के साथ काम करता है। भागफल वलय आमतौर पर परिमित भागफल (कारक) वलय होता है जो <math display="inline">\mathbf{F}_q[x]</math> मॉडुलो एक [[अलघुकरणीय बहुपद]] <math display="inline">\Phi(x)</math> में सभी बहुपदों को कम करके बनता है। इस परिमित भागफल वलय को <math>\mathbf{F}_q[x]/\Phi(x)</math> के रूप में लिखा जा सकता है, हालांकि कई लेखक <math>\mathbf{Z}_q[x]/\Phi(x)</math> लिखते हैं।<ref name=":0" />
+बहुपदों को सामान्य ढंग से जोड़ा और गुणा किया जा सकता है। आरएलडब्ल्यूई संदर्भ में बहुपदों के गुणांक और उन गुणांकों को सम्मिलित करने वाले सभी संचालन परिमित क्षेत्र में किए जाएंगे, विशेष रूप से अभाज्य पूर्णांक <math display="inline">q</math> के लिए फ़ील्ड <math display="inline">\mathbf{Z}/q\mathbf{Z} = \mathbf{F}_q</math> जोड़ और गुणा के संचालन के साथ परिमित क्षेत्र पर बहुपदों का सेट अनंत बहुपद वलय <math display="inline">\mathbf{F}_q[x]</math> बनाता है। आरएलडब्ल्यूई प्रसंग इस अनंत वलय के परिमित भागफल वलय के साथ काम करता है। भागफल वलय सामान्यतः परिमित भागफल (कारक) वलय होता है जो <math display="inline">\mathbf{F}_q[x]</math> मॉडुलो [[अलघुकरणीय बहुपद]] <math display="inline">\Phi(x)</math> में सभी बहुपदों को कम करके बनता है। इस परिमित भागफल वलय को <math>\mathbf{F}_q[x]/\Phi(x)</math> के रूप में लिखा जा सकता है, हालांकि कई लेखक <math>\mathbf{Z}_q[x]/\Phi(x)</math> लिखते हैं।<ref name=":0" />
-यदि बहुपद <math>\Phi(x)</math> की डिग्री है, तो भागफल वलय, <math>F_q</math> के गुणांकों के साथ <math display="inline">n</math> सापेक्ष <math>\Phi(x)</math> से कम डिग्री वाले बहुपदों का वलय बन जाता है। मान <math display="inline">n</math>, <math display="inline">q</math>, बहुपद <math>\Phi(x)</math> के साथ RLWE समस्या के लिए आंशिक रूप से गणितीय संदर्भ को परिभाषित करते हैं।
+यदि बहुपद <math>\Phi(x)</math> की डिग्री है, तो भागफल वलय, <math>F_q</math> के गुणांकों के साथ <math display="inline">n</math> सापेक्ष <math>\Phi(x)</math> से कम डिग्री वाले बहुपदों का वलय बन जाता है। मान <math display="inline">n</math>, <math display="inline">q</math>, बहुपद <math>\Phi(x)</math> के साथ आरएलडब्ल्यूई समस्या के लिए आंशिक रूप से गणितीय संदर्भ को परिभाषित करते हैं।
-आरएलडब्ल्यूई समस्या के लिए आवश्यक एक अन्य अवधारणा कुछ आदर्श के संबंध में "छोटे" बहुपदों का विचार है। RLWE समस्या में उपयोग किए जाने वाले विशिष्ट मानदंड को इन्फिनिटी मानदंड के रूप में जाना जाता है (जिसे एकसमान मानदंड भी कहा जाता है)। जब इन गुणांकों को पूर्णांकों के रूप में देखा जाता है, तो बहुपद का अनन्तता मान बहुपद का सबसे बड़ा गुणांक होता है। अत: <math>||a(x)||_\infty = b</math> बताता है कि बहुपद <math>a(x)</math> का अनन्तता मान <math>b</math> है। अतः <math>b</math> <math>a(x)</math> का सबसे बड़ा गुणांक है।
+आरएलडब्ल्यूई समस्या के लिए आवश्यक अन्य अवधारणा कुछ आदर्श के संबंध में "छोटे" बहुपदों का विचार है। आरएलडब्ल्यूई समस्या में उपयोग किए जाने वाले विशिष्ट मानदंड को इन्फिनिटी मानदंड के रूप में जाना जाता है (जिसे एकसमान मानदंड भी कहा जाता है)। जब इन गुणांकों को पूर्णांकों के रूप में देखा जाता है, तो बहुपद का अनन्तता मान बहुपद का सबसे बड़ा गुणांक होता है। अत: <math>||a(x)||_\infty = b</math> बताता है कि बहुपद <math>a(x)</math> का अनन्तता मान <math>b</math> है। अतः <math>b</math> <math>a(x)</math> का सबसे बड़ा गुणांक है।
-RLWE समस्या को समझने के लिए आवश्यक अंतिम अवधारणा <math>\mathbf{F}_q[x]/\Phi(x)</math> में यादृच्छिक बहुपदों की उत्पत्ति और "छोटे" बहुपदों की उत्पत्ति है। एक यादृच्छिक बहुपद आसानी से यादृच्छिक रूप से <math>\mathbf{F}_q</math>से बहुपद के <math>n</math> गुणांकों का नमूना लेकर उत्पन्न होता है, जहाँ <math>\mathbf{F}_q</math> को विशेष रूप से सेट <math>\{-(q-1)/2, ..., -1, 0, 1, ..., (q-1)/2\}</math>के रूप में दर्शाया जाता है।
+आरएलडब्ल्यूई समस्या को समझने के लिए आवश्यक अंतिम अवधारणा <math>\mathbf{F}_q[x]/\Phi(x)</math> में यादृच्छिक बहुपदों की उत्पत्ति और "छोटे" बहुपदों की उत्पत्ति है। यादृच्छिक बहुपद आसानी से यादृच्छिक रूप से <math>\mathbf{F}_q</math>से बहुपद के <math>n</math> गुणांकों का नमूना लेकर उत्पन्न होता है, जहाँ <math>\mathbf{F}_q</math> को विशेष रूप से सेट <math>\{-(q-1)/2, ..., -1, 0, 1, ..., (q-1)/2\}</math>के रूप में दर्शाया जाता है।
 बेतरतीब ढंग से एक "छोटा" बहुपद उत्पन्न करना <math>\mathbf{F}_q</math> से बहुपद के गुणांक उत्पन्न करके किया जाता है जो या तो गारंटी देता है या बहुत कम गुणांक बनाता है। जब <math>q</math> एक अभाज्य पूर्णांक होता है, तो इसे करने के दो सामान्य तरीके हैं:
-# यूनिफ़ॉर्म सैंपलिंग का उपयोग करना - छोटे बहुपद के गुणांकों को छोटे गुणांकों के एक सेट से समान रूप से नमूना लिया जाता है। मान लें कि <math display="inline">b</math> एक पूर्णांक है जो <math display="inline">q</math> से बहुत कम है। यदि हम यादृच्छिक रूप से समुच्चय से गुणांक चुनते हैं: <math display="inline">\{ -b, -b+1, -b+2, \ldots , -2, -1, 0, 1, 2, \ldots , b-2, b-1, b \}</math>बहुपद बाउंड (<math display="inline">b</math>) के संबंध में छोटा होगा।
+# यूनिफ़ॉर्म सैंपलिंग का उपयोग करना - छोटे बहुपद के गुणांकों को छोटे गुणांकों के सेट से समान रूप से नमूना लिया जाता है। मान लें कि <math display="inline">b</math> एक पूर्णांक है जो <math display="inline">q</math> से बहुत कम है। यदि हम यादृच्छिक रूप से समुच्चय से गुणांक चुनते हैं: <math display="inline">\{ -b, -b+1, -b+2, \ldots , -2, -1, 0, 1, 2, \ldots , b-2, b-1, b \}</math>बहुपद बाउंड (<math display="inline">b</math>) के संबंध में छोटा होगा।
-# असतत गॉसियन नमूनाकरण का उपयोग करना - <math display="inline">q</math> के लिए एक विषम मान के लिए, बहुपद के गुणांकों को बेतरतीब ढंग से चुना जाता है माध्य <math>0</math> और वितरण पैरामीटर <math display="inline">\sigma</math> के साथ असतत गॉसियन वितरण के अनुसार सेट <math display="inline"> \{ -(q-1)/2, \ldots , (q-1)/2 \} </math> से नमूनाकरण। संदर्भों में विस्तार से बताया गया है कि यह कैसे पूरा किया जा सकता है। यह एकसमान प्रतिचयन की तुलना में अधिक जटिल है लेकिन यह एल्गोरिथ्म की सुरक्षा के प्रमाण की अनुमति देता है। द्वारकानाथ और गालब्रेथ द्वारा लिखित पेपर "सैम्पलिंग फ्रॉम डिस्क्रीट गॉसियन्स फॉर लैटिस-बेस्ड क्रिप्टोग्राफी ऑन अ कन्स्ट्रेन्ड डिवाइस" इस समस्या का अवलोकन प्रदान करता है।<ref>{{Cite journal|title = विवश डिवाइस पर जाली-आधारित क्रिप्टोग्राफी के लिए असतत गॉसियन से नमूनाकरण|journal = Applicable Algebra in Engineering, Communication and Computing|date = 2014-03-18|issn = 0938-1279|pages = 159–180|volume = 25|issue = 3|doi = 10.1007/s00200-014-0218-3|first1 = Nagarjun C.|last1 = Dwarakanath|first2 = Steven D.|last2 = Galbraith|s2cid = 13718364}}</ref>
+# असतत गॉसियन नमूनाकरण का उपयोग करना - <math display="inline">q</math> के लिए विषम मान के लिए, बहुपद के गुणांकों को बेतरतीब ढंग से चुना जाता है माध्य <math>0</math> और वितरण पैरामीटर <math display="inline">\sigma</math> के साथ असतत गॉसियन वितरण के अनुसार सेट <math display="inline"> \{ -(q-1)/2, \ldots , (q-1)/2 \} </math> से नमूनाकरण। संदर्भों में विस्तार से बताया गया है कि यह कैसे पूरा किया जा सकता है। यह एकसमान प्रतिचयन की तुलना में अधिक जटिल है लेकिन यह एल्गोरिथ्म की सुरक्षा के प्रमाण की अनुमति देता है। द्वारकानाथ और गालब्रेथ द्वारा लिखित पेपर "सैम्पलिंग फ्रॉम डिस्क्रीट गॉसियन्स फॉर लैटिस-बेस्ड क्रिप्टोग्राफी ऑन अ कन्स्ट्रेन्ड डिवाइस" इस समस्या का अवलोकन प्रदान करता है।<ref>{{Cite journal|title = विवश डिवाइस पर जाली-आधारित क्रिप्टोग्राफी के लिए असतत गॉसियन से नमूनाकरण|journal = Applicable Algebra in Engineering, Communication and Computing|date = 2014-03-18|issn = 0938-1279|pages = 159–180|volume = 25|issue = 3|doi = 10.1007/s00200-014-0218-3|first1 = Nagarjun C.|last1 = Dwarakanath|first2 = Steven D.|last2 = Galbraith|s2cid = 13718364}}</ref>
 == आरएलडब्ल्यूई समस्या ==
-आरएलडब्ल्यूई समस्या को दो अलग-अलग तरीकों से कहा जा सकता है: एक "खोज" संस्करण और एक "निर्णय" संस्करण। दोनों एक ही रचना से प्रारंभ होते हैं। मान लें
+आरएलडब्ल्यूई समस्या को दो अलग-अलग तरीकों से कहा जा सकता है: "खोज" संस्करण और "निर्णय" संस्करण। दोनों एक ही रचना से प्रारंभ होते हैं। मान लें
-* <math>a_i(x)</math> <math>\mathbf{F}_q[x]/\Phi(x)</math> से सभी <math>\mathbf{F}_q</math> के गुणांकों के साथ यादृच्छिक लेकिन ज्ञात बहुपदों का एक समूह है।
+* <math>a_i(x)</math> <math>\mathbf{F}_q[x]/\Phi(x)</math> से सभी <math>\mathbf{F}_q</math> के गुणांकों के साथ यादृच्छिक लेकिन ज्ञात बहुपदों का समूह है।
-*<math>e_i(x)</math> रिंग <math>\mathbf{F}_q[x]/\Phi(x)</math>में एक बाउंड <math>b</math> के सापेक्ष छोटे यादृच्छिक और अज्ञात बहुपदों का एक सेट है।
+*<math>e_i(x)</math> रिंग <math>\mathbf{F}_q[x]/\Phi(x)</math>में बाउंड <math>b</math> के सापेक्ष छोटे यादृच्छिक और अज्ञात बहुपदों का सेट है।
-*<math>s(x)</math> रिंग <math>\mathbf{F}_q[x]/\Phi(x)</math> में बंधे <math>b</math> के सापेक्ष एक छोटा अज्ञात बहुपद हो।
+*<math>s(x)</math> रिंग <math>\mathbf{F}_q[x]/\Phi(x)</math> में बंधे <math>b</math> के सापेक्ष छोटा अज्ञात बहुपद हो।
 * <math>b_i(x) = (a_i(x)\cdot s(x)) + e_i(x)</math>.
 खोज संस्करण में बहुपद जोड़े <math>( a_i(x), b_i(x) )</math>सूची दिए जाने पर अज्ञात बहुपद <math>s(x)</math> को खोजने पर जोर देता है।
-समस्या का निर्णय संस्करण इस प्रकार बताया जा सकता है। बहुपद जोड़े <math>( a_i(x), b_i(x) )</math> की एक सूची दी गई है, यह निर्धारित करें कि क्या <math>b_i(x)</math> बहुपद <math>b_i(x) = (a_i(x)\cdot s(x)) + e_i(x)</math> के रूप में बनाए गए थे या सभी <math>\mathbf{F}_q</math> के गुणांकों के साथ <math>\mathbf{F}_q[x]/\Phi(x)</math> से यादृच्छिक रूप से उत्पन्न किए गए थे।
+समस्या का निर्णय संस्करण इस प्रकार बताया जा सकता है। बहुपद जोड़े <math>( a_i(x), b_i(x) )</math> की सूची दी गई है, यह निर्धारित करें कि क्या <math>b_i(x)</math> बहुपद <math>b_i(x) = (a_i(x)\cdot s(x)) + e_i(x)</math> के रूप में बनाए गए थे या सभी <math>\mathbf{F}_q</math> के गुणांकों के साथ <math>\mathbf{F}_q[x]/\Phi(x)</math> से यादृच्छिक रूप से उत्पन्न किए गए थे।
-इस समस्या की कठिनाई भागफल बहुपद <math>\Phi(x)</math> इसकी डिग्री (<math>n</math>), क्षेत्र (<math>\mathbf{F}_q</math>), और छोटेपन की सीमा (<math>b</math>) के विकल्प द्वारा निर्धारित की जाती है। कई RLWE-आधारित सार्वजनिक कुंजी एल्गोरिदम में, निजी कुंजी छोटे बहुपदों <math>s(x)</math> और <math>e(x)</math> की जोड़ी होगी। संबंधित सार्वजनिक कुंजी बहुपद <math>a(x)</math> की जोड़ी होगी, जिसे <math>\mathbf{F}_q[x]/\Phi(x)</math> और बहुपद <math>t(x)= (a(x)\cdot s(x)) + e(x)</math>से यादृच्छिक रूप से चुना गया है।  <math>a(x)</math> और <math>t(x)</math> दिया हुआ है, यह बहुपद <math>s(x)</math> को पुनर्प्राप्त करने के लिए कम्प्यूटेशनल रूप से अक्षम होना चाहिए।
+इस समस्या की कठिनाई भागफल बहुपद <math>\Phi(x)</math> इसकी डिग्री (<math>n</math>), क्षेत्र (<math>\mathbf{F}_q</math>), और छोटेपन की सीमा (<math>b</math>) के विकल्प द्वारा निर्धारित की जाती है। कई आरएलडब्ल्यूई-आधारित सार्वजनिक कुंजी एल्गोरिदम में, निजी कुंजी छोटे बहुपदों <math>s(x)</math> और <math>e(x)</math> की जोड़ी होगी। संबंधित सार्वजनिक कुंजी बहुपद <math>a(x)</math> की जोड़ी होगी, जिसे <math>\mathbf{F}_q[x]/\Phi(x)</math> और बहुपद <math>t(x)= (a(x)\cdot s(x)) + e(x)</math>से यादृच्छिक रूप से चुना गया है।  <math>a(x)</math> और <math>t(x)</math> दिया हुआ है, यह बहुपद <math>s(x)</math> को पुनर्प्राप्त करने के लिए कम्प्यूटेशनल रूप से अक्षम होना चाहिए।
 == सुरक्षा में कमी ==
-ऐसे मामलों में जहां बहुपद <math>\Phi(x)</math> एक [[साइक्लोटोमिक बहुपद]] है, आरएलडब्ल्यूई समस्या के खोज संस्करण को हल करने में कठिनाई के तत्वों से बने एक आदर्श जाली में एक छोटा वेक्टर (लेकिन जरूरी नहीं कि सबसे छोटा वेक्टर) खोजने के बराबर है <math>\mathbf{Z}[x]/\Phi(x)</math> पूर्णांक वैक्टर के रूप में प्रतिनिधित्व किया।<ref name=":0">{{Cite journal|title = आइडियल लैटिस और लर्निंग विद एरर्स ओवर रिंग्स पर|url = http://eprint.iacr.org/2012/230|date = 2012|first1 = Vadim|last1 = Lyubashevsky|first2 = Chris|last2 = Peikert|first3 = Oded|last3 = Regev| journal=Cryptology ePrint Archive }}</ref> इस समस्या को आमतौर पर सबसे छोटी वेक्टर समस्या | अनुमानित सबसे छोटी वेक्टर समस्या (α-SVP) के रूप में जाना जाता है और यह सबसे छोटे वेक्टर के α गुना से कम वेक्टर खोजने की समस्या है। इस तुल्यता के प्रमाण के लेखक लिखते हैं:
+ऐसे मामलों में जहां बहुपद <math>\Phi(x)</math> चक्रीय बहुपद है, आरएलडब्ल्यूई समस्या के खोज संस्करण को हल करने में कठिनाई लघु सदिश खोजने के बराबर है (लेकिन जरूरी नहीं कि सबसे छोटा वेक्टर) <math>\mathbf{Z}[x]/\Phi(x)</math> के तत्वों से बने आदर्श जाली में पूर्णांक वैक्टर के रूप में दर्शाया गया है।<ref name=":0">{{Cite journal|title = आइडियल लैटिस और लर्निंग विद एरर्स ओवर रिंग्स पर|url = http://eprint.iacr.org/2012/230|date = 2012|first1 = Vadim|last1 = Lyubashevsky|first2 = Chris|last2 = Peikert|first3 = Oded|last3 = Regev| journal=Cryptology ePrint Archive }}</ref> इस समस्या को सामान्यतः अनुमानित सबसे छोटी वेक्टर समस्या (α-SVP) के रूप में जाना जाता है और यह वेक्टर को खोजने की समस्या है जो सबसे छोटे वेक्टर के α गुना से कम है। इस तुल्यता के प्रमाण के लेखक लिखते हैं:
-: ... हम आदर्श लैटिस में अनुमानित एसवीपी (सबसे खराब स्थिति में) से क्वांटम कमी देते हैं <math>\mathbf{R}</math> रिंग-एलडब्ल्यूई के खोज संस्करण में, जहां लक्ष्य रहस्य को पुनर्प्राप्त करना है <math>s \in \mathbf{R}_q</math> (उच्च संभावना के साथ, किसी के लिए <math>s</math>) मनमाने ढंग से कई शोर वाले उत्पादों से।<ref name=":0" />
+: "... हम रिंग-एलडब्ल्यूई के खोज संस्करण में <math>\mathbf{R}</math> में आदर्श जाली पर अनुमानित एसवीपी (सबसे खराब स्थिति में) से एक मात्रा में कमी देते हैं, जहां लक्ष्य याच्छिक ढंग से कई शोर उत्पादों से सीक्रेट <math>s \in \mathbf{R}_q</math> (किसी भी <math>s</math> के लिए उच्च संभावना के साथ) को पुनर्प्राप्त करना है।" <ref name=":0" />
-उस बोली में, द रिंग <math>\mathbf{R}</math> है <math>\mathbf{Z}[x]/\Phi(x)</math> और अंगूठी <math>\mathbf{R}_q</math> है <math>\mathbf{F}_q[x]/\Phi(x)</math>.
+उक्त उद्धरण में, वलय <math>\mathbf{R}</math>, <math>\mathbf{Z}[x]/\Phi(x)</math>और वलय <math>\mathbf{R}_q</math>, <math>\mathbf{F}_q[x]/\Phi(x)</math>है।
-में डेनियल मिकिसियो द्वारा किए गए कार्य के कारण नियमित लैटिस में α-SVP को [[ एनपी कठिन ]] के रूप में जाना जाता है, हालांकि त्रुटियों की समस्या के साथ सामान्य सीखने में कमी के लिए आवश्यक α के मूल्यों के लिए नहीं।<ref name=":1">{{Cite journal|title = एक जाली में सबसे छोटा वेक्टर कुछ स्थिरांक के भीतर अनुमानित करना कठिन है|journal = SIAM Journal on Computing|date = January 1, 2001|issn = 0097-5397|pages = 2008–2035|volume = 30|issue = 6|doi = 10.1137/S0097539700373039|first = D.|last = Micciancio|citeseerx = 10.1.1.93.6646}}</ref> हालांकि, यह दिखाने के लिए अभी तक कोई सबूत नहीं है कि आदर्श जाली के लिए α-SVP की कठिनाई औसत α-SVP के बराबर है। बल्कि हमारे पास इस बात का प्रमाण है कि यदि कोई α-SVP उदाहरण हैं जो आदर्श जाली में हल करना कठिन है तो यादृच्छिक उदाहरणों में आरएलडब्ल्यूई समस्या कठिन होगी।<ref name=":0" />
+में डेनियल मिकिसियो द्वारा किए गए कार्य के कारण नियमित जाली में α-SVP को NP-हार्ड के रूप में जाना जाता है, हालांकि त्रुटियों की समस्या के साथ सामान्य सीखने में कमी के लिए आवश्यक α के मूल्यों के लिए नहीं।<ref name=":1">{{Cite journal|title = एक जाली में सबसे छोटा वेक्टर कुछ स्थिरांक के भीतर अनुमानित करना कठिन है|journal = SIAM Journal on Computing|date = January 1, 2001|issn = 0097-5397|pages = 2008–2035|volume = 30|issue = 6|doi = 10.1137/S0097539700373039|first = D.|last = Micciancio|citeseerx = 10.1.1.93.6646}}</ref> हालांकि, यह दिखाने के लिए अभी तक कोई सबूत नहीं है कि आदर्श लैटिस के लिए α-SVP की कठिनाई औसत α-SVP के बराबर है। बल्कि हमारे पास इस बात का प्रमाण है कि यदि कोई α-SVP उदाहरण हैं जो आदर्श जाली में हल करना कठिन है तो आरएलडब्ल्यूई समस्या यादृच्छिक उदाहरणों में कठिन होगी।<ref name=":0" />
-आइडियल लैटिस में सबसे छोटी वेक्टर समस्याओं की कठिनाई के बारे में, शोधकर्ता माइकल श्नाइडर लिखते हैं, अब तक आदर्श लैटिस की विशेष संरचना का उपयोग करने वाला कोई एसवीपी एल्गोरिदम नहीं है। यह व्यापक रूप से माना जाता है कि आदर्श जाली में एसवीपी (और अन्य सभी जाली समस्याओं) को हल करना उतना ही कठिन है जितना कि नियमित जाली में।<ref>{{Cite journal|title = आदर्श जालक में लघुतम सदिशों की छानबीन करना|url = http://eprint.iacr.org/2011/458|date = 2011|first = Michael|last = Schneider| journal=Cryptology ePrint Archive }}</ref> नियमित जाली पर इन समस्याओं की कठिनाई सिद्ध रूप से एनपी-कठिन है।<ref name=":1" />  हालांकि, कुछ ऐसे शोधकर्ता हैं जो यह नहीं मानते हैं कि आदर्श जाली समान सुरक्षा गुणों को नियमित जाली के रूप में साझा करते हैं।<ref>{{Cite web|title = cr.yp.to: 2014.02.13: A subfield-logarithm attack against ideal lattices|url = http://blog.cr.yp.to/20140213-ideal.html|website = blog.cr.yp.to|access-date = 2015-07-03}}</ref>
+आइडियल लैटिस में सबसे छोटी वेक्टर समस्याओं की कठिनाई के बारे में, शोधकर्ता माइकल श्नाइडर लिखते हैं, अब तक आदर्श लैटिस की विशेष संरचना का उपयोग करने वाला कोई एसवीपी एल्गोरिदम नहीं है। यह व्यापक रूप से माना जाता है कि आदर्श जाली में एसवीपी (और अन्य सभी जाली समस्याओं) को हल करना उतना ही कठिन है जितना कि नियमित जाली में।<ref>{{Cite journal|title = आदर्श जालक में लघुतम सदिशों की छानबीन करना|url = http://eprint.iacr.org/2011/458|date = 2011|first = Michael|last = Schneider| journal=Cryptology ePrint Archive }}</ref> नियमित जाली पर इन समस्याओं की कठिनाई सिद्ध रूप से एनपी-कठिन है।<ref name=":1" /> हालांकि, कुछ ऐसे शोधकर्ता हैं जो यह नहीं मानते हैं कि आदर्श जाली समान सुरक्षा गुणों को नियमित जाली के रूप में साझा करते हैं।<ref>{{Cite web|title = cr.yp.to: 2014.02.13: A subfield-logarithm attack against ideal lattices|url = http://blog.cr.yp.to/20140213-ideal.html|website = blog.cr.yp.to|access-date = 2015-07-03}}</ref>
-पिकर्ट का मानना है कि ये सुरक्षा समानताएं आरएलडब्ल्यूई समस्या को भविष्य की क्रिप्टोग्राफी के लिए एक अच्छा आधार बनाती हैं। वह लिखते हैं: एक गणितीय प्रमाण है कि क्रिप्टोसिस्टम (कुछ औपचारिक हमले के मॉडल के भीतर) को उसके यादृच्छिक उदाहरणों पर तोड़ने का एकमात्र तरीका सबसे खराब स्थिति (मूल में जोर) में अंतर्निहित जाली समस्या को हल करने में सक्षम होना है।<ref>{{Cite web |title = What does GCHQ's "cautionary tale" mean for lattice cryptography? |url = http://web.eecs.umich.edu/~cpeikert/soliloquy.html |website = www.eecs.umich.edu|access-date = 2016-01-05 |archive-url = https://web.archive.org/web/20160317165656/http://web.eecs.umich.edu/~cpeikert/soliloquy.html |archive-date = 2016-03-17}}</ref>
+पिकर्ट का मानना है कि ये सुरक्षा समानताएं आरएलडब्ल्यूई समस्या को भविष्य की क्रिप्टोग्राफी के लिए एक अच्छा आधार बनाती हैं। वह लिखते हैं: गणितीय प्रमाण है कि क्रिप्टोसिस्टम (कुछ औपचारिक हमले के मॉडल के भीतर) को उसके यादृच्छिक उदाहरणों पर तोड़ने का एकमात्र तरीका सबसे खराब स्थिति (मूल में जोर) में अंतर्निहित जाली समस्या को हल करने में सक्षम होना है।<ref>{{Cite web |title = What does GCHQ's "cautionary tale" mean for lattice cryptography? |url = http://web.eecs.umich.edu/~cpeikert/soliloquy.html |website = www.eecs.umich.edu|access-date = 2016-01-05 |archive-url = https://web.archive.org/web/20160317165656/http://web.eecs.umich.edu/~cpeikert/soliloquy.html |archive-date = 2016-03-17}}</ref>
+== आरएलडब्ल्यूई क्रिप्टोग्राफी ==
+आरएलडब्ल्यूई-आधारित क्रिप्टोग्राफी का एक बड़ा फायदा यह है कि मूल लर्निंग विद एरर (एलडब्ल्यूई) आधारित क्रिप्टोग्राफी सार्वजनिक और निजी कुंजी के आकार में पाई जाती है। आरएलडब्ल्यूई कुंजियाँ मोटे तौर पर एलडब्ल्यूई में चाबियों का वर्गमूल होती हैं।<ref name=":0" /> 128 बिट्स की सुरक्षा के लिए, आरएलडब्ल्यूई क्रिप्टोग्राफ़िक एल्गोरिथम लंबाई में लगभग 7000 बिट्स की सार्वजनिक कुंजी का उपयोग करेगा।<ref>{{Cite journal|title = जाली क्रिप्टोग्राफी का उपयोग कर इंटरनेट के लिए एक व्यावहारिक कुंजी एक्सचेंज|url = http://eprint.iacr.org/2015/138|date = 2015|first = Vikram|last = Singh| journal=Cryptology ePrint Archive }}</ref> संबंधित वामपंथी उग्रवादी योजना के लिए समान स्तर की सुरक्षा के लिए 49 मिलियन बिट की सार्वजनिक कुंजी की आवश्यकता होगी।<ref name=":0" /> दूसरी ओर, आरएलडब्ल्यूई कुंजियाँ आरएसए और एलिप्टिक कर्व डिफी-हेलमैन जैसे वर्तमान में उपयोग किए जाने वाले सार्वजनिक कुंजी एल्गोरिदम के लिए कुंजियों के आकार से बड़ी होती हैं, जिन्हें 128-बिट स्तर की सुरक्षा प्राप्त करने के लिए क्रमशः 3072 बिट और 256 बिट के सार्वजनिक कुंजी आकार की आवश्यकता होती है। हालांकि, कम्प्यूटेशनल दृष्टिकोण से, आरएलडब्ल्यूई एल्गोरिदम को मौजूदा सार्वजनिक कुंजी सिस्टम के बराबर या उससे बेहतर दिखाया गया है।<ref>{{Cite journal|title = रिंग-एलडब्ल्यूई एन्क्रिप्शन का कुशल सॉफ्टवेयर कार्यान्वयन|url = http://eprint.iacr.org/2014/725|date = 2014|first = Ruan de Clercq, Sujoy Sinha Roy, Frederik Vercauteren, Ingrid|last = Verbauwhede| journal=Cryptology ePrint Archive }}</ref>
-== आरएलडब्ल्यूई क्रिप्टोग्राफी ==
+आरएलडब्ल्यूई क्रिप्टोग्राफिक एल्गोरिदम के तीन समूह उपस्थित हैं:
-आरएलडब्ल्यूई आधारित क्रिप्टोग्राफी का एक बड़ा फायदा यह है कि त्रुटियों के साथ मूल सीखने (LWE) आधारित क्रिप्टोग्राफी सार्वजनिक और निजी कुंजियों के आकार में पाई जाती है। आरएलडब्ल्यूई कुंजियाँ मोटे तौर पर वामपंथी उग्रवादियों में कुंजियों का वर्गमूल होती हैं।<ref name=":0" />  सुरक्षा के 128 बिट्स के लिए एक आरएलडब्ल्यूई क्रिप्टोग्राफ़िक एल्गोरिथम लंबाई में लगभग 7000 बिट्स सार्वजनिक कुंजियों का उपयोग करेगा।<ref>{{Cite journal|title = जाली क्रिप्टोग्राफी का उपयोग कर इंटरनेट के लिए एक व्यावहारिक कुंजी एक्सचेंज|url = http://eprint.iacr.org/2015/138|date = 2015|first = Vikram|last = Singh| journal=Cryptology ePrint Archive }}</ref> इसी स्तर की सुरक्षा के लिए संबंधित LWE योजना के लिए 49 मिलियन बिट्स की सार्वजनिक कुंजियों की आवश्यकता होगी।<ref name=":0" />{{failed verification|date=August 2016}} दूसरी ओर, आरएलडब्ल्यूई कुंजियाँ RSA और एलिप्टिक कर्व डिफी-हेलमैन जैसे वर्तमान में उपयोग किए जाने वाले सार्वजनिक कुंजी एल्गोरिदम के लिए कुंजियों के आकार से बड़ी हैं, जिन्हें 128-बिट स्तर प्राप्त करने के लिए क्रमशः 3072 बिट और 256 बिट के सार्वजनिक [[कुंजी आकार]] की आवश्यकता होती है। सुरक्षा। एक कम्प्यूटेशनल दृष्टिकोण से, हालांकि, आरएलडब्ल्यूई एल्गोरिदम को मौजूदा सार्वजनिक कुंजी सिस्टम के बराबर या उससे बेहतर दिखाया गया है।<ref>{{Cite journal|title = रिंग-एलडब्ल्यूई एन्क्रिप्शन का कुशल सॉफ्टवेयर कार्यान्वयन|url = http://eprint.iacr.org/2014/725|date = 2014|first = Ruan de Clercq, Sujoy Sinha Roy, Frederik Vercauteren, Ingrid|last = Verbauwhede| journal=Cryptology ePrint Archive }}</ref>
-आरएलडब्ल्यूई क्रिप्टोग्राफिक एल्गोरिदम के तीन समूह मौजूद हैं:
+=== त्रुटियों के साथ रिंग लर्निंग प्रमुख आदान-प्रदान (आरएलडब्ल्यूई-केईएक्स) ===
+{{main|त्रुटियों के साथ रिंग सीखना कुंजी विनिमय}}
-=== त्रुटियों के साथ रिंग लर्निंग प्रमुख आदान-प्रदान (आरएलडब्ल्यूई-KEX) ===
+प्रमुख विनिमय के लिए वामपंथी उग्रवाद और वामपंथी उग्रवाद का उपयोग करने का मौलिक विचार प्रस्तावित किया गया था और जिंताई डिंग द्वारा 2011 में सिनसिनाटी विश्वविद्यालय में दाखिल किया गया था। मूल विचार मैट्रिक्स गुणन की संबद्धता से आता है, और त्रुटियों का उपयोग सुरक्षा प्रदान करने के लिए किया जाता है। 2012 में अनंतिम पेटेंट आवेदन दायर करने के बाद 2012 में पेपर <ref>{{Cite journal|last1=Ding|first1=Jintai|last2=Xie|first2=Xiang|last3=Lin|first3=Xiaodong|date=2012-01-01|title=त्रुटियों के साथ सीखने की समस्या पर आधारित एक सरल प्रमाणित सुरक्षित कुंजी विनिमय योजना|journal=Cryptology ePrint Archive |url=http://eprint.iacr.org/2012/688}}</ref> दिखाई दिया।
-{{main|Ring learning with errors key exchange}}
-प्रमुख विनिमय के लिए वामपंथी उग्रवाद और वामपंथी उग्रवाद का इस्तेमाल करने का मौलिक विचार जिंताई डिंग द्वारा 2011 में सिनसिनाटी विश्वविद्यालय में प्रस्तावित और दायर किया गया था। मूल विचार मैट्रिक्स गुणन की संबद्धता से आता है, और सुरक्षा प्रदान करने के लिए त्रुटियों का उपयोग किया जाता है। कागज़<ref>{{Cite journal|last1=Ding|first1=Jintai|last2=Xie|first2=Xiang|last3=Lin|first3=Xiaodong|date=2012-01-01|title=त्रुटियों के साथ सीखने की समस्या पर आधारित एक सरल प्रमाणित सुरक्षित कुंजी विनिमय योजना|journal=Cryptology ePrint Archive |url=http://eprint.iacr.org/2012/688}}</ref> 2012 में एक अनंतिम पेटेंट आवेदन दायर करने के बाद 2012 में दिखाई दिया।
 में, पिकर्ट<ref>{{Cite journal|last=Peikert|first=Chris|date=2014-01-01|title=इंटरनेट के लिए जाली क्रिप्टोग्राफी|journal=Cryptology ePrint Archive |url=http://eprint.iacr.org/2014/070}}</ref> डिंग के समान मूल विचार के बाद एक प्रमुख परिवहन योजना प्रस्तुत की, जहां डिंग के निर्माण में गोलाई के लिए अतिरिक्त 1 बिट सिग्नल भेजने का नया विचार भी उपयोग किया जाता है। डिफी-हेलमैन कुंजी एक्सचेंज के क्लासिक एमक्यूवी संस्करण का एक आरएलडब्ल्यूई संस्करण बाद में झांग एट अल द्वारा प्रकाशित किया गया था।<ref>{{Cite journal|title = आइडियल लैटिस से ऑथेंटिकेटेड की एक्सचेंज|url = http://eprint.iacr.org/2014/589|date = 2014|first1 = Jiang|last1 = Zhang|first2 = Zhenfeng|last2 = Zhang|first3 = Jintai|last3 = Ding|first4 = Michael|last4 = Snook|first5 = Özgür|last5 = Dagdelen| journal=Cryptology ePrint Archive }}</ref> दोनों प्रमुख एक्सचेंजों की सुरक्षा सीधे एक आदर्श जाली में लगभग छोटे वैक्टर खोजने की समस्या से संबंधित है।
 === त्रुटि हस्ताक्षर के साथ रिंग लर्निंग (आरएलडब्ल्यूई-एसआईजी) ===
-{{main|Ring learning with errors signature}}
+{{main|हस्ताक्षरित त्रुटियों के साथ रिंग लर्निंग}}
-क्लासिक फीगे-फिएट-शमीर पहचान योजना का एक आरएलडब्ल्यूई संस्करण | फीगे-फिएट-शमीर पहचान प्रोटोकॉल बनाया गया था और 2011 में हुबाशेव्स्की द्वारा एक डिजिटल हस्ताक्षर में परिवर्तित किया गया था।<ref>{{Cite journal|title = ट्रैपडोर के बिना जाली हस्ताक्षर|url = http://eprint.iacr.org/2011/537|date = 2011|first = Vadim|last = Lyubashevsky| journal=Cryptology ePrint Archive }}</ref> इस हस्ताक्षर का विवरण 2012 में गुनेसु, ल्यूबाशेव्स्की और 2012 में पोप्पलमैन द्वारा विस्तारित किया गया था और उनके पेपर प्रैक्टिकल लैटिस आधारित क्रिप्टोग्राफी - एंबेडेड सिस्टम के लिए एक हस्ताक्षर योजना में प्रकाशित किया गया था।<ref>{{Cite book|title = Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems|publisher = Springer Berlin Heidelberg|date = 2012|isbn = 978-3-642-33026-1|pages = 530–547|series = Lecture Notes in Computer Science|first1 = Tim|last1 = Güneysu|first2 = Vadim|last2 = Lyubashevsky|first3 = Thomas|last3 = Pöppelmann|editor-first = Emmanuel|editor-last = Prouff|editor-first2 = Patrick|editor-last2 = Schaumont|doi = 10.1007/978-3-642-33027-8_31}}</ref> इन पेपरों ने विभिन्न प्रकार के हालिया सिग्नेचर एल्गोरिदम के लिए आधार तैयार किया, कुछ सीधे रिंग लर्निंग विद एरर्स प्रॉब्लम पर आधारित थे और कुछ जो समान कठिन आरएलडब्ल्यूई समस्याओं से बंधे नहीं थे।<ref>{{Cite web|title = ब्लिस हस्ताक्षर योजना|url = http://bliss.di.ens.fr/|website = bliss.di.ens.fr|access-date = 2015-07-04}}</ref>
+चिरसम्मत फीज-फिएट-शमीर आइडेंटिफिकेशन प्रोटोकॉल का आरएलडब्ल्यूई संस्करण बनाया गया था और 2011 में हुबाशेवस्की द्वारा डिजिटल हस्ताक्षर में परिवर्तित किया गया था।<ref>{{Cite journal|title = ट्रैपडोर के बिना जाली हस्ताक्षर|url = http://eprint.iacr.org/2011/537|date = 2011|first = Vadim|last = Lyubashevsky| journal=Cryptology ePrint Archive }}</ref>  इस हस्ताक्षर का विवरण 2012 में गुनेसू, ल्युबाशेवस्की और पोप्पलमैन द्वारा 2012 में विस्तारित किया गया था और उनके पेपर "प्रैक्टिकल लैटिस बेस्ड क्रिप्टोग्राफी - ए सिग्नेचर स्कीम फॉर एंबेडेड सिस्टम्स" में प्रकाशित किया गया था।<ref>{{Cite book|title = Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems|publisher = Springer Berlin Heidelberg|date = 2012|isbn = 978-3-642-33026-1|pages = 530–547|series = Lecture Notes in Computer Science|first1 = Tim|last1 = Güneysu|first2 = Vadim|last2 = Lyubashevsky|first3 = Thomas|last3 = Pöppelmann|editor-first = Emmanuel|editor-last = Prouff|editor-first2 = Patrick|editor-last2 = Schaumont|doi = 10.1007/978-3-642-33027-8_31}}</ref> इन पेपर्स ने हाल ही के सिग्नेचर एल्गोरिदम वर्ग के लिए आधार तैयार किया, कुछ सीधे रिंग लर्निंग विद एरर प्रॉब्लम पर आधारित थे और कुछ जो समान कठिन आरएलडब्ल्यूई समस्याओं से बंधे नहीं थे।<ref>{{Cite web|title = ब्लिस हस्ताक्षर योजना|url = http://bliss.di.ens.fr/|website = bliss.di.ens.fr|access-date = 2015-07-04}}</ref>
 === त्रुटियों के साथ रिंग लर्निंग होमोमोर्फिक एन्क्रिप्शन (आरएलडब्ल्यूई-HOM) ===
-{{main|Homomorphic encryption}}
+{{main|होमोमोर्फिक एन्क्रिप्शन}}
-होमोमोर्फिक एन्क्रिप्शन का उद्देश्य उन कंप्यूटिंग उपकरणों पर संवेदनशील डेटा पर संगणना की अनुमति देना है, जिन पर डेटा के साथ भरोसा नहीं किया जाना चाहिए। इन कंप्यूटिंग उपकरणों को सिफरटेक्स्ट को संसाधित करने की अनुमति है जो एक होमोमोर्फिक एन्क्रिप्शन से आउटपुट होता है। 2011 में, ब्रेक्सकी और वैकुंठनाथन ने रिंग-एलडब्ल्यूई से पूरी तरह से होमोमोर्फिक एन्क्रिप्शन प्रकाशित किया और कुंजी निर्भर संदेशों के लिए सुरक्षा जो सीधे आरएलडब्ल्यूई समस्या पर एक होमोमोर्फिक एन्क्रिप्शन योजना बनाता है।<ref>{{Cite book|title = रिंग-एलडब्ल्यूई से पूरी तरह से होमोमोर्फिक एन्क्रिप्शन और प्रमुख आश्रित संदेशों के लिए सुरक्षा|publisher = Springer Berlin Heidelberg|date = 2011|isbn = 978-3-642-22791-2|pages = 505–524|series = Lecture Notes in Computer Science|first1 = Zvika|last1 = Brakerski|first2 = Vinod|last2 = Vaikuntanathan|editor-first = Phillip|editor-last = Rogaway|doi = 10.1007/978-3-642-22792-9_29}}</ref>
+होमोमोर्फिक एन्क्रिप्शन का उद्देश्य संवेदनशील डेटा की संगणनाओं को उन कंप्यूटिंग उपकरणों पर होने देना है जिन पर डेटा के साथ भरोसा नहीं किया जाना चाहिए। इन कंप्यूटिंग डिवाइसों को सिफरटेक्स्ट को प्रोसेस करने की अनुमति है जो होमोमोर्फिक एन्क्रिप्शन से आउटपुट है। 2011 में, ब्रैकर्सकी और वैकुंठनाथन ने "रिंग-एलडब्ल्यूई से पूरी तरह से होमोमोर्फिक एन्क्रिप्शन और कुंजी निर्भर संदेशों के लिए सुरक्षा" प्रकाशित की, जो सीधे आरएलडब्ल्यूई समस्या पर होमोमोर्फिक एन्क्रिप्शन योजना बनाता है।<ref>{{Cite book|title = रिंग-एलडब्ल्यूई से पूरी तरह से होमोमोर्फिक एन्क्रिप्शन और प्रमुख आश्रित संदेशों के लिए सुरक्षा|publisher = Springer Berlin Heidelberg|date = 2011|isbn = 978-3-642-22791-2|pages = 505–524|series = Lecture Notes in Computer Science|first1 = Zvika|last1 = Brakerski|first2 = Vinod|last2 = Vaikuntanathan|editor-first = Phillip|editor-last = Rogaway|doi = 10.1007/978-3-642-22792-9_29}}</ref>
 ==संदर्भ==
 {{Reflist|30em}}

v t e कम्प्यूटेशनल कठोरता धारणाएं
संख्या सिद्धांत	पूर्णांक कारक फी-छिपा आरएसए समस्या मजबूत आरएसए द्विघात अवशेष निर्णायक समग्र अवशेष उच्च अवशेष
समूह सिद्धांत	असतत लॉगरिथम डिफी-हेलमैन निर्णायक डिफी -हेलमैन कम्प्यूटेशनल डिफी -हेलमैन
जोड़ियां	बाहरी diffie -hellman उप-समूह छिपा हुआ निर्णय रैखिक
जाली	सबसे छोटा वेक्टर समस्या निकटतम वेक्टर समस्या ( GAP त्रुटियों के साथ सीखना त्रुटियों के साथ रिंग सीखना लघु पूर्णांक समाधान
गैर-क्रिप्टोग्राफ़िक	घातीय समय परिकल्पना अद्वितीय खेल अनुमान लगाए गए क्लिक कॉनजेक्चर

Anonymous

Search

रिंग लर्निंग विद एरर्स: Difference between revisions

Namespaces

More

Page actions

Revision as of 14:30, 16 May 2023

Contents

पृष्ठभूमि

आरएलडब्ल्यूई समस्या

सुरक्षा में कमी

आरएलडब्ल्यूई क्रिप्टोग्राफी

त्रुटियों के साथ रिंग लर्निंग प्रमुख आदान-प्रदान (आरएलडब्ल्यूई-केईएक्स)

त्रुटि हस्ताक्षर के साथ रिंग लर्निंग (आरएलडब्ल्यूई-एसआईजी)

त्रुटियों के साथ रिंग लर्निंग होमोमोर्फिक एन्क्रिप्शन (आरएलडब्ल्यूई-HOM)

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

रिंग लर्निंग विद एरर्स: Difference between revisions

Revision as of 14:30, 16 May 2023

पृष्ठभूमि

आरएलडब्ल्यूई समस्या

सुरक्षा में कमी

आरएलडब्ल्यूई क्रिप्टोग्राफी

त्रुटियों के साथ रिंग लर्निंग प्रमुख आदान-प्रदान (आरएलडब्ल्यूई-केईएक्स)

त्रुटि हस्ताक्षर के साथ रिंग लर्निंग (आरएलडब्ल्यूई-एसआईजी)

त्रुटियों के साथ रिंग लर्निंग होमोमोर्फिक एन्क्रिप्शन (आरएलडब्ल्यूई-HOM)

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories