2025-11-10T02:59:44.540641

A Characterization of Semi-Involutory MDS Matrices

Chatterjee, Laha
In symmetric cryptography, maximum distance separable (MDS) matrices with computationally simple inverses have wide applications. Many block ciphers like AES, SQUARE, SHARK, and hash functions like PHOTON use an MDS matrix in the diffusion layer. In this article, we first characterize all $3 \times 3$ irreducible semi-involutory matrices over the finite field of characteristic $2$. Using this matrix characterization, we provide a necessary and sufficient condition to construct MDS semi-involutory matrices using only their diagonal entries and the entries of an associated diagonal matrix. Finally, we count the number of $3 \times 3$ semi-involutory MDS matrices over any finite field of characteristic $2$.
academic

अर्ध-अंतर्वलनी MDS मैट्रिक्स की विशेषता

मूल जानकारी

  • पेपर ID: 2406.12842
  • शीर्षक: अर्ध-अंतर्वलनी MDS मैट्रिक्स की विशेषता
  • लेखक: तपस चटर्जी (भारतीय प्रौद्योगिकी संस्थान रोपड़), अयंतिका लाहा (भारतीय प्रौद्योगिकी संस्थान रोपड़)
  • वर्गीकरण: cs.CR (क्रिप्टोग्राफी और सुरक्षा)
  • प्रकाशन समय: 1 जनवरी 2025 (v2 संस्करण)
  • पेपर लिंक: https://arxiv.org/abs/2406.12842

सारांश

सममित क्रिप्टोग्राफी में, अधिकतम दूरी अलग करने योग्य (MDS) मैट्रिक्स जिनके व्युत्क्रम मैट्रिक्स की गणना सरल है, का व्यापक अनुप्रयोग है। AES, SQUARE, SHARK जैसे कई ब्लॉक सिफर और PHOTON जैसे हैश फंक्शन अपनी विसरण परत में MDS मैट्रिक्स का उपयोग करते हैं। यह पेपर पहले विशेषता 2 के परिमित क्षेत्र पर सभी 3×3 अपरिवर्तनीय अर्ध-अंतर्वलनी मैट्रिक्स की विशेषता बताता है। इस मैट्रिक्स विशेषता के आधार पर, हम केवल विकर्ण तत्वों और संबंधित विकर्ण मैट्रिक्स तत्वों का उपयोग करके MDS अर्ध-अंतर्वलनी मैट्रिक्स के निर्माण के लिए आवश्यक और पर्याप्त शर्तें प्रदान करते हैं। अंत में, हम विशेषता 2 के किसी भी परिमित क्षेत्र पर 3×3 अर्ध-अंतर्वलनी MDS मैट्रिक्स की संख्या की गणना करते हैं।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या की पृष्ठभूमि

  1. विसरण परत का महत्व: सममित क्रिप्टोग्राफी में, Shannon द्वारा प्रस्तावित "भ्रम और विसरण" की अवधारणा क्रिप्टोग्राफिक डिजाइन का आधार है। विसरण परत सिफरटेक्स्ट और प्लेनटेक्स्ट के बीच संबंध को छिपाने के लिए जिम्मेदार है, और MDS मैट्रिक्स अपनी अधिकतम शाखा संख्या के कारण पूर्ण विसरण प्रदान कर सकते हैं।
  2. कम्प्यूटेशनल दक्षता की आवश्यकता: हल्के क्रिप्टोग्राफी अनुप्रयोगों में, न केवल MDS मैट्रिक्स को सुरक्षा प्रदान करनी चाहिए, बल्कि इसके व्युत्क्रम मैट्रिक्स को कुशलतापूर्वक लागू किया जाना चाहिए। अंतर्वलनी मैट्रिक्स (A² = I) इसलिए ध्यान आकर्षित करते हैं क्योंकि उनका व्युत्क्रम स्वयं है।
  3. मौजूदा विधियों की सीमाएं:
    • अंतर्वलनी MDS मैट्रिक्स की खोज स्थान अपेक्षाकृत सीमित है
    • कुछ आकारों के अंतर्वलनी चक्रीय मैट्रिक्स मौजूद नहीं हैं
    • डिजाइन विकल्पों को विस्तारित करने के लिए अधिक व्यापक मैट्रिक्स वर्ग की आवश्यकता है

अनुसंधान प्रेरणा

यह पेपर अर्ध-अंतर्वलनी मैट्रिक्स को अंतर्वलनी मैट्रिक्स के सामान्यीकरण के रूप में प्रस्तुत करता है, जिसे गैर-विलक्षण विकर्ण मैट्रिक्स D₁ और D₂ के अस्तित्व के रूप में परिभाषित किया जाता है जैसे कि M⁻¹ = D₁MD₂। यह सामान्यीकरण क्रिप्टोग्राफिक डिजाइन के लिए उपलब्ध मैट्रिक्स वर्गों को महत्वपूर्ण रूप से विस्तारित करता है।

मुख्य योगदान

  1. सैद्धांतिक विशेषता: विशेषता 2 के परिमित क्षेत्र पर सभी 3×3 अपरिवर्तनीय अर्ध-अंतर्वलनी मैट्रिक्स की संरचना की पूर्ण विशेषता
  2. निर्माण विधि: केवल 6 पैरामीटर (3 विकर्ण तत्व + 3 संबंधित विकर्ण मैट्रिक्स तत्व) का उपयोग करके 3×3 अर्ध-अंतर्वलनी MDS मैट्रिक्स के निर्माण के लिए आवश्यक और पर्याप्त शर्तें
  3. गणना परिणाम: F₂ᵐ पर 3×3 अर्ध-अंतर्वलनी MDS मैट्रिक्स की संख्या (2ᵐ-1)⁵(2ᵐ-2)(2ᵐ-4) के रूप में सटीक गणना
  4. पूर्ववर्ती परिणामों का सामान्यीकरण: Güzel आदि द्वारा अंतर्वलनी MDS मैट्रिक्स के बारे में परिणामों को अधिक बड़े अर्ध-अंतर्वलनी मैट्रिक्स वर्ग तक सामान्यीकृत करना

विधि विवरण

कार्य परिभाषा

विशेषता 2 के परिमित क्षेत्र F₂ᵐ पर 3×3 मैट्रिक्स A का अध्ययन करें, जिसमें आवश्यकता है:

  • अर्ध-अंतर्वलनी गुण: गैर-विलक्षण विकर्ण मैट्रिक्स D मौजूद है जैसे कि ADA विकर्ण मैट्रिक्स है
  • MDS गुण: A के सभी वर्ग उप-मैट्रिक्स गैर-विलक्षण हैं
  • अपरिवर्तनीयता: A को क्रमचय समानता के माध्यम से घटाए गए रूप में परिवर्तित नहीं किया जा सकता

मुख्य प्रमेय

प्रमेय 4.1 (संरचना विशेषता)

मान लीजिए A एक 3×3 अपरिवर्तनीय अर्ध-अंतर्वलनी मैट्रिक्स है, संबंधित विकर्ण मैट्रिक्स D = diag(d₁,d₂,d₃) के साथ, तो गैर-विकर्ण तत्वों को इस प्रकार व्यक्त किया जा सकता है:

  • a₁₂ = (a₁₁d₁ + a₃₃d₃)d₂⁻¹x
  • a₁₃ = (a₁₁d₁ + a₂₂d₂)d₃⁻¹xy
  • a₂₁ = (a₂₂d₂ + a₃₃d₃)d₁⁻¹x⁻¹
  • a₂₃ = (a₂₂d₂ + a₁₁d₁)d₃⁻¹y
  • a₃₁ = (a₃₃d₃ + a₂₂d₂)d₁⁻¹(xy)⁻¹
  • a₃₂ = (a₃₃d₃ + a₁₁d₁)d₂⁻¹y⁻¹

जहां x,y ∈ F₂ᵐ* गैर-शून्य तत्व हैं।

प्रमेय 4.5 (MDS आवश्यक और पर्याप्त शर्त)

उपरोक्त संरचना का मैट्रिक्स A अर्ध-अंतर्वलनी MDS मैट्रिक्स है यदि और केवल यदि:

  • a₁₁d₁ + a₂₂d₂ ≠ 0
  • a₁₁d₁ + a₃₃d₃ ≠ 0
  • a₂₂d₂ + a₃₃d₃ ≠ 0
  • a₁₁d₁ + a₂₂d₂ + a₃₃d₃ ≠ 0

तकनीकी नवाचार बिंदु

  1. एकीकृत ढांचा: अंतर्वलनी मैट्रिक्स को अर्ध-अंतर्वलनी मैट्रिक्स के विशेष मामले के रूप में प्रस्तुत करना, एकीकृत विश्लेषण ढांचा प्रदान करता है
  2. पैरामीट्रिक निर्माण: 8 पैरामीटर के माध्यम से 3×3 अर्ध-अंतर्वलनी MDS मैट्रिक्स को पूरी तरह से चिह्नित करना, खोज स्थान को बहुत सरल करता है
  3. गणना तकनीक: समावेशन-बहिष्करण सिद्धांत का उपयोग करके शर्तों को पूरा करने वाले पैरामीटर संयोजनों की संख्या की सटीक गणना

प्रायोगिक सेटअप

सैद्धांतिक सत्यापन

पेपर मुख्य रूप से सैद्धांतिक कार्य है, विशिष्ट उदाहरणों के माध्यम से सैद्धांतिक परिणामों को सत्यापित करता है:

उदाहरण 4.6: F₂₄ पर अर्ध-अंतर्वलनी MDS मैट्रिक्स का निर्माण

  • जनन बहुपद: x⁴ + x³ + 1
  • पैरामीटर चयन: a₁₁=1, a₂₂=α, a₃₃=α², d₁=α, d₂=α, d₃=α³+1, x=1, y=α
  • सभी MDS शर्तों को पूरा करने का सत्यापन

गणना सत्यापन

गणना सूत्र को सत्यापित करने के लिए विशिष्ट गणना के माध्यम से:

  • F₂₂: 0 अर्ध-अंतर्वलनी MDS मैट्रिक्स
  • F₂₃: 403,368 अर्ध-अंतर्वलनी MDS मैट्रिक्स
  • F₂₄: 127,575,000 अर्ध-अंतर्वलनी MDS मैट्रिक्स

प्रायोगिक परिणाम

मुख्य परिणाम

  1. संरचना पूर्णता: सभी 3×3 अर्ध-अंतर्वलनी मैट्रिक्स की संरचना को सफलतापूर्वक चिह्नित किया, यह साबित किया कि इसे 8 पैरामीटर द्वारा पूरी तरह से निर्धारित किया जा सकता है
  2. MDS निर्णय: यह निर्धारित करने के लिए सरल शर्तें प्रदान करता है कि अर्ध-अंतर्वलनी मैट्रिक्स कब MDS गुण रखता है
  3. संख्या वृद्धि: अंतर्वलनी MDS मैट्रिक्स की तुलना में, अर्ध-अंतर्वलनी MDS मैट्रिक्स की संख्या में उल्लेखनीय वृद्धि:
    • F₂₃ पर अंतर्वलनी MDS मैट्रिक्स: 1,176
    • F₂₃ पर अर्ध-अंतर्वलनी MDS मैट्रिक्स: 403,368 (लगभग 343 गुना वृद्धि)

सैद्धांतिक खोजें

  1. सामान्यीकरण: अर्ध-अंतर्वलनी गुण वास्तव में अंतर्वलनी गुण को सामान्यीकृत करता है, अर्ध-अंतर्वलनी लेकिन गैर-अंतर्वलनी MDS मैट्रिक्स मौजूद हैं
  2. कम्प्यूटेशनल लाभ: अर्ध-अंतर्वलनी MDS मैट्रिक्स का व्युत्क्रम मैट्रिक्स अभी भी सरल विकर्ण मैट्रिक्स गुणन के माध्यम से प्राप्त किया जा सकता है, कम्प्यूटेशनल दक्षता को बनाए रखता है
  3. अस्तित्व: F₂₂ पर शर्तों को पूरा करने वाला कोई अर्ध-अंतर्वलनी MDS मैट्रिक्स मौजूद नहीं है, लेकिन F₂ᵐ (m≥3) पर इस तरह के मैट्रिक्स की बहुतायत मौजूद है

संबंधित कार्य

ऐतिहासिक विकास

  1. अंतर्वलनी मैट्रिक्स अनुसंधान: Youssef आदि (2007) ने पहली बार क्रिप्टोग्राफी में अंतर्वलनी रैखिक परिवर्तन पेश किए
  2. MDS निर्माण विधियां: Gupta और Ray (2013) ने कई MDS मैट्रिक्स निर्माण विधियां प्रदान कीं
  3. चक्रीय मैट्रिक्स सीमाएं: Gupta आदि ने अंतर्वलनी चक्रीय मैट्रिक्स की गैर-अस्तित्व साबित की
  4. अर्ध-अंतर्वलनी अवधारणा: Cheon आदि (2021) ने अर्ध-अंतर्वलनी मैट्रिक्स अवधारणा पेश की

इस पेपर का योगदान

मौजूदा कार्य की तुलना में, यह पेपर:

  • अर्ध-अंतर्वलनी अवधारणा को पहली बार MDS मैट्रिक्स निर्माण में लागू करता है
  • अंतर्वलनी मैट्रिक्स की तुलना में बड़ा डिजाइन स्थान प्रदान करता है
  • सटीक गणना परिणाम देता है

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. 3×3 अर्ध-अंतर्वलनी मैट्रिक्स की बीजगणितीय संरचना को पूरी तरह से चिह्नित किया
  2. अर्ध-अंतर्वलनी गुण और MDS गुण के बीच संबंध स्थापित किया
  3. साबित किया कि अर्ध-अंतर्वलनी MDS मैट्रिक्स क्रिप्टोग्राफिक डिजाइन में व्यावहारिक मूल्य रखते हैं

सीमाएं

  1. आयाम सीमा: वर्तमान परिणाम केवल 3×3 मैट्रिक्स पर लागू होते हैं
  2. विशेषता सीमा: सिद्धांत मुख्य रूप से विशेषता 2 के परिमित क्षेत्र पर केंद्रित है
  3. अपरिवर्तनीयता: मैट्रिक्स के अपरिवर्तनीय गुण की आवश्यकता है

भविष्य की दिशाएं

  1. उच्च आयाम मैट्रिक्स तक सामान्यीकरण (विशेष रूप से सम क्रम या 2 की घातें)
  2. अन्य विशेषता परिमित क्षेत्रों पर स्थिति का अनुसंधान
  3. वास्तविक क्रिप्टोग्राफिक सिस्टम में अर्ध-अंतर्वलनी मैट्रिक्स के अनुप्रयोग की खोज

गहन मूल्यांकन

शक्तियां

  1. सैद्धांतिक पूर्णता: 3×3 अर्ध-अंतर्वलनी MDS मैट्रिक्स की पूर्ण विशेषता प्रदान करता है, सैद्धांतिक परिणाम कठोर हैं
  2. व्यावहारिक मूल्य: क्रिप्टोग्राफिक डिजाइन के लिए नए उपकरण प्रदान करता है, डिजाइन स्थान को विस्तारित करता है
  3. कम्प्यूटेशनल दक्षता: व्युत्क्रम मैट्रिक्स गणना की सरलता को बनाए रखता है, हल्के अनुप्रयोगों के लिए उपयुक्त
  4. सटीक गणना: अस्तित्व की संख्या देता है, यादृच्छिक चयन में सहायता करता है

कमियां

  1. आयाम सीमा: केवल 3×3 मामले पर विचार करता है, उच्च आयामों में सामान्यीकरण अभी भी खुली समस्या है
  2. निर्माण जटिलता: हालांकि पैरामीट्रिक रूप दिया गया है, वास्तविक निर्माण को अभी भी कई बाधाओं को पूरा करना चाहिए
  3. अनुप्रयोग सत्यापन: वास्तविक क्रिप्टोग्राफिक सिस्टम में सुरक्षा विश्लेषण की कमी है

प्रभाव

  1. सैद्धांतिक योगदान: परिमित क्षेत्र पर मैट्रिक्स सिद्धांत के लिए नई अंतर्दृष्टि प्रदान करता है
  2. क्रिप्टोग्राफिक अनुप्रयोग: हल्के क्रिप्टोग्राफी डिजाइन के लिए नए उम्मीदवार मैट्रिक्स प्रदान करता है
  3. विधि नवाचार: गणना विधि अन्य समान समस्याओं तक विस्तारित की जा सकती है

प्रयोज्य परिदृश्य

  1. हल्के क्रिप्टोग्राफी: संसाधन-सीमित वातावरण में ब्लॉक सिफर डिजाइन के लिए उपयुक्त
  2. हैश फंक्शन: उच्च-दक्षता विसरण परत की आवश्यकता वाले हैश फंक्शन निर्माण में उपयोग किया जा सकता है
  3. सैद्धांतिक अनुसंधान: उच्च आयाम मामलों के आगे अनुसंधान के लिए आधार प्रदान करता है

संदर्भ

पेपर 25 संबंधित संदर्भों का हवाला देता है, मुख्य रूप से शामिल हैं:

  • Shannon के क्रिप्टोग्राफिक सिद्धांत मूल कार्य
  • AES जैसे शास्त्रीय क्रिप्टोग्राफिक एल्गोरिदम
  • MDS मैट्रिक्स निर्माण के महत्वपूर्ण सैद्धांतिक परिणाम
  • अर्ध-अंतर्वलनी मैट्रिक्स के नवीनतम अनुसंधान प्रगति

यह कार्य मौजूदा सैद्धांतिक आधार पर वास्तविक प्रगति प्राप्त करता है, अर्ध-अंतर्वलनी MDS मैट्रिक्स के सिद्धांत और अनुप्रयोग के लिए एक ठोस आधार स्थापित करता है।