बेंट फलन

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 है:

$2^{2-1}-2^{{\frac {2}{2}}-1}=2-1=1$

File:0001 0001 0001 1110 nonlinearity.svg

बूलियन फलन $x_{1}x_{2}\oplus x_{3}x_{4}$ झुका है; अर्थात्, इसकी गैर-रैखिकता 6 है (which is what these Walsh Matrices show). निम्नलिखित सूत्र से पता चलता है कि 4-एरी फलन मुड़ा हुआ है जब इसकी गैर-रैखिकता 6 है:

$2^{4-1}-2^{{\frac {4}{2}}-1}=8-2=6$

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

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

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

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

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

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

बेंट फलन को वॉल्श रूपांतरण के संदर्भ में परिभाषित किया गया है। बूलियन फलन का वॉल्श रूपांतरण $f:\mathbb {Z} _{2}^{n}\to \mathbb {Z} _{2}$ फलन है ${\hat {f}}:\mathbb {Z} _{2}^{n}\to \mathbb {Z}$ द्वारा दिए गए

${\hat {f}}(a)=\sum _{\scriptstyle {x\in \mathbb {Z} _{2}^{n}}}(-1)^{f(x)+a\cdot x}$

जहाँ a · x = a₁x₁ + a₂x₂ + … + a_nx_n (mod 2) Zⁿ
₂ में डॉट उत्पाद हैं। वैकल्पिक रूप से, मान लो S₀(a) = { x ∈ Zⁿ
₂ : f(x) = a · x } और S₁(a) = { x ∈ Zⁿ
₂ : f(x) ≠ a · x }. तब |S₀(a)| + |S₁(a)| = 2ⁿ और इसलिए

${\hat {f}}(a)=\left|S_{0}(a)\right|-\left|S_{1}(a)\right|=2\left|S_{0}(a)\right|-2^{n}.$

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

$-2^{n}\leq {\hat {f}}(a)\leq 2^{n}.$

इसके अतिरिक्त, रैखिक फलन f₀(x) = a · x और एफ़िन फलन f₁(x) = a · x + 1 दो चरम स्थितियों के अनुरूप है, क्योंकि

${\hat {f}}_{0}(a)=2^{n},~{\hat {f}}_{1}(a)=-2^{n}.$

इस प्रकार, प्रत्येक के लिए a ∈ Zⁿ
₂ का मान है ${\hat {f}}(a)$ यह दर्शाता है कि फलन f(x) f से श्रेणी में कहाँ स्थित है₀(एक्स) से एफ₁(एक्स)।

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

रोथौस ने बेंट फलन को बूलियन फलन के रूप में परिभाषित किया $f:\mathbb {Z} _{2}^{n}\to \mathbb {Z} _{2}$ जिसका वॉल्श रूपांतरण निरंतर निरपेक्ष मान रखता है। बेंट फलन अर्थ में सभी एफ़िन फलन से समतुल्य हैं, इसलिए वे किसी भी एफ़िन फलन के साथ अनुमान लगाने में समान रूप से कठिन हैं।

बीजगणितीय सामान्य रूप में लिखे गए बेंट फलनों के सबसे सरल उदाहरण हैं F(x₁, x₂) = x₁x₂ और G(x₁, x₂, x₃, x₄) = x₁x₂ ⊕ x₃x₄. यह पैटर्न जारी है: x₁x₂ ⊕ x₃x₄ ⊕ … ⊕ x_n−1x_n बेंट फलन है $\mathbb {Z} _{2}^{n}\to \mathbb {Z} _{2}$ प्रत्येक सम n के लिए, किन्तु जैसे-जैसे n बढ़ता है, वैसे-वैसे अन्य बेंट फलनों की विस्तृत विविधता होती है। मानों का क्रम (−1)^f(x), के साथ x ∈ Zⁿ
₂ लेक्सिकोग्राफिक क्रम में लिया गया है, इसे बेंट अनुक्रम कहा जाता है; बेंट फलन और बेंट सीक्वेंस में समान गुण होते हैं। इस ±1 रूप में वॉल्श रूपांतरण की गणना आसानी से की जाती है

${\hat {f}}(a)=W\left(2^{n}\right)(-1)^{f(a)},$

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

रोथौस ने सिद्ध किया कि बेंट फलन केवल n के लिए भी उपस्थित होते हैं, और बेंट फलन f के लिए, $\left|\stackrel{^<!--\; ^\; -->}{f}(a)\right|=$