बेंट फलन: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{Short description|Special type of Boolean function}}
{{Short description|Special type of Boolean function}}
[[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 एफ़िन functions)</small>.{{paragraph}}


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


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


यह ज्ञात है कि वी. ए. एलिसेव और ओ. पी. स्टेपचेनकोव ने 1962 में यूएसएसआर में बेंट फलनों का अध्ययन किया, जिसे उन्होंने न्यूनतम कार्य कहा था।<ref name=bent-book/> चूंकि, उनके परिणाम अभी भी सार्वजनिक नहीं किए गए हैं।
यह ज्ञात है कि वी. ए. एलिसेव और ओ. पी. स्टेपचेनकोव ने 1962 में यूएसएसआर में बेंट फलनों का अध्ययन किया, जिसे उन्होंने न्यूनतम कार्य कहा था।<ref name=bent-book/> चूंकि, उनके परिणाम अभी भी सार्वजनिक नहीं किए गए हैं।
Line 19: Line 19:


== [[वॉल्श रूपांतरण]] ==
== [[वॉल्श रूपांतरण]] ==
बेंट फलनफ़ंक्शंस को वॉल्श ट्रांसफ़ॉर्म के संदर्भ में परिभाषित किया गया है। बूलियन फलन का वॉल्श रूपांतरण <math>f:\Z_2^n \to \Z_2</math> कार्य है <math>\hat{f}:\Z_2^n \to \Z</math> द्वारा दिए गए
बेंट फलन को वॉल्श रूपांतरण के संदर्भ में परिभाषित किया गया है। बूलियन फलन का वॉल्श रूपांतरण <math>f:\Z_2^n \to \Z_2</math> फलन है <math>\hat{f}:\Z_2^n \to \Z</math> द्वारा दिए गए
:<math>\hat{f}(a) = \sum_{\scriptstyle{x \in \Z_2^n}} (-1)^{f(x) + a \cdot x}</math>
:<math>\hat{f}(a) = \sum_{\scriptstyle{x \in \Z_2^n}} (-1)^{f(x) + a \cdot x}</math>
कहाँ {{nowrap|1=''a'' · ''x'' = ''a''<sub>1</sub>''x''<sub>1</sub> + ''a''<sub>2</sub>''x''<sub>2</sub> + … + ''a''<sub>''n''</sub>''x''<sub>''n''</sub> (mod 2)}} Z में [[डॉट उत्पाद]] है{{sup sub|''n''|2}}.<ref name=bool/>वैकल्पिक रूप से, चलो {{nowrap|1=''S''<sub>0</sub>(''a'') = { ''x'' ∈ '''Z'''{{sup sub|''n''|2}} : ''f''(''x'') = ''a'' · ''x'' } }} और {{nowrap|1=''S''<sub>1</sub>(''a'') = { ''x'' ∈ '''Z'''{{sup sub|''n''|2}} : ''f''(''x'') ≠ ''a'' · ''x'' } }}. तब {{nowrap|1={{abs|''S''<sub>0</sub>(''a'')}} + {{abs|''S''<sub>1</sub>(''a'')}} = 2<sup>''n''</sup>}} और इसलिए
जहाँ {{nowrap|1=''a'' · ''x'' = ''a''<sub>1</sub>''x''<sub>1</sub> + ''a''<sub>2</sub>''x''<sub>2</sub> + … + ''a''<sub>''n''</sub>''x''<sub>''n''</sub> (mod 2)}} Z{{sup sub|''n''|2}} में [[डॉट उत्पाद]] हैं।<ref name=bool/> वैकल्पिक रूप से, मान लो {{nowrap|1=''S''<sub>0</sub>(''a'') = { ''x'' ∈ '''Z'''{{sup sub|''n''|2}} : ''f''(''x'') = ''a'' · ''x'' } }} और {{nowrap|1=''S''<sub>1</sub>(''a'') = { ''x'' ∈ '''Z'''{{sup sub|''n''|2}} : ''f''(''x'') ≠ ''a'' · ''x'' } }}. तब {{nowrap|1={{abs|''S''<sub>0</sub>(''a'')}} + {{abs|''S''<sub>1</sub>(''a'')}} = 2<sup>''n''</sup>}} और इसलिए
:<math>\hat{f}(a) = \left|S_0(a)\right| - \left|S_1(a)\right| = 2 \left|S_0(a)\right| - 2^n.</math>
:<math>\hat{f}(a) = \left|S_0(a)\right| - \left|S_1(a)\right| = 2 \left|S_0(a)\right| - 2^n.</math>
किसी भी बूलियन फलन के लिए f और {{nowrap|''a'' ∈ '''Z'''{{sup sub|''n''|2}}}} परिवर्तन सीमा में है
किसी भी बूलियन फलन के लिए f और {{nowrap|''a'' ∈ '''Z'''{{sup sub|''n''|2}}}} परिवर्तन सीमा में है
:<math>-2^n \leq \hat{f}(a) \leq 2^n.</math>
:<math>-2^n \leq \hat{f}(a) \leq 2^n.</math>
इसके अतिरिक्त, रैखिक कार्य {{nowrap|1=''f''<sub>0</sub>(''x'') = ''a'' · ''x''}} और affine फलन {{nowrap|1=''f''<sub>1</sub>(''x'') = ''a'' · ''x'' + 1}} दो चरम मामलों के अनुरूप है, क्योंकि
इसके अतिरिक्त, रैखिक कार्य {{nowrap|1=''f''<sub>0</sub>(''x'') = ''a'' · ''x''}} और एफ़िन फलन {{nowrap|1=''f''<sub>1</sub>(''x'') = ''a'' · ''x'' + 1}} दो चरम मामलों के अनुरूप है, क्योंकि
:<math>
:<math>
   \hat{f}_0(a) = 2^n,~
   \hat{f}_0(a) = 2^n,~
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/>


रोथौस ने सिद्ध किया कि बेंट फलन केवल 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> ऐसा है कि
:<math>\hat{f}(a) = \sum_{x \in \mathbb{Z}_m^n} e^{\frac{2\pi i}{m} (f(x) - a \cdot x)}</math>
:<math>\hat{f}(a) = \sum_{x \in \mathbb{Z}_m^n} e^{\frac{2\pi i}{m} (f(x) - a \cdot x)}</math>
स्थिर निरपेक्ष मान 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/>
आंशिक रूप से बेंट कार्य वाल्श परिवर्तन और स्वतःसंबंध फलनों पर शर्त द्वारा परिभाषित बड़े वर्ग का निर्माण करते हैं। सभी एफ़िन और बेंट कार्य आंशिक रूप से बेंट हैं। बदले में यह ''पठार वाले फलनों'' का उचित उपवर्ग है।<ref name=plat/>


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


क्रिप्टोग्राफिक रूप से महत्वपूर्ण फलनों के वर्गों को अन्य संबंधित नाम दिए गए हैं <math>f:\Z_2^n \to \Z_2^n</math>, जैसे लगभग बेंट कार्य और टेढ़े-मेढ़े कार्य। जबकि बेंट कार्य स्वयं नहीं होते हैं (ये बूलियन कार्य भी नहीं होते हैं), वे बेंट फलनों से निकटता से संबंधित होते हैं और अच्छे अरैखिक गुण होते हैं।
क्रिप्टोग्राफिक रूप से महत्वपूर्ण फलनों के वर्गों को अन्य संबंधित नाम दिए गए हैं <math>f:\Z_2^n \to \Z_2^n</math>, जैसे लगभग बेंट कार्य और टेढ़े-मेढ़े कार्य। जबकि बेंट कार्य स्वयं नहीं होते हैं (ये बूलियन कार्य भी नहीं होते हैं), वे बेंट फलनों से निकटता से संबंधित होते हैं और अच्छे अरैखिक गुण होते हैं।

Revision as of 07:16, 5 March 2023

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

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

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

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

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

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