خوارزمية كسر التشفير المشهورة حصلت للتو على ترقية

هذه مهمة شركة LLL: امنحها (أو إخوانها) أساسًا لشبكة متعددة الأبعاد، وسوف تنتج شبكة أفضل. تُعرف هذه العملية باسم تقليل أساس الشبكة.

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

من الناحية النظرية، تعمل خوارزمية LLL الأصلية بسرعة: الوقت الذي يستغرقه التشغيل لا يتزايد بشكل كبير مع حجم الإدخال – أي بعد الشبكة وحجم (بالبت) الأرقام في ناقلات الأساس لكنه يزيد كدالة متعددة الحدود، و”إذا كنت تريد فعلًا القيام بذلك، فإن الزمن متعدد الحدود ليس ممكنًا دائمًا”، كما يقول ليو دوكاس، عالم التشفير في معهد الأبحاث الوطني CWI في هولندا.

من الناحية العملية، هذا يعني أن خوارزمية LLL الأصلية لا يمكنها التعامل مع المدخلات الكبيرة جدًا. قال كيغان رايان، طالب الدكتوراه في جامعة كاليفورنيا، سان دييغو: “أراد علماء الرياضيات وعلماء التشفير القدرة على فعل المزيد”. عمل الباحثون على تحسين خوارزميات نمط LLL لاستيعاب مدخلات أكبر، وغالبًا ما حققوا أداءً جيدًا. ومع ذلك، ظلت بعض المهام بعيدة المنال.

تجمع الورقة الجديدة، التي كتبها رايان ومستشارته نادية هيننجر، بين استراتيجيات متعددة لتحسين كفاءة خوارزمية نمط LLL. لسبب واحد، تستخدم هذه التقنية بنية متكررة تقسم المهمة إلى أجزاء أصغر. ومن ناحية أخرى، تدير الخوارزمية دقة الأرقام المعنية بعناية، وتوصل إلى التوازن بين السرعة والنتيجة الصحيحة. يتيح العمل الجديد للباحثين تقليل قواعد الشبكات بآلاف الأبعاد.

وقد اتبع العمل السابق نهجًا مشابهًا: تجمع ورقة عام 2021 أيضًا بين إدارة التكرار والدقة لإجراء عمل سريع للشبكات الكبيرة، ولكنها عملت فقط مع أنواع معينة من الشبكات، وليس كل تلك التي تعتبر مهمة في التشفير. تتصرف الخوارزمية الجديدة بشكل جيد على نطاق أوسع بكثير. وقال توماس إسبيتاو، الباحث في التشفير في شركة PQShield ومؤلف نسخة 2021: “أنا سعيد حقًا لأن شخصًا ما فعل ذلك”. وقال إن عمل فريقه قدم “دليلاً على المفهوم”. تظهر النتيجة الجديدة أنه “يمكنك القيام بتقليل الشبكة بسرعة كبيرة وبطريقة سليمة.”

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

يمكن لخوارزميات نمط LLL أيضًا أن تلعب دورًا في الأبحاث المتعلقة بأنظمة التشفير القائمة على الشبكة المصممة لتبقى آمنة حتى في المستقبل باستخدام أجهزة الكمبيوتر الكمومية القوية. وهي لا تشكل تهديدًا لمثل هذه الأنظمة، نظرًا لأن إزالتها تتطلب العثور على نواقل أقصر مما يمكن لهذه الخوارزميات تحقيقه. لكن أفضل الهجمات التي يعرفها الباحثون هي استخدام خوارزمية من طراز LLL باعتبارها “لبنة بناء أساسية”، كما قال ويسيل فان ووردين، عالم التشفير في جامعة بوردو. وفي التجارب العملية لدراسة هذه الهجمات، يمكن لهذه الكتلة الأساسية أن تبطئ كل شيء. وباستخدام الأداة الجديدة، قد يتمكن الباحثون من توسيع نطاق التجارب التي يمكنهم إجراؤها على خوارزميات الهجوم، مما يوفر صورة أوضح لكيفية أدائها.

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