बेंट फलन

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

$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$

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

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

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

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

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

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

बेंट फ़ंक्शंस को वॉल्श ट्रांसफ़ॉर्म के संदर्भ में परिभाषित किया गया है। बूलियन फ़ंक्शन का वॉल्श रूपांतरण $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 और affine समारोह 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|{\hat {f}}(a)\right|=2^{\frac {n}{2}}$ सभी के लिए a ∈ Z