⚛️ quantum physics

Module Lattice Security (Part IV): Probabilistic Polynomial Quantum Attack on Module-LWE over 2-Power Cyclotomics

تقدم هذه الورقة هجوماً كمياً في وقت متعدد الحدود يكسر مخططات ML-KEM وFalcon وHawk وNTRU المعيارية عبر حلقات دورية من قوى العدد 2، وذلك باستخدام تفكيك برج لمسألة المثال الرئيسي لتحقيق احتمالية نجاح عالية مع عامل تقريب مُتحقق منه.

المؤلفون الأصليون: Ming-Xing Luo

نُشر 2026-05-19

📖 4 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Ming-Xing Luo

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

الصورة الكبيرة: مفتاح كوانتي لفتح الخزائن الرقمية

تخيل أن أكثر الخزائن الرقمية أماناً في العالم (مثل تلك التي تحمي الأسرار الحكومية أو بيانات البنوك) مبنية باستخدام نوع معين من "المتاهات" الرياضية. هذه المتاهات تعتمد على أشكال معقدة تسمى الشبكات (Lattices). حالياً، نعتقد أن هذه المتاهات ضخمة ومتعرجة جداً بحيث لا يمكن حتى لأسرع الحواسيب الفائقة حلها، وهذا هو سبب اعتبارها آمنة للمستقبل (التشفير ما بعد الكوانتوم).

تزعم هذه الورقة البحثية أنها وجدت مفتاحاً رئيسياً كوانتياً يمكنه فتح هذه المتاهات المحددة بشكل أسرع بكثير مما كان يعتقد الجميع. يجادل المؤلفون، بقيادة مينغ-شينغ لوو، بأن الحاسوب الكوانتي لا يحتاج فقط إلى أن يكون "سريعاً"، بل يجب أن يكون "ذكياً" بشأن الشكل المحدد للمتاهمة. ومن خلال استغلال اختصار هندسي مخفي، يمكنهم كسر أنظمة التشفير التي اختارها المعهد الوطني للمعايير والتقنية (NIST) مؤخراً كمعيار عالمي جديد.

الرحلة المكونة من أربعة أجزاء نحو الحل

هذه الورقة هي الجزء الأخير من سلسلة مكونة من أربعة أجزاء. فكر في الأمر كفريق من أربعة محققين يحلون جريمة سطو ضخمة، حيث حل كل محقق قطعة مختلفة من اللغز:

الجزء الأول (الخريطة): أثبتوا أن "تضاريس" هذه المتاهات بسيطة جداً في الواقع. الأمر يشبه اكتشاف أن غابة تبدو معقدة هي في الحقيقة شبكة حيث تؤدي كل مساراتها إلى ساحة مركزية واحدة. هذا يعني عدم وجود طرق مسدودة أو حلقات مخفية قد تربك المهاجم.
الجزء الثاني (الترجمة): أظهروا أنه يمكنك ترجمة مشكلة "الموديول" المعقدة (متاهة ثلاثية الأبعاد) إلى مشكلة "مثالية" أبسط (متاهة ثنائية الأبعاد) دون فقدان الكثير من المعلومات. الأمر يشبه إدراك أن لغزاً ثلاثي الأبعاد هو مجرد رسم مسطح تم طيه؛ يمكنك فكه بسهولة.
الجزء الثالث (المسطرة): قاموا بقياس "الضجيج" في النظام. في هذه المتاهات، يوجد دائماً قدر من السكون أو التشويش. لقد أثبتوا أن هذا التشويش صغير ويمكن التنبؤ به لدرجة أنه لا يخفي الحل. الأمر يشبه إدراك أن الضباب في الغابة رقيق جداً لدرجة أنك تستطيع رؤية علامة الخروج بوضوح.
الجزء الرابع (الهجوم - هذه الورقة): هذا هو التنفيذ. لقد جمعوا الخريطة، والترجمة، والمسطرة في وصفة واحدة (خوارزمية) يمكن للحاسوب الكوانتي اتباعها لكسر الشفرة.

كيف يعمل الهجوم: تشبيه "البرج"

جوهر هجومهم هو طريقة تسمى البرج السيكلوتومي (Cyclotomic Tower).

تخيل أنك تحاول تسلق برج ضخم مكون من 256 طابقاً للوصول إلى الطابق العلوي حيث يُحتفظ بالسر.

الطريقة القديمة (الحواسيب التقليدية): تحاول تسلق كل درجة واحدة تلو الأخرى. سيستغرق ذلك وقتاً طويلاً جداً (وقتاً أسياً).
الطريقة الكوانتية (طريقة المؤلفين): أدركوا أن البرج مبني في طبقات. بدلاً من التسلق درجة بدرجة، يمكنك ركوب مصعد يقفز من طابق إلى الطابق التالي، بحيث يحل لغزاً صغيراً عند كل توقف.
- الخطوة 1: اذهب إلى الطابق الثالث. حل لغزاً صغيراً.
- الخطوة 2: اذهب إلى الطابق الرابع. استخدم الإجابة من الطابق الثالث لحل لغز أكبر قليلاً.
- الخطوة 3: كرر العملية حتى تصل إلى القمة.

لأن هذا البرج مبني بنمط رياضي محدد (قوى العدد 2)، فإن طريقة "المصعد" هذه فعالة للغاية. يثبت المؤلفون أن الحاسوب الكوانتي يمكنه القيام بهذا التسلق بأكمله في وقت حدودي (Polynomial time). وباللغة البسيطة: إذا كان البرج مكوناً من 256 طابقاً، فقد يستغرق الحاسوب التقليدي وقتاً أطول من عمر الكون، لكن الحاسوب الكوانتي يمكنه القيام بذلك في الوقت الذي يستغرقه إعداد كوب من القهوة.

النتيجة: كسر المعايير

اختبرت الورقة هذه الطريقة ضد معايير التشفير المحددة التي اختارها NIST:

ML-KEM (Kyber): المعيار الأساسي لتبادل المفاتيح الآمن.
Falcon & Hawk: معايير التواقيع الرقمية (مثل بطاقة الهوية الرقمية).
NTRU: عائلة أخرى من أنظمة التشفير.

النتائج:
أجرى المؤلفون عمليات محاكاة وبراهين رياضية تظهر أن الخوارزمية الكوانتية الخاصة بهم يمكنها كسر هذه الشفرات بنسبة نجاح تبلغ 99%.

لقد حسبوا "هامش الأمان". تخيل أن القفل يتطلب مفتاحاً طوله 1,665 وحدة لكسره. مفتاحهم الكوانتي طوله حوالي 103 وحدات فقط.
ولأن مفتاحهم أقصر بكثير من الطول المطلوب، فإن القفل يفتح بسهولة.

إنهم يزعمون أن جميع مجموعات المعايير (parameter sets) لهذه الأنظمة تعتبر الآن "مكسورة" إذا وجد حاسوب كوانتي واسع النطاق.

التكلفة: ما مدى ضخامة الحاسوب الكوانتي؟

قد تتساءل، "ما مدى قوة هذا الحاسوب الكوانتي الذي نحتاجه؟"
لقد قام المؤلفون بحساب الموارد المطلوبة:

الكيوبتات (البتات الكمية): يقدرون أنك تحتاج إلى حوالي 1.4 مليون كيوبت فيزيائي (ما يترجم إلى حوالي 1,400 كيوبت "منطقي" أو مصحح للأخطاء).
الوقت: ستستغرق العملية وقتاً معقولاً، وهو ما يعادل تقريباً عدد العمليات التي يقوم بها حاسوب فائق حديث في بضعة أيام، ولكن يتم تنفيذها بواسطة آلة كوانتية.

العقبة:
هذا إنجاز نظري. نحن لا نملك حالياً حواسيب كوانتية تحتوي على 1.4 مليون كيوبت. ومع ذلك، تثبت الورقة أنه إذا بنينا واحداً، فإن معايير التشفير هذه لن تكون آمنة.

ملخص في جملة واحدة

تثبت هذه الورقة أن نوعاً معيناً من "المتاهات" الرياضية المستخدمة في التشفير الآمن الحديث يحتوي على اختصار مخفي يمكن لحاسوب كوانتي مستقبلي استغلاله، مما يسمح له بفتح النظام بمفتاح أصغر بكثير وأسهل في العثور عليه مما كان يُعتقد سابقاً.

ملخص تقني: هجوم كمي متعدد الحدود احتمالي على مسألة التعلم مع الخطأ الموديولي (Module-LWE) فوق السيكلوتوميات ذات قوى العدد 2

بيان المشكلة
تتناول الورقة البحثية أمن المخططات التشفيرية القائمة على "التعلم مع الخطأ الموديولي" (Module-LWE)، وتحديداً التركيز على معيار NIST المتمثل في ML-KEM (المعروف سابقاً بـ CRYSTALS-Kyber) والمخططات الأخرى المرتبطة بالشبكات (Falcon، Hawk، NTRU) المبنية فوق حلقات السيكلوتوميات ذات قوى العدد 2 ( $R = \mathbb{Z}[\zeta_{2^k}]$ ). تتمثل المشكلة المركزية في استعادة المفاتيح السرية عبر مسألة المتجه الأقصر (SVP) على الشبكات الموديولية. وبينما تعتمد الهجمات الكلاسيكية على خوارزميات تقليل الشبكة (مثل BKZ) ذات التعقيد الأسي، تبحث الورقة فيما إذا كان بإمكان خصم كمي استغلال البنية الجبرية للحلقات السيكلوتومية لحل مسألة المثالية الرئيسية (PIP) ومسألة المولد القصير (SGP) بكفاءة.

حدد المؤلفون سؤالين جوهريين لم يتم حلهما في الأعمال السابقة (تحديداً هجوم CDPR):

هل عامل التقريب الذي حققه هجوم CDPR صغير بما يكفي لكسر مفاتيح ML-KEM الكاملة (أي هل $\gamma < q/2$ )؟
هل تحقق خوارزمية PIP الكمية الأساسية تعقيداً زمنياً متعدد الحدود حقيقياً دون وجود أعباء زمنية أسية خفية أو الاعتماد على فرضية ريمان المعممة (GRH)؟

المنهجية
تقدم الورقة خط هجوم موحداً يتكون من أربع مراحل (الخوارزمية 1) يدمج النتائج من الأجزاء الأول والثاني والثالث من السلسلة مع خوارزمية كمية جديدة متعددة الحدود لحل مسألة PIP (الجزء الرابع).

اختزال الموديول إلى مثالية (Module-to-Ideal Reduction): يبدأ الهجوم باختزال حالة Module-LWE إلى مسألة مثالية رئيسية. باستخدام تفكيك "غرام-شميت"، يتم تحويل أساس الموديول إلى حاصل ضرب مثليات رئيسية. يثبت المؤلفون أن الاختزال لا يؤدي إلا إلى عامل ثابت $\alpha_d = O(1)$ ، وهو مستقل عن رتبة الموديول $d$ .
البرج الكمي لمسألة PIP (Quantum Tower PIP): بدلاً من حل مسألة PIP مباشرة في الحقل الكامل $\mathbb{Q}(\zeta_{2^k})$ $Q (ζ_{2^{k}})$ ، يقترح المؤلفون استراتيجية "تفكيك البرج". يقومون بتفكيك الحقل إلى سلسلة من الامتدادات التربيعية: $\mathbb{Q} \subset \mathbb{Q}(\zeta_8) \subset \dots \subset \mathbb{Q}(\zeta_{2^k})$ $Q \subset Q (ζ_{8}) \subset \dots \subset Q (ζ_{2^{k}})$ .
- في كل مستوى $L$ ، تقوم الخوارزمية بحل مسألة PIP للامتداد النسبي باستخدام مسألة المجموعة الجزئية الخفية الآبلية (Abelian HSP).
- من المهم ملاحظة أن عدد مولدات الوحدات الجديدة في كل مستوى ينمو خطياً ( $\Delta r_L = 2^{L-3}$ )، مما يحافظ على حجم مسألة HSP ضمن حدود متعددة الحدود.
- يتجنب هذا النهج انفجار المعاملات المتأصل في تمثيلات أساس القوة، ويلغي الحاجة إلى فرضية ريمان المعممة (GRH)، حيث ثبت أن عدد الفئات للحقل الجزئي الحقيقي الأقصى هو 1 لـ $k \le 12$ .
مسألة المتجه الأقرب في اللوغاريتم (Log-Unit CVP): بمجرد العثور على مولد $g$ $g$ للمثالية (والذي قد يكون طويلاً بشكل أسي)، تقوم الخوارزمية بحساب تمثيل اللوغاريتم الخاص به. بعد ذلك، تحل مسألة المتجه الأقرب (CVP) على شبكة اللوغاريتم-الوحدة لإيجاد فرق الوحدة $\epsilon$ $ϵ$ بحيث $g = g_0 \epsilon$ $g = g_{0} ϵ$ ، حيث $g_0$ $g_{0}$ هو المولد القصير.
- يستخدم المؤلفون خوارزمية "باباي" للمستوى الأقرب (Babai's nearest-plane algorithm). ويثبتون أنه بالنسبة للمولدات الحلقية القصيرة، يقع المتجه المستهدف ضمن "نصف قطر الالتقاط" للشبكة، مما يسمح لخوارزمية باباي باستعادة فرق الوحدة بدقة.
استعادة المولد القصير: يتم إعادة بناء الوحدة $\epsilon$ من حل مسألة CVP، ويتم استعادة المولد القصير كـ $g_0 = g \cdot \epsilon^{-1}$ .

المساهمات الرئيسية

حل PIP كمي متعدد الحدود: تقدم الورقة أول بناء لخوارزمية كمية متعددة الحدود لمسألة PIP فوق الحلقات السيكلوتومية ذات قوى العدد 2. التعقيد هو $O(n^3 \log^2 n)$ من البوابات الكمية و $O(n^2 \log n)$ من الكيوبتات، حيث $n$ هو درجة الحلقة. هذا يزيل العبء الأسي الذي كان مرتبطاً بخوارزمية Biasse-Song.
تحليل دقيق لعامل التقريب: يشتق المؤلفون عامل تقريب دقيق $\gamma = \alpha_d \cdot \exp(\sigma_d \sqrt{2 \ln n})$ . ويثبتون أن تباين $\sigma_d$ للتمثيل اللوغاريتمي هو $O(1)$ ومستقل عن المعامل $q$ .
التحقق من عدد الفئات: يعتمد العمل على الإثبات (من الجزء الأول) بأن عدد الفئات للحقل الجزئي الحقيقي الأقصى هو 1 ( $h^+_k = 1$ ) لجميع قيم $k \le 12$ ، مما يضمن أن كل مثالية هي مثالية رئيسية.
التوسع إلى مخططات متعددة: تم توسيع الإطار ليشمل ما وراء ML-KEM لتحليل متغيرات Falcon و Hawk و NTRU فوق السيكلوتوميات ذات قوى العدد 2، مما يثبت أن نفس نقاط الضعف الجبرية تنطبق عليها.

النتائج
يقدم المؤلفون تقديرات أمنية ملموسة لمجموعات المعلمات القياسية:

ML-KEM-1024: يحقق الهجوم عامل تقريب وسيط $\gamma_{med} \approx 21$ وعامل مئوي بنسبة 99% قدره $\gamma_{99\%} \approx 103$ . كلتا القيمتين أقل بكثير من عتبة الأمان $q/2 = 1665$ . تُقدر احتمالية النجاح بـ $\ge 0.99$ لـ $d \le 3$ وبـ $\ge 0.90$ لـ $d=4$ ، مع إمكانية تقليل احتمالية الفشل إلى $< 10^{-6}$ عبر التكرار.
تقديرات الموارد: بالنسبة لـ ML-KEM-1024 ( $n=256$ )، يتطلب الهجوم حوالي $2^{27}$ بوابة منطقية و $1.4 \times 10^6$ كيوبت فيزيائي (بافتراض كود السطح بمسافة 30).
مخططات أخرى:
- Falcon: يكسر الهجوم Falcon-512 و Falcon-1024 بهوامش قدرها $72\times$ و $63\times$ على التوالي.
- Hawk: يكسر الهجوم Hawk-512 و Hawk-1024. أما Hawk-256 فقد كُسر شرطياً؛ فبينما يتجاوز الحد الرسمي لنسبة 99% العتبة، تظهر المحاكاة التجريبية معدل نجاح قدره 99.99%.
- NTRU: ينطبق الهجوم على متغيرات NTRU-HPS و NTRU-HRSS فوق الحلقات السيكلوتومية ذات قوى العدد 2، محققاً هوامش تتراوح بين $11\times$ إلى $45\times$ .

الأهمية والادعاءات
تدعي الورقة أنها تحل الأسئلة المفتوحة المتعلقة بهجوم CDPR من خلال إثبات ما يلي:

عامل التقريب صغير بما يكفي لكسر جميع معايير ML-KEM و Falcon و Hawk و NTRU المعتمدة فوق الحلقات السيكلوتومية ذات قوى العدد 2 تحت هجوم كمي.
يمكن حل مسألة PIP في وقت متعدد الحدود الحقيقي ( $O(n^3 \log^2 n)$ ) دون عوامل أسية خفية أو الاعتماد على فرضيات نظرية عددية غير مثبتة مثل GRH.
تسمح البنية الجبرية للحلقات السيكلوتومية ذات قوى العدد 2 لخصم كمي بتقليل عامل التقريب من كونه فوق-متعدد الحدود ( $\approx 2^{54}$ في التقديرات السابقة) إلى ما دون-متعدد الحدود ( $\approx 2^{21}$ )، مما يكسر فعلياً افتراضات الأمان لهذه المرشحات لما بعد الكم.

يشير المؤلفون إلى أنه بينما الهجوم احتمالي، فإن احتمالية الفشل منخفضة ويمكن التخفيف منها عبر التكرارات المستقلة. كما يؤكدون أن النتائج تعتمد على الخصائص الجبرية المحددة للحلقات السيكلوتومية ذات قوى العدد 2 وتفاهة عدد الفئات لـ $k \le 12$ .