التعلّم مع الأخطاء: المسألة الصعبة

طرح Oded Regev مسألة التعلم مع الأخطاء (LWE) عام 2005 بوصفها أساسًا للتشفير ما بعد الكمي. وبمعرفة مصفوفة عشوائية A على Z_q ومتجه ‎b = As + e‎، يكون الهدف هو إيجاد المتجه السري s. والمتجه e هو خطأ صغير مستمد من توزيع غاوسي متقطع، مما يجعل حل المسألة غير عملي حسابيًا.

في مشكلة LWE، تكون A مصفوفة عشوائية بأبعاد m x n، مأخوذة بانتظام من Z_q، حيث q عدد أولي يُستخدم معاملًا. أما السر s فهو متجه ذو n أبعاد، وe متجه أخطاء صغير تُسحب عناصره من توزيع غاوسي ضيق. وحتى مع معرفة بنية A، لا يستطيع المهاجم تمييز b من متجه عشوائي موزع بانتظام.

هناك صيغتان قياسيتان لمشكلة LWE. تطلب LWE البحثية استرجاع السر s مع إعطاء عدد كبير من العينات (A, b). أما LWE التقريبية فتطلب تمييز العينات (A, As + e) من الأزواج العشوائية الموزعة بانتظام (A, u). والصياغتان متكافئتان من الناحية متعددة الحدود، أي إن تحويل خوارزمية تحل إحداهما إلى خوارزمية تحل الأخرى ممكن.

يُسحب حد الخطأ في LWE من توزيع غاوسي متقطع على الأعداد الصحيحة، مَعْلَمًا بالانحراف المعياري sigma. وتضمن قيم sigma الصغيرة أن يكون e قصيرًا مقارنةً بـ q، مما يجعل b يبدو تقريبًا مثل As mod q. ولو كانت sigma تساوي صفرًا، لما وُجد خطأ، ولأمكن حل النظام باستخدام الحذف الغاوسي؛ لذلك فالخطأ عنصر أساسي في الصعوبة.

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

بخلاف RSA وتشفير المنحنيات البيضوية، لا توفر أي خوارزمية كمومية معروفة تسريعًا أُسّيًا ضد LWE. ولا تمنح خوارزمية Grover أكثر من تسريع تربيعي، كما أن أفضل خوارزميات الشبكات الكمومية، وهي متغيرات من BKZ، لا تكسر LWE عند اختيار المعلمات بصورة صحيحة. وهذا يجعل LWE أساسًا قويًا للأمن ما بعد الكم.

يتحكم في أمان LWE ثلاثة معلمات: البعد n، أي طول السر، والمعامل q، والانحراف المعياري للخطأ sigma. ويؤدي تكبير n وتصغير النسبة q/sigma إلى زيادة الأمان. ولتحقيق أمان ما بعد الكم بمستوى 128 بت، تكون القيم المعتادة n = 1024، وq نحو 12289، وsigma نحو 3.2. وتُستخدم أداة تقدير الشبكات التي طورها Albrecht وآخرون لتقييم الأمان الفعلي.

مشكلة الحل الصحيح القصير (SIS) هي افتراض ذو صعوبة مرتبطة بالشبكات، ويُستخدم في التواقيع. عند إعطاء مصفوفة عشوائية A على Z_q، يجب إيجاد متجه قصير غير صفري x بحيث Ax = 0 mod q. وتشكّل SIS أساس دوال التجزئة ومخططات التوقيع في عالم الشبكات، وهي تكمل LWE التي تقوم عليها عمليات التشفير وتغليف المفاتيح.

يعمل مخطط تشفير بسيط قائم على LWE كما يلي: المفتاح العام هو (A, b = As + e)، والمفتاح السري هو s. ولتشفير بت m، يحسب المرسل (u, v) = (A^T r, b^T r + m * floor(q/2)) لمتجه ثنائي عشوائي r. ثم يحسب فك التشفير v - s^T u ويقرّب الناتج لاسترجاع m. يحقق هذا المخطط أمان IND-CPA وفق افتراض LWE.

أتاحت LWE نطاقًا واسعًا من البنى التشفيرية التي تتجاوز التشفير الأساسي. وتشمل هذه البنى التشفير متجانسًا بالكامل (FHE)، والتشفير القائم على الهوية (IBE)، والتشفير القائم على السمات (ABE)، وبروتوكولات تبادل المفاتيح. ويُعد CRYSTALS-Kyber، المعروف الآن باسم ML-KEM والمقنن باعتباره FIPS 203، أكثر المخططات القائمة على LWE استخدامًا في التطبيقات العملية.

بدأ التشفير القائم على LWE يدخل أنظمة الإنتاج بالفعل. وأجرت Google وCloudflare تجارب على TLS باستخدام Kyber بين عامي 2018 و2020. وأضاف Chrome وFirefox دعمًا لـ ML-KEM-768 في مصافحات TLS الهجينة عام 2024. وأضاف Signal Protocol طبقة ما بعد الكم (PQXDH) باستخدام ML-KEM-1024 لتحقيق السرية الأمامية، وحماية سرية الرسائل طويلة الأمد من الحواسيب الكمومية المستقبلية.

أي عبارة تصف على أفضل وجه ضمان الصعوبة الذي توفره مشكلة LWE؟

تُعد LWE أحد أكثر افتراضات الصعوبة في مرحلة ما بعد الكم دراسةً، إذ يدعمها اختزال قوي من الحالة الأسوأ لمشكلات الشبكات. وتتحكم معلماتها الثلاث (n, q, sigma) في المفاضلة بين الأمان والأداء. تقاوم LWE الهجمات الكمومية، وتدعم المخططات التي قننتها NIST. وفهم LWE هو المدخل إلى جميع تقنيات التشفير الحديثة القائمة على الشبكات، بما في ذلك ML-KEM وML-DSA.