आदर्श जालक: Difference between revisions

From Vigyanwiki
(Text)
No edit summary
 
(6 intermediate revisions by 3 users not shown)
Line 37: Line 37:
# <math> c = P_{(\centerdot,n)} </math> इस कॉलम की बराबरी करने के लिए
# <math> c = P_{(\centerdot,n)} </math> इस कॉलम की बराबरी करने के लिए
# '''एल्स रिटर्न फाल्स'''  
# '''एल्स रिटर्न फाल्स'''  
# '''इफ''' <math> z \mid c_i </math> फॉर <math> i = 1, \ldots , n </math> '''देन'''
# '''इफ''' <math> z \mid c_i </math> फॉर <math> i = 1, \ldots , n </math> '''देन'''  
# खोजने के लिए [[चीनी शेष प्रमेय|सीआरटी]] का उपयोग करें <math> q^\ast \equiv (c/z) \bmod (d/z) </math> और <math> q^ \ast \equiv 0 \bmod \ z </math>
# खोजने के लिए [[चीनी शेष प्रमेय|सीआरटी]] का उपयोग करें <math> q^\ast \equiv (c/z) \bmod (d/z) </math> और <math> q^ \ast \equiv 0 \bmod \ z </math>
# '''एल्स रिटर्न फाल्स'''  
# '''एल्स रिटर्न फाल्स'''  
Line 87: Line 87:


=== कुशल टक्कर प्रतिरोधी हैश फ़ंक्शन ===
=== कुशल टक्कर प्रतिरोधी हैश फ़ंक्शन ===
'''क्रिप्टोग्राफ़ी में आदर्श जालक की मुख्य उपयोगिता इस तथ्य से उपजी है कि बहुत ही कुशल और व्यावहारिक टक्कर प्रतिरोध क्रिप्टोग्राफ़िक हैश फ़ंक्शन को इस तरह के जालक में अनुमानित जालक समस्या खोजने की कठोरता के आधार पर बनाया जा सकता है।'''<ref name="Lyubattacks2008"/>पिकर्ट और रोसेन द्वारा स्वतंत्र रूप से निर्मित टक्कर प्रतिरोध क्रिप्टोग्राफ़िक हैश फ़ंक्शन,<ref name="PeiRos2006"/>साथ ही ल्युबाशेव्स्की और माइकियानसियो, आदर्श जालक (चक्रीय जालक का एक सामान्यीकरण) पर आधारित थे, और एक तेज़ और व्यावहारिक कार्यान्वयन प्रदान किया।<ref name="LyubPeiReg2010"/>इन परिणामों ने पहचान योजनाओं और हस्ताक्षरों सहित अन्य कुशल क्रिप्टोग्राफ़िक निर्माणों का मार्ग प्रशस्त किया।
क्रिप्टोग्राफ़ी में आदर्श जालक की मुख्य उपयोगिता इस तथ्य से उपजी है कि इस तरह के जाली में लगभग सबसे छोटा वेक्टर खोजने की कठोरता के आधार पर बहुत ही कुशल और व्यावहारिक टक्कर प्रतिरोधी हैश फ़ंक्शन बनाए जा सकते हैं।<ref name="Lyubattacks2008"/>पिकर्ट और रोसेन द्वारा स्वतंत्र रूप से निर्मित टक्कर प्रतिरोध क्रिप्टोग्राफ़िक हैश फ़ंक्शन,<ref name="PeiRos2006"/>साथ ही ल्युबाशेव्स्की और माइकियानसियो, आदर्श जालक (चक्रीय जालक का एक सामान्यीकरण) पर आधारित थे, और एक तेज़ और व्यावहारिक कार्यान्वयन प्रदान करता है।।<ref name="LyubPeiReg2010"/>इन परिणामों ने पहचान योजनाओं और हस्ताक्षरों सहित अन्य कुशल क्रिप्टोग्राफ़िक निर्माणों का मार्ग प्रशस्त किया।


हुबाशेव्स्की और मिकिसियानियो<ref name="LyubMic2006"/>कुशल टकराव प्रतिरोध क्रिप्टोग्राफ़िक हैश फ़ंक्शन का निर्माण दिया जो आदर्श जालक के लिए जालक समस्या की सबसे खराब स्थिति के आधार पर सुरक्षित साबित हो सकता है। उन्होंने क्रिप्टोग्राफ़िक हैश फ़ंक्शन परिवारों को परिभाषित किया: एक वलय दी (गणित) <math>R = \mathbb{Z}_p[x]/\langle f \rangle </math>, कहाँ <math> f \in \mathbb{Z}_p[x] </math> डिग्री का एक मोनिक, अलघुकरणीय बहुपद है <math> n </math> और <math> p </math> मोटे तौर पर क्रम का पूर्णांक है <math> n^2 </math>, बनाना <math> m </math> यादृच्छिक तत्व <math> a_1, \dots , a_m \in R </math>, कहाँ <math> m </math> एक स्थिरांक है। आदेश दिया <math> m </math>-टुपल <math> h = (a_1, \ldots, a_m) \in R^m </math> हैश फ़ंक्शन निर्धारित करता है। यह तत्वों को मैप करेगा <math> D^m </math>, कहाँ <math> D </math> का रणनीतिक रूप से चुना गया सबसमुच्चय है <math> R </math>, को <math> R </math>. एक तत्व के लिए <math> b = (b_1, \ldots , b_m) \in D^m </math>, हैश है <math> h(b) = \sum_{i=1}^{m}\alpha_i \centerdot b_i</math>. यहाँ कुंजी का आकार (क्रिप्टोग्राफ़िक हैश फ़ंक्शन) है <math> O(mn \log p) = O(n \log n)</math>, और ऑपरेशन <math> \alpha_i \centerdot b_i </math> समय पर किया जा सकता है <math> O(n \log n \log \log n) </math> [[फास्ट फूरियर ट्रांसफॉर्म]] | फास्ट फूरियर ट्रांसफॉर्म (FFT) का उपयोग करके {{Citation needed|reason=FFT has roundoff errors that are unacceptable in integer mathematics for implementing cryptographic schemes. Without a citation, this seems crazy, and even with a citation this seems dubious/arguable/etc... two different implementations of FFT used in two different implementations of this hash function will almost certainly yield different results for identical input after iteratively/repeatedly hashing.|date=January 2018}}, बहुपद के उपयुक्त विकल्प के लिए <math> f </math>. तब से <math> m </math> स्थिर है,
हुबाशेव्स्की और मिकिसियानियो<ref name="LyubMic2006"/>कुशल टकराव प्रतिरोध क्रिप्टोग्राफ़िक हैश फ़ंक्शन का निर्माण दिया जो आदर्श जालक के लिए सबसे छोटी वेक्टर समस्या की सबसे खराब स्थिति के आधार पर सुरक्षित प्रमाणित हो सकता है। उन्होंने क्रिप्टोग्राफ़िक हैश फ़ंक्शन परिवारों को परिभाषित किया: एक वलय <math>R = \mathbb{Z}_p[x]/\langle f \rangle </math> दी , जहाँ<math> f \in \mathbb{Z}_p[x] </math> डिग्री का एक मोनिक, अलघुकरणीय बहुपद डिग्री <math> n </math> और <math> p </math> लगभग क्रम का पूर्णांक <math> n^2 </math> है, <math> m </math> यादृच्छिक तत्व <math> a_1, \dots , a_m \in R </math>, जहाँ <math> m </math> एक स्थिरांक है। क्रमशः <math> m </math>-टुपल <math> h = (a_1, \ldots, a_m) \in R^m </math> हैश फ़ंक्शन निर्धारित करता है। यह तत्वों को <math> D^m </math>में मैप करेगा, जहाँ <math> D </math>, <math> R </math> से <math> R </math> का एक रणनीतिक रूप से चुना गया उपसमुच्चय है। एक तत्व के लिए <math> b = (b_1, \ldots , b_m) \in D^m </math>, हैश <math> h(b) = \sum_{i=1}^{m}\alpha_i \centerdot b_i</math>है। यहाँ कुंजी का आकार (क्रिप्टोग्राफ़िक हैश फ़ंक्शन) <math> O(mn \log p) = O(n \log n)</math>है, और ऑपरेशन <math> \alpha_i \centerdot b_i </math>, <math> O(n \log n \log \log n) </math>समय पर बहुपद <math> f </math> के उपयुक्त विकल्प के लिए [[फास्ट फूरियर ट्रांसफॉर्म]] (FFT) का उपयोग किया जाता है।  {{Citation needed|reason=FFT has roundoff errors that are unacceptable in integer mathematics for implementing cryptographic schemes. Without a citation, this seems crazy, and even with a citation this seems dubious/arguable/etc... two different implementations of FFT used in two different implementations of this hash function will almost certainly yield different results for identical input after iteratively/repeatedly hashing.|date=January 2018}} चूँकि <math> m </math> एक नियतांक है, हैशिंग के लिए <math> O(n \log n \log \log n)</math> समय की आवश्यकता होती है। उन्होंने प्रमाणित किया कि क्रिप्टोग्राफ़िक हैश फ़ंक्शन परिवार टकराव प्रतिरोधी है, यह दिखाते हुए कि यदि कोई बहुपद समय एल्गोरिदम है जो बहुपद-समय एल्गोरिथ्म जो <math> b \neq b' \in D^m </math>खोजने में गैर-नगण्य संभाव्यता के साथ सफल होता है जैसे कि<math> h(b) = h(b') </math> है, अक्रमतः चुने गए क्रिप्टोग्राफ़िक हैश फ़ंक्शन <math> h \in R^m </math> के लिए , फिर एक निश्चित समस्या जिसे "सबसे छोटी वेक्टर समस्या" कहा जाता है, वलय <math> \mathbb{Z}[x]/\langle f \rangle </math>के प्रत्येक आदर्श के लिए बहुपद समय में हल करने योग्य है।
हैशिंग के लिए समय की आवश्यकता होती है <math> O(n \log n \log \log n)</math>. उन्होंने साबित किया कि क्रिप्टोग्राफ़िक हैश फ़ंक्शन परिवार टकराव प्रतिरोध है, यह दिखाते हुए कि यदि कोई बहुपद समय है। बहुपद-समय एल्गोरिथ्म जो खोजने में गैर-नगण्य संभाव्यता के साथ सफल होता है <math> b \neq b' \in D^m </math> ऐसा है कि
<math> h(b) = h(b') </math>, बेतरतीब ढंग से चुने गए क्रिप्टोग्राफ़िक हैश फ़ंक्शन के लिए <math> h \in R^m </math>, फिर एक निश्चित
वलय (गणित) के प्रत्येक आदर्श (वलय थ्योरी) के लिए "जालक समस्या" नामक समस्या बहुपद समय में हल करने योग्य है <math> \mathbb{Z}[x]/\langle f \rangle </math>.


2006 में हुबाशेवस्की और मिकिसियानियो के काम के आधार पर, मिकसियानियो और रेगेव<ref name="MicRegLBC2009">Daniele Micciancio, Oded Regev [http://www.cs.tau.ac.il/~odedr/papers/pqc.pdf Lattice-based Cryptography] {{Webarchive|url=https://web.archive.org/web/20110723090945/http://www.cs.tau.ac.il/~odedr/papers/pqc.pdf |date=2011-07-23 }}. In ''POST-QUANTUM CRYPTOGRAPHY'', 2009.</ref> आदर्श जालक के आधार पर क्रिप्टोग्राफ़िक हैश फ़ंक्शन के निम्नलिखित एल्गोरिथम को परिभाषित किया गया है:
2006 में हुबाशेवस्की और मिकिसियानियो के काम के आधार पर, मिकसियानियो और रेगेव<ref name="MicRegLBC2009">Daniele Micciancio, Oded Regev [http://www.cs.tau.ac.il/~odedr/papers/pqc.pdf Lattice-based Cryptography] {{Webarchive|url=https://web.archive.org/web/20110723090945/http://www.cs.tau.ac.il/~odedr/papers/pqc.pdf |date=2011-07-23 }}. In ''POST-QUANTUM CRYPTOGRAPHY'', 2009.</ref> आदर्श जालक के आधार पर क्रिप्टोग्राफ़िक हैश फ़ंक्शन के निम्नलिखित एल्गोरिथम को परिभाषित किया गया है:


* 'पैरामीटर:' पूर्णांक <math> q, n, m, d </math> साथ <math> n \mid m </math>, और सदिश एफ <math> \in \mathbb{Z}^n </math>.
* '''पैरामीटर:''' पूर्णांक <math> q, n, m, d </math> साथ <math> n \mid m </math>, और सदिश एफ <math> \in \mathbb{Z}^n </math>.
* चाबी: <math> m/n </math> वैक्टर <math> a_1, \ldots , a_{m/n} </math> स्वतंत्र रूप से और समान रूप से यादृच्छिक रूप से चुना गया <math> \mathbb{Z}_q^n </math>.
* '''की:''' <math> m/n </math> वैक्टर <math> a_1, \ldots , a_{m/n} </math> स्वतंत्र रूप से और समान रूप से यादृच्छिक रूप से <math> \mathbb{Z}_q^n </math>चुना गया।
* हैश फंकशन:  <math> f_A : \lbrace 0, \ldots , d-1 \rbrace ^m \longrightarrow \mathbb{Z}_q^n </math> द्वारा दिए गए <math> f_A(y)= [F \ast a_1 | \ldots | F \ast a_{m/n}]y \bmod \ q </math>.
* '''हैश फ़ंक्शन:''' <math> f_A : \lbrace 0, \ldots , d-1 \rbrace ^m \longrightarrow \mathbb{Z}_q^n </math> द्वारा दिए गए <math> f_A(y)= [F \ast a_1 | \ldots | F \ast a_{m/n}]y \bmod \ q </math>.


यहाँ <math> n,m,q,d </math> पैरामीटर हैं, f एक सदिश है <math> \mathbb{Z}^n </math> और <math> A </math> संरचित ब्लॉकों वाला एक ब्लॉक-मैट्रिक्स है <math> A^{(i)} = F \ast a^{(i)}</math>.
यहाँ <math> n,m,q,d </math> पैरामीटर हैं, f<math> \mathbb{Z}^n </math> में एक सदिश है और <math> A </math> संरचित ब्लॉकों वाला एक ब्लॉक-मैट्रिक्स <math> A^{(i)} = F \ast a^{(i)}</math>है।


में लघु वैक्टर ढूँढना <math> \Lambda_q^\perp ([F \ast a_1 | \ldots | F \ast a_{m/n}])</math> औसतन (यहां तक ​​​​कि केवल उलटा बहुपद के साथ भी
औसत रूप से <math> \Lambda_q^\perp ([F \ast a_1 | \ldots | F \ast a_{m/n}])</math> में छोटे वैक्टर ढूँढना (यहां तक ​​कि केवल व्युत्क्रम बहुपद संभाव्यता के साथ) आदर्श जाली पर सबसे खराब स्थिति में विभिन्न जाली समस्याओं (जैसे अनुमानित SVP और SIVP) को हल करना उतना ही कठिन है, परंतु सदिश 'f' निम्नलिखित दो गुणों को संतुष्ट करता हो:
संभाव्यता) सबसे खराब स्थिति में विभिन्न जालक समस्याओं (जैसे अनुमानित जालक समस्या और SIVP) को हल करने जितना कठिन है
* किसी भी दो इकाई वैक्टर 'यू', 'वी' के लिए, सदिश '''[F∗u]v''' छोटा (कहते हैं, बहुपद <math> n </math>, प्रायः <math> O(\sqrt{n}))</math> मानदंड है।
आदर्श जालक पर स्थिति, बशर्ते सदिश 'f' निम्नलिखित दो गुणों को संतुष्ट करता हो:
* बहुपद <math> f(x) = x^n+f_n x^{n-1}+\cdots+f_1 \in \mathbb{Z}[x] </math> पूर्णांकों पर अलघुकरणीय बहुपद है, अर्थात, यह छोटी डिग्री के पूर्णांक बहुपदों के गुणनफल में कारक नहीं है।
* किसी भी दो इकाई वैक्टर 'यू', 'वी' के लिए, सदिश '[F∗u]v' छोटा है (कहते हैं, बहुपद <math> n </math>, आम तौर पर <math> O(\sqrt{n}))</math> मानदंड।
* बहुपद <math> f(x) = x^n+f_n x^{n-1}+\cdots+f_1 \in \mathbb{Z}[x] </math> पूर्णांकों पर इरेड्यूसिबल बहुपद है, अर्थात, यह छोटी डिग्री के पूर्णांक बहुपदों के गुणनफल में कारक नहीं है।


पहली संपत्ति सदिश द्वारा संतुष्ट है <math> \mathbf{F} = (-1,0, \ldots ,0) </math> [[ परिचालित मैट्रिक्स ]] के अनुरूप,
पहला गुण सदिश <math> \mathbf{F} = (-1,0, \ldots ,0) </math> द्वारा संतुष्ट है [[ परिचालित मैट्रिक्स |परिचालित मैट्रिक्स]] के अनुरूप, क्योंकि [F∗u]v के सभी निर्देशांक 1 से घिरे हैं, और इसलिए <math> \lVert [\textbf{F} \ast \textbf{u}]\textbf{v} \rVert \leq{\sqrt{n}}  </math> है। हालाँकि, बहुपद <math> x^n-1  </math> तदनुसार <math> \mathbf{f} = (-1,0, \ldots ,0) </math> अलघुकरणीय बहुपद नहीं है क्योंकि यह क्रमगुणितअ  <math> (x-1)(x^{n-1}+x^{n-2}+\cdots+ x + 1)</math>है, और यही कारण है कि टक्करों को कुशलता से पाया जा सकता है। इसलिए, <math> \mathbf{f} = (-1,0, \ldots ,0) </math> टक्कर प्रतिरोध क्रिप्टोग्राफ़िक हैश फ़ंक्शन प्राप्त करने के लिए एक अच्छा विकल्प नहीं है, लेकिन कई अन्य विकल्प संभव हैं। उदाहरण के लिए, f के कुछ विकल्प जिसके लिए दोनों गुण संतुष्ट (और इसलिए, सबसे खराब स्थिति वाली सुरक्षा गारंटी के साथ टकराव प्रतिरोध क्रिप्टोग्राफ़िक हैश फ़ंक्शन का परिणाम है) हैं
क्योंकि [F∗u]v के सभी निर्देशांक 1 से घिरे हैं, और इसलिए <math> \lVert [\textbf{F} \ast \textbf{u}]\textbf{v} \rVert \leq{\sqrt{n}}  </math>. हालाँकि, बहुपद <math> x^n-1  </math> तदनुसार <math> \mathbf{f} = (-1,0, \ldots ,0) </math> इर्रिड्यूसिबल बहुपद नहीं है क्योंकि यह कारक है <math> (x-1)(x^{n-1}+x^{n-2}+\cdots+ x + 1)</math>, और यही कारण है कि टक्करों को कुशलता से पाया जा सकता है। इसलिए, <math> \mathbf{f} = (-1,0, \ldots ,0) </math> टक्कर प्रतिरोध क्रिप्टोग्राफ़िक हैश फ़ंक्शन प्राप्त करने के लिए एक अच्छा विकल्प नहीं है, लेकिन कई अन्य विकल्प संभव हैं। उदाहरण के लिए, f के कुछ विकल्प जिसके लिए दोनों गुण संतुष्ट हैं (और इसलिए, सबसे खराब स्थिति वाली सुरक्षा गारंटी के साथ टकराव प्रतिरोध क्रिप्टोग्राफ़िक हैश फ़ंक्शन का परिणाम है) हैं
* <math> \mathbf{f} = (1, \ldots ,1) \in \mathbb{Z}^n </math> जहाँ <math> n + 1 </math> अभाज्य है, और
* <math> \mathbf{f} = (1, \ldots ,1) \in \mathbb{Z}^n </math> कहाँ <math> n + 1 </math> प्रमुख है, और
* <math> \mathbf{f} = (1,0, \ldots ,0) \in \mathbb{Z}^n </math> के लिए <math> n </math> की 2 घात के बराबर।
* <math> \mathbf{f} = (1,0, \ldots ,0) \in \mathbb{Z}^n </math> के लिए <math> n </math> 2 की शक्ति के बराबर।


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


आदर्श (जैसे, चक्रीय) जालक में सबसे छोटे सदिश को अनुमानित करने की जटिलता के आधार पर डिजिटल हस्ताक्षरों का उनका सीधा निर्माण।<ref name="MicLyubAsympt2008"/>  हुबाशेव्स्की और मिचियानसियो की योजना<ref name="MicLyubAsympt2008"/>आदर्श जालक के आधार पर सबसे खराब स्थिति वाली सुरक्षा गारंटी है और यह अब तक ज्ञात सबसे विषम रूप से कुशल निर्माण है, जो हस्ताक्षर पीढ़ी और सत्यापन एल्गोरिदम प्रदान करता है जो लगभग [[रैखिक समय]] में चलता है।<ref name="MicRegLBC2009"/>
आदर्श (जैसे, चक्रीय) जालक में सबसे छोटे सदिश को अनुमानित करने की जटिलता के आधार पर डिजिटल हस्ताक्षरों का उनका सीधा निर्माण होता है।<ref name="MicLyubAsympt2008"/>  हुबाशेव्स्की और मिचियानसियो की योजना<ref name="MicLyubAsympt2008"/>आदर्श जालक के आधार पर सबसे खराब स्थिति वाली सुरक्षा गारंटी है और यह अब तक ज्ञात सबसे विषम रूप से कुशल निर्माण है, जो हस्ताक्षर पीढ़ी और सत्यापन एल्गोरिदम प्रदान करता है जो लगभग [[रैखिक समय]] में चलता है।<ref name="MicRegLBC2009"/>


उनके काम द्वारा उठाई गई मुख्य खुली समस्याओं में से एक समान दक्षता के साथ एक बार के हस्ताक्षर का निर्माण कर रही है, लेकिन सन्निकटन धारणा की कमजोर कठोरता पर आधारित है। उदाहरण के लिए, जालक समस्या का अनुमान लगाने की कठोरता के आधार पर सुरक्षा के साथ एक बार का हस्ताक्षर प्रदान करना बहुत अच्छा होगा | सबसे छोटी सदिश समस्या (एसवीपी) (आदर्श जालक में) के एक कारक के भीतर <math> \tilde{O}(n) </math>.<ref name="MicLyubAsympt2008"/>
उनके काम द्वारा उठाई गई मुख्य खुली समस्याओं में से एक समान दक्षता के साथ एक बार के हस्ताक्षर का निर्माण कर रही है, लेकिन सन्निकटन धारणा की कमजोर कठोरता पर आधारित है।उदाहरण के लिए,<math> \tilde{O}(n) </math> के एक कारक के भीतर शॉर्टेस्ट वेक्टर प्रॉब्लम (एसवीपी) (आदर्श जालक में) को अनुमानित करने की कठोरता के आधार पर सुरक्षा के साथ एक बार का हस्ताक्षर प्रदान करना बहुत अच्छा होगा।<ref name="MicLyubAsympt2008"/>


उनका निर्माण एक बार के हस्ताक्षर (यानी हस्ताक्षर जो एक संदेश को सुरक्षित रूप से हस्ताक्षर करने की अनुमति देता है) से सामान्य हस्ताक्षर योजनाओं के मानक परिवर्तन पर आधारित है, साथ में जालक आधारित एक बार के हस्ताक्षर के एक उपन्यास निर्माण के साथ जिसकी सुरक्षा अंततः आधारित है वलय (गणित) में आइडियल (वलय थ्योरी) के अनुरूप सभी जालक में जालक समस्या का अनुमान लगाने की सबसे खराब स्थिति <math> \mathbb{Z}[x]/\langle f \rangle </math> किसी भी अलघुकरणीय बहुपद के लिए <math> f </math>.
उनका निर्माण एक बार के हस्ताक्षर (यानी हस्ताक्षर जो एक संदेश पर सुरक्षित रूप से हस्ताक्षर करने की अनुमति देता है) से सामान्य हस्ताक्षर योजनाओं के मानक परिवर्तन पर आधारित है, साथ में जालक आधारित एक बार के हस्ताक्षर के एक नवीन निर्माण के साथ जिसकी सुरक्षा अंततः किसी भी अलघुकरणीय बहुपद <math> f </math> के लिए वलय <math> \mathbb{Z}[x]/\langle f \rangle </math> में आदर्शों के अनुरूप सभी जालक में सबसे कम वेक्टर का अनुमान लगाने की सबसे खराब स्थिति की कठोरता पर आधारित है।


की-जनरेशन एल्गोरिथम:
'''की-जनरेशन एल्गोरिथम:'''''इनपुट'': <math> 1^n</math>, अलघुकरणीय बहुपद <math> f \in \mathbb{Z} </math> , <math> n</math> डिग्री का।
''इनपुट'': <math> 1^n</math>, अलघुकरणीय बहुपद <math> f \in \mathbb{Z} </math> डिग्री का <math> n</math>.
# समुच्चय <math> p \longleftarrow (\varphi n)^3 </math>, <math> m \longleftarrow \lceil \log n \rceil </math>, <math> R \longleftarrow \mathbb{Z}_p[x]/\langle f \rangle </math>
# तय करना <math> p \longleftarrow (\varphi n)^3 </math>, <math> m \longleftarrow \lceil \log n \rceil </math>, <math> R \longleftarrow \mathbb{Z}_p[x]/\langle f \rangle </math>
# सभी सकारात्मक के लिए <math> i </math>, माना सेट <math> DK_i </math> और <math> DL_i </math> के रूप में परिभाषित किया जाना चाहिए:
# सभी सकारात्मक के लिए <math> i </math>, समुच्चय करते हैं <math> DK_i </math> और <math> DL_i </math> के रूप में परिभाषित किया जाना चाहिए:
:<math> DK_i  = \lbrace \hat{y} \in R^m </math> ऐसा है कि <math> \lVert \hat{y} \rVert_\infty \leq 5ip^{1/m} \rbrace </math>
:<math> DK_i  = \lbrace \hat{y} \in R^m </math> ऐसा है कि <math> \lVert \hat{y} \rVert_\infty \leq 5ip^{1/m} \rbrace </math>
:<math> DL_i  = \lbrace \hat{y} \in R^m </math> ऐसा है कि <math>\lVert \hat{y} \rVert_\infty \leq 5in \varphi p^{1/m} \rbrace </math>
:<math> DL_i  = \lbrace \hat{y} \in R^m </math> ऐसा है कि <math>\lVert \hat{y} \rVert_\infty \leq 5in \varphi p^{1/m} \rbrace </math>
# समान रूप से यादृच्छिक चुनें <math> h \in \mathcal{H}_{R,m} </math>
# समान रूप से यादृच्छिक <math> h \in \mathcal{H}_{R,m} </math> चुनें
# समान रूप से यादृच्छिक स्ट्वलय चुनें <math> r \in \lbrace 0, 1 \rbrace^{\lfloor \log^2n \rfloor} </math>
# समान रूप से यादृच्छिक स्ट्रिंग <math> r \in \lbrace 0, 1 \rbrace^{\lfloor \log^2n \rfloor} </math> चुनें
# अगर <math> r = 0^{\lfloor \log^2n \rfloor} </math> तब
# '''इफ''' <math> r = 0^{\lfloor \log^2n \rfloor} </math> '''देन'''
# तय करना <math> j = \lfloor \log^2n \rfloor </math>
# सेट <math> j = \lfloor \log^2n \rfloor </math>
# अन्य
# '''एल्स'''
# तय करना <math> j </math> स्ट्वलय में पहले 1 की स्थिति के लिए <math> r </math>
# सेट <math> j </math> स्ट्रिंग <math> r </math> में पहले 1 की स्थिति के लिए
# अगर अंत
# '''एन्ड इफ'''
# चुनना <math> \hat{k} , \hat{l}</math> स्वतंत्र रूप से और समान रूप से यादृच्छिक रूप से <math> DK_j </math> और <math> DL_j </math> क्रमश:
# <math> \hat{k} , \hat{l}</math> स्वतंत्र रूप से और समान रूप से यादृच्छिक रूप से <math> DK_j </math> और <math> DL_j </math> क्रमश: चुनें
# हस्ताक्षर कुंजी: <math> (\hat{k} , \hat{l})</math>. सत्यापन कुंजी: <math> (h,h(\hat{k}) , h(\hat{l})) </math>
# हस्ताक्षर कुंजी: <math> (\hat{k} , \hat{l})</math>. सत्यापन कुंजी: <math> (h,h(\hat{k}) , h(\hat{l})) </math>
हस्ताक्षर एल्गोरिथ्म:
'''हस्ताक्षर एल्गोरिथ्म:'''


''इनपुट:'' संदेश <math> z \in R </math> ऐसा है कि <math> \lVert z \rVert_\infty \leq 1 </math>; हस्ताक्षर कुंजी <math> (\hat{k} , \hat{l})</math>
''इनपुट:'' संदेश <math> z \in R </math> ऐसा है कि <math> \lVert z \rVert_\infty \leq 1 </math>; हस्ताक्षर कुंजी <math> (\hat{k} , \hat{l})</math>
आउटपुट: <math> \hat{s} \longleftarrow \hat{k}z + \hat{l} </math>
आउटपुट: <math> \hat{s} \longleftarrow \hat{k}z + \hat{l} </math>
सत्यापन एल्गोरिथम:
 
'''सत्यापन एल्गोरिथम:'''


''इनपुट:'' संदेश <math> z </math>; हस्ताक्षर <math> \hat{s} </math>; सत्यापन कुंजी <math> (h,h(\hat{k}) , h(\hat{l})) </math>
''इनपुट:'' संदेश <math> z </math>; हस्ताक्षर <math> \hat{s} </math>; सत्यापन कुंजी <math> (h,h(\hat{k}) , h(\hat{l})) </math>
आउटपुट: "स्वीकार करें", यदि <math> \lVert \hat{s} \rVert_\infty \leq 10 \varphi p^{1/m}n \log^2n </math> और <math> \hat{s} = \hat{k}z + \hat{l} </math>
 
"अस्वीकार", अन्यथा।
आउटपुट: "ACCEPT", इफ <math> \lVert \hat{s} \rVert_\infty \leq 10 \varphi p^{1/m}n \log^2n </math> और <math> \hat{s} = \hat{k}z + \hat{l} </math>अन्यथा, "REJECT"


=== स्विफ्ट हैश फ़ंक्शन ===
=== स्विफ्ट हैश फ़ंक्शन ===
क्रिप्टोग्राफ़िक हैश फ़ंक्शन काफी कुशल है और इसमें एसिम्प्टोटिक रूप से गणना की जा सकती है <math> \tilde{O}(m) </math> [[जटिल संख्या]]ओं पर फास्ट फूरियर ट्रांसफॉर्म | फास्ट फूरियर ट्रांसफॉर्म (FFT) का उपयोग करते हुए समय। हालाँकि, व्यवहार में, यह एक पर्याप्त उपरि वहन करता है। Micciancio और Regev द्वारा परिभाषित क्रिप्टोग्राफ़िक हैश फ़ंक्शन का [[SWIFFT]] परिवार<ref name="MicRegLBC2009"/>अनिवार्य रूप से फास्ट फूरियर ट्रांसफॉर्म|(FFT) का उपयोग करके उपरोक्त क्रिप्टोग्राफ़िक हैश फ़ंक्शन का एक अत्यधिक अनुकूलित संस्करण है <math> \mathbb{Z}_q</math>. सदिश f पर समुच्चय है <math> (1, 0,\dots , 0) \in \mathbb{Z}^n </math> के लिए <math> n </math> 2 की शक्ति के बराबर, ताकि संबंधित बहुपद <math> x^n + 1 </math> इर्रेड्यूसिबल बहुपद है।
क्रिप्टोग्राफ़िक हैश फ़ंक्शन काफी कुशल है और [[जटिल संख्या]]ओं पर फास्ट फूरियर ट्रांसफॉर्म (FFT) का उपयोग करते हुए <math> \tilde{O}(m) </math> समय में असम्बद्ध रूप से गणना की जा सकती है। हालाँकि, व्यवहार में, यह एक पर्याप्त उपरिवहन करता है। मिकिसियानियो और रेगेव द्वारा परिभाषित हैश फ़ंक्शन का [[SWIFFT|एस डब्ल्यू आई एफ एफ टी]] परिवार<ref name="MicRegLBC2009"/>अनिवार्य रूप से <math> \mathbb{Z}_q</math> में फास्ट फूरियर ट्रांसफॉर्म (FFT) का उपयोग करके उपरोक्त हैश फ़ंक्शन का एक अत्यधिक अनुकूलित संस्करण है। सदिश f पर समुच्चय <math> (1, 0,\dots , 0) \in \mathbb{Z}^n </math> <math> n </math> के लिए 2 की घात के बराबर है, ताकि संबंधित बहुपद <math> x^n + 1 </math> अलघुकरणीय बहुपद है। माना <math> q </math> एक [[अभाज्य संख्या]] हो जैसे कि <math>2n</math> विभाजित <math> q-1 </math>, और माना <math> \textbf{W} \in \mathbb{Z}^{n \times n}_{q}</math> एक [[उलटा मैट्रिक्स|व्युत्क्रमणीय मैट्रिक्स]] ओवर होने दें <math> \mathbb{Z}_q </math> बाद में चुना जाना है। एस डब्ल्यू आई एफ एफ टी क्रिप्टोग्राफ़िक हैश फ़ंक्शन एक कुंजी <math>\tilde{a}^{(1)} , \ldots , \tilde{a}^{(m/n)}</math>को मैप करता है <math> m/n </math> को मिलाकर  सदिश समान रूप से चुने गए <math> \mathbb{Z}^{n}_{q} </math> और एक इनपुट <math> y \in \lbrace 0, \ldots , d-1 \rbrace^m </math> को <math> \textbf{W}^{\centerdot} f_A(y) \bmod \ q </math> जहाँ<math> \textbf{A} = [ \textbf{F} \ast \alpha^{(1)}, \ldots, \textbf{F} \ast \alpha^{(m/n)} ] </math> पहले की तरह और <math> \alpha^{(i)} = \textbf{W}^{-1} \tilde{a}^{(i)} \bmod q </math> है। व्युत्क्रमणीय मैट्रिक्स द्वारा गुणन  <math> \textbf{W}^{-1} </math> मैप एक समान रूप से चुने गए <math> \tilde{a} \in  \mathbb{Z}^n_q </math> एक समान रूप से चुने गए के लिए <math> \alpha \in  \mathbb{Z}^{n}_q </math>है। इसके अतिरिक्त, <math> \textbf{W}^{\centerdot} f_A(y)=\textbf{W}^{\centerdot} f_A(y') \pmod q </math> अगर और केवल अगर <math> f_A(y)= f_A(y') \pmod q </math>है। साथ में, ये दो तथ्य स्थापित करते हैं कि एस डब्ल्यू आई एफ एफ टी में टकराव खोजना अंतर्निहित आदर्श जालक फंक्शन <math> f_A </math> में [[हैश टक्कर|टकराव]] खोजने के बराबर है, और एस डब्ल्यू आई एफ एफ टी की दावा किया गया टक्कर प्रतिरोध गुण आदर्श जालक पर सबसे खराब स्थिति वाली जालक समस्याओं के संबंध में समर्थित है।
होने देना <math> q </math> एक [[अभाज्य संख्या]] हो जैसे कि <math>2n</math> विभाजित <math> q-1 </math>, और जाने <math> \textbf{W} \in \mathbb{Z}^{n \times n}_{q}</math> एक [[उलटा मैट्रिक्स]] खत्म हो <math> \mathbb{Z}_q </math> बाद में चुना जाना है। SWIFFT क्रिप्टोग्राफ़िक हैश फ़ंक्शन एक कुंजी को मैप करता है <math>\tilde{a}^{(1)} , \ldots , \tilde{a}^{(m/n)}</math> को मिलाकर <math> m/n </math> सदिश समान रूप से चुने गए <math> \mathbb{Z}^{n}_{q} </math> और एक इनपुट <math> y \in \lbrace 0, \ldots , d-1 \rbrace^m </math> को <math> \textbf{W}^{\centerdot} f_A(y) \bmod \ q </math> कहाँ <math> \textbf{A} = [ \textbf{F} \ast \alpha^{(1)}, \ldots, \textbf{F} \ast \alpha^{(m/n)} ] </math> पहले की तरह है और <math> \alpha^{(i)} = \textbf{W}^{-1} \tilde{a}^{(i)} \bmod q </math>.
व्युत्क्रमणीय मैट्रिक्स द्वारा गुणन  <math> \textbf{W}^{-1} </math> नक्शे एक समान रूप से चुने गए <math> \tilde{a} \in  \mathbb{Z}^n_q </math> एक समान रूप से चुने गए के लिए <math> \alpha \in  \mathbb{Z}^{n}_q </math>. इसके अतिरिक्त, <math> \textbf{W}^{\centerdot} f_A(y)=\textbf{W}^{\centerdot} f_A(y') \pmod q </math> अगर और केवल अगर <math> f_A(y)= f_A(y') \pmod q </math>.
साथ में, ये दो तथ्य स्थापित करते हैं कि SWIFFT में टकराव खोजना अंतर्निहित आदर्श जालक कार्य में [[हैश टक्कर]] खोजने के बराबर है <math> f_A </math>, और SWIFFT की दावा की गई टक्कर प्रतिरोध संपत्ति आदर्श जालक पर सबसे खराब स्थिति वाली जालक समस्याओं के कनेक्शन द्वारा समर्थित है।


SWIFFT हैश फ़ंक्शन का एल्गोरिथ्म है:
एस डब्ल्यू आई एफ एफ टी हैश फ़ंक्शन का एल्गोरिथ्म है:
* 'पैरामीटर:' पूर्णांक <math> n, m, q, d </math> ऐसा है कि <math> n </math> 2 की शक्ति है, <math> q </math> प्रधान है, <math> 2n \mid (q-1)</math> और <math> n \mid m </math>.
* '''पैरामीटर:''' पूर्णांक <math> n, m, q, d </math> ऐसा है कि <math> n </math> 2 की घात है, <math> q </math> अभाज्य है, <math> 2n \mid (q-1)</math> और <math> n \mid m </math>.
* चाबी: <math> m/n </math> वैक्टर <math> \tilde{a}_1, \ldots , \tilde{a}_{m/n} </math> स्वतंत्र रूप से और समान रूप से यादृच्छिक रूप से चुना गया <math> \mathbb{Z}_q^n </math>.
* '''की:''' <math> m/n </math> वैक्टर <math> \tilde{a}_1, \ldots , \tilde{a}_{m/n} </math> स्वतंत्र रूप से और समान रूप से यादृच्छिक रूप से चुना गया <math> \mathbb{Z}_q^n </math>.
* इनपुट: <math> m/n </math> वैक्टर <math> y^{(1)}, \dots , y^{(m/n)} \in \lbrace 0, \dots , d-1 \rbrace ^n </math>.
* '''इनपुट:''' <math> m/n </math> सदिश <math> y^{(1)}, \dots , y^{(m/n)} \in \lbrace 0, \dots , d-1 \rbrace ^n </math>.
* आउटपुट: सदिश <math> \sum_{i=1}^{m/n} \tilde{a}^{(i)} \odot (\textbf{W}y^{(i)}) \in \mathbb{Z}_q^n </math>, कहाँ <math> \odot </math> घटक-वार सदिश उत्पाद है।
* '''आउटपुट:''' सदिश <math> \sum_{i=1}^{m/n} \tilde{a}^{(i)} \odot (\textbf{W}y^{(i)}) \in \mathbb{Z}_q^n </math>, जहाँ <math> \odot </math> घटक-वार सदिश उत्पाद है।


===त्रुटियों के साथ सीखना (एलडब्ल्यूई)===
===त्रुटियों के साथ सीखना (एलडब्ल्यूई)===


==== त्रुटियों के साथ वलय लर्निंग|रिंग-वामपंथी ====
==== वलय-एलडब्ल्यूई ====
त्रुटियों के साथ सीखना | त्रुटियों के साथ सीखना (एलडब्ल्यूई) समस्या को सबसे खराब स्थिति वाली जालक समस्याओं के रूप में कठिन दिखाया गया है और कई क्रिप्टोग्राफ़िक अनुप्रयोगों के लिए नींव के रूप में कार्य किया है। हालाँकि, ये अनुप्रयोग त्रुटियों के साथ सीखने के उपयोग में अंतर्निहित द्विघात ओवरहेड के कारण अक्षम हैं। त्रुटियों के अनुप्रयोगों के साथ वास्तव में कुशल सीखने के लिए, हुबाशेवस्की, पिकर्ट और रेगेव<ref name="LyubPeiReg2010"/>रिंगों की एक विस्तृत श्रेणी में त्रुटियों की समस्या के साथ सीखने के एक उपयुक्त संस्करण को परिभाषित किया और इन रिंगों में आदर्श जालक पर सबसे खराब स्थिति की धारणाओं के तहत इसकी कठोरता को साबित किया। उन्होंने अपने लर्निंग विद एरर्स वर्जन रिंग-एलडब्ल्यूई का नाम दिया।
लर्निंग विद एरर्स (एलडब्ल्यूई) समस्या को सबसे खराब स्थिति वाली जालक समस्याओं के रूप में कठिन दिखाया गया है और कई क्रिप्टोग्राफ़िक अनुप्रयोगों के लिए नींव के रूप में कार्य किया है। हालाँकि, ये अनुप्रयोग त्रुटियों के साथ सीखने के उपयोग में अंतर्निहित द्विघात उपरिव्यय के कारण अक्षम हैं। त्रुटियों के अनुप्रयोगों के साथ सचमुच में कुशल रूप सीखने के लिए, हुबाशेवस्की, पिकर्ट और रेगेव<ref name="LyubPeiReg2010"/>वलयों की एक विस्तृत श्रेणी में त्रुटियों की समस्या के साथ सीखने के एक उपयुक्त संस्करण को परिभाषित किया और इन वलयों में आदर्श जालक पर सबसे खराब स्थिति की धारणाओं के तहत इसकी कठोरता को प्रमाणित किया। उन्होंने अपने लर्निंग विद एरर्स वर्जन रिंग-एलडब्ल्यूई का नाम दिया।


होने देना <math> f(x)= x^n+1 \in \mathbb{Z}[x] </math>, जहां सुरक्षा पैरामीटर <math> n </math> 2 की शक्ति है, बनाना <math> f(x) </math> तर्कों पर अप्रासंगिक। (यह खासतौर पर <math> f(x) </math> [[साइक्लोटोमिक बहुपद]]ों के परिवार से आता है, जो इस काम में एक विशेष भूमिका निभाते हैं)।
माना <math> f(x)= x^n+1 \in \mathbb{Z}[x] </math>, जहां सुरक्षा पैरामीटर <math> n </math> 2 की घात है, परिमेय <math> f(x) </math> को अप्रासंगिक बनाना। (यह विशेष <math> f(x) </math> [[साइक्लोटोमिक बहुपद|साइक्लोटोमिक बहुपदों]] के परिवार से आता है, जो इस काम में एक विशेष भूमिका निभाते हैं)।


होने देना <math> R= \mathbb{Z}[x]/\langle f(x) \rangle </math> पूर्णांक बहुपद मॉड्यूलो की वलय बनें <math> f(x) </math>. घटक <math> R </math> (यानी, अवशेषों का रूप <math> f(x) </math>) आमतौर पर डिग्री से कम के पूर्णांक बहुपदों द्वारा दर्शाए जाते हैं <math> n </math>. होने देना <math> q \equiv 1 \bmod 2n </math> एक पर्याप्त रूप से बड़े सार्वजनिक प्रमुख मॉड्यूलस बनें (एक बहुपद से घिरा हुआ <math> n </math>), और जाने <math> R_q = R/\langle q \rangle = \mathbb{Z}_q[x]/\langle f(x) \rangle </math> दोनों पूर्णांक बहुपद मॉड्यूलो की वलय बनें <math> f(x) </math> और <math> q </math>. घटक <math> R_q </math> से कम डिग्री वाले बहुपदों द्वारा प्रदर्शित किया जा सकता है <math> n </math>-जिसके गुणांक से हैं <math> \lbrace 0 , \dots , q-1 \rbrace </math>.
माना <math> R= \mathbb{Z}[x]/\langle f(x) \rangle </math> पूर्णांक बहुपद मॉड्यूलो <math> f(x) </math>का वलय हो। <math> R </math> के घटक  (यानी, अवशेषों मॉड्यूलो <math> f(x) </math> का रूप ) प्रायः <math> n </math> से कम डिग्री के पूर्णांक बहुपदों द्वारा दर्शाए जाते हैं। माना <math> q \equiv 1 \bmod 2n </math> एक पर्याप्त रूप से बड़े सार्वजनिक प्रमुख मॉड्यूलस बनें (<math> n </math> में एक बहुपद से घिरा हुआ), और माना  <math> R_q = R/\langle q \rangle = \mathbb{Z}_q[x]/\langle f(x) \rangle </math> दोनों पूर्णांक बहुपद मॉड्यूलो <math> f(x) </math> और <math> q </math> की वलय बनें। घटक <math> R_q </math> <math> n </math> डिग्री वाले बहुपदों द्वारा प्रदर्शित किया जा सकता है -जिसके गुणांक <math> \lbrace 0 , \dots , q-1 \rbrace </math> हैं।


ऊपर वर्णित वलय में, आर-एलडब्ल्यूई समस्या का वर्णन इस प्रकार किया जा सकता है।
ऊपर वर्णित वलय में, आर-एलडब्ल्यूई समस्या का वर्णन इस प्रकार किया जा सकता है।माना <math> s = s(x) \in R_q </math> एक समान रूप से यादृच्छिक वलय तत्व हो, जिसे गुप्त रखा जाता है। एलडब्ल्यूई के अनुरूप, हमलावर का लक्ष्य मनमाने ढंग से कई (स्वतंत्र) 'यादृच्छिक शोर वलय समीकरणों' को सचमुच में एक समान से अलग करना है। अधिक विशेष रूप से, शोर समीकरण <math> (a, b \approx a \centerdot s) \in R_q \times R_q </math> रूप के होते हैं, जहां a समान रूप से यादृच्छिक है और उत्पाद <math> a \centerdot s </math> कुछ 'छोटे' यादृच्छिक त्रुटि शब्द से परेशान है, जिसे <math> R </math> पर एक निश्चित वितरण से चुना गया है।
होने देना <math> s = s(x) \in R_q </math> एक समान रूप से यादृच्छिक वलय तत्व हो, जिसे गुप्त रखा जाता है। मानक वामपंथी उग्रवाद के अनुरूप, हमलावर का लक्ष्य मनमाने ढंग से कई (स्वतंत्र) 'यादृच्छिक शोर वलय समीकरणों' को वास्तव में एक समान से अलग करना है। अधिक विशेष रूप से, शोर समीकरण रूप के होते हैं <math> (a, b \approx a \centerdot s) \in R_q \times R_q </math>, जहां एक समान रूप से यादृच्छिक और उत्पाद है <math> a \centerdot s </math> एक निश्चित वितरण से चुने गए कुछ 'छोटे' यादृच्छिक त्रुटि शब्द से परेशान है <math> R </math>.


उन्होंने आदर्श जालक पर अनुमानित जालक समस्या (सबसे खराब स्थिति में) से एक मात्रा में कमी दी <math> R </math> रिंग-एलडब्ल्यूई के खोज संस्करण में, जहां लक्ष्य रहस्य को पुनर्प्राप्त करना है <math> s \in R_q </math> (उच्च संभावना के साथ, किसी के लिए <math> s </math>) मनमाने ढंग से कई शोर वाले उत्पादों से। यह परिणाम सामान्य जालक के लिए रेगेव की पुनरावृत्त मात्रा में कमी की सामान्य रूपरेखा का अनुसरण करता है,<ref name="Reg2010">Oded Regev. [http://www.cs.tau.ac.il/~odedr/papers/qcrypto.pdf  On lattices, learning with errors, random linear codes, and cryptography  ] {{Webarchive|url=https://web.archive.org/web/20101206195712/http://www.cs.tau.ac.il/~odedr/papers/qcrypto.pdf |date=2010-12-06 }}. In ''Journal of the ACM'', 2009.</ref> लेकिन आदर्श जालक कमी के 'बीजगणितीय' और 'ज्यामितीय' घटकों दोनों में कई नई तकनीकी बाधाओं का परिचय देती हैं। वे<ref name="LyubPeiReg2010"/>  बीजगणितीय संख्या सिद्धांत का उपयोग किया, विशेष रूप से, इन बाधाओं को दूर करने के लिए एक संख्या क्षेत्र के विहित एम्बेडिंग और चीनी शेष प्रमेय। उन्हें निम्नलिखित प्रमेय प्राप्त हुआ:
उन्होंने रिंग-एलडब्ल्यूई के खोज संस्करण में <math> R </math> में आदर्श जालक पर अनुमानित एसवीपी (सबसे खराब स्थिति में) से एक मात्रा में कमी दी, जहां लक्ष्य स्वेच्छतः कई शोर वाले उत्पादों से गुप्त <math> s \in R_q </math> (उच्च संभावना के साथ, किसी भी <math> s </math> के लिए) को पुनर्प्राप्त करना है। यह परिणाम सामान्य जालक के लिए रेगेव की पुनरावृत्त मात्रा में कमी की सामान्य रूपरेखा का अनुसरण करता है,<ref name="Reg2010">Oded Regev. [http://www.cs.tau.ac.il/~odedr/papers/qcrypto.pdf  On lattices, learning with errors, random linear codes, and cryptography  ] {{Webarchive|url=https://web.archive.org/web/20101206195712/http://www.cs.tau.ac.il/~odedr/papers/qcrypto.pdf |date=2010-12-06 }}. In ''Journal of the ACM'', 2009.</ref> लेकिन आदर्श जालक कमी के 'बीजगणितीय' और 'ज्यामितीय' घटकों दोनों में कई नई तकनीकी बाधाओं का परिचय देती हैं। उन्होंने<ref name="LyubPeiReg2010"/>  बीजगणितीय संख्या सिद्धांत का उपयोग किया, विशेष रूप से, इन बाधाओं को दूर करने के लिए एक संख्या क्षेत्र के विहित एम्बेडिंग और चीनी शेष प्रमेय। उन्हें निम्नलिखित प्रमेय प्राप्त हुआ:


प्रमेय चलो <math> K </math> डिग्री का एक मनमाना संख्या क्षेत्र हो <math> n </math>. होने देना <math> \alpha = \alpha (n) \in (0, 1) </math> मनमाना हो, और (तर्कसंगत) पूर्णांक मापांक दें <math> q = q(n) \geq 2 </math> ऐसा हो कि <math> \alpha \centerdot q \geq \omega (\sqrt{\log n}) </math>. से एक संभाव्य बहुपद-समय क्वांटम कमी है <math> K </math>-<math> DGS_\gamma </math> को <math> \mathcal{O}_K </math>- <math> LWE_{q, \Psi \leq \alpha} </math>, कहाँ <math> \gamma = \eta_\epsilon(I) \centerdot \omega(\sqrt{\log n})/\alpha </math>.
'''प्रमेय''' माना <math> K </math> डिग्री <math> n </math> का एक मनमाना संख्या क्षेत्र  हो। माना  <math> \alpha = \alpha (n) \in (0, 1) </math> स्वेच्छतः हो, और (तर्कसंगत) पूर्णांक मापांक <math> q = q(n) \geq 2 </math> दें, ऐसा <math> \alpha \centerdot q \geq \omega (\sqrt{\log n}) </math> हो। <math> K </math>-<math> DGS_\gamma </math> को <math> \mathcal{O}_K </math>- <math> LWE_{q, \Psi \leq \alpha} </math> से एक संभाव्य बहुपद-समय क्वांटम कमी है, जहाँ <math> \gamma = \eta_\epsilon(I) \centerdot \omega(\sqrt{\log n})/\alpha </math> है।


2013 में, गुनेसु, ल्यूबाशेवस्की, और पोप्पलमैन ने वलय लर्निंग विद एरर्स समस्या के आधार पर एक डिजिटल हस्ताक्षर योजना प्रस्तावित की।<ref>{{Cite web|title=Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems|url=https://www.di.ens.fr/~lyubash/papers/signaturechess.pdf|archive-url=https://web.archive.org/web/20140518004537/https://www.di.ens.fr/~lyubash/papers/signaturechess.pdf|access-date = 18 May 2014|archive-date=2014-05-18}}</ref> 2014 में, Peikert ने अपने पेपर, इंटरनेट के लिए जालक क्रिप्टोग्राफी में वलय लर्निंग विथ एरर्स की एक्सचेंज (RLWE-KEX) प्रस्तुत किया।<ref name=":0">{{Cite book|publisher = Springer International Publishing|date = 2014-10-01|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|chapter = Lattice Cryptography for the Internet|citeseerx = 10.1.1.800.4743| s2cid=8123895 }}</ref> इसे सिंह के कार्य द्वारा और विकसित किया गया।<ref>{{Cite journal|title = जाली क्रिप्टोग्राफी का उपयोग कर इंटरनेट के लिए एक व्यावहारिक कुंजी एक्सचेंज|url = http://eprint.iacr.org/2015/138|date = 2015|first = Vikram|last = Singh| journal=Cryptology ePrint Archive }}</ref>
2013 में, गुनेसु, ल्यूबाशेवस्की, और पोप्पलमैन ने वलय लर्निंग विद एरर्स समस्या के आधार पर एक डिजिटल हस्ताक्षर योजना प्रस्तावित की।<ref>{{Cite web|title=Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems|url=https://www.di.ens.fr/~lyubash/papers/signaturechess.pdf|archive-url=https://web.archive.org/web/20140518004537/https://www.di.ens.fr/~lyubash/papers/signaturechess.pdf|access-date = 18 May 2014|archive-date=2014-05-18}}</ref> 2014 में, पैकर्ट ने अपने पेपर," इंटरनेट के लिए जालक क्रिप्टोग्राफी" में वलय लर्निंग विथ एरर्स की एक्सचेंज (आर एल डब्ल्यू इ- के इ एक्स) प्रस्तुत किया।<ref name=":0">{{Cite book|publisher = Springer International Publishing|date = 2014-10-01|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|chapter = Lattice Cryptography for the Internet|citeseerx = 10.1.1.800.4743| s2cid=8123895 }}</ref> इसे सिंह के कार्य द्वारा और विकसित किया गया।<ref>{{Cite journal|title = जाली क्रिप्टोग्राफी का उपयोग कर इंटरनेट के लिए एक व्यावहारिक कुंजी एक्सचेंज|url = http://eprint.iacr.org/2015/138|date = 2015|first = Vikram|last = Singh| journal=Cryptology ePrint Archive }}</ref>


==== आदर्श एलडब्ल्यूई ====
स्टीहले, स्टेनफेल्ड, तनाका और ज़गावा<ref name="stehle2009">
Damien Stehlé, Ron Steinfeld, Keisuke Tanaka and Keita Xagawa.  [http://eprint.iacr.org/2009/285.pdf Efficient public key encryption based on ideal lattices]. In ''Lecture Notes in Computer Science'', 2009.</ref> ने एलडब्ल्यूई समस्या (आदर्श -एलडब्ल्यूई)  के एक संरचित संस्करण को आदर्श जालक में अनुमानित एसवीपी की सबसे खराब स्थिति कठोरता के आधार पर एक कुशल सार्वजनिक कुंजी एन्क्रिप्शन योजना का वर्णन करने के लिए परिभाषित किया। यह पहली सीपीए-सुरक्षित सार्वजनिक कुंजी एन्क्रिप्शन योजना है, जिसकी सुरक्षा सबसे खराब स्थिति वाले उदाहरणों की कठोरता  <math> \tilde{O}(n^2) </math>-आदर्श-एसवीपी उप-घातीय क्वांटम हमलों के खिलाफ पर निर्भर करती है। यह असीमित रूप से इष्टतम दक्षता प्राप्त करता है: सार्वजनिक/निजी कुंजी लंबाई <math> \tilde{O}(n) </math> बिट्स है  और परिशोधित एन्क्रिप्शन/डिक्रिप्शन लागत <math> \tilde{O}(1) </math> बिट है प्रति संदेश बिट संचालन (<math> \tilde{\Omega}(n) </math> बिट्स एक बार में, <math> \tilde{O}(n) </math> लागत पर एन्क्रिप्ट करना)। यहां सुरक्षा धारणा यह है कि <math> \tilde{O}(n^2) </math>-आदर्श-एसवीपी को किसी भी उप-घातीय समय क्वांटम एल्गोरिदम द्वारा हल नहीं किया जा सकता है। यह उल्लेखनीय है कि यह मानक सार्वजनिक-कुंजी क्रिप्टोग्राफ़ी सुरक्षा मान्यताओं से अधिक मजबूत है। दूसरी ओर, अधिकांश सार्वजनिक-कुंजी क्रिप्टोग्राफी के विपरीत, जालक-आधारित क्रिप्टोग्राफी उप-घातीय क्वांटम हमलों के खिलाफ सुरक्षा की अनुमति देती है।


==== आदर्श वामपंथी उग्रवाद ====
सामान्य जालक पर आधारित अधिकांश क्रिप्टो सिस्टम्स लर्निंग विद एरर्स (एलडब्ल्यूई) की औसत-स्थिति की कठोरता पर निर्भर करते हैं। उनकी योजना एलडब्ल्यूई के एक संरचित संस्करण पर आधारित है, जिसे वे आदर्श -एलडब्ल्यूई कहते हैं। प्रतिबंध से लेकर आदर्श जालक तक उत्पन्न होने वाली दो मुख्य कठिनाइयों को दूर करने के लिए उन्हें कुछ तकनीकों को पेश करने की आवश्यकता थी। सबसे पहले, असंरचित जालक पर आधारित पिछली क्रिप्टो प्रणालियाँ रेगेव के सबसे बुरे स्थिति से लेकर औसत स्थिति क्लासिकल रिडक्शन बाउंडेड डिस्टेंस डिकोडिंग समस्या (बीडीडी) से एलडब्ल्यूई तक का उपयोग करती हैं (यह एसवीपी से एलडब्ल्यूई तक क्वांटम रिडक्शन में चिरसम्मत चरण है)। यह कमी मानी गई जालक के असंरचित-पन का फायदा उठाती है, और आदर्श-एलडब्ल्यूई में सम्मिलित संरचित जालक तक ले जाने के लिए प्रतीत नहीं होती है। विशेष रूप से, एलडब्ल्यूई मैट्रिसेस की पंक्तियों की संभाव्य स्वतंत्रता एकल पंक्ति पर विचार करने की अनुमति देती है। दूसरे, पिछले क्रिप्टो सिस्टम में उपयोग किए जाने वाले अन्य घटक, अर्थात् रेगेव की त्रुटियों के साथ सीखने के कम्प्यूटेशनल संस्करण से इसके निर्णायक संस्करण में कमी, आदर्श-एलडब्ल्यूई के लिए भी विफल प्रतीत होती है: यह त्रुटियों के मैट्रिक्स के साथ सीखने के स्तंभों की संभाव्य स्वतंत्रता पर निर्भर करता है। .
चोरी, स्टेनफेल्ड, तनाका और ज़गावा<ref name="stehle2009">
Damien Stehlé, Ron Steinfeld, Keisuke Tanaka and Keita Xagawa.  [http://eprint.iacr.org/2009/285.pdf Efficient public key encryption based on ideal lattices]. In ''Lecture Notes in Computer Science'', 2009.</ref> आदर्श जालक में अनुमानित जालक समस्या की सबसे खराब स्थिति कठोरता के आधार पर एक कुशल सार्वजनिक कुंजी एन्क्रिप्शन योजना का वर्णन करने के लिए LWE समस्या (आदर्श-LWE) के एक संरचित संस्करण को परिभाषित किया। यह पहली सीपीए-सुरक्षित सार्वजनिक कुंजी एन्क्रिप्शन योजना है, जिसकी सुरक्षा सबसे खराब स्थिति वाले उदाहरणों की कठोरता पर निर्भर करती है <math> \tilde{O}(n^2) </math>-आइडियल-एसवीपी उप-घातीय क्वांटम हमलों के खिलाफ। यह असीमित रूप से इष्टतम दक्षता प्राप्त करता है: सार्वजनिक/निजी कुंजी लंबाई है <math> \tilde{O}(n) </math> बिट्स और परिशोधित एन्क्रिप्शन/डिक्रिप्शन लागत है <math> \tilde{O}(1) </math> बिट ऑपरेशंस प्रति संदेश बिट (एन्क्रिप्टिंग <math> \tilde{\Omega}(n) </math> बिट्स एक बार में, एक पर <math> \tilde{O}(n) </math> लागत)। यहां सुरक्षा धारणा यह है कि <math> \tilde{O}(n^2) </math>-आइडियल-एसवीपी को किसी भी उप-घातीय समय क्वांटम एल्गोरिदम द्वारा हल नहीं किया जा सकता है। यह उल्लेखनीय है कि यह मानक सार्वजनिक-कुंजी क्रिप्टोग्राफ़ी सुरक्षा मान्यताओं से अधिक मजबूत है। दूसरी ओर, अधिकांश सार्वजनिक-कुंजी क्रिप्टोग्राफी के विपरीत, जालक-आधारित क्रिप्टोग्राफी उप-घातीय क्वांटम हमलों के खिलाफ सुरक्षा की अनुमति देती है।


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


इन कठिनाइयों को दूर करने के लिए, उन्होंने कटौती के शास्त्रीय कदम से परहेज किया। इसके बजाय, उन्होंने त्रुटियों के साथ सीखने के लिए SIS (औसत-स्थिति टक्कर-ढूंढने की समस्या) से एक नया क्वांटम औसत-केस रिडक्शन बनाने के लिए क्वांटम कदम का उपयोग किया। यह आइडियल-एसआईएस से लेकर आइडियल-एलडब्ल्यूई तक भी काम करता है। वर्स्ट-केस आइडियल-एसवीपी से एवरेज-केस आइडियल-एसआईएस में कमी के साथ संयुक्त, उन्होंने आइडियल-एसवीपी से आइडियल-एलडब्ल्यूई तक क्वांटम कमी प्राप्त की। यह आइडियल-एलडब्ल्यूई के कम्प्यूटेशनल वेरिएंट की कठोरता को दर्शाता है। क्योंकि उन्होंने निर्णयात्मक संस्करण की कठोरता प्राप्त नहीं की, उन्होंने एन्क्रिप्शन के लिए छद्म यादृच्छिक बिट्स प्राप्त करने के लिए एक सामान्य हार्डकोर फ़ंक्शन का उपयोग किया। यही कारण है कि उन्हें जालक समस्या की घातीय कठोरता को मानने की आवश्यकता थी।
=== पूरी तरह से समरूप एन्क्रिप्शन ===
एक पूरी तरह से [[होमोमोर्फिक एन्क्रिप्शन]] (एफएचई) योजना वह है जो पहले डिक्रिप्ट करने की आवश्यकता के बिना एन्क्रिप्टेड डेटा पर गणना करने की अनुमति देती है। रिवेस्ट, एडलमैन और शमीर द्वारा आरएसए के आविष्कार के तुरंत बाद, 1978 में रिवेस्ट, एडलमैन और डर्टौज़ोस<ref>R. Rivest, L. Adleman, and M. Dertouzos. [On data banks and privacy homomorphisms.]. In ''In Foundations of Secure Computation,'' pp. 169–180, 1978.</ref> द्वारा पूरी तरह से होमोमोर्फिक एन्क्रिप्शन योजना के निर्माण की समस्या को सामने रखा गया था। <ref>R. Rivest, A. Shamir, and L. Adleman. [A method for obtaining digital signatures and public-key cryptosystems.]. In ''Comm. of the ACM,''21:2, pages 120–126, 1978.</ref>


=== पूरी तरह से समरूप एन्क्रिप्शन ===
एक एन्क्रिप्शन योजना <math> \varepsilon = (\mathsf{KeyGen}, \mathsf{Encrypt}, \mathsf{Decrypt}, \mathsf{Eval}) </math> में सर्किट <math> \mathcal{C}</math> के लिए समरूपी है अगर, किसी भी सर्किट के लिए <math> C \in \mathcal{C}</math>,
एक पूरी तरह से [[होमोमोर्फिक एन्क्रिप्शन]] (एफएचई) योजना वह है जो पहले डिक्रिप्ट करने की आवश्यकता के बिना एन्क्रिप्टेड डेटा पर गणना करने की अनुमति देती है। पूरी तरह से होमोमोर्फिक एन्क्रिप्शन योजना के निर्माण की समस्या को सबसे पहले रिवेस्ट, एडलमैन और डर्टोज़ोस ने सामने रखा था।<ref>R. Rivest, L. Adleman, and M. Dertouzos. [On data banks and privacy homomorphisms.]. In ''In Foundations of Secure Computation,'' pp. 169–180, 1978.</ref> 1978 में, रिवेस्ट, एडलमैन और शमीर द्वारा [[आरएसए (एल्गोरिदम)]] के आविष्कार के तुरंत बाद।<ref>R. Rivest, A. Shamir, and L. Adleman. [A method for obtaining digital signatures and public-key cryptosystems.]. In ''Comm. of the ACM,''21:2, pages 120–126, 1978.</ref>
एक एन्क्रिप्शन योजना <math> \varepsilon = (\mathsf{KeyGen}, \mathsf{Encrypt}, \mathsf{Decrypt}, \mathsf{Eval}) </math> में सर्किट के लिए होमोमोर्फिक है <math> \mathcal{C}</math> अगर, किसी भी सर्किट के लिए <math> C \in \mathcal{C}</math>,


दिया गया <math>PK, SK \leftarrow \mathsf{KeyGen}(1^\lambda)</math>, <math> y = \mathsf{Encrypt}(PK, x)</math>, और <math>y' = \mathsf{Eval}(PK, C, y)</math>,
दिया गया <math>PK, SK \leftarrow \mathsf{KeyGen}(1^\lambda)</math>, <math> y = \mathsf{Encrypt}(PK, x)</math>, और <math>y' = \mathsf{Eval}(PK, C, y)</math>,
Line 194: Line 185:
यह मानता है <math>\mathsf{Decrypt}(SK, y') = C(x)</math>.
यह मानता है <math>\mathsf{Decrypt}(SK, y') = C(x)</math>.


<math> \varepsilon </math> पूरी तरह से समरूप है अगर यह आकार के सभी सर्किटों के लिए समरूप है <math>\operatorname{poly}(\lambda)</math> कहाँ <math>\lambda</math> योजना का सुरक्षा पैरामीटर है।
<math> \varepsilon </math> पूरी तरह से समरूप है अगर यह आकार <math>\operatorname{poly}(\lambda)</math> के सभी सर्किटों के लिए समरूप है  जहाँ <math>\lambda</math> योजना का सुरक्षा पैरामीटर है।


2009 में, जेंट्री<ref>Craig Gentry. [http://portal.acm.org/citation.cfm?id=1536414.1536440 Fully Homomorphic Encryption Using Ideal Lattices]. In ''the 41st ACM Symposium on Theory of Computing (STOC)'', 2009.</ref> पूरी तरह से होमोमोर्फिक एन्क्रिप्शन योजना के निर्माण की समस्या का पहला समाधान प्रस्तावित किया। उनकी योजना आदर्श जालक पर आधारित थी।
2009 में, जेंट्री<ref>Craig Gentry. [http://portal.acm.org/citation.cfm?id=1536414.1536440 Fully Homomorphic Encryption Using Ideal Lattices]. In ''the 41st ACM Symposium on Theory of Computing (STOC)'', 2009.</ref> पूरी तरह से समरूपी एन्क्रिप्शन योजना के निर्माण की समस्या का पहला समाधान प्रस्तावित किया। उनकी योजना आदर्श जालक पर आधारित थी।


== यह भी देखें ==
== यह भी देखें ==
Line 207: Line 198:
==संदर्भ==
==संदर्भ==
<references/>
<references/>
[[Category: संख्या सिद्धांत]] [[Category: जाली आधारित क्रिप्टोग्राफी]] [[Category: पोस्ट-क्वांटम क्रिप्टोग्राफी]]


[[Category: Machine Translated Page]]
[[Category:All articles with unsourced statements]]
[[Category:Articles with unsourced statements from January 2018]]
[[Category:Created On 11/05/2023]]
[[Category:Created On 11/05/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:Webarchive template wayback links]]
[[Category:जाली आधारित क्रिप्टोग्राफी]]
[[Category:पोस्ट-क्वांटम क्रिप्टोग्राफी]]
[[Category:संख्या सिद्धांत]]

Latest revision as of 17:36, 18 May 2023

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

वलय लर्निंग विद एरर्स पर आधारित क्वांटम कंप्यूटर अहमले प्रतिरोधी क्रिप्टोग्राफी के लिए आदर्श जालक भी आधार बनाते हैं।[2] ये क्रिप्टोसिस्टम इस धारणा के तहत काफी सुरक्षित हैं कि इन आदर्श जालक में सबसे छोटी सदिश समस्या (एसवीपी) कठिन है।

परिचय

सामान्य शब्दों में, आदर्श जालक ऐसे जालक होते हैं जो डिग्री के कुछ अलघुकरणीय बहुपद के लिए ̩ रूप के वलय में आदर्शों के अनुरूप होते हैं। [1]पूर्व कार्य से आदर्श जालक की सभी परिभाषाएँ निम्नलिखित सामान्य धारणा के उदाहरण हैं: मान लीजिए एक वलय हो जिसका योज्य समूह समतुल्य है (अर्थात्, यह रैंक का मुक्त -मॉड्यूल है), और मान लीजिए किसी -विमीय वास्तविक सदिश स्थान में एक योगात्मक समरूपता मानचित्रण जालक के लिए हो (उदा., )। एम्बेडिंग के तहत वलय के लिए आदर्श जालक का परिवार सभी जालकों का समुच्चय है, जहां में एक आदर्श है। [3]

परिभाषा

अंकन

माना डिग्री का एक मोनिक बहुपद हो, और भागफल वलय पर विचार करें।

प्रतिनिधियों के मानक समुच्चय का उपयोग करना, और सदिशों के साथ बहुपदों की पहचान, भागफल वलय such that such that पूर्णांक जालक के लिए समूह समरूपता (एक योजक समूह के रूप में) है, और कोई आदर्श आप एक संबंधित पूर्णांक को सूक्ष्म रूप से परिभाषित करते हैं।

एक आदर्श जालक एक पूर्णांक जालक है ऐसा है कि कुछ मोनिक बहुपद के लिए डिग्री और आदर्श जालक हैं।

संबंधित गुण

यह पता चला है कि के प्रासंगिक गुण परिणामी कार्य के लिए टक्कर प्रतिरोधी होने के लिए हैं:

  • अखंडनीय बहुपद होना चाहिए।
  • वलय मानदंड से बहुत बड़ा नहीं है किसी भी बहुपद के लिए, मात्रात्मक अर्थ में है।

पहली संपत्ति का तात्पर्य है कि वलय का हर आदर्श में एक पूर्ण-रैंक जालक को परिभाषित करता है और प्रमाण में एक मौलिक भूमिका निभाता है।

लेम्मा: हर आदर्श का , जहाँ डिग्री का एक मोनिक, अखंडनीय बहुपद पूर्णांक बहुपद है , पूर्ण-रैंक जालक के लिए समरूपी है।

डिंग और लिंडनर[4] ने प्रमाण दिया कि आदर्श जालक को सामान्य से अलग करना बहुपद समय में किया जा सकता है और यह दिखाया कि व्यवहार में अक्रमतः चुने गए जालक कभी भी आदर्श नहीं होते हैं। उन्होंने केवल उस स्थिति पर विचार किया जहां जालक का पूर्ण रैंक है, यानी आधार में रैखिक स्वतंत्र सदिश सम्मिलित है। यह एक मौलिक प्रतिबंध नहीं है क्योंकि हुबाशेव्स्की और मिचियानसियो ने दिखाया है कि यदि एक जालक एक अखंडनीय मोनिक बहुपद के संबंध में आदर्श है, तो इसकी पूर्ण रैंक है, जैसा कि उपरोक्त लेम्मा में दिया गया है।

एल्गोरिद्म: पूर्ण रैंक आधारों वाले आदर्श जालकों की पहचान करना

डेटा: एक पूर्ण-रैंक आधार
परिणाम: ट्रू और , अगर के संबंध में एक आदर्श जालक फैलाता है , अन्यथा फाल्स है।

  1. एचएनएफ में रूपांतरित करें
  2. , , और गणना करें
  3. उत्पाद की गणना करें
  4. इफ P का केवल अंतिम स्तंभ गैर-शून्य है देन
  5. इस कॉलम की बराबरी करने के लिए
  6. एल्स रिटर्न फाल्स
  7. इफ फॉर देन
  8. खोजने के लिए सीआरटी का उपयोग करें और
  9. एल्स रिटर्न फाल्स
  10. इफ देन
  11. रिटर्न ट्रू
  12. एल्स रिटर्न फाल्स

जहां मैट्रिक्स एम है

इस एल्गोरिथम का उपयोग करते हुए, यह देखा जा सकता है कि कई जालक आदर्श जालक नहीं होते हैं। उदाहरण के लिए, माना और , तब

आदर्श है, लेकिन

नहीं है। साथ हुबाशेव्स्की और मिचियानसियो द्वारा दिया गया एक उदाहरण है।[5]
उस पर एल्गोरिदम का प्रदर्शन करना और आधार को बी के रूप में संदर्भित करना, मैट्रिक्स बी पहले से ही हर्मिट सामान्य रूप में है इसलिए पहले चरण की आवश्यकता नहीं है। निर्धारक है, सहायक मैट्रिक्स

और अंत में, उत्पाद है

इस बिंदु पर एल्गोरिथ्म बंद हो जाता है, क्योंकि अंतिम स्तंभ के अलावा सभी अगर शून्य होना है एक आदर्श जालक फैलाएगा।

क्रिप्टोग्राफी में प्रयोग

मिचियानसियो [6] संरचित चक्रीय जालक के वर्ग को पेश किया, जो बहुपद के वलय में आदर्शों के अनुरूप है, और पॉली (एन) -एसवीपी के चक्रीय जालक के प्रतिबंध के अनुमान की सबसे खराब स्थिति की कठोरता के आधार पर पहला सिद्ध रूप से सुरक्षित वन-वे फ़ंक्शन प्रस्तुत किया। (समस्या γ-एसवीपी में किसी दिए गए जालक के गैर-शून्य सदिश की गणना करने में सम्मिलित है, जिसका मानदंड कम से कम गैर-शून्य जालक सदिश के मानक से γ गुना बड़ा नहीं है।) उसी समय, इसकी बीजगणितीय संरचना के कारण, यह एक तरफा कार्य एनटीआरयू योजना मूल्यांकन समय और स्टोरेज लागत की तुलना में उच्च दक्षता प्राप्त करता है)। इसके बाद, हुबाशेव्स्की और मिचियानसियो[5]और स्वतंत्र रूप से पीकर्ट और रोसेन[7] ने दिखाया कि एक कुशल और सिद्ध रूप से सुरक्षित टकराव प्रतिरोध क्रिप्टोग्राफ़िक हैश फ़ंक्शन बनाने के लिए मिचियानसियो के कार्य को कैसे संशोधित किया जाए। इसके लिए, उन्होंने आदर्श जालक के अधिक सामान्य वर्ग को प्रस्तुत किया, जो बहुपद के वलय में आदर्शों के अनुरूप है। टकराव प्रतिरोध पॉली (एन) -एसवीपी के आदर्श जालक (पॉली (एन) -आईडियल-एसवीपी कहा जाता है) के प्रतिबंध की कठोरता पर निर्भर करता है। औसत-मामले की टक्कर-ढूँढने की समस्या एक प्राकृतिक कम्प्यूटेशनल समस्या है जिसे आदर्श-एसआईएस कहा जाता है, जिसे आदर्श-एसवीपी के सबसे खराब-स्थिति उदाहरणों के रूप में कठिन दिखाया गया है। आदर्श जालक से सिद्ध रूप से सुरक्षित कुशल चिहनक योजनाएँ भी प्रस्तावित की गई हैं,[1][8] लेकिन आदर्श जालक से कुशल सिद्ध रूप से सुरक्षित सार्वजनिक कुंजी एन्क्रिप्शन का निर्माण करना एक दिलचस्प खुली समस्या थी।

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

कुशल टक्कर प्रतिरोधी हैश फ़ंक्शन

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

हुबाशेव्स्की और मिकिसियानियो[5]कुशल टकराव प्रतिरोध क्रिप्टोग्राफ़िक हैश फ़ंक्शन का निर्माण दिया जो आदर्श जालक के लिए सबसे छोटी वेक्टर समस्या की सबसे खराब स्थिति के आधार पर सुरक्षित प्रमाणित हो सकता है। उन्होंने क्रिप्टोग्राफ़िक हैश फ़ंक्शन परिवारों को परिभाषित किया: एक वलय दी , जहाँ डिग्री का एक मोनिक, अलघुकरणीय बहुपद डिग्री और लगभग क्रम का पूर्णांक है, यादृच्छिक तत्व , जहाँ एक स्थिरांक है। क्रमशः -टुपल हैश फ़ंक्शन निर्धारित करता है। यह तत्वों को में मैप करेगा, जहाँ , से का एक रणनीतिक रूप से चुना गया उपसमुच्चय है। एक तत्व के लिए , हैश है। यहाँ कुंजी का आकार (क्रिप्टोग्राफ़िक हैश फ़ंक्शन) है, और ऑपरेशन , समय पर बहुपद के उपयुक्त विकल्प के लिए फास्ट फूरियर ट्रांसफॉर्म (FFT) का उपयोग किया जाता है।[citation needed] चूँकि एक नियतांक है, हैशिंग के लिए समय की आवश्यकता होती है। उन्होंने प्रमाणित किया कि क्रिप्टोग्राफ़िक हैश फ़ंक्शन परिवार टकराव प्रतिरोधी है, यह दिखाते हुए कि यदि कोई बहुपद समय एल्गोरिदम है जो बहुपद-समय एल्गोरिथ्म जो खोजने में गैर-नगण्य संभाव्यता के साथ सफल होता है जैसे कि है, अक्रमतः चुने गए क्रिप्टोग्राफ़िक हैश फ़ंक्शन के लिए , फिर एक निश्चित समस्या जिसे "सबसे छोटी वेक्टर समस्या" कहा जाता है, वलय के प्रत्येक आदर्श के लिए बहुपद समय में हल करने योग्य है।

2006 में हुबाशेवस्की और मिकिसियानियो के काम के आधार पर, मिकसियानियो और रेगेव[12] आदर्श जालक के आधार पर क्रिप्टोग्राफ़िक हैश फ़ंक्शन के निम्नलिखित एल्गोरिथम को परिभाषित किया गया है:

  • पैरामीटर: पूर्णांक साथ , और सदिश एफ .
  • की: वैक्टर स्वतंत्र रूप से और समान रूप से यादृच्छिक रूप से चुना गया।
  • हैश फ़ंक्शन: द्वारा दिए गए .

यहाँ पैरामीटर हैं, f, में एक सदिश है और संरचित ब्लॉकों वाला एक ब्लॉक-मैट्रिक्स है।

औसत रूप से में छोटे वैक्टर ढूँढना (यहां तक ​​कि केवल व्युत्क्रम बहुपद संभाव्यता के साथ) आदर्श जाली पर सबसे खराब स्थिति में विभिन्न जाली समस्याओं (जैसे अनुमानित SVP और SIVP) को हल करना उतना ही कठिन है, परंतु सदिश 'f' निम्नलिखित दो गुणों को संतुष्ट करता हो:

  • किसी भी दो इकाई वैक्टर 'यू', 'वी' के लिए, सदिश [F∗u]v छोटा (कहते हैं, बहुपद , प्रायः मानदंड है।
  • बहुपद पूर्णांकों पर अलघुकरणीय बहुपद है, अर्थात, यह छोटी डिग्री के पूर्णांक बहुपदों के गुणनफल में कारक नहीं है।

पहला गुण सदिश द्वारा संतुष्ट है परिचालित मैट्रिक्स के अनुरूप, क्योंकि [F∗u]v के सभी निर्देशांक 1 से घिरे हैं, और इसलिए है। हालाँकि, बहुपद तदनुसार अलघुकरणीय बहुपद नहीं है क्योंकि यह क्रमगुणितअ है, और यही कारण है कि टक्करों को कुशलता से पाया जा सकता है। इसलिए, टक्कर प्रतिरोध क्रिप्टोग्राफ़िक हैश फ़ंक्शन प्राप्त करने के लिए एक अच्छा विकल्प नहीं है, लेकिन कई अन्य विकल्प संभव हैं। उदाहरण के लिए, f के कुछ विकल्प जिसके लिए दोनों गुण संतुष्ट (और इसलिए, सबसे खराब स्थिति वाली सुरक्षा गारंटी के साथ टकराव प्रतिरोध क्रिप्टोग्राफ़िक हैश फ़ंक्शन का परिणाम है) हैं

  • जहाँ अभाज्य है, और
  • के लिए की 2 घात के बराबर।

डिजिटल हस्ताक्षर

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

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

उनके काम द्वारा उठाई गई मुख्य खुली समस्याओं में से एक समान दक्षता के साथ एक बार के हस्ताक्षर का निर्माण कर रही है, लेकिन सन्निकटन धारणा की कमजोर कठोरता पर आधारित है।उदाहरण के लिए, के एक कारक के भीतर शॉर्टेस्ट वेक्टर प्रॉब्लम (एसवीपी) (आदर्श जालक में) को अनुमानित करने की कठोरता के आधार पर सुरक्षा के साथ एक बार का हस्ताक्षर प्रदान करना बहुत अच्छा होगा।[8]

उनका निर्माण एक बार के हस्ताक्षर (यानी हस्ताक्षर जो एक संदेश पर सुरक्षित रूप से हस्ताक्षर करने की अनुमति देता है) से सामान्य हस्ताक्षर योजनाओं के मानक परिवर्तन पर आधारित है, साथ में जालक आधारित एक बार के हस्ताक्षर के एक नवीन निर्माण के साथ जिसकी सुरक्षा अंततः किसी भी अलघुकरणीय बहुपद के लिए वलय में आदर्शों के अनुरूप सभी जालक में सबसे कम वेक्टर का अनुमान लगाने की सबसे खराब स्थिति की कठोरता पर आधारित है।

की-जनरेशन एल्गोरिथम:इनपुट: , अलघुकरणीय बहुपद , डिग्री का।

  1. समुच्चय , ,
  2. सभी सकारात्मक के लिए , माना सेट और के रूप में परिभाषित किया जाना चाहिए:
ऐसा है कि
ऐसा है कि
  1. समान रूप से यादृच्छिक चुनें
  2. समान रूप से यादृच्छिक स्ट्रिंग चुनें
  3. इफ देन
  4. सेट
  5. एल्स
  6. सेट स्ट्रिंग में पहले 1 की स्थिति के लिए
  7. एन्ड इफ
  8. स्वतंत्र रूप से और समान रूप से यादृच्छिक रूप से और क्रमश: चुनें
  9. हस्ताक्षर कुंजी: . सत्यापन कुंजी:

हस्ताक्षर एल्गोरिथ्म:

इनपुट: संदेश ऐसा है कि ; हस्ताक्षर कुंजी

आउटपुट:

सत्यापन एल्गोरिथम:

इनपुट: संदेश ; हस्ताक्षर ; सत्यापन कुंजी

आउटपुट: "ACCEPT", इफ और अन्यथा, "REJECT"।

स्विफ्ट हैश फ़ंक्शन

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

एस डब्ल्यू आई एफ एफ टी हैश फ़ंक्शन का एल्गोरिथ्म है:

  • पैरामीटर: पूर्णांक ऐसा है कि 2 की घात है, अभाज्य है, और .
  • की: वैक्टर स्वतंत्र रूप से और समान रूप से यादृच्छिक रूप से चुना गया .
  • इनपुट: सदिश .
  • आउटपुट: सदिश , जहाँ घटक-वार सदिश उत्पाद है।

त्रुटियों के साथ सीखना (एलडब्ल्यूई)

वलय-एलडब्ल्यूई

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

माना , जहां सुरक्षा पैरामीटर 2 की घात है, परिमेय को अप्रासंगिक बनाना। (यह विशेष साइक्लोटोमिक बहुपदों के परिवार से आता है, जो इस काम में एक विशेष भूमिका निभाते हैं)।

माना पूर्णांक बहुपद मॉड्यूलो का वलय हो। के घटक (यानी, अवशेषों मॉड्यूलो का रूप ) प्रायः से कम डिग्री के पूर्णांक बहुपदों द्वारा दर्शाए जाते हैं। माना एक पर्याप्त रूप से बड़े सार्वजनिक प्रमुख मॉड्यूलस बनें ( में एक बहुपद से घिरा हुआ), और माना दोनों पूर्णांक बहुपद मॉड्यूलो और की वलय बनें। घटक डिग्री वाले बहुपदों द्वारा प्रदर्शित किया जा सकता है -जिसके गुणांक हैं।

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

उन्होंने रिंग-एलडब्ल्यूई के खोज संस्करण में में आदर्श जालक पर अनुमानित एसवीपी (सबसे खराब स्थिति में) से एक मात्रा में कमी दी, जहां लक्ष्य स्वेच्छतः कई शोर वाले उत्पादों से गुप्त (उच्च संभावना के साथ, किसी भी के लिए) को पुनर्प्राप्त करना है। यह परिणाम सामान्य जालक के लिए रेगेव की पुनरावृत्त मात्रा में कमी की सामान्य रूपरेखा का अनुसरण करता है,[13] लेकिन आदर्श जालक कमी के 'बीजगणितीय' और 'ज्यामितीय' घटकों दोनों में कई नई तकनीकी बाधाओं का परिचय देती हैं। उन्होंने[3] बीजगणितीय संख्या सिद्धांत का उपयोग किया, विशेष रूप से, इन बाधाओं को दूर करने के लिए एक संख्या क्षेत्र के विहित एम्बेडिंग और चीनी शेष प्रमेय। उन्हें निम्नलिखित प्रमेय प्राप्त हुआ:

प्रमेय माना डिग्री का एक मनमाना संख्या क्षेत्र हो। माना स्वेच्छतः हो, और (तर्कसंगत) पूर्णांक मापांक दें, ऐसा हो। - को - से एक संभाव्य बहुपद-समय क्वांटम कमी है, जहाँ है।

2013 में, गुनेसु, ल्यूबाशेवस्की, और पोप्पलमैन ने वलय लर्निंग विद एरर्स समस्या के आधार पर एक डिजिटल हस्ताक्षर योजना प्रस्तावित की।[14] 2014 में, पैकर्ट ने अपने पेपर," इंटरनेट के लिए जालक क्रिप्टोग्राफी" में वलय लर्निंग विथ एरर्स की एक्सचेंज (आर एल डब्ल्यू इ- के इ एक्स) प्रस्तुत किया।[10] इसे सिंह के कार्य द्वारा और विकसित किया गया।[15]

आदर्श एलडब्ल्यूई

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

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

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

पूरी तरह से समरूप एन्क्रिप्शन

एक पूरी तरह से होमोमोर्फिक एन्क्रिप्शन (एफएचई) योजना वह है जो पहले डिक्रिप्ट करने की आवश्यकता के बिना एन्क्रिप्टेड डेटा पर गणना करने की अनुमति देती है। रिवेस्ट, एडलमैन और शमीर द्वारा आरएसए के आविष्कार के तुरंत बाद, 1978 में रिवेस्ट, एडलमैन और डर्टौज़ोस[17] द्वारा पूरी तरह से होमोमोर्फिक एन्क्रिप्शन योजना के निर्माण की समस्या को सामने रखा गया था। [18]

एक एन्क्रिप्शन योजना में सर्किट के लिए समरूपी है अगर, किसी भी सर्किट के लिए ,

दिया गया , , और ,

यह मानता है .

पूरी तरह से समरूप है अगर यह आकार के सभी सर्किटों के लिए समरूप है जहाँ योजना का सुरक्षा पैरामीटर है।

2009 में, जेंट्री[19] पूरी तरह से समरूपी एन्क्रिप्शन योजना के निर्माण की समस्या का पहला समाधान प्रस्तावित किया। उनकी योजना आदर्श जालक पर आधारित थी।

यह भी देखें

संदर्भ

  1. 1.0 1.1 1.2 1.3 Vadim Lyubashevsky. Lattice-Based Identification Schemes Secure Under Active Attacks. In Proceedings of the Practice and theory in public key cryptography , 11th international conference on Public key cryptography, 2008.
  2. Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (2010). "आदर्श लैटिस और रिंग्स पर त्रुटियों के साथ सीखने पर". In Proc. Of EUROCRYPT, Volume 6110 of LNCS: 1–23. CiteSeerX 10.1.1.297.6108.
  3. 3.0 3.1 3.2 3.3 Vadim Lyubashevsky, Chris Peikert and Oded Regev. On Ideal Lattices and Learning with Errors over Rings. In Eurocrypt 2010, Lecture Notes in Computer Science, 2010.
  4. Jintai Ding and Richard Lindner. Identifying Ideal Lattices. In Cryptology ePrint Archive, Report 2007/322, 2007.
  5. 5.0 5.1 5.2 Lyubashevsky, V., Micciancio, D. Generalized compact knapsacks are collision resistant.. In CBugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4052, pp. 144–155. Springer, Heidelberg (2006).
  6. Micciancio, D. Generalized compact knapsacks, cyclic lattices, and efficient oneway functions.. In Computational Complexity 16(4), 365–411 (2007).
  7. 7.0 7.1 Peikert, C., Rosen, A. Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. Archived 2012-10-16 at the Wayback Machine. In Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 145–166. Springer, Heidelberg (2006).
  8. 8.0 8.1 8.2 8.3 Vadim Lyubashevsky and Daniele Micciancio. Asymptotically efficient lattice-based digital signatures. In Proceedings of the 5th conference on Theory of cryptography, 2008.
  9. Ding, Jintai; Xie, Xiang; Lin, Xiaodong (2012). त्रुटियों के साथ सीखने की समस्या पर आधारित एक सरल प्रमाणित सुरक्षित कुंजी विनिमय योजना (PDF).
  10. 10.0 10.1 Peikert, Chris (2014-10-01). "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.
  11. Lyubashevsky, Vadim (29 Jul 2012). "ट्रैपडोर के बिना जाली हस्ताक्षर" (PDF). IACR ePrint Archive. IACR. Retrieved 21 June 2014.
  12. 12.0 12.1 12.2 Daniele Micciancio, Oded Regev Lattice-based Cryptography Archived 2011-07-23 at the Wayback Machine. In POST-QUANTUM CRYPTOGRAPHY, 2009.
  13. Oded Regev. On lattices, learning with errors, random linear codes, and cryptography Archived 2010-12-06 at the Wayback Machine. In Journal of the ACM, 2009.
  14. "Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems" (PDF). Archived from the original (PDF) on 2014-05-18. Retrieved 18 May 2014.
  15. Singh, Vikram (2015). "जाली क्रिप्टोग्राफी का उपयोग कर इंटरनेट के लिए एक व्यावहारिक कुंजी एक्सचेंज". Cryptology ePrint Archive.
  16. Damien Stehlé, Ron Steinfeld, Keisuke Tanaka and Keita Xagawa. Efficient public key encryption based on ideal lattices. In Lecture Notes in Computer Science, 2009.
  17. R. Rivest, L. Adleman, and M. Dertouzos. [On data banks and privacy homomorphisms.]. In In Foundations of Secure Computation, pp. 169–180, 1978.
  18. R. Rivest, A. Shamir, and L. Adleman. [A method for obtaining digital signatures and public-key cryptosystems.]. In Comm. of the ACM,21:2, pages 120–126, 1978.
  19. Craig Gentry. Fully Homomorphic Encryption Using Ideal Lattices. In the 41st ACM Symposium on Theory of Computing (STOC), 2009.