बेंट फलन

हैमिंग वजन 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$

बूलियन फलन $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 और 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ⁿ
₂.वास्तव में, ${\hat {f}}(a)=2^{\frac {n}{2}}(-1)^{g(a)}$, जहाँ g भी मुड़ा हुआ है। इस मामले में, ${\hat {g}}(a)=2^{\frac {n}{2}}(-1)^{f(a)}$, इसलिए f और g को द्वैत (गणित) फलन माना जाता है।

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

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

निर्माण

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

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

अनुप्रयोग

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

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

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

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

सामान्यीकरण

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

सामान्यीकृत झुकाव फलनों का सबसे आम वर्ग मॉड्यूलर अंकगणितीय प्रकार है, $f:\mathbb {Z} _{m}^{n}\to \mathbb {Z} _{m}$ ऐसा है कि

${\hat {f}}(a)=\sum _{x\in \mathbb {Z} _{m}^{n}}e^{{\frac {2\pi i}{m}}(f(x)-a\cdot x)}$

स्थिर निरपेक्ष मान m है^n/2. बिल्कुल सही गैर रेखीय कार्य $f:\mathbb {Z} _{m}^{n}\to \mathbb {Z} _{m}$, वे ऐसे कि सभी अशून्य a के लिए, f(x + a) − f(a) प्रत्येक मान लेता है m^{n − 1} बार, सामान्यीकृत बेंट हैं। यदि m अभाज्य संख्या है, तो इसका विलोम सत्य है। ज्यादातर मामलों में केवल प्रधान एम माना जाता है। विषम अभाज्य m के लिए, प्रत्येक सकारात्मक n, सम और विषम के लिए सामान्यीकृत बेंट कार्य हैं। उनके पास बाइनरी बेंट फलनफ़ंक्शंस के समान कई अच्छे क्रिप्टोग्राफ़िक गुण हैं।

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

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

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

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

यह भी देखें

• सहसंबंध प्रतिरक्षा

अग्रिम पठन

• C. Carlet (May 1993). Two New Classes of Bent Functions. Eurocrypt '93. pp. 77–101.
• J. Seberry; X. Zhang (March 1994). "Constructions of Bent Functions from Two Known Bent Functions". Australasian Journal of Combinatorics. 9: 21–35. CiteSeerX 10.1.1.55.531. ISSN 1034-4942.
• T. Neumann (May 2006). "Bent Functions". CiteSeerX 10.1.1.85.8731. {{cite journal}}: Cite journal requires |journal= (help)
• Colbourn, Charles J.; Dinitz, Jeffrey H. (2006). Handbook of Combinatorial Designs (2nd ed.). CRC Press. pp. 337–339. ISBN 978-1-58488-506-1.
• Cusick, T.W.; Stanica, P. (2009). Cryptographic Boolean Functions and Applications. Academic Press. ISBN 9780123748904.