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

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

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

पृष्ठभूमि

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

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

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

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

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

आरएलडब्ल्यूई समस्या को समझने के लिए आवश्यक अंतिम अवधारणा यादृच्छिक बहुपदों की पीढ़ी है $\mathbf {F} _{q}[x]/\Phi (x)$ और छोटे बहुपदों की पीढ़ी। एक यादृच्छिक बहुपद आसानी से यादृच्छिक रूप से नमूने द्वारा उत्पन्न होता है $n$ से बहुपद के गुणांक $\mathbf {F} _{q}$, कहाँ $\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. गॉसियन फ़ंक्शन का उपयोग#Discrete_Gaussian - के लिए एक विषम मान के लिए ${\textstyle q}$, बहुपद के गुणांकों को सेट से नमूने द्वारा यादृच्छिक रूप से चुना जाता है ${\textstyle \{-(q-1)/2,\ldots ,(q-1)/2\}}$ माध्य के साथ असतत गाऊसी वितरण के अनुसार $0$ और वितरण पैरामीटर ${\textstyle \sigma }$. संदर्भ पूरे विस्तार से वर्णन करते हैं कि यह कैसे पूरा किया जा सकता है। यह एकसमान नमूनाकरण की तुलना में अधिक जटिल है लेकिन यह एल्गोरिथम की सुरक्षा के प्रमाण की अनुमति देता है। द्वारकानाथ और गालब्रेथ द्वारा एक विवश डिवाइस पर जाली-आधारित क्रिप्टोग्राफी के लिए असतत गॉसियन से पेपर नमूनाकरण इस समस्या का एक अवलोकन प्रदान करता है।

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

RLWE समस्या को दो अलग-अलग तरीकों से कहा जा सकता है: एक खोज संस्करण और एक निर्णय संस्करण। दोनों एक ही निर्माण से शुरू होते हैं। होने देना

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

खोज संस्करण अज्ञात बहुपद खोजने पर जोर देता है $s(x)$ बहुपद जोड़े की सूची दी गई है $(a_{i}(x),b_{i}(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}[x]/\Phi (x)$ सभी के गुणांकों के साथ $\mathbf {F} _{q}$.

इस समस्या की कठिनाई भागफल बहुपद की पसंद से परिचालित होती है ($\Phi (x)$), इसकी डिग्री ($n$), फील्ड ($\mathbf {F} _{q}$), और छोटापन बाध्य ($b$). कई RLWE आधारित सार्वजनिक कुंजी एल्गोरिदम में निजी कुंजी छोटे बहुपदों की एक जोड़ी होगी $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)$ एक साइक्लोटोमिक बहुपद है, RLWE समस्या के खोज संस्करण को हल करने में कठिनाई के तत्वों से बने एक आदर्श जाली में एक छोटा वेक्टर (लेकिन जरूरी नहीं कि सबसे छोटा वेक्टर) खोजने के बराबर है $\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 को एनपी कठिन के रूप में जाना जाता है, हालांकि त्रुटियों की समस्या के साथ सामान्य सीखने में कमी के लिए आवश्यक α के मूल्यों के लिए नहीं। हालांकि, यह दिखाने के लिए अभी तक कोई सबूत नहीं है कि आदर्श जाली के लिए α-SVP की कठिनाई औसत α-SVP के बराबर है। बल्कि हमारे पास इस बात का प्रमाण है कि यदि कोई α-SVP उदाहरण हैं जो आदर्श जाली में हल करना कठिन है तो यादृच्छिक उदाहरणों में RLWE समस्या कठिन होगी।

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

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

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

त्रुटियों के साथ रिंग लर्निंग प्रमुख आदान-प्रदान (RLWE-KEX)

Main article: Ring learning with errors key exchange

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

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

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

Main article: Ring learning with errors signature

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

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

Main article: Homomorphic encryption

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