The complexity of solving a system of equations of the same degree
تضع هذه الورقة حدوداً عليا لدرجة الانتظام وتعقيد الحل لأنظمة المعادلات ذات الدرجة نفسها، والتي تُعد ذات صلة بعلم التشفير، وذلك من خلال تحليل تأثير عدد المعادلات، والمتغيرات، ودرجة المعادلة، مع أو بدون معادلات الحقل.
البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل
تخيل أنك تحاول فك شفرة سرية، ولكن بدلاً من قفل ذي أرقام، يتكون القفل من شبكة متشابكة من الألغاز الرياضية. في عالم التشفير، وتحديداً النوع المصمم للصمود أمام وصول الحواسيب الكمومية القوية، غالباً ما تكون هذه الألغاز عبارة عن أنظمة من المعادلات متعددة الحدود. فكر في هذه المعادلات كقواعد للعبة: "إذا كان لديك تفاحتان وثلاث برتقالات، فيجب أن يكون المجموع خمسة". في العالم الحقيقي، تكون هذه القواعد أكثر تعقيداً بكثير، حيث تتضمن عشرات المتغيرات وقوى عالية، وكل ذلك يحدث داخل كون رياضي محدود (مثل ساعة لا تحتوي على 12 ساعة بل على 256 ساعة).
السؤال الكبير لخبراء الأمن هو: ما مدى صعوبة حل هذه الشبكة من القواعد؟ إذا كانت سهلة للغاية، فقد كُسرت الشفرة السرية. وإذا كانت مستحيلة الصعوبة، فإن الشفرة آمنة. ولقياس هذه الصعوبة، يستخدم الرياضيون مفهوماً يسمى "درجة الانتظام". يمكنك التفكير في هذا المفهوم كـ "الارتفاع الأقصى" للجبل الذي يتعين عليك تسلقه لتجد الحل. لفترة طويلة، خمن الخبراء كم سيكون ارتفاع هذا الجبل بافتراض أن اللغز يتصرف بطريقة "متوسطة" أو "عشوائية" للغاية. ولكن ماذا لو لم يكن اللغز متوسطاً؟ ماذا لو كان له بنية غريبة ومحددة تجعل الجبل أعلى أو أقل من التخمين؟ تأتي هذه الورقة البحثية لتجيب على هذا السؤال بخريطة لا تعتمد على التخمين.
قام المؤلفان، جوليا غاغيرو وإليسا غورلا، بابتكار طريقة جديدة لحساب الارتفاع الأقصى المطلق لهذا الجبل لنوع معين من الألغاز: وهو النوع الذي يكون فيه كل قانون (معادلة) له نفس درجة التعقيد تماماً. هما لا يخمنان فحسب؛ بل يثبتان حدوداً عليا صارمة لمدى وصول درجة الانتظام. تعتمد نتائجهم على فكرة رياضية مشهورة ومعتقد بها على نطاق واسع تسمى "حدسية إيزنباود-غرين-هاريس"، لكنهم لا يعتمدون على الافتراضات المهتزة التي تقول "من المحتمل أن يكون عشوائياً" والتي يستخدمها خبراء التشفير عادةً.
إليك جوهر اكتشافهما: لقد وجدا أن ارتفاع الجبل يعتمد على ثلاثة أشياء بسيطة: عدد القواعد التي لديك، وعدد المتغيرات (المجاهيل) في اللعبة، ودرجة المعادلات نفسها. لقد أثبتا أنه إذا كان لديك نظام من المعادلات من نفس الدرجة، فهناك سقف صلب لمدى التعقيد. وإذا أضفت "معادلات المجال" (وهي قواعد إضافية تقول "لا يمكنك العد بما يتجاوز حجم الكون")، فقد وجدا سقفاً مشابهاً ومختلفاً قليلاً.
لماذا يهم هذا؟ لأن أمن العديد من مخططات التشفير يعتمد على فكرة أن حل هذه المعادلات صعب للغاية. إذا كانت الحدود العليا الجديدة التي أثبتتها المؤلفتان أقل مما كان يُعتقد سابقاً، فقد يعني ذلك أن بعض الأنظمة أقل أماناً مما كنا نأمل. وعلى العكس من ذلك، إذا كانت الحدود عالية، فإن ذلك يؤكد أن النظام هو بالفعل لغز يصعب حله. وتستبعد الورقة البحثية صراحةً فكرة أنه يمكننا دائماً الاعتماد على افتراض "شبه الانتظام" (الفكرة القائلة بأن النظام يتصرف مثل مجموعة عشوائية ومتوسطة من المعادلات) للحصول على الإجابة الصحيحة. في الواقع، يظهران أنه بالنسبة لخيارات معينة من المعلمات، فإن التسلسل "شبه المنتظم" ببساطة لا يوجد. طريقتهم تعمل حتى عندما يكون النظام غريباً أو مهيكلاً، مما يوفر شبكة أمان من الرياضيات المثبتة بدلاً من مجرد تخمين.
في عالم تحليل التشفير الجبري، حيث يحاول المهاجمون كسر الشفرات عن طريق تحويلها إلى أنظمة معادلات ضخمة، توفر هذه الورقة البحثية مسطرة جديدة. إنها تقيس "درجة الحل" – وهي النقطة التي سيجد عندها خوارزم الحاسوب (مثل محلل أساس غروبر) الإجابة أخيراً. تُظهر المؤلفتان أنه بالنسبة للأنظمة ذات الدرجة نفسها، فإن درجة الحل هذه تكون محكومة بصيغة تتضمن عدد المعادلات والمتغيرات. بل إنهما تقدمان صيغاً محددة للحالات التي تكون فيها المعادلات تربيعية (درجة 2) أو تكعيبية (درجة 3)، وللأنظمة فوق الحقول الثنائية (حيث كل شيء هو 0 أو 1).
يكمن جمال عملهما في أنه تحليل لـ "السيناريو الأسوأ". هما لا يقولان "هذا النظام سهل". بل يقولان: "مهما كان ترتيب هذه الأنواع المحددة من المعادلات، فلن تحتاج أبداً لتسلق أعلى من هذا الارتفاع المحدد". وهذا أمر بالغ الأهمية لأنه يمنح خبراء التشفير ضماناً مثبتاً. إذا وقعت معلمات النظام ضمن حدودهما، فنحن نعرف بالضبط مقدار القوة الحوسبية المطلوبة لكسره، دون الحاجة إلى إجراء عمليات محاكاة مكلفة أو الأمل في أن يتصرف النظام بشكل "طبيعي".
كما تتناول الورقة البحثية الموقف المعقد حيث تكون المعادلات "فائقة التحديد" (أي وجود قواعد أكثر من المجاهيل). في هذه الحالات، يظهران أن التعقيد غالباً ما ينخفض إلى مستوى المعادلات نفسها، مما يجعل حلها أسهل. كما ينظران فيما يحدث عند إضافة "معادلات المجال" (قواعد الحقل المحدود) إلى المزيج، وهو خطوة شائعة في الهجمات الواقعية. ويثبتان أن إضافة هذه المعادلات لا يجعل الجبل أعلى؛ بل في الواقع، غالباً ما يجعل الطريق إلى القمة أقصر أو يبقى كما هو.
في نهاية المطاف، يتعلق هذا البحث باستبدال "أنا أعتقد" بـ "أنا أعلم". وبينما تعتمد النتائج على حدسية كبرى في الجبر التبادلي (وهي مقبولة على نطاق واسع ولكن لم تثبت بعد)، فإن الحدود نفسها دقيقة رياضياً ضمن هذا الإطار. إنها تقدم حداً واضحاً ومثبتاً لأمن العديد من مخططات التشفير لما بعد الكم. بالنسبة لمراهق فضولي حول كيفية الحفاظ على أسرارنا في عالم رقمي، فإن هذه الورقة تشبه العثور على المخطط لأقوى قفل في الكون، حيث توضح بالضبط عدد الدورات اللازمة لفتح القفل، بغض النظر عن مدى مهارة صانع القفل في جعله معقداً. إنها تذكرنا بأنه في المعركة بين صانعي الشفرات وكاسريها، أحياناً يكون أفضل سلاح هو حقيقة رياضية دقيقة وغير قابلة للتزعزع.
غارق في أبحاث مجالك؟
تصلك نشرة يومية بأحدث الأبحاث المطابقة لكلماتك البحثية المفتاحية — مع ملخصات تقنية، بلغتك.