2025-11-22T00:52:16.221665

A Symmetric-Key Cryptosystem Based on the Burnside Ring of a Compact Lie Group

Ghanem
Classical linear ciphers, such as the Hill cipher, operate on fixed, finite-dimensional modules and are therefore vulnerable to straightforward known-plaintext attacks that recover the key as a fully determined linear operator. We propose a symmetric-key cryptosystem whose linear action takes place instead in the Burnside ring $A(G)$ of a compact Lie group $G$, with emphasis on the case $G=O(2)$. The secret key consists of (i) a compact Lie group $G$; (ii) a secret total ordering of the subgroup orbit-basis of $A(G)$; and (iii) a finite set $S$ of indices of irreducible $G$-representations, whose associated basic degrees define an involutory multiplier $k\in A(G)$. Messages of arbitrary finite length are encoded as finitely supported elements of $A(G)$ and encrypted via the Burnside product with $k$. For $G=O(2)$ we prove that encryption preserves plaintext support among the generators $\{(D_1),\dots,(D_L),(SO(2)),(O(2))\}$, avoiding ciphertext expansion and security leakage. We then analyze security in passive models, showing that any finite set of observations constrains the action only on a finite-rank submodule $W_L\subset A(O(2))$, and we show information-theoretic non-identifiability of the key from such data. Finally, we prove the scheme is \emph{not} IND-CPA secure, by presenting a one-query chosen-plaintext distinguisher based on dihedral probes.
academic

نظام تشفير بمفتاح متماثل قائم على حلقة بيرنسايد لمجموعة لي المضغوطة

المعلومات الأساسية

  • معرّف الورقة: 2510.10901
  • العنوان: A Symmetric-Key Cryptosystem Based on the Burnside Ring of a Compact Lie Group
  • المؤلف: Ziad Ghanem
  • التصنيف: cs.CR (التشفير والأمان)، math.RA (الحلقات والجبر)
  • تاريخ النشر: 13 أكتوبر 2025 (نسخة أولية من arXiv)
  • رابط الورقة: https://arxiv.org/abs/2510.10901

الملخص

تعمل الأنظمة التشفيرية الخطية التقليدية (مثل تشفير Hill) على وحدات محدودة الأبعاد ثابتة، مما يجعلها عرضة للهجمات المباشرة بالنصوص المعروفة، حيث يمكن للمهاجم استرجاع مفتاح المشغل الخطي المحدد بالكامل من خلال طرق الجبر الخطي. تقترح هذه الورقة نظام تشفير بمفتاح متماثل تعمل عملياته الخطية في حلقة بيرنسايد A(G) لمجموعة لي المضغوطة G، مع التركيز على حالة G=O(2). يتكون المفتاح من ثلاثة أجزاء: (i) مجموعة لي المضغوطة G؛ (ii) ترتيب كامل سري لأساس مدارات المجموعات الجزئية من A(G)؛ (iii) مجموعة محدودة S من مؤشرات التمثيلات G غير القابلة للاختزال، حيث تحدد درجاتها الأساسية ذات الصلة مضروب الانقلاب k∈A(G). يتم ترميز أي رسالة بطول محدود كعنصر محدود الدعم من A(G)، ويتم تشفيرها من خلال الضرب في بيرنسايد مع k.

خلفية البحث والدافع

خلفية المشكلة

  1. ضعف الأنظمة التشفيرية الخطية التقليدية: تعمل الأنظمة التشفيرية الخطية الكلاسيكية مثل تشفير Hill في فضاء محدود الأبعاد، مما يسمح للمهاجم بجمع عدد كافٍ من أزواج النص الصريح-النص المشفر لبناء نظام معادلات خطية، وبالتالي استرجاع المفتاح بالكامل.
  2. الحاجة إلى التشفير ما بعد الكم: يدفع التهديد من الحوسبة الكمية الباحثين للبحث عن بدائل تشفيرية قائمة على افتراضات نظرية أعداد غير تقليدية، بما في ذلك الأنظمة القائمة على نظرية المجموعات ونظرية الرسوم البيانية.
  3. القيود الأساسية للمنصات محدودة الأبعاد: بينما توفر الأنظمة التشفيرية الجبرية الحالية بدائل مهمة، إلا أنها لا تزال تعمل على منصات محدودة الأبعاد، مع وجود ثغرات مفاهيمية - حيث يمكن لعدد كافٍ من أزواج النص الصريح-النص المشفر أن تقيد بالكامل مشغل المفتاح.

دافع البحث

يتمثل الدافع الأساسي للورقة في تجاوز قيود الإعدادات محدودة الأبعاد، بنقل عمليات التشفير إلى وحدات ذات رتبة لا نهائية - حلقة بيرنسايد لمجموعات لي المضغوطة، وبالتالي تجنب النقاط الضعيفة الأساسية للأنظمة التشفيرية الخطية التقليدية من الناحية النظرية.

المساهمات الأساسية

  1. اقتراح نظام تشفير جديد قائم على حلقة بيرنسايد: تطبيق أول لحلقة بيرنسايد لمجموعات لي المضغوطة في التشفير، خاصة في حالة مجموعة O(2).
  2. إثبات خاصية الحفاظ على الدعم: بالنسبة لـ G=O(2)، تم إثبات أن عملية التشفير تحافظ على دعم النص الصريح في المولدات {(D₁),...,(D_L),(SO(2)),(O(2))}، مما يتجنب توسع النص المشفر وتسرب الأمان.
  3. إنشاء تحليل الأمان في النموذج السلبي: تم إثبات أن أي مجموعة ملاحظات محدودة يمكنها فقط تقييد العمليات على وحدة فرعية محدودة الرتبة W_L⊂A(O(2))، وإظهار عدم قابلية تحديد المفتاح من الناحية المعلوماتية من البيانات المحدودة.
  4. إثبات عدم الأمان IND-CPA: من خلال مميز الاختيار الفردي للنص الصريح القائم على استكشاف ثنائي الوجه، تم إثبات أن المخطط لا يفي بمتطلبات أمان IND-CPA.

شرح الطريقة

تعريف المهمة

تصميم مخطط تشفير بمفتاح متماثل حيث:

  • الإدخال: رسالة بطول محدود تعسفي
  • الإخراج: عنصر مشفر في حلقة بيرنسايد
  • القيود: الاستفادة من البنية اللانهائية الأبعاد للمقاومة ضد هجمات الجبر الخطي التقليدية

أساسيات نظرية حلقة بيرنسايد

بناء حلقة بيرنسايد

بالنسبة لمجموعة لي المضغوطة G، يتم تعريف حلقة بيرنسايد A(G) كما يلي:

  • الأساس: مجموعة فئات الاقتران للمجموعات الجزئية Φ₀(G) = {(H) : H ≤ G, W(H) محدودة}
  • البنية: وحدة Z حرة A(G) = ZΦ₀(G)
  • الضرب: ضرب بيرنسايد المعرّف من خلال عد المدارات

حلقة بيرنسايد لـ O(2)

بالنسبة لـ G = O(2)، تتضمن العناصر الأساسية:

  • (O(2)): فئة الاقتران للمجموعة نفسها
  • (SO(2)): فئة الاقتران للمجموعة الخطية الخاصة
  • (Dₖ): فئات الاقتران للمجموعات الثنائية الوجه المحدودة، k ≥ 1

قواعد الضرب كما هي موضحة في الجدول:

·(O(2))(SO(2))(Dₘ)
(O(2))(O(2))(SO(2))(Dₘ)
(SO(2))(SO(2))2(SO(2))0
(Dₖ)(Dₖ)02(D_l), l=gcd(k,m)

تصميم النظام التشفيري

بنية المفتاح

يتكون المفتاح من ثلاثية (G,O,S):

  1. المجموعة G: مجموعة لي المضغوطة، مثل G = O(2)
  2. الترتيب O: ترتيب سري كامل للعناصر الأساسية Φ₀(G)
  3. مجموعة مؤشرات التمثيل S: مجموعة محدودة S = {k₁,k₂,...,kₘ}

بناء عنصر المفتاح

بناء عنصر المفتاح من المجموعة S: k=∏j∈Sdeg⁡Vjk = \prod_{j \in S} \deg_{V_j}

حيث deg_ هي الدرجة الأساسية للتمثيل j غير القابل للاختزال. بالنسبة لـ O(2):

  • deg_ = (O(2)) (التمثيل البديهي)
  • deg_ = (O(2)) - (Dₘ) (التمثيلات غير البديهية)

بروتوكول التشفير/فك التشفير

  1. المعالجة المسبقة: تحويل البيانات الأولية إلى متجه صحيح p⃗ ∈ Z^L
  2. ترميز الحلقة: استخدام الترتيب السري O لتعيين المتجه إلى p ∈ A(G)
  3. التشفير: حساب النص المشفر c = p · k
  4. النقل: إرسال النص المشفر محدود الدعم
  5. فك التشفير: نظراً لأن k انقلاب، احسب p = c · k
  6. فك الترميز: استرجاع البيانات الأصلية

نقاط الابتكار التقني

  1. منصة لانهائية الأبعاد: تجاوز القيود محدودة الأبعاد، العمل في وحدات ذات رتبة لا نهائية
  2. خاصية الانقلاب: عنصر المفتاح k يحقق k² = (O(2))، مما يبسط عملية فك التشفير
  3. الحفاظ على الدعم: التشفير لا يزيد من أقصى مؤشر ثنائي الوجه للنص الصريح، مما يتجنب تضخم النص المشفر

التحليل النظري

نظرية الحفاظ على الدعم

القضية 3.1: دع النص الصريح يكون p = Σᵢ₌₁ᴸ aᵢ(Dᵢ)، إذا كان المفتاح k هو حاصل ضرب أي درجات أساسية، فإن النص المشفر c = p·k هو أيضاً عنصر من الوحدة الفرعية Z{(D₁),...,(D_L)}.

نقاط الإثبات:

  • (Dᵢ)·(O(2)) = (Dᵢ)
  • (Dᵢ)·(Dₘ) = 2(D_{gcd(i,m)})
  • نظراً لأن gcd(i,m) ≤ i ≤ L، فإن دعم النتيجة لا يتجاوز النطاق الأصلي

تحليل الأمان السلبي

نافذة الملاحظة المحدودة

أي مجموعة ملاحظات محدودة {pⱼ,cⱼ} مقيدة بوحدة فرعية محدودة الرتبة: WL:=Z[{(D1),...,(DL)}]⊂A(O(2))W_L := \mathbb{Z}[\{(D_1),...,(D_L)\}] \subset A(O(2))

عدم قابلية تمييز المفتاح

القضية 4.1: دع S = {s₁,...,sₘ} تكون مجموعة المفتاح، q عدد أولي و q > L. بناء S' = {s₁q,...,sₘq}، ثم k_S و k_{S'} ينتجان نفس التحويل الخطي على W_L.

النتيجة 4.1: بالنسبة لأي مجموعة ملاحظات محدودة في W_L، توجد مجموعات مفاتيح مختلفة لا نهائية متسقة مع الملاحظات، والمفتاح غير قابل للتحديد من الناحية المعلوماتية.

ضعف هجوم الاختيار الفردي للنص الصريح

هجوم استكشاف ثنائي الوجه

بالنسبة للاستعلام p = (Dₓ)، النص المشفر هو: cx=(Dx)⋅kS=(Dx)+∑n≥12αS(n)(Dgcd(x,n))c_x = (D_x) \cdot k_S = (D_x) + \sum_{n≥1} 2α_S(n)(D_{gcd(x,n)})

حيث يتم تحديد α_S(n) من خلال الصيغة المعطاة في القضية 2.1.

القضية 4.2: بالنسبة لأي مجموعتي مفاتيح مختلفتين S₀ ≠ S₁، يوجد x ∈ ℕ بحيث (Dₓ)·k_{S₀} ≠ (Dₓ)·k_{S₁}.

مميز الاستعلام الفردي:

  1. احسب β_{S₀}(x) و β_{S₁}(x)
  2. اختر x الذي يحقق β_{S₀}(x) ≠ β_{S₁}(x)
  3. استعلم p = (Dₓ)، وحدد المفتاح بناءً على المعاملات

تقييم الأمان

المميزات

  1. المقاومة ضد الهجمات السلبية: تحت هجمات النص المشفر والهجمات بالنصوص المعروفة، يتمتع المفتاح بعدم قابلية التحديد من الناحية المعلوماتية
  2. عدم تضخم النص المشفر: خاصية الحفاظ على الدعم تتجنب توسع النص المشفر
  3. الابتكار النظري: أول تطبيق لأدوات الطوبولوجيا الجبرية في التشفير

القيود

  1. عدم الامتثال لـ IND-CPA: لا يمكن للبناء الخطي الحتمي تحقيق الاختلاف المعياري
  2. قيود الاستخدام العملي: قد تؤثر البنية الرياضية المعقدة على كفاءة التنفيذ الفعلي
  3. سيناريوهات التطبيق المحدودة: مناسب بشكل أساسي للسيناريوهات التي تتطلب أماناً سلبياً ولكن يمكنها قبول التشفير الحتمي

الأعمال ذات الصلة

الأنظمة التشفيرية الخطية التقليدية

  • تشفير Hill وأشكاله المختلفة
  • تحليل ضعف التحويلات الخطية محدودة الأبعاد

التشفير ما بعد الكم

  • أنظمة تشفير خرائط المجموعات الثنائية (PGM)
  • الأنظمة التشفيرية المتماثلة القائمة على نظرية الرسوم البيانية
  • طرق الحد الأدنى من الأشجار المولدة (MST) ومصفوفات المجاورة

التشفير الجبري

  • تطبيقات نظرية المجموعات في التشفير
  • نظرية التمثيل ونظرية الدرجات المتساوية

الخلاصة والمناقشة

الاستنتاجات الرئيسية

  1. تم بناء نظام تشفير متماثل بنجاح قائم على حلقة بيرنسايد اللانهائية الأبعاد
  2. إظهار الأمان النظري تحت نموذج الهجمات السلبية
  3. إثبات القيود الأساسية للمخططات الخطية الحتمية

الاتجاهات المستقبلية

  1. التوسعات غير الحتمية: إدخال العشوائية لتجنب هجمات CPA
  2. مجموعات لي الأخرى: استكشاف الخصائص التشفيرية لمجموعات لي المضغوطة المختلفة
  3. تحسينات التنفيذ: تطوير خوارزميات فعالة لعمليات حلقة بيرنسايد
  4. المخططات الهجينة: دمج تقنيات التشفير التقليدية لتحسين الاستخدام العملي

التقييم المتعمق

الابتكارية

  • اختراق نظري: أول تطبيق لنظرية حلقة بيرنسايد في التشفير
  • ابتكار المفاهيم: تجاوز القيود الأساسية للمنصات محدودة الأبعاد
  • العمق الرياضي: دمج الطوبولوجيا الجبرية ونظرية التمثيل والتشفير

المساهمات التقنية

  • إثباتات رياضية صارمة وتحليل نظري
  • إطار تقييم أمان شامل
  • وصف واضح لآليات الهجوم والدفاع

القيمة العملية

  • توفير أفكار جديدة لمجال التشفير ما بعد الكم
  • إظهار إمكانات النظريات الرياضية البحتة في التطبيقات
  • توفير حالة دراسية لفهم قيود التشفير الحتمي

القيود

  • عدم الامتثال لتعريفات الأمان المعيارية الحديثة
  • قد تكون تعقيدات التنفيذ عالية نسبياً
  • سيناريوهات التطبيق محدودة نسبياً

تمثل هذه الورقة محاولة مثيرة للاهتمام في البحث المتقاطع بين التشفير والرياضيات البحتة. بينما توجد قيود على الاستخدام العملي، فإنها توفر مساهمة قيمة لتطور النظرية في هذا المجال.