أساس مشكلة التعلم مع الأخطاء (LWE)

التعلّم مع الأخطاء (LWE) الذي قدّمه Regev عام 2005: عند إعطائك عددًا كبيرًا من المعادلات الخطية المشوشة على Z_q، ابحث عن المتجه السري s. تكون الضوضاء e صغيرة، لكنها تمنع الحذف الغاوسي. من دون الضوضاء، يكون النظام سهلًا؛ أما مع وجود ضوضاء ولو صغيرة جدًا، فيصبح صعبًا حسابيًا.

المفتاح السري s ∈ Z_q^n. يتلقى الخصم عينات (a_i, b_i)، حيث تكون a_i ∈ Z_q^n عشوائية، وb_i = + e_i mod q، وتكون e_i ضوضاء صغيرة من التوزيع χ (مثل التوزيع الغاوسي ذي σ = √n). تتمثل المهمة في إيجاد s عند إعطاء عدد كثير حدودي من العينات.

من دون ضوضاء: b_i = mod q. يستعيد الحذف الغاوسي s بتعقيد O(n^3). مع الضوضاء: تكفي معادلة واحدة خاطئة لإفساد عملية الحذف. تكون الضوضاء صغيرة بما يكفي لنجاح فك التشفير باستخدام المفتاح، وكبيرة بما يكفي لمنع تحليل الشيفرة.

أثبت Regev أن LWE تختزل إلى مسائل الشبكات في أسوأ الحالات (SIVP وGapSVP) باستخدام اختزال كمومي. وهذا يعني أنه إذا أمكن كسر LWE، فسيكون بالإمكان حل العديد من مسائل الشبكات الصعبة، لكن لا توجد خوارزمية كمومية معروفة لمسائل الشبكات. لذلك تُعد LWE آمنة في مرحلة ما بعد الحوسبة الكمومية.

تستبدل RLWE ‏Z_q^n بالحلقة Z_q[x]/(f(x)) حيث f متعددة حدود دائرية. وتشفّر عينة RLWE واحدة n معادلات، ما يجعلها أكثر كفاءة بكثير. وتشكّل RLWE أساس Kyber (KEM) وDilithium (التوقيعات) وأنظمة HE مثل BFV وBGV وCKKS.

يعتمد الأمان على: n (البُعد، وعادةً ما يتراوح بين 512 و2048)، وq (المعامل، من 1024 إلى 2^60)، وσ (الانحراف المعياري للضوضاء). تؤدي زيادة n وتقليل نسبة σ/q إلى زيادة الصعوبة. تستخدم معايير NIST لما بعد الحوسبة الكمومية n=256 (بُعد الوحدة) مع k من الوحدات (k=2 أو 3 أو 4).

المفتاح العام: (A, b=As+e). لتشفير البت m: اختر r عشوائيًا، واحسب النص المشفر (u=A^T r, v = b^T r + m*q/2). لفك التشفير: v - s^T u = e^T r + m*q/2 ≈ m*q/2. قرّب إلى أقرب قيمة لـ m. تحافظ الضوضاء e على إخفاء m داخل النص المشفر أثناء التشفير.

تتمثل LWE التقريرية في التمييز بين (a, As+e) و(a, u)، حيث تكون u عشوائيةً وفق توزيع منتظم. ولا يمكن تمييزهما حسابيًا بافتراض صعوبة LWE. ويشكّل ذلك أساس الأمان الدلالي، إذ تبدو النصوص المشفرة كضوضاء عشوائية للخصوم الذين لا يملكون المفتاح السري.

أفضل الهجمات المعروفة هي اختزال الشبكات باستخدام BKZ (اختزال Block Korkine-Zolotarev). وتعقيدها شبه أسي، لكنه ليس كثير الحدود. وتتطلب BKZ-β تنفيذ 2^{0.292β} عملية. وبالنسبة إلى LWE-512، يبلغ الأمان نحو 128 بتًا ضد BKZ. ولا يُعرف أي تسريع كمومي لـ BKZ.

تُعد Module-LWE، المستخدمة في Kyber، نسخةً من RLWE على وحدات ذات رتبة k. وهي توفر مرونة؛ إذ يحقق k=2 أمانًا بمقدار 512 بتًا، وk=3 أمانًا بمقدار 768 بتًا، وk=4 أمانًا بمقدار 1024 بت. ويتدرج الأمان والأداء مع k. وقد اختارت NIST ‏Kyber، الذي أُعيدت تسميته إلى ML-KEM، معيارًا للتشفير ما بعد الكمومي.

يعتمد أمان RSA وECC على تحليل العوامل الصحيحة واللوغاريتم المتقطع، وهما معرضان للحوسبة الكمومية باستخدام خوارزمية Shor. أما أمان LWE فيعتمد على مسائل الشبكات الصعبة في أسوأ الحالات، ولا يوجد تسريع كمومي معروف لها. تبلغ أحجام المفاتيح نحو 1 كيلوبايت لمفاتيح LWE مقابل 256 بايتًا لـ RSA-2048. مفاتيح LWE أكبر، لكنها آمنة في مواجهة الحوسبة الكمومية.

ما الذي يجعل حل LWE صعبًا حتى مع توفر عدد كبير من العينات؟

تتمثل LWE في إيجاد المفتاح السري s من معادلات خطية مشوشة، وهي صعبة كموميًا. وتستخدم RLWE حلقات متعددة الحدود لتحقيق الكفاءة. وتشكل LWE وRLWE أساس Kyber وDilithium وأنظمة HE. التالي: نظاما HE ‏BGV وBFV لإجراء العمليات على الأعداد الصحيحة.