Ring-LWE وشبكات Module

يتطلب LWE القياسي عمليات ضرب كبيرة للمصفوفات والمتجهات، مما يؤدي إلى أحجام مفاتيح كبيرة. وقد استبدل Ring-LWE، الذي قدمه Lyubashevsky وPeikert وRegev عام 2010، المتجهات والمصفوفات بكثيرات حدود في الحلقة R_q = Z_q[X]/(f(X)). ويتيح هذا الإطار ذي البنية مفاتيح أصغر بكثير وحسابات أسرع، مما يجعل Ring-LWE أساسًا عمليًا لتشفير الشبكات في العالم الحقيقي.

يكون كثير الحدود f(X) المستخدم في Ring-LWE عادةً على الصورة f(X) = X^n + 1، حيث n قوة للعدد 2. وهذا هو كثير الحدود السيكلوتومي من الرتبة 2n. ويُختار لأنه غير قابل للاختزال على Z، ويضمن امتلاك الحلقة R_q خصائص جبرية جيدة، ويتيح تحويل نظرية الأعداد (NTT) لإجراء الضرب بكفاءة. وقد دُرست الحلقات السيكلوتومية دراسة عميقة، ويُعتقد أنها آمنة.

في Ring-LWE، يكون السر s كثيرة حدود في R_q، وتأخذ العينات الشكل (a, b = a*s + e)، حيث a عنصر عشوائي موزع بانتظام من الحلقة، وe كثيرة حدود صغيرة للأخطاء. ويرى المهاجم عددًا كبيرًا من هذه العينات، وعليه استرجاع s أو تمييزها من العينات الموزعة بانتظام. وتستند الصعوبة إلى افتراض Ring-LWE، الذي يملك اختزالًا من مشكلات الحالة الأسوأ على الشبكات المثالية.

تكون Ring-LWE أصعب على المهاجم، لكنها تأتي أيضًا باختزال أمني يختلف قليلًا عن اختزال LWE العادي. فالاختزال ينطلق من مشكلات الحالة الأسوأ على الشبكات المثالية (ideal-SVP)، وليس من الشبكات العامة. ومن حيث المبدأ، قد تجعل البنية الإضافية للشبكات المثالية مهاجمتها أسهل من الشبكات العامة، ولا يزال هذا مجالًا نشطًا للبحث. ولا يُعرف أي هجوم عملي يستغل هذه البنية.

تعمم Module-LWE (M-LWE) كلًا من LWE وRing-LWE، إذ تعمل على مصفوفة k x k من عناصر الحلقة بدلًا من عنصر حلقي واحد أو مصفوفة كبيرة من الأعداد الصحيحة. وعندما تكون k = 1، تختزل إلى Ring-LWE؛ ومع ازدياد k، تقترب من LWE القياسية. وتتيح هذه المعلمة القابلة للضبط k تحقيق توازن بين الثقة بالأمان والأداء.

يعتمد CRYSTALS-Kyber، المعروف الآن باسم ML-KEM وFIPS 203، على Module-LWE مع مصفوفة من الرتبة k فوق R_q. وتتحكم المعلمة k مباشرةً في مستوى الأمان: تستهدف k=2 أمانًا بمستوى 128 بت (ML-KEM-512)، وتستهدف k=3 مستوى 192 بت (ML-KEM-768)، وتستهدف k=4 مستوى 256 بت (ML-KEM-1024). وتتيح بنية الوحدات استخدام قاعدة شيفرة واحدة مع تغيير مستوى الأمان بتغيير k.

يُعد ضرب كثيرات الحدود في R_q = Z_q[X]/(X^n + 1) عنق الزجاجة من حيث الأداء. وتحول تقنية تحويل نظرية الأعداد (NTT)، وهي تحويل فورييه متقطع على Z_q، كثيرات الحدود إلى صيغة التقييم، حيث يصبح الضرب عملية عنصر بعنصر. وعند اختيار q بحيث ينطبق NTT، يستغرق ضرب كثيرات الحدود زمنًا قدره O(n log n) بدلًا من O(n^2)، وهو تحسين حاسم في ML-KEM وML-DSA.

يتطلب NTT أن يكون q عدداً أولياً بحيث q = 1 mod 2n، مما يضمن احتواء Z_q على جذر وحدة بدائي من الرتبة 2n. وبالنسبة إلى ML-KEM حيث n = 256، يحقق q = 3329 هذا الشرط. ويتميز NTT على Z_3329 بسرعة فائقة على العتاد الحديث المزود بتعليمات SIMD، مما يتيح تنفيذ آلاف عمليات ML-KEM في الثانية على المعالجات المركزية المتاحة تجارياً.

يؤدي كل من Ring-LWE وModule-LWE إلى تقليص أحجام المفاتيح بدرجة كبيرة مقارنةً بـ LWE القياسي. فقد يبلغ حجم المفتاح العام في LWE القياسي لتحقيق أمان بمقدار 128 بتاً نحو 1 MB؛ بينما يقلله Ring-LWE إلى نحو 800 بايت، ويحقق Module-LWE (ML-KEM-768) مفتاحاً عاماً حجمه 1184 بايت مع أمان لما بعد الكم بمقدار 192 بتاً. وتجعل هذه البنية المدمجة مخططات الشبكات عملية بالنسبة إلى TLS والأنظمة المضمنة.

يشعر بعض علماء التشفير بالقلق من أن البنية الجبرية الإضافية للحلقات السيكلوتومية قد تتيح هجمات لا تنطبق على LWE العادي. ففي عام 2024، نشر Elias Rokicki وزملاؤه تحليلاً لمتعدد الحدود السيكلوتومي من الرتبة 2n، ولم يجدوا استغلالات عملية، لكنهم أبرزوا أهمية مواصلة التدقيق. وقد أخذت عملية NIST الخاصة بالتشفير ما بعد الكم هذا الخطر في الحسبان، واختارت Module-LWE جزئياً لتقليل الاعتماد على بنية حلقية واحدة.

بالإضافة إلى Kyber، يشكل Ring-LWE أساس CRYSTALS-Dilithium (ML-DSA)، وهو نظام التوقيع الذي وضع NIST معياره. وتتيح مكتبة SEAL من Microsoft التشفير المتجانس باستخدام Ring-LWE. كما تتضمن مكتبة Tink للتشفير من Google دعماً لـ ML-KEM. وقد انتقل Ring-LWE من بناء نظري إلى نشر في بيئات الإنتاج خلال فترة قصيرة بصورة لافتة، مدفوعاً بعملية وضع المعايير التي أجراها NIST.

ما الميزة الأساسية لـ Ring-LWE مقارنةً بـ LWE القياسي؟

ينقل Ring-LWE مسألة LWE إلى حلقة كثيرات الحدود R_q = Z_q[X]/(X^n+1)، مما يقلل أحجام المفاتيح بدرجة كبيرة ويتيح حسابات سريعة تستند إلى NTT. ويعمم Module-LWE هذا الأسلوب باستخدام بنية ذات رتبة k، وهو ما يشكل أساس ML-KEM (FIPS 203) وML-DSA (FIPS 204). كما يتيح العدد الأولي q = 3329، الملائم لـ NTT، تنفيذاً فعالاً. ويستند الأمان إلى صعوبة المسائل على الشبكات المثالية وشبكات الوحدات.