बेंट फलन

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

साहचर्य के गणित क्षेत्र में, एक मुड़ा हुआ कार्य एक विशेष प्रकार का बूलियन फलन है जो अधिकतम गैर-रैखिक है; ट्रुथ टेबल के बीच हैमिंग दूरी द्वारा मापे जाने पर यह सभी रैखिक मानचित्र और 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ⁿ
₂.वास्तव में, ${\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.