बेंट फलन: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 2: Line 2:
[[File:Boolean functions like 1000 nonlinearity.svg|thumb|[[हैमिंग वजन]] 1 के साथ चार 2-आरी बूलियन फलन मुड़े हुए हैं; यानी, उनकी गैर-रैखिकता 1 है <small>(these Walsh matrices show the Hamming distance to each of the eight linear and affine functions)</small>.{{paragraph}}
[[File:Boolean functions like 1000 nonlinearity.svg|thumb|[[हैमिंग वजन]] 1 के साथ चार 2-आरी बूलियन फलन मुड़े हुए हैं; यानी, उनकी गैर-रैखिकता 1 है <small>(these Walsh matrices show the Hamming distance to each of the eight linear and affine functions)</small>.{{paragraph}}


निम्नलिखित सूत्र से पता चलता है कि एक 2-एरी फलन मुड़ा हुआ है जब इसकी गैर-रैखिकता 1 है:
निम्नलिखित सूत्र से पता चलता है कि 2-एरी फलन मुड़ा हुआ है जब इसकी गैर-रैखिकता 1 है:
{{glossary}}{{defn|<math>2^{2-1} - 2^{\frac{2}{2}-1} = 2 - 1 = 1</math>}}{{glossary end}}]]
{{glossary}}{{defn|<math>2^{2-1} - 2^{\frac{2}{2}-1} = 2 - 1 = 1</math>}}{{glossary end}}]]
[[File:0001 0001 0001 1110 nonlinearity.svg|thumb|बूलियन फलन <math>x_1 x_2 \oplus x_3 x_4</math> झुका है; यानी, इसकी गैर-रैखिकता 6 है <small>(which is what these Walsh Matrices show)</small>.{{paragraph}}
[[File:0001 0001 0001 1110 nonlinearity.svg|thumb|बूलियन फलन <math>x_1 x_2 \oplus x_3 x_4</math> झुका है; यानी, इसकी गैर-रैखिकता 6 है <small>(which is what these Walsh Matrices show)</small>.{{paragraph}}


निम्नलिखित सूत्र से पता चलता है कि एक 4-एरी फलन मुड़ा हुआ है जब इसकी गैर-रैखिकता 6 है:
निम्नलिखित सूत्र से पता चलता है कि 4-एरी फलन मुड़ा हुआ है जब इसकी गैर-रैखिकता 6 है:
{{glossary}}{{defn|<math>2^{4-1} - 2^{\frac{4}{2}-1} = 8-2 = 6</math>}}{{glossary end}}]][[साहचर्य]] के गणित क्षेत्र में, एक मुड़ा हुआ कार्य एक विशेष प्रकार का [[बूलियन समारोह|बूलियन फलन]] है जो अधिकतम गैर-रैखिक है; [[ट्रुथ टेबल]] के बीच [[हैमिंग दूरी]] द्वारा मापे जाने पर यह सभी रैखिक मानचित्र और affine कार्यों के सेट से जितना संभव हो उतना अलग है। ठोस रूप से, इसका अर्थ है कि फलन के आउटपुट और रैखिक फलन के बीच अधिकतम [[सहसंबंध गुणांक]] न्यूनतम है। इसके अलावा, एक बेंट फलन के [[बूलियन व्युत्पन्न]] एक [[संतुलित बूलियन फ़ंक्शन|संतुलित बूलियन फलन]] बूलियन फलन हैं, इसलिए इनपुट चर में किसी भी बदलाव के लिए 50 प्रतिशत संभावना है कि आउटपुट मान बदल जाएगा।
{{glossary}}{{defn|<math>2^{4-1} - 2^{\frac{4}{2}-1} = 8-2 = 6</math>}}{{glossary end}}]][[साहचर्य]] के गणित क्षेत्र में, मुड़ा हुआ कार्य विशेष प्रकार का [[बूलियन समारोह|बूलियन फलन]] है जो अधिकतम गैर-रैखिक है; [[ट्रुथ टेबल]] के बीच [[हैमिंग दूरी]] द्वारा मापे जाने पर यह सभी रैखिक मानचित्र और affine कार्यों के सेट से जितना संभव हो उतना अलग है। ठोस रूप से, इसका अर्थ है कि फलन के आउटपुट और रैखिक फलन के बीच अधिकतम [[सहसंबंध गुणांक]] न्यूनतम है। इसके अलावा, बेंट फलन के [[बूलियन व्युत्पन्न]] [[संतुलित बूलियन फ़ंक्शन|संतुलित बूलियन फलन]] बूलियन फलन हैं, इसलिए इनपुट चर में किसी भी बदलाव के लिए 50 प्रतिशत संभावना है कि आउटपुट मान बदल जाएगा।


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


बेंट फ़ंक्शंस को 1960 के दशक में [[ऑस्कर रोथौस]] द्वारा 1976 तक प्रकाशित नहीं किए गए शोध में परिभाषित और नामित किया गया था।<ref name="rothaus" />[[क्रिप्टोग्राफी]] में उनके अनुप्रयोगों के लिए उनका बड़े पैमाने पर अध्ययन किया गया है, लेकिन [[ रंगावली विस्तार ]], [[ कोडिंग सिद्धांत ]] और [[संयोजन डिजाइन]] के लिए भी लागू किया गया है। परिभाषा को कई तरीकों से विस्तारित किया जा सकता है, जिससे सामान्यीकृत मुड़े हुए कार्यों के विभिन्न वर्ग हो सकते हैं जो मूल के कई उपयोगी गुणों को साझा करते हैं।
बेंट फ़ंक्शंस को 1960 के दशक में [[ऑस्कर रोथौस]] द्वारा 1976 तक प्रकाशित नहीं किए गए शोध में परिभाषित और नामित किया गया था।<ref name="rothaus" />[[क्रिप्टोग्राफी]] में उनके अनुप्रयोगों के लिए उनका बड़े पैमाने पर अध्ययन किया गया है, लेकिन [[ रंगावली विस्तार ]], [[ कोडिंग सिद्धांत ]] और [[संयोजन डिजाइन]] के लिए भी लागू किया गया है। परिभाषा को कई तरीकों से विस्तारित किया जा सकता है, जिससे सामान्यीकृत मुड़े हुए कार्यों के विभिन्न वर्ग हो सकते हैं जो मूल के कई उपयोगी गुणों को साझा करते हैं।
Line 15: Line 15:
यह ज्ञात है कि 1962 में यूएसएसआर में वी। ए। एलिसेव और ओ.पी. स्टेपचेनकोव ने तुला कार्यों का अध्ययन किया, जिसे उन्होंने न्यूनतम कार्य कहा।<ref name=bent-book/>हालांकि, उनके परिणाम अभी भी सार्वजनिक नहीं किए गए हैं।
यह ज्ञात है कि 1962 में यूएसएसआर में वी। ए। एलिसेव और ओ.पी. स्टेपचेनकोव ने तुला कार्यों का अध्ययन किया, जिसे उन्होंने न्यूनतम कार्य कहा।<ref name=bent-book/>हालांकि, उनके परिणाम अभी भी सार्वजनिक नहीं किए गए हैं।


मुड़े हुए कार्यों को पूरी तरह से गैर-रैखिक (पीएन) बूलियन कार्यों के रूप में भी जाना जाता है। कुछ ऐसे कार्य जो पूर्ण अरैखिकता के जितना करीब हो सकते हैं (उदाहरण के लिए बिट्स की एक विषम संख्या के कार्यों के लिए, या सदिश कार्यों के लिए) लगभग पूरी तरह से अरैखिक (APN) के रूप में जाने जाते हैं।<ref>{{Cite journal|last1=Blondeau|last2=Nyberg|date=2015-03-01|title=बिल्कुल सही गैर रेखीय कार्य और क्रिप्टोग्राफी|journal=Finite Fields and Their Applications|language=en|volume=32|pages=120–147|doi=10.1016/j.ffa.2014.10.007|issn=1071-5797|doi-access=free}}</ref>
मुड़े हुए कार्यों को पूरी तरह से गैर-रैखिक (पीएन) बूलियन कार्यों के रूप में भी जाना जाता है। कुछ ऐसे कार्य जो पूर्ण अरैखिकता के जितना करीब हो सकते हैं (उदाहरण के लिए बिट्स की विषम संख्या के कार्यों के लिए, या सदिश कार्यों के लिए) लगभग पूरी तरह से अरैखिक (APN) के रूप में जाने जाते हैं।<ref>{{Cite journal|last1=Blondeau|last2=Nyberg|date=2015-03-01|title=बिल्कुल सही गैर रेखीय कार्य और क्रिप्टोग्राफी|journal=Finite Fields and Their Applications|language=en|volume=32|pages=120–147|doi=10.1016/j.ffa.2014.10.007|issn=1071-5797|doi-access=free}}</ref>




Line 34: Line 34:
== परिभाषा और गुण ==
== परिभाषा और गुण ==


रोथौस ने मुड़े हुए फलन को बूलियन फलन के रूप में परिभाषित किया <math>f:\Z_2^n \to \Z_2</math> जिसका वॉल्श रूपांतरण निरंतर निरपेक्ष मान रखता है। बेंट फ़ंक्शंस एक अर्थ में सभी एफ़िन फ़ंक्शंस से समतुल्य हैं, इसलिए वे किसी भी एफ़िन फलन के साथ अनुमान लगाने में समान रूप से कठिन हैं।
रोथौस ने मुड़े हुए फलन को बूलियन फलन के रूप में परिभाषित किया <math>f:\Z_2^n \to \Z_2</math> जिसका वॉल्श रूपांतरण निरंतर निरपेक्ष मान रखता है। बेंट फ़ंक्शंस अर्थ में सभी एफ़िन फ़ंक्शंस से समतुल्य हैं, इसलिए वे किसी भी एफ़िन फलन के साथ अनुमान लगाने में समान रूप से कठिन हैं।


[[बीजगणितीय सामान्य रूप]] में लिखे गए मुड़े हुए कार्यों के सबसे सरल उदाहरण हैं {{nowrap|''F''(''x''<sub>1</sub>, ''x''<sub>2</sub>) {{=}} ''x''<sub>1</sub>''x''<sub>2</sub>}} और {{nowrap|''G''(''x''<sub>1</sub>, ''x''<sub>2</sub>, ''x''<sub>3</sub>, ''x''<sub>4</sub>) {{=}} ''x''<sub>1</sub>''x''<sub>2</sub> ⊕ ''x''<sub>3</sub>''x''<sub>4</sub>}}. यह पैटर्न जारी है: {{nowrap|''x''<sub>1</sub>''x''<sub>2</sub> ⊕ ''x''<sub>3</sub>''x''<sub>4</sub> ⊕ … ⊕ ''x''<sub>''n''−1</sub>''x''<sub>''n''</sub>}} एक मुड़ा हुआ कार्य है <math>\Z_2^n \to \Z_2</math> प्रत्येक सम n के लिए, लेकिन जैसे-जैसे n बढ़ता है, वैसे-वैसे अन्य मुड़े हुए कार्यों की एक विस्तृत विविधता होती है।<ref name=nonlin/>मानों का क्रम (−1)<sup>f(x)</sup>, के साथ {{nowrap|''x'' ∈ '''Z'''{{sup sub|''n''|2}}}} [[लेक्सिकोग्राफिक ऑर्डर]] में लिया गया है, इसे बेंट अनुक्रम कहा जाता है; बेंट फ़ंक्शंस और बेंट सीक्वेंस में समान गुण होते हैं। इस ±1 रूप में वॉल्श रूपांतरण की गणना आसानी से की जाती है
[[बीजगणितीय सामान्य रूप]] में लिखे गए मुड़े हुए कार्यों के सबसे सरल उदाहरण हैं {{nowrap|''F''(''x''<sub>1</sub>, ''x''<sub>2</sub>) {{=}} ''x''<sub>1</sub>''x''<sub>2</sub>}} और {{nowrap|''G''(''x''<sub>1</sub>, ''x''<sub>2</sub>, ''x''<sub>3</sub>, ''x''<sub>4</sub>) {{=}} ''x''<sub>1</sub>''x''<sub>2</sub> ⊕ ''x''<sub>3</sub>''x''<sub>4</sub>}}. यह पैटर्न जारी है: {{nowrap|''x''<sub>1</sub>''x''<sub>2</sub> ⊕ ''x''<sub>3</sub>''x''<sub>4</sub> ⊕ … ⊕ ''x''<sub>''n''−1</sub>''x''<sub>''n''</sub>}} मुड़ा हुआ कार्य है <math>\Z_2^n \to \Z_2</math> प्रत्येक सम n के लिए, लेकिन जैसे-जैसे n बढ़ता है, वैसे-वैसे अन्य मुड़े हुए कार्यों की विस्तृत विविधता होती है।<ref name=nonlin/>मानों का क्रम (−1)<sup>f(x)</sup>, के साथ {{nowrap|''x'' ∈ '''Z'''{{sup sub|''n''|2}}}} [[लेक्सिकोग्राफिक ऑर्डर]] में लिया गया है, इसे बेंट अनुक्रम कहा जाता है; बेंट फ़ंक्शंस और बेंट सीक्वेंस में समान गुण होते हैं। इस ±1 रूप में वॉल्श रूपांतरण की गणना आसानी से की जाती है
:<math>\hat{f}(a) = W\left(2^n\right) (-1)^{f(a)},</math>
:<math>\hat{f}(a) = W\left(2^n\right) (-1)^{f(a)},</math>
जहां डब्ल्यू (2<sup>n</sup>) प्राकृतिक क्रम वाला [[ वॉल्श मैट्रिक्स ]] है और अनुक्रम को [[कॉलम वेक्टर]] के रूप में माना जाता है।<ref name=dual/>
जहां डब्ल्यू (2<sup>n</sup>) प्राकृतिक क्रम वाला [[ वॉल्श मैट्रिक्स ]] है और अनुक्रम को [[कॉलम वेक्टर]] के रूप में माना जाता है।<ref name=dual/>
Line 42: Line 42:
रोथौस ने सिद्ध किया कि मुड़े हुए फलन केवल n के लिए भी मौजूद होते हैं, और मुड़े हुए फलन f के लिए, <math>\left|\hat{f}(a)\right| = 2^\frac{n}{2}</math> सभी के लिए {{nowrap|''a'' ∈ '''Z'''{{sup sub|''n''|2}}}}.<ref name=bool/>वास्तव में, <math>\hat{f}(a) = 2^\frac{n}{2}(-1)^{g(a)}</math>, जहाँ g भी मुड़ा हुआ है। इस मामले में, <math>\hat{g}(a) = 2^\frac{n}{2}(-1)^{f(a)}</math>, इसलिए f और g को द्वैत (गणित) फलन माना जाता है।<ref name=dual/>
रोथौस ने सिद्ध किया कि मुड़े हुए फलन केवल n के लिए भी मौजूद होते हैं, और मुड़े हुए फलन f के लिए, <math>\left|\hat{f}(a)\right| = 2^\frac{n}{2}</math> सभी के लिए {{nowrap|''a'' ∈ '''Z'''{{sup sub|''n''|2}}}}.<ref name=bool/>वास्तव में, <math>\hat{f}(a) = 2^\frac{n}{2}(-1)^{g(a)}</math>, जहाँ g भी मुड़ा हुआ है। इस मामले में, <math>\hat{g}(a) = 2^\frac{n}{2}(-1)^{f(a)}</math>, इसलिए f और g को द्वैत (गणित) फलन माना जाता है।<ref name=dual/>


प्रत्येक बेंट फलन का एक हैमिंग वजन होता है (जितनी बार यह मान 1 लेता है)। {{nowrap|2<sup>''n''−1</sup> ± 2<sup>{{frac|''n''|2}}−1</sup>}}, और वास्तव में उन दो नंबरों में से किसी एक पर किसी भी एफ़िन फलन से सहमत हैं। तो एफ की गैर-रैखिकता (न्यूनतम संख्या जितनी बार यह किसी भी फलन के बराबर होती है) है {{nowrap|2<sup>''n''−1</sup> − 2<sup>{{frac|''n''|2}}−1</sup>}}, अधिकतम संभव। इसके विपरीत, कोई भी बूलियन अरैखिकता के साथ कार्य करता है {{nowrap|2<sup>''n''−1</sup> − 2<sup>{{frac|''n''|2}}−1</sup>}} झुका है।<ref name=bool/>बीजगणितीय सामान्य रूप में f के बहुपद की डिग्री (जिसे f का अरैखिक क्रम कहा जाता है) अधिकतम है {{frac|''n''|2}} (के लिए {{nowrap|''n'' > 2}}).<ref name=nonlin/>
प्रत्येक बेंट फलन का हैमिंग वजन होता है (जितनी बार यह मान 1 लेता है)। {{nowrap|2<sup>''n''−1</sup> ± 2<sup>{{frac|''n''|2}}−1</sup>}}, और वास्तव में उन दो नंबरों में से किसी पर किसी भी एफ़िन फलन से सहमत हैं। तो एफ की गैर-रैखिकता (न्यूनतम संख्या जितनी बार यह किसी भी फलन के बराबर होती है) है {{nowrap|2<sup>''n''−1</sup> − 2<sup>{{frac|''n''|2}}−1</sup>}}, अधिकतम संभव। इसके विपरीत, कोई भी बूलियन अरैखिकता के साथ कार्य करता है {{nowrap|2<sup>''n''−1</sup> − 2<sup>{{frac|''n''|2}}−1</sup>}} झुका है।<ref name=bool/>बीजगणितीय सामान्य रूप में f के बहुपद की डिग्री (जिसे f का अरैखिक क्रम कहा जाता है) अधिकतम है {{frac|''n''|2}} (के लिए {{nowrap|''n'' > 2}}).<ref name=nonlin/>


हालांकि मुड़े हुए कार्य कई चरों के बूलियन कार्यों में दुर्लभ रूप से दुर्लभ हैं, वे कई अलग-अलग प्रकारों में आते हैं। मुड़े हुए कार्यों के विशेष वर्गों में विस्तृत शोध किया गया है, जैसे [[सजातीय बहुपद]] वाले<ref name=homo/>या जो [[परिमित क्षेत्र]] पर [[एकपद]]ी से उत्पन्न होते हैं,<ref name=mono/>लेकिन अब तक झुके हुए कार्यों ने पूर्ण गणना या वर्गीकरण के सभी प्रयासों को विफल कर दिया है।
हालांकि मुड़े हुए कार्य कई चरों के बूलियन कार्यों में दुर्लभ रूप से दुर्लभ हैं, वे कई अलग-अलग प्रकारों में आते हैं। मुड़े हुए कार्यों के विशेष वर्गों में विस्तृत शोध किया गया है, जैसे [[सजातीय बहुपद]] वाले<ref name=homo/>या जो [[परिमित क्षेत्र]] पर [[एकपद]]ी से उत्पन्न होते हैं,<ref name=mono/>लेकिन अब तक झुके हुए कार्यों ने पूर्ण गणना या वर्गीकरण के सभी प्रयासों को विफल कर दिया है।
Line 54: Line 54:
1982 की शुरुआत में यह पता चला था कि मुड़े हुए कार्यों के आधार पर अधिकतम लंबाई के अनुक्रमों में [[सीडीएमए]] में उपयोग के लिए [[गोल्ड कोड]] और [[ कासमी संहिता ]] के प्रतिद्वंद्विता वाले क्रॉस-सहसंबंध और ऑटोसहसंबंध गुण हैं।<ref name=seq/>स्प्रेड स्पेक्ट्रम तकनीकों में इन अनुक्रमों के कई अनुप्रयोग हैं।
1982 की शुरुआत में यह पता चला था कि मुड़े हुए कार्यों के आधार पर अधिकतम लंबाई के अनुक्रमों में [[सीडीएमए]] में उपयोग के लिए [[गोल्ड कोड]] और [[ कासमी संहिता ]] के प्रतिद्वंद्विता वाले क्रॉस-सहसंबंध और ऑटोसहसंबंध गुण हैं।<ref name=seq/>स्प्रेड स्पेक्ट्रम तकनीकों में इन अनुक्रमों के कई अनुप्रयोग हैं।


मुड़े हुए कार्यों के गुण आधुनिक डिजिटल क्रिप्टोग्राफी में स्वाभाविक रूप से रुचि रखते हैं, जो इनपुट और आउटपुट के बीच संबंधों को अस्पष्ट करना चाहता है। 1988 तक फ़ॉरे ने माना कि किसी फलन के वाल्श रूपांतरण का उपयोग यह दिखाने के लिए किया जा सकता है कि यह [[सख्त हिमस्खलन मानदंड]] (SAC) और उच्च-क्रम के सामान्यीकरण को संतुष्ट करता है, और इस उपकरण की सिफारिश की कि अच्छे [[एस-बॉक्स]] के लिए उम्मीदवारों का चयन करें, जो निकट-परिपूर्ण भ्रम को प्राप्त करें और प्रसार।<ref name=spectral/>वास्तव में, SAC को उच्चतम संभव क्रम में संतुष्ट करने वाले कार्य हमेशा झुके हुए होते हैं।<ref name=sac/>इसके अलावा, मुड़े हुए कार्य जहाँ तक संभव हो, रैखिक संरचना कहलाते हैं, गैर-शून्य वैक्टर ऐसे होते हैं {{nowrap|''f''(''x'' + ''a'') + ''f''(''x'')}} स्थिरांक है। डिफरेंशियल क्रिप्टैनालिसिस की भाषा में (इस संपत्ति की खोज के बाद पेश किया गया) प्रत्येक गैर-अक्षीय बिंदु पर एक बेंट फलन f का व्युत्पन्न (अर्थात, {{nowrap|1=''f''<sub>''a''</sub>(''x'') = ''f''(''x'' + ''a'') + ''f''(''x''))}} एक संतुलित बूलियन फलन बूलियन फलन है, जो प्रत्येक मान को समय से ठीक आधा लेता है। इस संपत्ति को पूर्ण अरैखिकता कहा जाता है।<ref name=nonlin/>
मुड़े हुए कार्यों के गुण आधुनिक डिजिटल क्रिप्टोग्राफी में स्वाभाविक रूप से रुचि रखते हैं, जो इनपुट और आउटपुट के बीच संबंधों को अस्पष्ट करना चाहता है। 1988 तक फ़ॉरे ने माना कि किसी फलन के वाल्श रूपांतरण का उपयोग यह दिखाने के लिए किया जा सकता है कि यह [[सख्त हिमस्खलन मानदंड]] (SAC) और उच्च-क्रम के सामान्यीकरण को संतुष्ट करता है, और इस उपकरण की सिफारिश की कि अच्छे [[एस-बॉक्स]] के लिए उम्मीदवारों का चयन करें, जो निकट-परिपूर्ण भ्रम को प्राप्त करें और प्रसार।<ref name=spectral/>वास्तव में, SAC को उच्चतम संभव क्रम में संतुष्ट करने वाले कार्य हमेशा झुके हुए होते हैं।<ref name=sac/>इसके अलावा, मुड़े हुए कार्य जहाँ तक संभव हो, रैखिक संरचना कहलाते हैं, गैर-शून्य वैक्टर ऐसे होते हैं {{nowrap|''f''(''x'' + ''a'') + ''f''(''x'')}} स्थिरांक है। डिफरेंशियल क्रिप्टैनालिसिस की भाषा में (इस संपत्ति की खोज के बाद पेश किया गया) प्रत्येक गैर-अक्षीय बिंदु पर बेंट फलन f का व्युत्पन्न (अर्थात, {{nowrap|1=''f''<sub>''a''</sub>(''x'') = ''f''(''x'' + ''a'') + ''f''(''x''))}} संतुलित बूलियन फलन बूलियन फलन है, जो प्रत्येक मान को समय से ठीक आधा लेता है। इस संपत्ति को पूर्ण अरैखिकता कहा जाता है।<ref name=nonlin/>


इस तरह के अच्छे प्रसार गुणों को देखते हुए, विभेदक क्रिप्टैनालिसिस के लिए स्पष्ट रूप से पूर्ण प्रतिरोध, और रैखिक क्रिप्टैनालिसिस के लिए परिभाषा के अनुसार प्रतिरोध, बेंट फ़ंक्शंस पहले एस-बॉक्स जैसे सुरक्षित क्रिप्टोग्राफ़िक फ़ंक्शंस के लिए आदर्श विकल्प प्रतीत हो सकते हैं। उनका घातक दोष यह है कि वे संतुलित होने में विफल रहते हैं। विशेष रूप से, एक इन्वर्टिबल एस-बॉक्स को सीधे बेंट फ़ंक्शंस से नहीं बनाया जा सकता है, और एक बेंट कॉम्बिनेशन फलन का उपयोग करके एक [[स्ट्रीम सिफर]] एक सहसंबंध हमले के लिए असुरक्षित है। इसके बजाय, कोई बेंट फलन के साथ शुरू हो सकता है और परिणाम संतुलित होने तक बेतरतीब ढंग से उचित मूल्यों को पूरक कर सकता है। संशोधित फलन में अभी भी उच्च गैर-रैखिकता है, और इस तरह के कार्य बहुत दुर्लभ हैं, प्रक्रिया एक क्रूर-बल खोज की तुलना में बहुत तेज होनी चाहिए।<ref name=nonlin/>लेकिन इस तरह से निर्मित कार्य अन्य वांछनीय गुणों को खो सकते हैं, यहां तक ​​कि एसएसी को संतुष्ट करने में असफल होने पर भी - इसलिए सावधानीपूर्वक परीक्षण आवश्यक है।<ref name=sac/>कई क्रिप्टोग्राफ़रों ने संतुलित कार्यों को उत्पन्न करने के लिए तकनीकों पर काम किया है जो जितना संभव हो उतने अच्छे क्रिप्टोग्राफ़िक गुणों को बनाए रखता है।<ref name=nyberg/><ref name=highly/><ref name=cast/>
इस तरह के अच्छे प्रसार गुणों को देखते हुए, विभेदक क्रिप्टैनालिसिस के लिए स्पष्ट रूप से पूर्ण प्रतिरोध, और रैखिक क्रिप्टैनालिसिस के लिए परिभाषा के अनुसार प्रतिरोध, बेंट फ़ंक्शंस पहले एस-बॉक्स जैसे सुरक्षित क्रिप्टोग्राफ़िक फ़ंक्शंस के लिए आदर्श विकल्प प्रतीत हो सकते हैं। उनका घातक दोष यह है कि वे संतुलित होने में विफल रहते हैं। विशेष रूप से, इन्वर्टिबल एस-बॉक्स को सीधे बेंट फ़ंक्शंस से नहीं बनाया जा सकता है, और बेंट कॉम्बिनेशन फलन का उपयोग करके [[स्ट्रीम सिफर]] सहसंबंध हमले के लिए असुरक्षित है। इसके बजाय, कोई बेंट फलन के साथ शुरू हो सकता है और परिणाम संतुलित होने तक बेतरतीब ढंग से उचित मूल्यों को पूरक कर सकता है। संशोधित फलन में अभी भी उच्च गैर-रैखिकता है, और इस तरह के कार्य बहुत दुर्लभ हैं, प्रक्रिया क्रूर-बल खोज की तुलना में बहुत तेज होनी चाहिए।<ref name=nonlin/>लेकिन इस तरह से निर्मित कार्य अन्य वांछनीय गुणों को खो सकते हैं, यहां तक ​​कि एसएसी को संतुष्ट करने में असफल होने पर भी - इसलिए सावधानीपूर्वक परीक्षण आवश्यक है।<ref name=sac/>कई क्रिप्टोग्राफ़रों ने संतुलित कार्यों को उत्पन्न करने के लिए तकनीकों पर काम किया है जो जितना संभव हो उतने अच्छे क्रिप्टोग्राफ़िक गुणों को बनाए रखता है।<ref name=nyberg/><ref name=highly/><ref name=cast/>


इस सैद्धांतिक शोध में से कुछ को वास्तविक क्रिप्टोग्राफिक एल्गोरिदम में शामिल किया गया है। [[ब्लॉक सिफर]] [[CAST-128]] और [[CAST-256]] के लिए S-बॉक्स बनाने के लिए [[कार्लिस्ले एडम्स]] और [[स्टैफ़ोर्ड तवारेस]] द्वारा उपयोग की जाने वाली CAST डिज़ाइन प्रक्रिया, मुड़े हुए कार्यों का उपयोग करती है।<ref name=cast/>[[क्रिप्टोग्राफ़िक हैश फ़ंक्शन|क्रिप्टोग्राफ़िक हैश फलन]] [[HAVAL]] छह चरों पर मुड़े हुए कार्यों के सभी चार समतुल्य वर्गों के प्रतिनिधियों से निर्मित बूलियन फ़ंक्शंस का उपयोग करता है।<ref name=haval/>स्ट्रीम सिफर [[ अनाज (सिफर) ]] एक [[एनएलएफएसआर]] का उपयोग करता है जिसका गैर-रैखिक प्रतिक्रिया बहुपद डिजाइन द्वारा, एक मुड़े हुए कार्य और एक रैखिक कार्य का योग है।<ref name=grain/>
इस सैद्धांतिक शोध में से कुछ को वास्तविक क्रिप्टोग्राफिक एल्गोरिदम में शामिल किया गया है। [[ब्लॉक सिफर]] [[CAST-128]] और [[CAST-256]] के लिए S-बॉक्स बनाने के लिए [[कार्लिस्ले एडम्स]] और [[स्टैफ़ोर्ड तवारेस]] द्वारा उपयोग की जाने वाली CAST डिज़ाइन प्रक्रिया, मुड़े हुए कार्यों का उपयोग करती है।<ref name=cast/>[[क्रिप्टोग्राफ़िक हैश फ़ंक्शन|क्रिप्टोग्राफ़िक हैश फलन]] [[HAVAL]] छह चरों पर मुड़े हुए कार्यों के सभी चार समतुल्य वर्गों के प्रतिनिधियों से निर्मित बूलियन फ़ंक्शंस का उपयोग करता है।<ref name=haval/>स्ट्रीम सिफर [[ अनाज (सिफर) ]] [[एनएलएफएसआर]] का उपयोग करता है जिसका गैर-रैखिक प्रतिक्रिया बहुपद डिजाइन द्वारा, मुड़े हुए कार्य और रैखिक कार्य का योग है।<ref name=grain/>




== सामान्यीकरण ==
== सामान्यीकरण ==


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


सामान्यीकृत झुकाव कार्यों का सबसे आम वर्ग मॉड्यूलर अंकगणितीय प्रकार है, <math>f:\mathbb{Z}_m^n \to \mathbb{Z}_m</math> ऐसा है कि
सामान्यीकृत झुकाव कार्यों का सबसे आम वर्ग मॉड्यूलर अंकगणितीय प्रकार है, <math>f:\mathbb{Z}_m^n \to \mathbb{Z}_m</math> ऐसा है कि
Line 69: Line 69:
स्थिर निरपेक्ष मान m है<sup>n/2</sup>. बिल्कुल सही गैर रेखीय कार्य <math>f:\mathbb{Z}_m^n \to \mathbb{Z}_m</math>, वे ऐसे कि सभी अशून्य a के लिए, {{nowrap|''f''(''x'' + ''a'') − ''f''(''a'')}} प्रत्येक मान लेता है {{nowrap|''m''<sup>''n'' − 1</sup>}} बार, सामान्यीकृत मुड़े हुए हैं। यदि m [[अभाज्य संख्या]] है, तो इसका विलोम सत्य है। ज्यादातर मामलों में केवल प्रधान एम माना जाता है। विषम अभाज्य m के लिए, प्रत्येक सकारात्मक n, सम और विषम के लिए सामान्यीकृत मुड़े हुए कार्य हैं। उनके पास बाइनरी बेंट फ़ंक्शंस के समान कई अच्छे क्रिप्टोग्राफ़िक गुण हैं।<ref name=nyberg2/><ref name=gbf2/>
स्थिर निरपेक्ष मान m है<sup>n/2</sup>. बिल्कुल सही गैर रेखीय कार्य <math>f:\mathbb{Z}_m^n \to \mathbb{Z}_m</math>, वे ऐसे कि सभी अशून्य a के लिए, {{nowrap|''f''(''x'' + ''a'') − ''f''(''a'')}} प्रत्येक मान लेता है {{nowrap|''m''<sup>''n'' − 1</sup>}} बार, सामान्यीकृत मुड़े हुए हैं। यदि m [[अभाज्य संख्या]] है, तो इसका विलोम सत्य है। ज्यादातर मामलों में केवल प्रधान एम माना जाता है। विषम अभाज्य m के लिए, प्रत्येक सकारात्मक n, सम और विषम के लिए सामान्यीकृत मुड़े हुए कार्य हैं। उनके पास बाइनरी बेंट फ़ंक्शंस के समान कई अच्छे क्रिप्टोग्राफ़िक गुण हैं।<ref name=nyberg2/><ref name=gbf2/>


सेमी-बेंट फ़ंक्शंस, बेंट फ़ंक्शंस के लिए एक विषम-क्रम समकक्ष हैं। एक सेमी-बेंट फंक्शन है <math>f:\mathbb{Z}_m^n \to \mathbb{Z}_m</math> n विषम के साथ, जैसे कि <math>\left|\hat{f}\right|</math> केवल मान 0 और m लेता है<sup>(एन+1)/2</sup>. उनके पास अच्छी क्रिप्टोग्राफिक विशेषताएँ भी हैं, और उनमें से कुछ संतुलित हैं, सभी संभावित मूल्यों को समान रूप से अक्सर लेते हैं।<ref name=semi/>
सेमी-बेंट फ़ंक्शंस, बेंट फ़ंक्शंस के लिए विषम-क्रम समकक्ष हैं। सेमी-बेंट फंक्शन है <math>f:\mathbb{Z}_m^n \to \mathbb{Z}_m</math> n विषम के साथ, जैसे कि <math>\left|\hat{f}\right|</math> केवल मान 0 और m लेता है<sup>(एन+1)/2</sup>. उनके पास अच्छी क्रिप्टोग्राफिक विशेषताएँ भी हैं, और उनमें से कुछ संतुलित हैं, सभी संभावित मूल्यों को समान रूप से अक्सर लेते हैं।<ref name=semi/>


आंशिक रूप से मुड़े हुए कार्य वाल्श परिवर्तन और स्वतःसंबंध कार्यों पर एक शर्त द्वारा परिभाषित एक बड़े वर्ग का निर्माण करते हैं। सभी affine और मुड़े हुए कार्य आंशिक रूप से मुड़े हुए हैं। बदले में यह ''पठार वाले कार्यों'' का एक उचित उपवर्ग है।<ref name=plat/>
आंशिक रूप से मुड़े हुए कार्य वाल्श परिवर्तन और स्वतःसंबंध कार्यों पर शर्त द्वारा परिभाषित बड़े वर्ग का निर्माण करते हैं। सभी affine और मुड़े हुए कार्य आंशिक रूप से मुड़े हुए हैं। बदले में यह ''पठार वाले कार्यों'' का उचित उपवर्ग है।<ref name=plat/>


हाइपर-बेंट फ़ंक्शंस के पीछे का विचार परिमित फ़ील्ड GF(2) पर [[द्विभाजन]] मोनोमियल्स से आने वाले ''सभी'' बूलियन फ़ंक्शंस की न्यूनतम दूरी को अधिकतम करना है<sup>n</sup>), न केवल affine कार्य करता है। इन कार्यों के लिए यह दूरी स्थिर है, जो उन्हें प्रक्षेप हमले के लिए प्रतिरोधी बना सकती है।
हाइपर-बेंट फ़ंक्शंस के पीछे का विचार परिमित फ़ील्ड GF(2) पर [[द्विभाजन]] मोनोमियल्स से आने वाले ''सभी'' बूलियन फ़ंक्शंस की न्यूनतम दूरी को अधिकतम करना है<sup>n</sup>), न केवल affine कार्य करता है। इन कार्यों के लिए यह दूरी स्थिर है, जो उन्हें प्रक्षेप हमले के लिए प्रतिरोधी बना सकती है।

Revision as of 06:23, 5 March 2023

हैमिंग वजन 1 के साथ चार 2-आरी बूलियन फलन मुड़े हुए हैं; यानी, उनकी गैर-रैखिकता 1 है (these Walsh matrices show the Hamming distance to each of the eight linear and affine functions).
निम्नलिखित सूत्र से पता चलता है कि 2-एरी फलन मुड़ा हुआ है जब इसकी गैर-रैखिकता 1 है:
बूलियन फलन झुका है; यानी, इसकी गैर-रैखिकता 6 है (which is what these Walsh Matrices show).
निम्नलिखित सूत्र से पता चलता है कि 4-एरी फलन मुड़ा हुआ है जब इसकी गैर-रैखिकता 6 है:

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

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

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

यह ज्ञात है कि 1962 में यूएसएसआर में वी। ए। एलिसेव और ओ.पी. स्टेपचेनकोव ने तुला कार्यों का अध्ययन किया, जिसे उन्होंने न्यूनतम कार्य कहा।[2]हालांकि, उनके परिणाम अभी भी सार्वजनिक नहीं किए गए हैं।

मुड़े हुए कार्यों को पूरी तरह से गैर-रैखिक (पीएन) बूलियन कार्यों के रूप में भी जाना जाता है। कुछ ऐसे कार्य जो पूर्ण अरैखिकता के जितना करीब हो सकते हैं (उदाहरण के लिए बिट्स की विषम संख्या के कार्यों के लिए, या सदिश कार्यों के लिए) लगभग पूरी तरह से अरैखिक (APN) के रूप में जाने जाते हैं।[3]


वॉल्श रूपांतरण

बेंट फ़ंक्शंस को वॉल्श ट्रांसफ़ॉर्म के संदर्भ में परिभाषित किया गया है। बूलियन फलन का वॉल्श रूपांतरण कार्य है द्वारा दिए गए

कहाँ a · x = a1x1 + a2x2 + … + anxn (mod 2) Z में डॉट उत्पाद हैn
2.[4]वैकल्पिक रूप से, चलो S0(a) = { x ∈ Zn
2 : f(x) = a · x } और S1(a) = { x ∈ Zn
2 : f(x) ≠ a · x }. तब |S0(a)| + |S1(a)| = 2n और इसलिए

किसी भी बूलियन फलन के लिए f और a ∈ Zn
2 परिवर्तन सीमा में है

इसके अलावा, रैखिक कार्य f0(x) = a · x और affine फलन f1(x) = a · x + 1 दो चरम मामलों के अनुरूप है, क्योंकि

इस प्रकार, प्रत्येक के लिए a ∈ Zn
2 का मान है यह दर्शाता है कि फलन f(x) f से श्रेणी में कहाँ स्थित है0(एक्स) से एफ1(एक्स)।

परिभाषा और गुण

रोथौस ने मुड़े हुए फलन को बूलियन फलन के रूप में परिभाषित किया जिसका वॉल्श रूपांतरण निरंतर निरपेक्ष मान रखता है। बेंट फ़ंक्शंस अर्थ में सभी एफ़िन फ़ंक्शंस से समतुल्य हैं, इसलिए वे किसी भी एफ़िन फलन के साथ अनुमान लगाने में समान रूप से कठिन हैं।

बीजगणितीय सामान्य रूप में लिखे गए मुड़े हुए कार्यों के सबसे सरल उदाहरण हैं F(x1, x2) = x1x2 और G(x1, x2, x3, x4) = x1x2 ⊕ x3x4. यह पैटर्न जारी है: x1x2 ⊕ x3x4 ⊕ … ⊕ xn−1xn मुड़ा हुआ कार्य है प्रत्येक सम n के लिए, लेकिन जैसे-जैसे n बढ़ता है, वैसे-वैसे अन्य मुड़े हुए कार्यों की विस्तृत विविधता होती है।[5]मानों का क्रम (−1)f(x), के साथ x ∈ Zn
2 लेक्सिकोग्राफिक ऑर्डर में लिया गया है, इसे बेंट अनुक्रम कहा जाता है; बेंट फ़ंक्शंस और बेंट सीक्वेंस में समान गुण होते हैं। इस ±1 रूप में वॉल्श रूपांतरण की गणना आसानी से की जाती है

जहां डब्ल्यू (2n) प्राकृतिक क्रम वाला वॉल्श मैट्रिक्स है और अनुक्रम को कॉलम वेक्टर के रूप में माना जाता है।[6]

रोथौस ने सिद्ध किया कि मुड़े हुए फलन केवल n के लिए भी मौजूद होते हैं, और मुड़े हुए फलन f के लिए, सभी के लिए a ∈ Zn
2.[4]वास्तव में, , जहाँ g भी मुड़ा हुआ है। इस मामले में, , इसलिए f और g को द्वैत (गणित) फलन माना जाता है।[6]

प्रत्येक बेंट फलन का हैमिंग वजन होता है (जितनी बार यह मान 1 लेता है)। 2n−1 ± 2n⁄2−1, और वास्तव में उन दो नंबरों में से किसी पर किसी भी एफ़िन फलन से सहमत हैं। तो एफ की गैर-रैखिकता (न्यूनतम संख्या जितनी बार यह किसी भी फलन के बराबर होती है) है 2n−1 − 2n⁄2−1, अधिकतम संभव। इसके विपरीत, कोई भी बूलियन अरैखिकता के साथ कार्य करता है 2n−1 − 2n⁄2−1 झुका है।[4]बीजगणितीय सामान्य रूप में f के बहुपद की डिग्री (जिसे f का अरैखिक क्रम कहा जाता है) अधिकतम है n⁄2 (के लिए n > 2).[5]

हालांकि मुड़े हुए कार्य कई चरों के बूलियन कार्यों में दुर्लभ रूप से दुर्लभ हैं, वे कई अलग-अलग प्रकारों में आते हैं। मुड़े हुए कार्यों के विशेष वर्गों में विस्तृत शोध किया गया है, जैसे सजातीय बहुपद वाले[7]या जो परिमित क्षेत्र पर एकपदी से उत्पन्न होते हैं,[8]लेकिन अब तक झुके हुए कार्यों ने पूर्ण गणना या वर्गीकरण के सभी प्रयासों को विफल कर दिया है।

निर्माण

बेंट कार्यों के लिए कई प्रकार के निर्माण होते हैं।[2]* कॉम्बिनेटरियल कंस्ट्रक्शन: इटरेटिव कंस्ट्रक्शन, मैओराना-मैकफारलैंड कंस्ट्रक्शन, आंशिक स्प्रेड, डिलन और डॉबर्टिन के बेंट फंक्शन, मिन्टरम बेंट फंक्शन, बेंट इटरेटिव फंक्शन

  • बीजगणितीय निर्माण: गोल्ड, डिलन, कासमी, कैंटो-लिएंडर और कैंटो-चारपिन-कुयरेघ्यान के प्रतिपादकों के साथ मोनोमियल बेंट फलन; निहो तुला कार्य, आदि।

अनुप्रयोग

1982 की शुरुआत में यह पता चला था कि मुड़े हुए कार्यों के आधार पर अधिकतम लंबाई के अनुक्रमों में सीडीएमए में उपयोग के लिए गोल्ड कोड और कासमी संहिता के प्रतिद्वंद्विता वाले क्रॉस-सहसंबंध और ऑटोसहसंबंध गुण हैं।[9]स्प्रेड स्पेक्ट्रम तकनीकों में इन अनुक्रमों के कई अनुप्रयोग हैं।

मुड़े हुए कार्यों के गुण आधुनिक डिजिटल क्रिप्टोग्राफी में स्वाभाविक रूप से रुचि रखते हैं, जो इनपुट और आउटपुट के बीच संबंधों को अस्पष्ट करना चाहता है। 1988 तक फ़ॉरे ने माना कि किसी फलन के वाल्श रूपांतरण का उपयोग यह दिखाने के लिए किया जा सकता है कि यह सख्त हिमस्खलन मानदंड (SAC) और उच्च-क्रम के सामान्यीकरण को संतुष्ट करता है, और इस उपकरण की सिफारिश की कि अच्छे एस-बॉक्स के लिए उम्मीदवारों का चयन करें, जो निकट-परिपूर्ण भ्रम को प्राप्त करें और प्रसार।[10]वास्तव में, SAC को उच्चतम संभव क्रम में संतुष्ट करने वाले कार्य हमेशा झुके हुए होते हैं।[11]इसके अलावा, मुड़े हुए कार्य जहाँ तक संभव हो, रैखिक संरचना कहलाते हैं, गैर-शून्य वैक्टर ऐसे होते हैं f(x + a) + f(x) स्थिरांक है। डिफरेंशियल क्रिप्टैनालिसिस की भाषा में (इस संपत्ति की खोज के बाद पेश किया गया) प्रत्येक गैर-अक्षीय बिंदु पर बेंट फलन f का व्युत्पन्न (अर्थात, fa(x) = f(x + a) + f(x)) संतुलित बूलियन फलन बूलियन फलन है, जो प्रत्येक मान को समय से ठीक आधा लेता है। इस संपत्ति को पूर्ण अरैखिकता कहा जाता है।[5]

इस तरह के अच्छे प्रसार गुणों को देखते हुए, विभेदक क्रिप्टैनालिसिस के लिए स्पष्ट रूप से पूर्ण प्रतिरोध, और रैखिक क्रिप्टैनालिसिस के लिए परिभाषा के अनुसार प्रतिरोध, बेंट फ़ंक्शंस पहले एस-बॉक्स जैसे सुरक्षित क्रिप्टोग्राफ़िक फ़ंक्शंस के लिए आदर्श विकल्प प्रतीत हो सकते हैं। उनका घातक दोष यह है कि वे संतुलित होने में विफल रहते हैं। विशेष रूप से, इन्वर्टिबल एस-बॉक्स को सीधे बेंट फ़ंक्शंस से नहीं बनाया जा सकता है, और बेंट कॉम्बिनेशन फलन का उपयोग करके स्ट्रीम सिफर सहसंबंध हमले के लिए असुरक्षित है। इसके बजाय, कोई बेंट फलन के साथ शुरू हो सकता है और परिणाम संतुलित होने तक बेतरतीब ढंग से उचित मूल्यों को पूरक कर सकता है। संशोधित फलन में अभी भी उच्च गैर-रैखिकता है, और इस तरह के कार्य बहुत दुर्लभ हैं, प्रक्रिया क्रूर-बल खोज की तुलना में बहुत तेज होनी चाहिए।[5]लेकिन इस तरह से निर्मित कार्य अन्य वांछनीय गुणों को खो सकते हैं, यहां तक ​​कि एसएसी को संतुष्ट करने में असफल होने पर भी - इसलिए सावधानीपूर्वक परीक्षण आवश्यक है।[11]कई क्रिप्टोग्राफ़रों ने संतुलित कार्यों को उत्पन्न करने के लिए तकनीकों पर काम किया है जो जितना संभव हो उतने अच्छे क्रिप्टोग्राफ़िक गुणों को बनाए रखता है।[12][13][14]

इस सैद्धांतिक शोध में से कुछ को वास्तविक क्रिप्टोग्राफिक एल्गोरिदम में शामिल किया गया है। ब्लॉक सिफर CAST-128 और CAST-256 के लिए S-बॉक्स बनाने के लिए कार्लिस्ले एडम्स और स्टैफ़ोर्ड तवारेस द्वारा उपयोग की जाने वाली CAST डिज़ाइन प्रक्रिया, मुड़े हुए कार्यों का उपयोग करती है।[14]क्रिप्टोग्राफ़िक हैश फलन HAVAL छह चरों पर मुड़े हुए कार्यों के सभी चार समतुल्य वर्गों के प्रतिनिधियों से निर्मित बूलियन फ़ंक्शंस का उपयोग करता है।[15]स्ट्रीम सिफर अनाज (सिफर) एनएलएफएसआर का उपयोग करता है जिसका गैर-रैखिक प्रतिक्रिया बहुपद डिजाइन द्वारा, मुड़े हुए कार्य और रैखिक कार्य का योग है।[16]


सामान्यीकरण

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

सामान्यीकृत झुकाव कार्यों का सबसे आम वर्ग मॉड्यूलर अंकगणितीय प्रकार है, ऐसा है कि

स्थिर निरपेक्ष मान m हैn/2. बिल्कुल सही गैर रेखीय कार्य , वे ऐसे कि सभी अशून्य a के लिए, f(x + a) − f(a) प्रत्येक मान लेता है mn − 1 बार, सामान्यीकृत मुड़े हुए हैं। यदि m अभाज्य संख्या है, तो इसका विलोम सत्य है। ज्यादातर मामलों में केवल प्रधान एम माना जाता है। विषम अभाज्य m के लिए, प्रत्येक सकारात्मक n, सम और विषम के लिए सामान्यीकृत मुड़े हुए कार्य हैं। उनके पास बाइनरी बेंट फ़ंक्शंस के समान कई अच्छे क्रिप्टोग्राफ़िक गुण हैं।[17][18]

सेमी-बेंट फ़ंक्शंस, बेंट फ़ंक्शंस के लिए विषम-क्रम समकक्ष हैं। सेमी-बेंट फंक्शन है n विषम के साथ, जैसे कि केवल मान 0 और m लेता है(एन+1)/2. उनके पास अच्छी क्रिप्टोग्राफिक विशेषताएँ भी हैं, और उनमें से कुछ संतुलित हैं, सभी संभावित मूल्यों को समान रूप से अक्सर लेते हैं।[19]

आंशिक रूप से मुड़े हुए कार्य वाल्श परिवर्तन और स्वतःसंबंध कार्यों पर शर्त द्वारा परिभाषित बड़े वर्ग का निर्माण करते हैं। सभी affine और मुड़े हुए कार्य आंशिक रूप से मुड़े हुए हैं। बदले में यह पठार वाले कार्यों का उचित उपवर्ग है।[20]

हाइपर-बेंट फ़ंक्शंस के पीछे का विचार परिमित फ़ील्ड GF(2) पर द्विभाजन मोनोमियल्स से आने वाले सभी बूलियन फ़ंक्शंस की न्यूनतम दूरी को अधिकतम करना हैn), न केवल affine कार्य करता है। इन कार्यों के लिए यह दूरी स्थिर है, जो उन्हें प्रक्षेप हमले के लिए प्रतिरोधी बना सकती है।

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

यह भी देखें

संदर्भ

  1. ↑ O. S. Rothaus (May 1976). "On "Bent" Functions". Journal of Combinatorial Theory, Series A. 20 (3): 300–305. doi:10.1016/0097-3165(76)90024-8. ISSN 0097-3165.
  2. ↑ 2.0 2.1 2.2 N. Tokareva (2015). Bent functions: results and applications to cryptography. Academic Press. ISBN 9780128023181.
  3. ↑ Blondeau; Nyberg (2015-03-01). "बिल्कुल सही गैर रेखीय कार्य और क्रिप्टोग्राफी". Finite Fields and Their Applications (in English). 32: 120–147. doi:10.1016/j.ffa.2014.10.007. ISSN 1071-5797.
  4. ↑ 4.0 4.1 4.2 C. Qu; J. Seberry; T. Xia (29 December 2001). "Boolean Functions in Cryptography". Retrieved 14 September 2009. {{cite journal}}: Cite journal requires |journal= (help)
  5. ↑ 5.0 5.1 5.2 5.3 W. Meier; O. Staffelbach (April 1989). Nonlinearity Criteria for Cryptographic Functions. Eurocrypt '89. pp. 549–562.
  6. ↑ 6.0 6.1 C. Carlet; L.E. Danielsen; M.G. Parker; P. Solé (19 May 2008). Self Dual Bent Functions (PDF). Fourth International Workshop on Boolean Functions: Cryptography and Applications (BFCA '08). Retrieved 21 September 2009.
  7. ↑ T. Xia; J. Seberry; J. Pieprzyk; C. Charnes (June 2004). "Homogeneous bent functions of degree n in 2n variables do not exist for n > 3". Discrete Applied Mathematics. 142 (1–3): 127–132. doi:10.1016/j.dam.2004.02.006. ISSN 0166-218X. Retrieved 21 September 2009.
  8. ↑ A. Canteaut; P. Charpin; G. Kyureghyan (January 2008). "A new class of monomial bent functions" (PDF). Finite Fields and Their Applications. 14 (1): 221–241. doi:10.1016/j.ffa.2007.02.004. ISSN 1071-5797. Archived from the original (PDF) on 21 July 2011. Retrieved 21 September 2009.
  9. ↑ J. Olsen; R. Scholtz; L. Welch (November 1982). "Bent-Function Sequences". IEEE Transactions on Information Theory. IT-28 (6): 858–864. doi:10.1109/tit.1982.1056589. ISSN 0018-9448. Archived from the original on 22 July 2011. Retrieved 24 September 2009.
  10. ↑ R. Forré (August 1988). The Strict Avalanche Criterion: Spectral Properties of Boolean Functions and an Extended Definition. CRYPTO '88. pp. 450–468.
  11. ↑ 11.0 11.1 C. Adams; S. Tavares (January 1990). "The Use of Bent Sequences to Achieve Higher-Order Strict Avalanche Criterion in S-box Design". Technical Report TR 90-013. Queen's University. CiteSeerX 10.1.1.41.8374. {{cite journal}}: Cite journal requires |journal= (help)
  12. ↑ K. Nyberg (April 1991). Perfect nonlinear S-boxes. Eurocrypt '91. pp. 378–386.
  13. ↑ J. Seberry; X. Zhang (December 1992). Highly Nonlinear 0–1 Balanced Boolean Functions Satisfying Strict Avalanche Criterion. AUSCRYPT '92. pp. 143–155. CiteSeerX 10.1.1.57.4992.
  14. ↑ 14.0 14.1 C. Adams (November 1997). "Constructing Symmetric Ciphers Using the CAST Design Procedure". Designs, Codes and Cryptography. 12 (3): 283–316. doi:10.1023/A:1008229029587. ISSN 0925-1022. S2CID 14365543. Archived from the original on 26 October 2008. Retrieved 20 September 2009.
  15. ↑ Y. Zheng; J. Pieprzyk; J. Seberry (December 1992). HAVAL – a one-way hashing algorithm with variable length of output. AUSCRYPT '92. pp. 83–104. Retrieved 20 June 2015.
  16. ↑ M. Hell; T. Johansson; A. Maximov; W. Meier. "A Stream Cipher Proposal: Grain-128" (PDF). Retrieved 24 September 2009. {{cite journal}}: Cite journal requires |journal= (help)
  17. ↑ K. Nyberg (May 1990). Constructions of bent functions and difference sets. Eurocrypt '90. pp. 151–160.
  18. ↑ Shashi Kant Pandey; B.K. Dass (September 2017). "On Walsh Spectrum of Cryptographic Boolean Function". Defence Science Journal. 67 (5): 536–541. doi:10.14429/dsj.67.10638. ISSN 0011-748X.
  19. ↑ K. Khoo; G. Gong; D. Stinson (February 2006). "A new characterization of semi-bent and bent functions on finite fields" (PostScript). Designs, Codes and Cryptography. 38 (2): 279–295. CiteSeerX 10.1.1.10.6303. doi:10.1007/s10623-005-6345-x. ISSN 0925-1022. S2CID 10572850. Retrieved 24 September 2009.
  20. ↑ Y. Zheng; X. Zhang (November 1999). Plateaued Functions. Second International Conference on Information and Communication Security (ICICS '99). pp. 284–300. Retrieved 24 September 2009.


अग्रिम पठन

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=बेंट_फलन&oldid=110326’