براهين الأمان والاختزالات في مخططات الشبكات

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

يوضح البرهان الرائد الذي قدمه Regev عام 2005 أن خوارزمية تعمل في زمن كثير الحدود لحل LWE التقريرية يمكن استخدامها لحل GapSVP (مشكلة أقصر متجه بفجوة) في شبكات ذات n أبعاد في أسوأ الحالات. وهذا الاختزال كمومي؛ إذ يستخدم إجراءً كمومياً لأخذ العينات لتحويل خوارزمية حل LWE إلى خوارزمية لحل مسائل الشبكات. وهذا يعني أن LWE لا تقل صعوبته عن مسائل الشبكات في أسوأ الحالات في ظل الحوسبة الكمومية.

اختزال Regev غير محكم؛ إذ تعني العوامل كثيرة الحدود في الاختزال أن مستوى الأمان الذي يضمنه البرهان أضعف إلى حد ما من المستوى الذي توحي به أفضل الهجمات المعروفة. وعند اختيار المعلمات العملية، يستخدم علماء التشفير الأمان الملموس الذي توفره أفضل الهجمات المعروفة، باستخدام مقدِّر الشبكات، بدلاً من حد الاختزال النظري، لأن الاختزال متحفظ.

يُثبت أمان نظام تشفير قائم على LWE وفق IND-CPA (عدم القابلية للتمييز في ظل هجوم النص الصريح المختار) باستخدام حجة هجينة. ويوضح البرهان أن وجود مميّز IND-CPA يستلزم وجود مميّز لـ LWE. وفي الهجين الأول، يُستبدل النص المشفر الحقيقي بسلسلة عشوائية موزعة بانتظام؛ وتنتج عدم القابلية للتمييز من افتراض LWE. ويوفر ذلك برهان أمان واضحاً للتشفير الأساسي القائم على الشبكات.

لا يكفي أمان IND-CPA لآليات تغليف المفاتيح المستخدمة في TLS؛ إذ تحتاج هذه الآليات إلى أمان IND-CCA2 (في ظل هجوم النص المشفر المختار). ويحوّل تحويل Fujisaki-Okamoto (FO) أي نظام IND-CPA إلى KEM يحقق IND-CCA2 ضمن نموذج العرّافة العشوائية (ROM). ويطبق ML-KEM نسخةً من تحويل FO على التشفير الأساسي القائم على Module-LWE، مما يوفر أمان IND-CCA2 المطلوب للنشر في العالم الحقيقي.

يمثل نموذج العرّافة العشوائية (ROM) دوال التجزئة على أنها دوال عشوائية حقاً. وتتطلب براهين أمان كثيرة، بما في ذلك براهين تحويل FO، استخدام ROM. أما عملياً، فدوال التجزئة مثل SHA-3 ليست عرّافات عشوائية حقيقية، ولذلك لا تضمن براهين ROM الأمان في النموذج القياسي. ومع ذلك، تحظى براهين ROM بقبول واسع في مجتمع التشفير باعتبارها دليلاً قوياً على الأمان.

لا يفترض البرهان في النموذج القياسي أي مثالية بشأن دوال التجزئة، ولذلك فهو أقوى بصورة صارمة من برهان ROM. وتستخدم معظم الأنظمة العملية القائمة على الشبكات براهين ROM، لأن براهين IND-CCA2 في النموذج القياسي لآليات KEM القائمة على الشبكات أكثر تعقيداً بكثير وتنتج معلمات عملية أسوأ. وقد قبل NIST البراهين المستندة إلى ROM في ML-KEM، ورآها كافية لمستويات الأمان المستهدفة.

يتم برهان أمان ML-KEM على خطوتين. أولاً، يُثبت أن التشفير الأساسي القائم على Module-LWE يحقق أمان IND-CPA وفق افتراض M-LWE. ثانياً، يرقّي تحويل Fujisaki-Okamoto، وبالتحديد تحويلا T وU المستخدمان في Kyber، هذا الأمان إلى IND-CCA2 في نموذج العرّافة العشوائية الكمومي (QROM)، الذي يتعامل مع المهاجمين الذين يستعلمون من العرّافة العشوائية في تراكب كمومي.

يُعد مقدِّر الشبكات الذي وضعه Albrecht وPlayer وScott الأداة القياسية لحساب الأمان الملموس للأنظمة القائمة على LWE. وهو يضع نموذجاً لتكلفة أفضل هجمات الشبكات المعروفة، مثل BKZ باستخدام الغربلة أو التعداد، ويخرج تقديراً للأمان بالبتات لمعلمات محددة (n, q, sigma). وتُحدَّث الأداة بانتظام مع نشر خوارزميات جديدة ونماذج جديدة لتكلفة العتاد.

تُعد خوارزمية Block Korkine-Zolotarev (BKZ) أفضل خوارزمية عملية لاختزال الشبكات. ويعثر BKZ، باستخدام حجم كتلة beta، على متجهات قصيرة بتعقيد يقارب 2^{0.292*beta} عملية بوابة عند استخدام أفضل خوارزميات الغربلة. وبالنسبة إلى ML-KEM-768، يبلغ الأمان الكلاسيكي المقدَّر نحو 180 بتاً، ويبلغ الأمان الكمومي نحو 164 بتاً، وهما أعلى بكثير من الهدف البالغ 192 بتاً.

توضح براهين الأمان التقاربية أن النظام آمن بالنسبة إلى معلمات كبيرة بما يكفي، لكنها لا تحدد ما المقصود عملياً بعبارة «كبيرة بما يكفي». ويسد تحليل الأمان الملموس هذه الفجوة من خلال تقدير التكلفة الفعلية لأفضل هجوم على المعلمات المختارة. ويعتمد وضع معايير ما بعد الكم بدرجة كبيرة على تحليل الأمان الملموس، مع اختيار معلمات تقاوم الهجمات على العتاد الكمومي المتوقع خلال أفق زمني يبلغ 30 عاماً.

ما التحويل المستخدم لترقية تشفير الشبكات ذي أمان IND-CPA إلى أمان IND-CCA2 في ML-KEM؟

ترجع براهين أمان الأنظمة القائمة على الشبكات أمان النظام إلى صعوبة LWE أو SVP. ويضمن اختزال Regev أن LWE لا يقل صعوبة عن مسائل الشبكات في أسوأ الحالات. ويرقّي تحويل Fujisaki-Okamoto أمان IND-CPA إلى IND-CCA2 في ROM. ويُقيَّم الأمان الملموس باستخدام مقدِّر الشبكات ونماذج تعقيد BKZ. وتعني فجوات إحكام الاختزال أن المعلمات العملية تعتمد على تقديرات تكلفة الهجمات بدلاً من حدود الاختزال وحدها.