रिंग लर्निंग विद एरर्स

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

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

पृष्ठभूमि

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

रिंग लर्निंग विथ एरर्स (आरएलडब्ल्यूई) समस्या परिमित क्षेत्र से गुणांक वाले बहुपदों के अंकगणित पर निर्मित है। प्रारूपिक बहुपद ${\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)$ लिखते हैं।

यदि बहुपद $\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$ एक अभाज्य पूर्णांक होता है, तो इसे करने के दो सामान्य तरीके हैं:

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

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

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

• $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)$ के तत्वों से बने आदर्श जाली में पूर्णांक वैक्टर के रूप में दर्शाया गया है। इस समस्या को सामान्यतः अनुमानित सबसे छोटी वेक्टर समस्या (α-SVP) के रूप में जाना जाता है और यह वेक्टर को खोजने की समस्या है जो सबसे छोटे वेक्टर के α गुना से कम है। इस तुल्यता के प्रमाण के लेखक लिखते हैं:

"... हम रिंग-एलडब्ल्यूई के खोज संस्करण में $\mathbf {R}$ में आदर्श जाली पर अनुमानित एसवीपी (सबसे खराब स्थिति में) से एक मात्रा में कमी देते हैं, जहां लक्ष्य याच्छिक ढंग से कई शोर उत्पादों से सीक्रेट $s\in \mathbf {R} _{q}$ (किसी भी $s$ के लिए उच्च संभावना के साथ) को पुनर्प्राप्त करना है।"

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

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

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

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

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

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

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

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

Main article: त्रुटियों के साथ रिंग सीखना कुंजी विनिमय

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

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

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

Main article: हस्ताक्षरित त्रुटियों के साथ रिंग लर्निंग

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

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

Main article: होमोमोर्फिक एन्क्रिप्शन

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