आदर्श जालक

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

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

परिचय

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

उस पर एल्गोरिदम का प्रदर्शन करना और आधार को बी के रूप में संदर्भित करना, मैट्रिक्स बी पहले से ही हर्मिट सामान्य रूप में है इसलिए पहले चरण की आवश्यकता नहीं है। निर्धारक $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)$मूल्यांकन समय और स्टोरेज लागत की तुलना में उच्च दक्षता प्राप्त करता है)। इसके बाद, हुबाशेव्स्की और मिचियानसियोऔर स्वतंत्र रूप से पीकर्ट और रोसेन ने दिखाया कि एक कुशल और सिद्ध रूप से सुरक्षित टकराव प्रतिरोध क्रिप्टोग्राफ़िक हैश फ़ंक्शन बनाने के लिए मिचियानसियो के कार्य को कैसे संशोधित किया जाए। इसके लिए, उन्होंने आदर्श जालक के अधिक सामान्य वर्ग को प्रस्तुत किया, जो बहुपद के वलय $\mathbb {Z} [x]/f(x)$ में आदर्शों के अनुरूप है। टकराव प्रतिरोध पॉली (एन) -एसवीपी के आदर्श जालक (पॉली (एन) -आईडियल-एसवीपी कहा जाता है) के प्रतिबंध की कठोरता पर निर्भर करता है। औसत-मामले की टक्कर-ढूँढने की समस्या एक प्राकृतिक कम्प्यूटेशनल समस्या है जिसे आदर्श-एसआईएस कहा जाता है, जिसे आदर्श-एसवीपी के सबसे खराब-स्थिति उदाहरणों के रूप में कठिन दिखाया गया है। आदर्श जालक से सिद्ध रूप से सुरक्षित कुशल चिहनक योजनाएँ भी प्रस्तावित की गई हैं, लेकिन आदर्श जालक से कुशल सिद्ध रूप से सुरक्षित सार्वजनिक कुंजी एन्क्रिप्शन का निर्माण करना एक दिलचस्प खुली समस्या थी।

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

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

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

हुबाशेव्स्की और मिकिसियानियोकुशल टकराव प्रतिरोध क्रिप्टोग्राफ़िक हैश फ़ंक्शन का निर्माण दिया जो आदर्श जालक के लिए सबसे छोटी वेक्टर समस्या की सबसे खराब स्थिति के आधार पर सुरक्षित प्रमाणित हो सकता है। उन्होंने क्रिप्टोग्राफ़िक हैश फ़ंक्शन परिवारों को परिभाषित किया: एक वलय $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)$समय पर बहुपद $f$ के उपयुक्त विकल्प के लिए फास्ट फूरियर ट्रांसफॉर्म (FFT) का उपयोग किया जाता है। चूँकि $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}])$ में छोटे वैक्टर ढूँढना (यहां तक ​​कि केवल व्युत्क्रम बहुपद संभाव्यता के साथ) आदर्श जाली पर सबसे खराब स्थिति में विभिन्न जाली समस्याओं (जैसे अनुमानित SVP और 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 घात के बराबर।

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

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

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

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

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

की-जनरेशन एल्गोरिथम:इनपुट: $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$ स्ट्रिंग $r$ में पहले 1 की स्थिति के लिए
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}}))$

आउटपुट: "ACCEPT", इफ $\lVert {\hat {s}}\rVert _{\infty }\leq 10\varphi p^{1/m}n\log ^{2}n$ और ${\hat {s}}={\hat {k}}z+{\hat {l}}$अन्यथा, "REJECT"।

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

क्रिप्टोग्राफ़िक हैश फ़ंक्शन काफी कुशल है और जटिल संख्याओं पर फास्ट फूरियर ट्रांसफॉर्म (FFT) का उपयोग करते हुए ${\tilde {O}}(m)$ समय में असम्बद्ध रूप से गणना की जा सकती है। हालाँकि, व्यवहार में, यह एक पर्याप्त उपरिवहन करता है। मिकिसियानियो और रेगेव द्वारा परिभाषित हैश फ़ंक्शन का एस डब्ल्यू आई एफ एफ टी परिवारअनिवार्य रूप से $\mathbb {Z} _{q}$ में फास्ट फूरियर ट्रांसफॉर्म (FFT) का उपयोग करके उपरोक्त हैश फ़ंक्शन का एक अत्यधिक अनुकूलित संस्करण है। सदिश 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}$ बाद में चुना जाना है। एस डब्ल्यू आई एफ एफ टी क्रिप्टोग्राफ़िक हैश फ़ंक्शन एक कुंजी ${\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}}$है। साथ में, ये दो तथ्य स्थापित करते हैं कि एस डब्ल्यू आई एफ एफ टी में टकराव खोजना अंतर्निहित आदर्श जालक फंक्शन $f_{A}$ में टकराव खोजने के बराबर है, और एस डब्ल्यू आई एफ एफ टी की दावा किया गया टक्कर प्रतिरोध गुण आदर्श जालक पर सबसे खराब स्थिति वाली जालक समस्याओं के संबंध में समर्थित है।

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

• पैरामीटर: पूर्णांक $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 में, जेंट्री पूरी तरह से होमोमोर्फिक एन्क्रिप्शन योजना के निर्माण की समस्या का पहला समाधान प्रस्तावित किया। उनकी योजना आदर्श जालक पर आधारित थी।

यह भी देखें

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