आदर्श जालक

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

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

परिचय

सामान्य शब्दों में, आदर्श जालक फॉर्म के वलय में आदर्श के अनुरूप जालक हैं $\mathbb {Z} [x]/\langle f\rangle$ कुछ अलघुकरणीय बहुपद के लिए $f$ डिग्री का $n$.पूर्व कार्य से आदर्श जालक की सभी परिभाषाएँ निम्नलिखित सामान्य धारणा के उदाहरण हैं: चलो $R$ एक वलय (गणित) हो जिसका वलय (गणित) समूह समरूपता है $\mathbb {Z} ^{n}$ (अर्थात्, यह एक मुक्त आबेली समूह है|नि:शुल्क $\mathbb {Z}$- फ्री एबेलियन ग्रुप # रैंक का मॉड्यूल $n$), और जाने $\sigma$ एक योगात्मक समरूपता मानचित्रण हो $R$ किसी जालक को $\sigma (R)$ एक में $n$-विमीय वास्तविक सदिश स्थान (उदा., $\mathbb {R} ^{n}$). अंगूठी के लिए आदर्श जालक का परिवार $R$ एम्बेडिंग के तहत $\sigma$ सभी जालियों का समुच्चय है $\sigma (I)$, कहाँ $I$ में एक आदर्श (वलय थ्योरी) है $R.$

परिभाषा

अंकन

होने देना $f\in \mathbb {Z} [x]$ डिग्री का एक मोनिक बहुपद हो $n$, और भागफल वलय पर विचार करें $\mathbb {Z} [x]/\langle f\rangle$.

प्रतिनिधियों के मानक सेट का उपयोग करना $\lbrace (g{\bmod {f}}):g\in \mathbb {Z} [x]\rbrace$, और सदिशों के साथ बहुपदों की पहचान, भागफल वलय $\mathbb {Z} [x]/\langle f\rangle$ पूर्णांक जालक के लिए समूह समरूपता (एक अंगूठी (गणित) के रूप में) है $\mathbb {Z} ^{n}$, और कोई आदर्श (वलय थ्योरी) $I\subseteq \mathbb {Z} [x]/\langle f\rangle$ आप एक संबंधित पूर्णांक को सूक्ष्म रूप से परिभाषित करते हैं ${\mathcal {L}}(I)\subseteq \mathbb {Z} ^{n}$.

एक आदर्श जालक एक पूर्णांक जालक है ${\mathcal {L}}(B)\subseteq \mathbb {Z} ^{n}$ ऐसा है कि $B=\lbrace g{\bmod {f}}:g\in I\rbrace$ कुछ मोनिक बहुपद के लिए $f$ डिग्री का $n$ और आदर्श (वलय थ्योरी) $I\subseteq \mathbb {Z} [x]/\langle f\rangle$.

संबंधित गुण

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

• $f$ इरेड्यूसिबल बहुपद होना चाहिए।
• वलय नॉर्म $\lVert g\rVert _{f}$ से बहुत बड़ा नहीं है $\lVert g\rVert _{\infty }$ किसी भी बहुपद के लिए $g$, मात्रात्मक अर्थ में।

पहली संपत्ति का तात्पर्य है कि वलय का हर आदर्श (गणित) $\mathbb {Z} [x]/\langle f\rangle$ में एक पूर्ण-रैंक जालक को परिभाषित करता है $\mathbb {Z} ^{n}$ और सबूतों में एक मौलिक भूमिका निभाता है।

लेम्मा: एवरी आइडियल (वलय थ्योरी) $I$ का $\mathbb {Z} [x]/\langle f\rangle$, कहाँ $f$ डिग्री का एक मोनिक, इर्रेड्यूसबल बहुपद पूर्णांक बहुपद है $n$, एक पूर्ण-रैंक जालक के लिए आइसोमॉर्फिक है $\mathbb {Z} ^{n}$.

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

एल्गोरिद्म: फुल रैंक बेस वाले आदर्श जालक की पहचान करना

डेटा: एक फुल-रैंक आधार $B\in \mathbb {Z} ^{(n,n)}$
परिणाम: 'सच' और ${\textbf {q}}$, अगर $B$ के संबंध में एक आदर्श जालक फैलाता है ${\textbf {q}}$, अन्यथा झूठा।

1. रूपांतरित करें $B$ हर्मिट सामान्य रूप में
2. गणना करें $A={\rm {adj}}(B)$, $d=\det(B)$, और $z=B_{(n,n)}$
3. उत्पाद की गणना करें $P=AMB{\bmod {d}}$
4. यदि P का केवल अंतिम स्तंभ गैर-शून्य है तब
5. तय करना $c=P_{(\centerdot ,n)}$ इस कॉलम की बराबरी करने के लिए
6. वरना झूठा लौटाओ
7. अगर $z\mid c_{i}$ के लिए $i=1,\ldots ,n$ तब
8. खोजने के लिए चीनी शेष प्रमेय का उपयोग करें $q^{\ast }\equiv (c/z){\bmod {(}}d/z)$ और $q^{\ast }\equiv 0{\bmod {\ }}z$
9. वरना झूठा लौटाओ
10. अगर $Bq^{\ast }\equiv 0{\bmod {(}}d/z)$ तब
11. रिटर्न सच, $q=Bq^{\ast }/d$
12. वरना झूठा लौटाओ

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

$M={\begin{pmatrix}0&\cdot &\cdot &\cdot &0\\&&&&\cdot \\&&&&\cdot \\I_{n-1}&&&&\cdot \\&&&&0\end{pmatrix}}$

इस एल्गोरिथम का उपयोग करते हुए, यह देखा जा सकता है कि कई जालक आदर्श जालक नहीं होते हैं। उदाहरण के लिए, चलो $n=2$ और $k\in \mathbb {Z} \smallsetminus \lbrace 0,\pm 1\rbrace$, तब

$B_{1}={\begin{pmatrix}k&0\\0&1\end{pmatrix}}$

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

$B_{2}={\begin{pmatrix}1&0\\0&k\end{pmatrix}}$

क्या नहीं है। $B_{2}$ साथ $k=2$ Lyubashevsky और Micciancio द्वारा दिया गया एक उदाहरण है। उस पर एल्गोरिदम का प्रदर्शन करना और आधार को बी के रूप में संदर्भित करना, मैट्रिक्स बी पहले से ही हर्मिट सामान्य रूप में है इसलिए पहले चरण की आवश्यकता नहीं है। निर्धारक है $d=2$सहायक मैट्रिक्स

$A={\begin{pmatrix}2&0\\0&1\end{pmatrix}},$

$M={\begin{pmatrix}0&0\\1&0\end{pmatrix}}$

और अंत में, उत्पाद $P=AMB{\bmod {d}}$ है

$P={\begin{pmatrix}0&0\\1&0\end{pmatrix}}.$

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

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

छोटा लड़का संरचित चक्रीय जालक के वर्ग को पेश किया, जो बहुपद के छल्ले में आदर्शों के अनुरूप है $\mathbb {Z} [x]/(x^{n}-1)$, और पॉली (एन) -एसवीपी के चक्रीय जालक के प्रतिबंध के अनुमान की सबसे खराब स्थिति की कठोरता के आधार पर पहला सिद्ध रूप से सुरक्षित वन-वे फ़ंक्शन प्रस्तुत किया। (समस्या γ-एसवीपी में किसी दिए गए जालक के गैर-शून्य वेक्टर की गणना करने में शामिल है, जिसका मानदंड कम से कम गैर-शून्य जालक वेक्टर के मानक से γ गुना बड़ा नहीं है।) उसी समय, इसके बीजगणितीय के लिए धन्यवाद संरचना, यह एक तरफा कार्य एनटीआरयूईन्क्रिप्ट योजना की तुलना में उच्च दक्षता प्राप्त करता है ${\tilde {O}}(n)$ मूल्यांकन समय और भंडारण लागत)। इसके बाद, Lyubashevsky और Micciancioऔर स्वतंत्र रूप से पीकर्ट और रोसेन ने दिखाया कि एक कुशल और सिद्ध रूप से सुरक्षित टकराव प्रतिरोध क्रिप्टोग्राफ़िक हैश फ़ंक्शन बनाने के लिए माइकियानसियो के कार्य को कैसे संशोधित किया जाए। इसके लिए, उन्होंने आदर्श जालक के अधिक सामान्य वर्ग की शुरुआत की, जो बहुपद के छल्ले में आइडियल (वलय थ्योरी) के अनुरूप है $\mathbb {Z} [x]/f(x)$. टकराव प्रतिरोध पॉली (एन) -एसवीपी के आदर्श जालक (पॉली (एन) -आईडियल-एसवीपी कहा जाता है) के प्रतिबंध की कठोरता पर निर्भर करता है। औसत-मामले की टक्कर-ढूँढने की समस्या एक प्राकृतिक कम्प्यूटेशनल समस्या है जिसे आइडियल-एसआईएस कहा जाता है, जिसे आइडियल-एसवीपी के सबसे खराब-केस उदाहरणों के रूप में कठिन दिखाया गया है। आदर्श जालक से सिद्ध रूप से सुरक्षित कुशल हस्ताक्षर योजनाएँ भी प्रस्तावित की गई हैं, लेकिन आदर्श जालक से कुशल सिद्ध रूप से सुरक्षित सार्वजनिक कुंजी क्रिप्टोग्राफी का निर्माण करना एक दिलचस्प खुली समस्या थी।

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

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

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

हुबाशेव्स्की और मिकिसियानियोकुशल टकराव प्रतिरोध क्रिप्टोग्राफ़िक हैश फ़ंक्शन का निर्माण दिया जो आदर्श जालक के लिए जालक समस्या की सबसे खराब स्थिति के आधार पर सुरक्षित साबित हो सकता है। उन्होंने क्रिप्टोग्राफ़िक हैश फ़ंक्शन परिवारों को परिभाषित किया: एक अंगूठी दी (गणित) $R=\mathbb {Z} _{p}[x]/\langle f\rangle$, कहाँ $f\in \mathbb {Z} _{p}[x]$ डिग्री का एक मोनिक, अलघुकरणीय बहुपद है $n$ और $p$ मोटे तौर पर क्रम का पूर्णांक है $n^{2}$, बनाना $m$ यादृच्छिक तत्व $a_{1},\dots ,a_{m}\in R$, कहाँ $m$ एक स्थिरांक है। आदेश दिया $m$-टुपल $h=(a_{1},\ldots ,a_{m})\in R^{m}$ हैश फ़ंक्शन निर्धारित करता है। यह तत्वों को मैप करेगा $D^{m}$, कहाँ $D$ का रणनीतिक रूप से चुना गया सबसेट है $R$, को $R$. एक तत्व के लिए $b=(b_{1},\ldots ,b_{m})\in D^{m}$, हैश है $h(b)=\sum _{i=1}^{m}\alpha _{i}\centerdot b_{i}$. यहाँ कुंजी का आकार (क्रिप्टोग्राफ़िक हैश फ़ंक्शन) है $O(mn\log p)=O(n\log n)$, और ऑपरेशन $\alpha _{i}\centerdot b_{i}$ समय पर किया जा सकता है $O(n\log n\log \log n)$ फास्ट फूरियर ट्रांसफॉर्म | फास्ट फूरियर ट्रांसफॉर्म (FFT) का उपयोग करके, बहुपद के उपयुक्त विकल्प के लिए $f$. तब से $m$ स्थिर है, हैशिंग के लिए समय की आवश्यकता होती है $O(n\log n\log \log n)$. उन्होंने साबित किया कि क्रिप्टोग्राफ़िक हैश फ़ंक्शन परिवार टकराव प्रतिरोध है, यह दिखाते हुए कि यदि कोई बहुपद समय है। बहुपद-समय एल्गोरिथ्म जो खोजने में गैर-नगण्य संभाव्यता के साथ सफल होता है $b\neq b'\in D^{m}$ ऐसा है कि $h(b)=h(b')$, बेतरतीब ढंग से चुने गए क्रिप्टोग्राफ़िक हैश फ़ंक्शन के लिए $h\in R^{m}$, फिर एक निश्चित वलय (गणित) के प्रत्येक आदर्श (वलय थ्योरी) के लिए "जालक समस्या" नामक समस्या बहुपद समय में हल करने योग्य है $\mathbb {Z} [x]/\langle f\rangle$.

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

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

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

में लघु वैक्टर ढूँढना $\Lambda _{q}^{\perp }([F\ast a_{1}|\ldots |F\ast a_{m/n}])$ औसतन (यहां तक ​​​​कि केवल उलटा बहुपद के साथ भी संभाव्यता) सबसे खराब स्थिति में विभिन्न जालक समस्याओं (जैसे अनुमानित जालक समस्या और SIVP) को हल करने जितना कठिन है आदर्श जालक पर स्थिति, बशर्ते सदिश 'f' निम्नलिखित दो गुणों को संतुष्ट करता हो:

• किसी भी दो इकाई वैक्टर 'यू', 'वी' के लिए, वेक्टर '[F∗u]v' छोटा है (कहते हैं, बहुपद $n$, आम तौर पर $O({\sqrt {n}}))$ मानदंड।
• बहुपद $f(x)=x^{n}+f_{n}x^{n-1}+\cdots +f_{1}\in \mathbb {Z} [x]$ पूर्णांकों पर इरेड्यूसिबल बहुपद है, अर्थात, यह छोटी डिग्री के पूर्णांक बहुपदों के गुणनफल में कारक नहीं है।

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

• $\mathbf {f} =(1,\ldots ,1)\in \mathbb {Z} ^{n}$ कहाँ $n+1$ प्रमुख है, और
• $\mathbf {f} =(1,0,\ldots ,0)\in \mathbb {Z} ^{n}$ के लिए $n$ 2 की शक्ति के बराबर।

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

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

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

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

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

की-जनरेशन एल्गोरिथम: इनपुट: $1^{n}$, अलघुकरणीय बहुपद $f\in \mathbb {Z}$ डिग्री का $n$.

1. तय करना $p\longleftarrow (\varphi n)^{3}$, $m\longleftarrow \lceil \log n\rceil$, $R\longleftarrow \mathbb {Z} _{p}[x]/\langle f\rangle$
2. सभी सकारात्मक के लिए $i$, सेट करते हैं $DK_{i}$ और $DL_{i}$ के रूप में परिभाषित किया जाना चाहिए:

$DK_{i}=\lbrace {\hat {y}}\in R^{m}$ ऐसा है कि $\lVert {\hat {y}}\rVert _{\infty }\leq 5ip^{1/m}\rbrace$

$DL_{i}=\lbrace {\hat {y}}\in R^{m}$ ऐसा है कि $\lVert {\hat {y}}\rVert _{\infty }\leq 5in\varphi p^{1/m}\rbrace$

1. समान रूप से यादृच्छिक चुनें $h\in {\mathcal {H}}_{R,m}$
2. समान रूप से यादृच्छिक स्ट्वलय चुनें $r\in \lbrace 0,1\rbrace ^{\lfloor \log ^{2}n\rfloor }$
3. अगर $r=0^{\lfloor \log ^{2}n\rfloor }$ तब
4. तय करना $j=\lfloor \log ^{2}n\rfloor$
5. अन्य
6. तय करना $j$ स्ट्वलय में पहले 1 की स्थिति के लिए $r$
7. अगर अंत
8. चुनना ${\hat {k}},{\hat {l}}$ स्वतंत्र रूप से और समान रूप से यादृच्छिक रूप से $DK_{j}$ और $DL_{j}$ क्रमश:
9. हस्ताक्षर कुंजी: $({\hat {k}},{\hat {l}})$. सत्यापन कुंजी: $(h,h({\hat {k}}),h({\hat {l}}))$

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

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

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

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

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

SWIFFT हैश फ़ंक्शन का एल्गोरिथ्म है:

• 'पैरामीटर:' पूर्णांक $n,m,q,d$ ऐसा है कि $n$ 2 की शक्ति है, $q$ प्रधान है, $2n\mid (q-1)$ और $n\mid m$.
• चाबी: $m/n$ वैक्टर ${\tilde {a}}_{1},\ldots ,{\tilde {a}}_{m/n}$ स्वतंत्र रूप से और समान रूप से यादृच्छिक रूप से चुना गया $\mathbb {Z} _{q}^{n}$.
• इनपुट: $m/n$ वैक्टर $y^{(1)},\dots ,y^{(m/n)}\in \lbrace 0,\dots ,d-1\rbrace ^{n}$.
• आउटपुट: वेक्टर $\sum _{i=1}^{m/n}{\tilde {a}}^{(i)}\odot ({\textbf {W}}y^{(i)})\in \mathbb {Z} _{q}^{n}$, कहाँ $\odot$ घटक-वार वेक्टर उत्पाद है।

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

त्रुटियों के साथ वलय लर्निंग|रिंग-वामपंथी

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

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

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

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

उन्होंने आदर्श जालक पर अनुमानित जालक समस्या (सबसे खराब स्थिति में) से एक मात्रा में कमी दी $R$ रिंग-एलडब्ल्यूई के खोज संस्करण में, जहां लक्ष्य रहस्य को पुनर्प्राप्त करना है $s\in R_{q}$ (उच्च संभावना के साथ, किसी के लिए $s$) मनमाने ढंग से कई शोर वाले उत्पादों से। यह परिणाम सामान्य जालक के लिए रेगेव की पुनरावृत्त मात्रा में कमी की सामान्य रूपरेखा का अनुसरण करता है, लेकिन आदर्श जालक कमी के 'बीजगणितीय' और 'ज्यामितीय' घटकों दोनों में कई नई तकनीकी बाधाओं का परिचय देती हैं। वे बीजगणितीय संख्या सिद्धांत का उपयोग किया, विशेष रूप से, इन बाधाओं को दूर करने के लिए एक संख्या क्षेत्र के विहित एम्बेडिंग और चीनी शेष प्रमेय। उन्हें निम्नलिखित प्रमेय प्राप्त हुआ:

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

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

आदर्श वामपंथी उग्रवाद

चोरी, स्टेनफेल्ड, तनाका और ज़गावा आदर्श जालक में अनुमानित जालक समस्या की सबसे खराब स्थिति कठोरता के आधार पर एक कुशल सार्वजनिक कुंजी एन्क्रिप्शन योजना का वर्णन करने के लिए LWE समस्या (आदर्श-LWE) के एक संरचित संस्करण को परिभाषित किया। यह पहली सीपीए-सुरक्षित सार्वजनिक कुंजी एन्क्रिप्शन योजना है, जिसकी सुरक्षा सबसे खराब स्थिति वाले उदाहरणों की कठोरता पर निर्भर करती है ${\tilde {O}}(n^{2})$-आइडियल-एसवीपी उप-घातीय क्वांटम हमलों के खिलाफ। यह असीमित रूप से इष्टतम दक्षता प्राप्त करता है: सार्वजनिक/निजी कुंजी लंबाई है ${\tilde {O}}(n)$ बिट्स और परिशोधित एन्क्रिप्शन/डिक्रिप्शन लागत है ${\tilde {O}}(1)$ बिट ऑपरेशंस प्रति संदेश बिट (एन्क्रिप्टिंग ${\tilde {\Omega }}(n)$ बिट्स एक बार में, एक पर ${\tilde {O}}(n)$ लागत)। यहां सुरक्षा धारणा यह है कि ${\tilde {O}}(n^{2})$-आइडियल-एसवीपी को किसी भी उप-घातीय समय क्वांटम एल्गोरिदम द्वारा हल नहीं किया जा सकता है। यह उल्लेखनीय है कि यह मानक सार्वजनिक-कुंजी क्रिप्टोग्राफ़ी सुरक्षा मान्यताओं से अधिक मजबूत है। दूसरी ओर, अधिकांश सार्वजनिक-कुंजी क्रिप्टोग्राफी के विपरीत, जालक-आधारित क्रिप्टोग्राफी उप-घातीय क्वांटम हमलों के खिलाफ सुरक्षा की अनुमति देती है।

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

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

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

एक पूरी तरह से होमोमोर्फिक एन्क्रिप्शन (एफएचई) योजना वह है जो पहले डिक्रिप्ट करने की आवश्यकता के बिना एन्क्रिप्टेड डेटा पर गणना करने की अनुमति देती है। पूरी तरह से होमोमोर्फिक एन्क्रिप्शन योजना के निर्माण की समस्या को सबसे पहले रिवेस्ट, एडलमैन और डर्टोज़ोस ने सामने रखा था। 1978 में, रिवेस्ट, एडलमैन और शमीर द्वारा आरएसए (एल्गोरिदम) के आविष्कार के तुरंत बाद। एक एन्क्रिप्शन योजना $\varepsilon =({\mathsf {KeyGen}},{\mathsf {Encrypt}},{\mathsf {Decrypt}},{\mathsf {Eval}})$ में सर्किट के लिए होमोमोर्फिक है ${\mathcal {C}}$ अगर, किसी भी सर्किट के लिए $C\in {\mathcal {C}}$,

दिया गया $PK,SK\leftarrow {\mathsf {KeyGen}}(1^{\lambda })$, $y={\mathsf {Encrypt}}(PK,x)$, और $y'={\mathsf {Eval}}(PK,C,y)$,

यह मानता है ${\mathsf {Decrypt}}(SK,y')=C(x)$.

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

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

यह भी देखें

• जालक आधारित क्रिप्टोग्राफी
• होमोमोर्फिक एन्क्रिप्शन
• त्रुटियों कुंजी विनिमय के साथ अंगूठी सीखना
• पोस्ट-क्वांटम क्रिप्टोग्राफी
• लघु पूर्णांक समाधान समस्या