Primitive-Root Determinant Densities over Prime Fields and Implications for PRIM-LWE

إليك ملخص تقني مفصل للورقة البحثية بعنوان "كثافات محددات الجذور الأولية فوق الحقول الأولية وتداعياتها على مسألة PRIM-LWE" للباحث فيبين سينغ سيرهوات.

1. بيان المشكلة

تتناول الورقة سؤالاً جوهرياً يتعلق بمسألة PRIM-LWE (التعلم مع الأخطاء مع محدد الجذر الأولي)، والتي قدمها سيرهوات، ويو، وديسميدت.

• السياق: مسألة PRIM-LWE هي نوع من مسألة LWE القياسية حيث يتم تقييد المصفوفة السرية $S$ بحيث يكون محددها (determinant) عبارة عن جذر أولي (primitive root) بمقياس الحقل الأولي $p$ (أي أن $\det(S)$ يولد الزمرة الضربية $\mathbb{F}_p^*$).
• السؤال الجوهري: يعتمد الاختزال الأمني (security reduction) من مسألة Decision-LWE القياسية إلى Decision-LWE-PRIM على القدرة على أخذ عينات من المصفوفات السرية ذات محددات جذور أولية. وتُحكم كفاءة هذا الاختزال بواسطة ثابت البعد الموحد $c(p)$، والذي يُعرف بأنه الكثافة الحدية للمصفوفات من النوع $n \times n$ فوق $\mathbb{F}_p$ ذات محددات جذور أولية عندما تؤول $n \to \infty$:
  $$c(p) = \frac{\phi(p-1)}{p-1} \prod_{j=1}^{\infty} \left(1 - \frac{1}{p^j}\right)$$
• المشكلة المفتوحة: لاحظ سيرهوات وزملاؤه سابقاً أنه إذا كان هناك عدد لا نهائي من الأعداد الأولية المبرمية (primorial primes) (وهي الأعداد الأولية من الشكل $N_k + 1$ حيث $N_k$ هو حاصل ضرب أول $k$ من الأعداد الأولية)، فإن $\inf_p c(p) = 0$. وقد تساءلوا عما إذا كان هذا الحد الأدنى (infimum) يساوي صفراً بشكل غير مشروط (دون افتراض اللانهاية غير المثبتة للأعداد الأولية المبرمية).
• التداعيات: إذا كان $\inf_p c(p) = 0$، فإن عبء إعادة أخذ العينات بالرفض (rejection-sampling overhead) المتمثل في ($1/c(p)$) قد يصبح نظرياً كبيراً جداً لبعض الأعداد الأولية، مما قد يضعف الضمانات الأمنية العملية لمسألة PRIM-LWE لأنواع معينة من المقاييس (moduli).

2. المنهجية

قام المؤلف بحل المشكلة باستخدام نظرية الأعداد التحليلية الكلاسيكية، متجنباً الافتراضات غير المثبتة. تعتمد المنهجية على:

• مبرهنة ديريكليه للأعداد الأولية في المتواليات الحسابية: لضمان وجود أعداد أولية $p \equiv 1 \pmod{N_k}$ لأي $k$.
• مبرهنة ميرتنز الثالثة: لتقدير السلوك التقاربي للمنتج $\prod (1 - 1/p_i)$.
• مبرهنة لينيك: لتحديد حجم أصغر عدد أولي في متوالية حسابية، مما يحدد معدل التضاؤل الكمي.
• نظرية إردوس-وينتر: لتحليل التوزيع الحدّي للدوال الجمعية عند تقييمها على الأعداد الأولية المزاحة ($p-1$).
• مبرهنات النقل (Transport Lemmas): لنقل النتائج التوزيعية من نسبة التوتينت (totient ratio) $\phi(p-1)/(p-1)$ إلى الكثافة الكاملة $c(p)$.

3. المساهمات والنتائج الرئيسية

أ. تلاشي الحد الأدنى بشكل غير مشروط

تثبت الورقة بشكل غير مشروط أن $\inf_{p \text{ prime}} c(p) = 0$.

• الآلية: لأي $k$، تضمن مبرهنة ديريكليه وجود عدد لا نهائي من الأعداد الأولية $p \equiv 1 \pmod{N_k}$. بالنسبة لهذه الأعداد، يكون $N_k \mid (p-1)$. وبناءً عليه، فإن النسبة $\frac{\phi(p-1)}{p-1}$ تكون محدودة من الأعلى بـ $\prod_{i=1}^k (1 - 1/p_i)$. وبموجب مبرهنة ميرتنز، فإن هذا المنتج يؤول إلى 0 عندما تؤول $k \to \infty$.
• الأهمية: هذا يحل المسألة المفتوحة دون الحاجة إلى افتراض كون الأعداد الأولية المبرمية لانهائية. وهو يؤكد أن ثابت الاختزال يمكن أن يكون صغيراً جداً لأنواع معينة من الأعداد الأولية.

ب. الرتبة التقاربية الحادة

تحدد الورقة المعدل الدقيق الذي يتضاءل به الحد الأدنى للكثافة:
$$\min_{p \le x} c(p) \asymp \frac{1}{\log \log x}$$

• الحد الأعلى: تم اشتقاقه باستخدام مبرهنة لينيك لإيجاد أصغر عدد أولي $p \equiv 1 \pmod{N_k}$ تحت $x$.
• الحد الأدنى: تم اشتقاقه من خلال إثبات أنه لأي $p \le x$، فإن عدد العوامل الأولية المتميزة $\omega(p-1)$ يكون محدوداً، مما يمنع الكثافة من التضاؤل بسرعة أكبر من $1/\log \log x$.
• التداعيات: التضاؤل بطيء للغاية. بالنسبة لمعاملات الأمن السيبراني (مثل $2^{128}$ أو $2^{4096}$)، يكون $\log \log x$ صغيراً (حوالي 4.5 إلى 7.95)، مما يعني أن الكثافة تظل ذات أهمية عملية.

ج. التوزيع الحدي

تحدد الورقة السلوك الإحصائي لـ $c(p)$ عبر مجموعة كل الأعداد الأولية:

• التوزيع: تمتلك $c(p)$ توزيعاً حدياً مستمراً ومنفرداً تماماً $G$ عبر الأعداد الأولية.
• الدعم: دعم هذا التوزيع هو بالضبط الفترة $[0, 1/2]$.
• الخصائص: دالة التوزيع $G$ تزايدية تماماً على $[0, 1/2]$. وهذا يعني أنه لأي عتبة $\tau \in (0, 1/2)$، فإن مجموعة الأعداد الأولية التي تحقق $c(p) \le \tau$ لها كثافة نسبية موجبة $G(\tau)$.
• الارتباط: توزيع $c(p)$ مطابق لتوزيع نسبة التوتينت $\phi(p-1)/(p-1)$، حيث أن حد المنتج اللانهائي $\prod (1 - p^{-j})$ يتقارب بسرعة نحو 1.

د. حدود صريحة للمقاييس التشفيرية

تقدم الورقة حدوداً دنيا ملموسة لـ $c(q)$ بناءً على بنية التحليل لعوامل $q-1$، وتحديداً عدد العوامل الأولية المتميزة $\omega(q-1)$.

• الحد العام: $c(q) \ge P_3 \prod_{i=1}^{\omega(q-1)} (1 - 1/p_i)$، حيث $P_3 \approx 0.56$.
• معايير NIST:
  • ML-KEM ($q=3329$): حيث $\omega(q-1)=2$. العبء $1/c(q) \le 2.17$.
  • ML-DSA ($q=8380417$): حيث $\omega(q-1)=4$. العبء $1/c(q) \le 3.42$.
• الأعداد الأولية الصديقة لـ NTT: توضح الورقة أن "صداقة الـ NTT" (عادة $q \equiv 1 \pmod{2^t}$) وحدها لا تضمن حداً جيداً، لأنها تتحكم فقط في الجزء الـ 2-آدي (2-adic) من $q-1$. ومع ذلك، فإن معظم أعداد الـ NTT العملية تمتلك أيضاً عدداً قليلاً من العوامل الأولية الفردية الصغيرة، مما يؤدي إلى $\omega(q-1)$ صغير وبالتالي عبء إعادة أخذ عينات بالرفض ضئيل.
• الحد الشامل: لأي عدد أولي $q > 2^{30}$، فإن $1/c(q) \le 1.79 \log q$.

4. الأهمية والتداعيات

1. حل عدم اليقين النظري: تثبت الورقة بشكل نهائي أن ثابت الاختزال $c(p)$ يمكن أن يقترب من الصفر، ولكنه يفعل ذلك ببطء شديد ($\Theta(1/\log \log p)$). وهذا ينفي إمكانية وجود حد أدنى موحد عبر جميع الأعداد الأولية، لكنه يؤكد أن الأعداد "الأسوأ حالاً" نادرة وتتضاءل ببطء.
2. الأمن العملي لـ PRIM-LWE: تؤكد النتائج صلاحية الاستخدام العملي لـ PRIM-LWE مع المقاييس التشفيرية القياسية. عبء إعادة أخذ العينات بالرفض للمقاييس المعتمدة من NIST صغير (عوامل 2.17 و 3.42)، مما يعني أن الاختزال الأمني يظل وثيقاً وفعالاً.
3. التوجيه في اختيار المقاييس: توضح الورقة المقايضة في اختيار المقاييس. لضمان عبء صغير، يجب اختيار أعداد أولية $q$ حيث يكون لبنية تحليل $q-1$ تحكم (تحديداً، عدد قليل من العوامل الأولية المتميزة $\omega(q-1)$).
4. الرؤية الرياضية: ترسي علاقة عميقة بين كثافة PRIM-LWE والتوزيعات العددية الكلاسيكية (Erdős–Wintner)، مثبتة أن الكثافة تتبع قانوناً منفرداً مستمراً بدعم كامل على $[0, 1/2]$.

ختاماً، بينما الحد الأدنى النظري للكثافة هو صفر، تُظهر الورقة أنه بالنسبة لجميع الأغراض التشفيرية العملية، فإن الكثافة تظل بعيدة عن الصفر بمعامل ثابت صغير، مما يضمن بقاء مسألة PRIM-LWE خياراً قابلاً للتطبيق وآمناً.