बेंट फलन: 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-आरी बूलियन फलन | [[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 है: | ||
| Line 7: | Line 7: | ||
निम्नलिखित सूत्र से पता चलता है कि 4-एरी फलन मुड़ा हुआ है जब इसकी गैर-रैखिकता 6 है: | निम्नलिखित सूत्र से पता चलता है कि 4-एरी फलन मुड़ा हुआ है जब इसकी गैर-रैखिकता 6 है: | ||
{{glossary}}{{defn|<math>2^{4-1} - 2^{\frac{4}{2}-1} = 8-2 = 6</math>}}{{glossary end}}]][[साहचर्य]] के गणित क्षेत्र में, | {{glossary}}{{defn|<math>2^{4-1} - 2^{\frac{4}{2}-1} = 8-2 = 6</math>}}{{glossary end}}]][[साहचर्य]] के गणित क्षेत्र में, बेंट फलन एक विशेष प्रकार का [[बूलियन समारोह|बूलियन फलन]] है जो अधिकतम गैर-रैखिक होता है; यह [[ट्रुथ टेबल|सत्य तालिकाओं]] के बीच [[हैमिंग दूरी]] द्वारा मापा जाने पर सभी रैखिक और एफ़िन फलनों के सेट से जितना संभव हो उतना अलग होता है। ठोस रूप से, इसका अर्थ है कि फलन के आउटपुट और रैखिक फलन के बीच अधिकतम [[सहसंबंध गुणांक]] न्यूनतम है। इसके अतिरिक्त, बेंट फलन के [[बूलियन व्युत्पन्न]] [[संतुलित बूलियन फ़ंक्शन|संतुलित बूलियन फलन]] हैं, इसलिए इनपुट चर में किसी भी बदलाव के लिए 50 प्रतिशत संभावना है कि आउटपुट मान बदल जाता हैं। | ||
अधिकतम गैर-रैखिकता का अर्थ है एफाइन (रैखिक) फलन द्वारा | अधिकतम गैर-रैखिकता का अर्थ है एफाइन (रैखिक) फलन द्वारा बेंट फलन का अनुमान लगाना कठिन है, [[रैखिक क्रिप्ट विश्लेषण]] के विरुद्ध बचाव में उपयोगी गुण है। इसके अतिरिक्त, फलन के आउटपुट में बदलाव का पता लगाने से इनपुट में क्या बदलाव आया है, इस बारे में कोई जानकारी नहीं मिलती है, जिससे फलन [[अंतर क्रिप्टैनालिसिस]] के प्रति प्रतिरोधी हो जाता है। | ||
बेंट फ़ंक्शंस को 1960 के दशक में [[ऑस्कर रोथौस]] द्वारा 1976 तक प्रकाशित नहीं किए गए शोध में परिभाषित और नामित किया गया था।<ref name="rothaus" />[[क्रिप्टोग्राफी]] में उनके अनुप्रयोगों के लिए उनका बड़े पैमाने पर अध्ययन किया गया है, लेकिन [[ रंगावली विस्तार ]], [[ कोडिंग सिद्धांत ]] और [[संयोजन डिजाइन]] के लिए भी लागू किया गया है। परिभाषा को कई | बेंट फ़ंक्शंस को 1960 के दशक में [[ऑस्कर रोथौस]] द्वारा 1976 तक प्रकाशित नहीं किए गए शोध में परिभाषित और नामित किया गया था।<ref name="rothaus" /> [[क्रिप्टोग्राफी]] में उनके अनुप्रयोगों के लिए उनका बड़े पैमाने पर अध्ययन किया गया है, लेकिन [[ रंगावली विस्तार |रंगावली विस्तार]] , [[ कोडिंग सिद्धांत |कोडिंग सिद्धांत]] और [[संयोजन डिजाइन]] के लिए भी लागू किया गया है। परिभाषा को कई विधियों से विस्तारित किया जा सकता है, जिससे सामान्यीकृत बेंट फलनों के विभिन्न वर्ग हो सकते हैं जो मूल के कई उपयोगी गुणों को साझा करते हैं। | ||
यह ज्ञात है कि | यह ज्ञात है कि वी. ए. एलिसेव और ओ. पी. स्टेपचेनकोव ने 1962 में यूएसएसआर में बेंट फलनों का अध्ययन किया, जिसे उन्होंने न्यूनतम कार्य कहा था।<ref name=bent-book/> चूंकि, उनके परिणाम अभी भी सार्वजनिक नहीं किए गए हैं। | ||
बेंट फलनों को पूरी तरह से गैर-रैखिक (पीएन) बूलियन फलनों के रूप में भी जाना जाता है। कुछ ऐसे कार्य जो पूर्ण अरैखिकता के जितना करीब हो सकते हैं (उदाहरण के लिए बिट्स की विषम संख्या के फलनों के लिए, या सदिश फलनों के लिए) लगभग पूरी तरह से अरैखिक (एपीएन) के रूप में जाने जाते हैं।<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 25: | Line 25: | ||
किसी भी बूलियन फलन के लिए 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}} दो चरम मामलों के अनुरूप है, क्योंकि | ||
:<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> जिसका वॉल्श रूपांतरण निरंतर निरपेक्ष मान रखता है। बेंट फ़ंक्शंस अर्थ में सभी एफ़िन फ़ंक्शंस से समतुल्य हैं, इसलिए वे किसी भी एफ़िन फलन के साथ अनुमान लगाने में समान रूप से कठिन हैं। | ||
[[बीजगणितीय सामान्य रूप]] में लिखे गए | [[बीजगणितीय सामान्य रूप]] में लिखे गए बेंट फलनों के सबसे सरल उदाहरण हैं {{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/> | ||
प्रत्येक बेंट फलन का हैमिंग वजन होता है (जितनी बार यह मान 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=bent-book/>* कॉम्बिनेटरियल कंस्ट्रक्शन: इटरेटिव कंस्ट्रक्शन, मैओराना-मैकफारलैंड कंस्ट्रक्शन, आंशिक स्प्रेड, डिलन और डॉबर्टिन के बेंट फंक्शन, मिन्टरम बेंट फंक्शन, बेंट इटरेटिव फंक्शन | ||
* बीजगणितीय निर्माण: गोल्ड, डिलन, कासमी, कैंटो-लिएंडर और कैंटो-चारपिन-कुयरेघ्यान के प्रतिपादकों के साथ मोनोमियल बेंट फलन; निहो | * बीजगणितीय निर्माण: गोल्ड, डिलन, कासमी, कैंटो-लिएंडर और कैंटो-चारपिन-कुयरेघ्यान के प्रतिपादकों के साथ मोनोमियल बेंट फलन; निहो बेंट कार्य, आदि। | ||
== अनुप्रयोग == | == अनुप्रयोग == | ||
1982 की शुरुआत में यह पता चला था कि | 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/> | |||
इस तरह के अच्छे प्रसार गुणों को देखते हुए, विभेदक क्रिप्टैनालिसिस के लिए स्पष्ट रूप से पूर्ण प्रतिरोध, और रैखिक क्रिप्टैनालिसिस के लिए परिभाषा के अनुसार प्रतिरोध, बेंट फ़ंक्शंस पहले एस-बॉक्स जैसे सुरक्षित क्रिप्टोग्राफ़िक फ़ंक्शंस के लिए आदर्श विकल्प प्रतीत हो सकते हैं। उनका घातक दोष यह है कि वे संतुलित होने में विफल रहते हैं। विशेष रूप से, इन्वर्टिबल एस-बॉक्स को सीधे बेंट फ़ंक्शंस से नहीं बनाया जा सकता है, और बेंट कॉम्बिनेशन फलन का उपयोग करके [[स्ट्रीम सिफर]] सहसंबंध हमले के लिए असुरक्षित है। इसके बजाय, कोई बेंट फलन के साथ शुरू हो सकता है और परिणाम संतुलित होने तक बेतरतीब ढंग से उचित मूल्यों को पूरक कर सकता है। संशोधित फलन में अभी भी उच्च गैर-रैखिकता है, और इस तरह के कार्य बहुत दुर्लभ हैं, प्रक्रिया क्रूर-बल खोज की तुलना में बहुत तेज होनी चाहिए।<ref name=nonlin/>लेकिन इस तरह से निर्मित कार्य अन्य वांछनीय गुणों को खो सकते हैं, यहां तक कि एसएसी को संतुष्ट करने में असफल होने पर भी - इसलिए सावधानीपूर्वक परीक्षण आवश्यक है।<ref name=sac/>कई क्रिप्टोग्राफ़रों ने संतुलित | इस तरह के अच्छे प्रसार गुणों को देखते हुए, विभेदक क्रिप्टैनालिसिस के लिए स्पष्ट रूप से पूर्ण प्रतिरोध, और रैखिक क्रिप्टैनालिसिस के लिए परिभाषा के अनुसार प्रतिरोध, बेंट फ़ंक्शंस पहले एस-बॉक्स जैसे सुरक्षित क्रिप्टोग्राफ़िक फ़ंक्शंस के लिए आदर्श विकल्प प्रतीत हो सकते हैं। उनका घातक दोष यह है कि वे संतुलित होने में विफल रहते हैं। विशेष रूप से, इन्वर्टिबल एस-बॉक्स को सीधे बेंट फ़ंक्शंस से नहीं बनाया जा सकता है, और बेंट कॉम्बिनेशन फलन का उपयोग करके [[स्ट्रीम सिफर]] सहसंबंध हमले के लिए असुरक्षित है। इसके बजाय, कोई बेंट फलन के साथ शुरू हो सकता है और परिणाम संतुलित होने तक बेतरतीब ढंग से उचित मूल्यों को पूरक कर सकता है। संशोधित फलन में अभी भी उच्च गैर-रैखिकता है, और इस तरह के कार्य बहुत दुर्लभ हैं, प्रक्रिया क्रूर-बल खोज की तुलना में बहुत तेज होनी चाहिए।<ref name=nonlin/>लेकिन इस तरह से निर्मित कार्य अन्य वांछनीय गुणों को खो सकते हैं, यहां तक कि एसएसी को संतुष्ट करने में असफल होने पर भी - इसलिए सावधानीपूर्वक परीक्षण आवश्यक है।<ref name=sac/>कई क्रिप्टोग्राफ़रों ने संतुलित फलनों को उत्पन्न करने के लिए तकनीकों पर काम किया है जो जितना संभव हो उतने अच्छे क्रिप्टोग्राफ़िक गुणों को बनाए रखता है।<ref name=nyberg/><ref name=highly/><ref name=cast/> | ||
इस सैद्धांतिक शोध में से कुछ को वास्तविक क्रिप्टोग्राफिक एल्गोरिदम में शामिल किया गया है। [[ब्लॉक सिफर]] [[CAST-128]] और [[CAST-256]] के लिए S-बॉक्स बनाने के लिए [[कार्लिस्ले एडम्स]] और [[स्टैफ़ोर्ड तवारेस]] द्वारा उपयोग की जाने वाली CAST डिज़ाइन प्रक्रिया, | इस सैद्धांतिक शोध में से कुछ को वास्तविक क्रिप्टोग्राफिक एल्गोरिदम में शामिल किया गया है। [[ब्लॉक सिफर]] [[CAST-128]] और [[CAST-256]] के लिए S-बॉक्स बनाने के लिए [[कार्लिस्ले एडम्स]] और [[स्टैफ़ोर्ड तवारेस]] द्वारा उपयोग की जाने वाली CAST डिज़ाइन प्रक्रिया, बेंट फलनों का उपयोग करती है।<ref name=cast/>[[क्रिप्टोग्राफ़िक हैश फ़ंक्शन|क्रिप्टोग्राफ़िक हैश फलन]] [[HAVAL]] छह चरों पर बेंट फलनों के सभी चार समतुल्य वर्गों के प्रतिनिधियों से निर्मित बूलियन फ़ंक्शंस का उपयोग करता है।<ref name=haval/>स्ट्रीम सिफर [[ अनाज (सिफर) |अनाज (सिफर)]] [[एनएलएफएसआर]] का उपयोग करता है जिसका गैर-रैखिक प्रतिक्रिया बहुपद डिजाइन द्वारा, बेंट कार्य और रैखिक कार्य का योग है।<ref name=grain/> | ||
== सामान्यीकरण == | == सामान्यीकरण == | ||
टोकरेवा के 2015 के मोनोग्राफ में | टोकरेवा के 2015 के मोनोग्राफ में बेंट फलनों के 25 से अधिक विभिन्न सामान्यीकरणों का वर्णन किया गया है।<ref name=bent-book/>बीजगणितीय सामान्यीकरण हैं (क्यू-वैल्यू बेंट फ़ंक्शंस, पी-एरी बेंट फ़ंक्शंस, परिमित क्षेत्र पर बेंट फ़ंक्शंस, श्मिट के सामान्यीकृत बूलियन बेंट फ़ंक्शंस, यूनिट सर्कल पर जटिल संख्याओं के सेट में परिमित एबेलियन समूह से बेंट फलन, बेंट परिमित एबेलियन समूह से परिमित एबेलियन समूह में कार्य करता है, गैर-एबेलियन बेंट फ़ंक्शंस, वेक्टरियल जी-बेंट फ़ंक्शंस, परिमित एबेलियन समूह पर बहुआयामी बेंट फ़ंक्शंस), कॉम्बीनेटरियल सामान्यीकरण (सममित बेंट फलन, सजातीय बेंट फलन, रोटेशन सममित बेंट फलन, सामान्य बेंट फ़ंक्शंस, स्व-दोहरी और एंटी-सेल्फ-डुअल बेंट फ़ंक्शंस, आंशिक रूप से परिभाषित बेंट फ़ंक्शंस, प्लेटेड फ़ंक्शंस, जेड-बेंट फ़ंक्शंस और क्वांटम बेंट फ़ंक्शंस) और क्रिप्टोग्राफ़िक सामान्यीकरण (सेमी-बेंट फ़ंक्शंस, संतुलित बेंट फ़ंक्शंस, आंशिक रूप से बेंट फ़ंक्शंस) हाइपर-बेंट फ़ंक्शंस, उच्च क्रम के बेंट फ़ंक्शंस, के-बेंट फ़ंक्शंस)। | ||
सामान्यीकृत झुकाव | सामान्यीकृत झुकाव फलनों का सबसे आम वर्ग मॉड्यूलर अंकगणितीय प्रकार है, <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 है<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/> | ||
हाइपर-बेंट फ़ंक्शंस के पीछे का विचार परिमित फ़ील्ड GF(2) पर [[द्विभाजन]] मोनोमियल्स से आने वाले ''सभी'' बूलियन फ़ंक्शंस की न्यूनतम दूरी को अधिकतम करना है<sup>n</sup>), न केवल affine कार्य करता है। इन | हाइपर-बेंट फ़ंक्शंस के पीछे का विचार परिमित फ़ील्ड GF(2) पर [[द्विभाजन]] मोनोमियल्स से आने वाले ''सभी'' बूलियन फ़ंक्शंस की न्यूनतम दूरी को अधिकतम करना है<sup>n</sup>), न केवल affine कार्य करता है। इन फलनों के लिए यह दूरी स्थिर है, जो उन्हें प्रक्षेप हमले के लिए प्रतिरोधी बना सकती है। | ||
क्रिप्टोग्राफिक रूप से महत्वपूर्ण | क्रिप्टोग्राफिक रूप से महत्वपूर्ण फलनों के वर्गों को अन्य संबंधित नाम दिए गए हैं <math>f:\Z_2^n \to \Z_2^n</math>, जैसे लगभग बेंट कार्य और टेढ़े-मेढ़े कार्य। जबकि बेंट कार्य स्वयं नहीं होते हैं (ये बूलियन कार्य भी नहीं होते हैं), वे बेंट फलनों से निकटता से संबंधित होते हैं और अच्छे अरैखिक गुण होते हैं। | ||
== यह भी देखें == | == यह भी देखें == | ||
Revision as of 06:58, 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 affine functions). निम्नलिखित सूत्र से पता चलता है कि 2-एरी फलन मुड़ा हुआ है जब इसकी गैर-रैखिकता 1 है:
File:0001 0001 0001 1110 nonlinearity.svg
बूलियन फलन झुका है; यानी, इसकी गैर-रैखिकता 6 है (which is what these Walsh Matrices show). निम्नलिखित सूत्र से पता चलता है कि 4-एरी फलन मुड़ा हुआ है जब इसकी गैर-रैखिकता 6 है:
साहचर्य के गणित क्षेत्र में, बेंट फलन एक विशेष प्रकार का बूलियन फलन है जो अधिकतम गैर-रैखिक होता है; यह सत्य तालिकाओं के बीच हैमिंग दूरी द्वारा मापा जाने पर सभी रैखिक और एफ़िन फलनों के सेट से जितना संभव हो उतना अलग होता है। ठोस रूप से, इसका अर्थ है कि फलन के आउटपुट और रैखिक फलन के बीच अधिकतम सहसंबंध गुणांक न्यूनतम है। इसके अतिरिक्त, बेंट फलन के बूलियन व्युत्पन्न