बेंट फलन

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

बूलियन फलन $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|{\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 तक फ़ॉरे ने माना कि किसी फलन के वाल्श रूपांतरण का उपयोग यह दिखाने के लिए किया जा सकता है कि यह सख्त हिमस्खलन मानदंड (एसएसी) और उच्च-क्रम के सामान्यीकरण को संतुष्ट करता है, और इस उपकरण की अनुशंसा करता है कि अच्छे एस-बॉक्स के लिए उम्मीदवारों का चयन करें, जो निकट-परिपूर्ण प्रसार प्राप्त करें। वास्तविक में, एसएसी को उच्चतम संभव क्रम में संतुष्ट करने वाले फलन हमेशा बेंट होते हैं। इसके अतिरिक्त, बेंट फलन जहाँ तक संभव हो, रैखिक संरचनाओं को गैर-शून्य वैक्टर कहा जाता है, जैसे कि f(x + a) + f(x) एक स्थिरांक है। डिफरेंशियल क्रिप्टैनालिसिस की भाषा में (इस गुण की खोज के बाद प्रस्तुत किया गया) प्रत्येक गैर-अक्षीय बिंदु पर बेंट फलन f का व्युत्पन्न (अर्थात, f_a(x) = f(x + a) + f(x)) संतुलित बूलियन फलन बूलियन फलन है, जो प्रत्येक मान को समय से ठीक आधा लेता है। इस गुण को पूर्ण अरैखिकता कहा जाता है।

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

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

सामान्यीकरण

टोकरेवा के 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^(n+1)/2 लेता हैं। उनके पास अच्छी क्रिप्टोग्राफिक विशेषताएँ भी हैं, और उनमें से कुछ संतुलित हैं, सभी संभावित मानों को समान रूप से अधिकांश लेते हैं।

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

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

अन्य संबंधित नाम क्रिप्टोग्राफ़िक रूप से फलनों $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.