نقدم ونحلل عائلة من دوال التجزئة والتصفية التي من المرجح أن تنتج تصادمات لتكوينات صغيرة قابلة للتخفيض من المتجهات. قد تقدم هذه الدوال تحسينات عملية لعمليات غربلة الشبكة للمتجهات القصيرة. بشكل خاص، في إطار تقارب واحد، تظهر العائلة سلوكاً تقاربياً مختلفاً بشكل ملحوظ عن دوال التجزئة والتصفية الحالية.
كما نعرض عائلة من دوال التجزئة والتصفية التي تزيد من احتمال حدوث تصادمات لتكوينات المتجهات الصغيرة القابلة للتخفيض. قد توفر هذه الدوال تحسينات عملية لعمليات غربلة الشبكة للمتجهات القصيرة. بشكل خاص، في إطار تقارب محدد، تظهر هذه العائلة سلوكاً تقاربياً مختلفاً بشكل كبير عن الدوال المستخدمة حالياً.
تعتمد خوارزميات ما بعد الكم مثل Kyber وDilithium وFALCON وFrodo وNTRU وغيرها على صعوبة إيجاد متجه قصير في شبكة، ولذلك فإن فهم صعوبة هذه المسألة الرياضية في الأبعاد الكبيرة مهم جداً لاختيار معاملات هذه الخوارزميات. وفقاً للفهم الحالي، يُعتقد أن الطريقة الأكثر فعالية لإيجاد متجهات قصيرة في شبكة ذات بعد كبير \(d\) هي "الغربلة". تم تقديم مفهوم غربلة متجهات الشبكة القصيرة لأول مرة بواسطة أجتاي وكومار وسيفاكومار (AKS). في خوارزميات الغربلة هذه، يُنتَج عدد كبير من المتجهات (بأسِّيّة في \(d\)) بأطوال متقاربة عن طريق أخذ مجموعات خطية صغيرة من متجهات الأساس. ثم تتم مقارنة أزواج المتجهات لمعرفة ما إذا كان جمع أو طرح أحدهما من الآخر يؤدي إلى متجه أقصر من أحدهما. بعد ذلك يُستبدل المتجه الأطول بالمتجه الأقصر في المجموعة وتتكرر العملية حتى لا يمكن العثور على متجه أقصر. تُستخدم استدلالات منظورة لتبرير حجم العينة اللازم للثقة في إيجاد متجهات أقصر بشكل مستمر.
كانت الفكرة الأولية (AKS) تعتمد على مقارنة جميع الأزواج الممكنة من المتجهات، لكن التحسينات التالية قللت من وقت التشغيل عبر النظر فقط في الأزواج "القريبة" إذ كانت الأكثر احتمالاً لإنتاج متجهات أقصر. لا يزال حساب المسافة بين كل زوج يستغرق وقتاً مربعياً في عدد المتجهات، لكن تجزئة كل متجه بدالة تحتفظ ببعض المعلومات عن موضعه تتيح الفرز حسب قيمة التجزئة للعثور على أزواج قريبة. تُعرف هذه الدوال بـ "التجزئة الحساسة للمسافة" (LSH)؛ انظر (polytope) كمثال. نهج مماثل (filter) هو عائلة من دوال التصفية التي تنتج مخرجاً ثنائياً لكل متجه، بحيث تمر المتجهات القريبة بقائمة من المعايير المحتملة.
تمتد خوارزميات الغربلة لتشمل ليس فقط الأزواج بل أيضاً الثلاثيات أو بشكل عام مجموعات تتكون منها مجموعة خطية أقصر (tuple). إيجاد مثل هذه المجموعات الخطية أكثر تعقيداً من حالة الأزواج حيث تناظر خطوة خفض إقليدس، إلا أن هناك خوارزميات سريعة مخصصة لإيجاد أقصر مجموعات خطية من ثلاثة (semaev) أو أربعة (nguyen) متجهات. نظراً لأن تعقيد الغربلة يتأثر بشكل ضعيف جداً بخطوة الخفض، يمكن فحص مجموعات أكبر لمجموعات خطية أقصر (مثل تعداد Schnorr-Euchner (schnorr) أو حتى غربلة بأبعاد أقل). طالما وُجدت مجموعة خطية أقصر بنِسَب إيجابية، تستمر الغربلة. التكوينات القابلة للخفض من مجموعات \(k\) تصبح أكثر شيوعاً مع زيادة \(k\)، ما يقلل عدد المتجهات الأولية المطلوبة ويخفض تكلفة الذاكرة. في هذه الورقة ننظر في مسألة إيجاد التكوينات القابلة للخفض من مجموعات \(k\)، مع التركيز على الحالة \(k=3\).
لتسريع الغربلة الحسابية لمجموعات \(k\)، نحتاج إلى دالة تصفية تحدد المجموعات القابلة للخفض بجهد أقل من فحص كل مجموعة. يتطلب ذلك توصيف عائلة كبيرة من الثلاثيات/المجموعات القابلة للخفض بالإضافة إلى اختبار رخيص ولكنه قوي لاختيار هذه المجموعات ضمن عينة ضخمة. النهج الحالية (klist, fast_tuple) تُنشئ مجموعة \(k\) تدريجياً من متجه إلى زوج ثم ثلاثي ... حتى \((k-1)\)-مجموعة، حيث يُختار كل متجه جديد من تصادمات التجزئة الزوجية أو عبر بقاء التصفية الثنائية.
في هذه الورقة نستكشف نهجاً مباشراً حيث نحدد مجموعات \(k\) القابلة للخفض عبر تصادمات \(k\)-طريق في دوال التجزئة أو عبر عائلات من \(k\) ناجيات من التصفية. نقترح تعميماً لتجزئة الزاوية من (angular, polytope) يمكن استخدامه كاختبار إحصائي لتحديد التكوينات القابلة للخفض. يرتبط هذا التعريف بمشكلة إيجاد مجموعات من المتجهات تقع جميعها بالقرب من نفس الفضاء الفرعي ذو \((k-1)\) بُعد. في هذه الحالة قد تصلح طرقنا أيضاً للتصنيف والتجميع في بيانات عالية الأبعاد عامة. يقدم تعميمنا تجزئات حساسة للمسافة لحالة \(k=2\)، تظهر سلوكاً تقاربياً مختلفاً عن التجزئات الحالية وقد يكون مفيداً لتطبيقات الغربلة. تشير تحليلاتنا إلى إمكانية تكييف التصفية لعائلات ناجيات من \(k\) وعائلة جديدة من دوال التصفية التي تستحق مزيداً من البحث.
تُعرّف دالة التجزئة للشبكة المتقاطعة كما في (polytope) من خلال اختيار \(d\) متجهات غاوسية مستقلة \(\vv r_i\). لكل متجه \(\vv v\) نُحسب \(\pm\vv r_i\cdot\vv v\)، ثم نختار الفهرس غير الموقع \(\pm i\) الذي يحقق أكبر قيمة مطلقة للجداء القياسي. قيمة التجزئة هي \[ H(\vv v)=(-1)^b i:\;b\in\{0,1\},\;(-1)^b\vv r_i\cdot\vv v\ge|\vv r_j\cdot\vv v|\;\forall\,1\le j\le d. \] بسبب ارتفاع البعد، يكون المتجه \(\vv r_i\) تقريباً متعامداً مع الباقي وذو نفس الطول، ما يجعله تقريبيّاً محور شبكة متقاطعة عشوائية. أشكال التجزئة تقترب حينها من اختيار أقرب رأس في تلك الشبكة، نسلّط عبره المتجهات القريبة لتصادم مشترك.
نلاحظ بعض النقاط حول هذه التجزئة تمهيداً لاختيارنا لتجزئة مشتركة تعمل كاختبار إحصائي للتكوينات القابلة للتقليص لـ \(k\):
أولاً، التجزئة تختبر الزوج \(\vv v_1,\vv v_2\) القريب ما يجعل \(\vv v_1-\vv v_2\) أقصر. يمكننا أيضاً تعريف تجزئة تختبر التقارب المعاكس بحيث يصبح \(\vv v_1+\vv v_2\) أقصر. حدسنا أن اختيار الفهرس بقيمة مطلقة أكبر يحقق التماثل على \(\pm\vv v\).
ثانياً، يمكننا استخدام عدد أقل من المتجهات العشوائية مع احتفاظ بقوة الاختبار. مجموعة من \(h\) متجهات عشوائية تمتد فضاء فرعياً ببُعد \(h\)، ونَتوقع أن تحافظ إسقاطات الأزواج على القرب أو المعاكس. هذا يخفض تكلفة التقييم، مع احتمال زيادة التصادمات لكل من الإيجابيات الحقيقية والخاطئة.
ثالثاً، يمكن اختيار أكثر من فهرس واحد. عبر جمع مجموعة من \(a\) فهارس بأعلى إسقاطات نحدد فضاء فرعياً أبعاده \(a\) يماثل توجّه المتجه. بدلاً من ذلك، إذا كتبنا \(h=a+b\) يمكننا جمع \(b\) فهارس بأصغر إسقاطات لتحديد الفضاء المتمم العمودي الأشد تعامداً.
لهذه الأسباب، نعرف عائلة من "تجزئات الإسقاط العشوائي" كالتالي:
لتكن \(\mathcal R=\{\vv r_1,\ldots,\vv r_h\}\subset\mathbb R^d\) مجموعة من المتجهات المستقلة مكوناتُها موزعة \(\mathcal N(0,1)\). لكل \(a,b\) حيث \(a+b=h\)، نعرّف دوال التجزئة \(H_{\mathcal R,a,b}(\vv v)\) عبر اختيار مجموعة \(A\) ذات حجم \(a\) من الفهارس التي تعطي أعلى قيم مطلقة للجداء \(\vv r_i\cdot\vv v\). بالتالي \[ H_{\mathcal R,a,b}(\vv v) =\Bigl\{A:\#A=a,\;|\vv r_i\cdot\vv v|\ge|\vv r_j\cdot\vv v|\;\forall\,i\in A,\;j\notin A\Bigr\}. \] يمكن كسر التعادلات باختيار الفهرس الأصغر حين تتساوى القيم.
نهتم بمعدل التصادم \(k\)-الطريق لعائلة التجزئة هذه على أنماط \(k\) من المتجهات. عند عدم ارتباط قيم التجزئة، نتوقع معدلاً بدائياً \(\binom ha^{-(k-1)}\). سنوضح في القسم [sec:reducible] ارتباط معدل التصادم بالجداءات القياسية الزوجية للأنماط. وفي القسم [sec:empirical] نجري تحقيقات تجريبية للمعدل الثلاثي لمختلف التكوينات القابلة للخفض وغير القابلة له. في القسم [sec:n_analysis] نقدم تعابير تحليلية للحالات \(a=1\) أو \(b=1\) عبر تكامل عددي في فضاء \(k+1\)-الأبعاد. أما في القسم [sec:asymptotic] فننظر للسلوك التقاربي لمعدل التصادم عندما \(b\to\infty\) مع ثبات \(a\)، ونثبت تعميماً للنتائج في (angular)، حيث كان \(h=d\), \(a=1\), \(b=d-1\). في (angular) يظهر أن المعدل السالبي اللوغاريتمي للتصادم الثنائي التقاربي هو \((\alpha-1)\log h\) مع \(\alpha(\tau)=4/(4-\tau^2)\) إذا كانت \(\tau\) مسافة المتجهين، ويمكن كتابتها أيضاً \(\alpha(\vv v_1\cdot\vv v_2)=2/(1-|\vv v_1\cdot\vv v_2|)\). في الحالة العامة نصل إلى \[ \log\frac{B((1+o(1))\alpha a,b)}{B(a,b)}, \] حيث \(B\) دالة بيتا و\(\alpha\) دالة للجداءات القياسية الزوجية للأنماط. ونسمي \(\alpha\) "القطر المزدوج الأقصر المربع". كذلك ندرس سلوك المصادمات عند \(a\to\infty\) مع ثبات \(b\)، فنحصل على \[ \Delta^{-b}\binom{a+b}b^{-(k-1)}, \] حيث \(\Delta\) هو جيب القطب للأنماط. ونقدم أيضاً معدلات بقاء الأنماط تحت اختبار تصفية الإسقاط العشوائي فوق أو تحت حدود كبيرة مطلقة، ما يمكّن تصميم مخططات تصفية للغربلة.
في هذا القسم نحاول توصيف عائلات أزواج المتجهات متساوية الطول حيث توفر بعض الجمعيات الخطية متجهات أقصر من الأصول.
عند النظر لما هو أكثر شيوعاً من أزواج قابلة للتخفيض، نتخيل أولاً \(k\)-زوجاً نموذجياً على كرة ذات بُعد \((d-1)\). إذا كان \(k\) صغيراً مقارنة بـ \(d\)، يكون الزوج قريباً من التعامد، فيتكوّن مكعب فائق تقريباً بأطوال أضلاعه مساوية لقطر الكُرة وموازي لمتجهات الزوج. نرغب في ضغط هذا المكعب الفائق عبر قطر رئيسي ليقتصر طوله الفرعي على أقل من طول الأضلاع، ما يضمن جمعية خطية أقصر. إذا كانت رؤوس القطر الرئيسي هي \(\vv u_1,\ldots,\vv u_k\) (والرؤوس المقابلة هي نفيها) فإن المتجه \[ \vv d=\vv u_1+\vv u_2+\cdots+\vv u_k \] يمثل هذا القطر. عبر مطابقة قانون التوزيع نجد \[ ||\vv d||^2=\ell^2\Bigl(k+\sum_{i\neq j}\cos(\vv u_i,\vv u_j)\Bigr), \] حيث \(\ell\) طول ضلع متوازي المستطيلات المعيني و\(\cos(\vv u_i,\vv u_j)\) جيب تمام زاوية المتجهين. لجعل \(||\vv d||^2<\ell^2\) يجب أن يكون \(\sum_{i\neq j}\cos(\vv u_i,\vv u_j)<-k+1\). يُحقق أقل تشويه عندما تكون كل الزوايا متساوية بحيث \(\cos(\vv u_i,\vv u_j)\approx -1/k\). بالتالي تتجمع المتجهات حول تكوين متناظر ذو زاوية بين كل زوج \(\arccos(-1/k)\)، وهو التكوين الذي نركز عليه وأهداف الاختبار لدينا.
في الحالة \(k=3\) ينحصر اهتمامنا على ثلاثيات تشكل متوازيات مستطيلات مسطحة≈متوازية الأضلاع تقريباً، وهو ما يرتبط ارتباطاً وثيقاً بالتبعية الخطية الجزئية أو المسطحة. تُستهدف هذه التكوينات عبر دوالنا؛ إذ من المرجح أن تشترك المتجهات العشوائية \(a\) ذات الجداءات القياسية الكبيرة مع المتجهات المدروسة على الفضاء الفرعي ثنائي الأبعاد، بينما توجه المتجهات \(b\) الأخرى نحو المتمم العمودي، فيزيد احتمال تصادم \(k\)-طريق.
إذا اقتصرنا على الجمع الخطي لمتجهاتنا \(k\) بمعاملات \(\pm1\)، لاحظنا في القسم [sec:reducible] أن قابلية خفض تكوين \(k\) من المتجهات الوحدوية تعتمد على مجموع الجداءات الزوجية: تكون قابلة للتقليص إذا كان \(\sum_{i\neq j}\vv u_i\cdot\vv u_j<-k-1\). من المثالي أن يعتمد معدل التصادم على هذا المجموع فقط، ولكن الدوران التماثلي للتجزئة يجعلنا نتوقع أنه يعتمد على مجموعة الجداءات القياسية الزوجية، وسنرى هذا عبر ثلاث طرق تحقيق.
لبعد معين \(d\)، يمكن توليد \(k\)-مجموعة عشوائية ذات جداءات قياسية زوجية محددة عبر إنشاء ثلاثي عشوائي ثم تطبيق جرام-شميدت لإعادة تحجيم المتجهات. يمكن تقدير معدل التصادم الثلاثي التجريبي لعائلة التجزئة الإسقاطية العشوائية \(H_{\mathcal R,a,b}\). نظرياً نتوقع معدل تصادم تقريبي \(p\approx\binom{a+b}b^{-(k-1)}\)، وللعينة \(N\) نتوقع توزيعاً ثنائي الحدين \(\mathcal B(N,p)\). لتقدير متوسط المعدل بدقة 1% عند ثقة 95% نحتاج تقريبياً \(N\approx10^5p^{-2}\)، ما يحول دون التحقيق للحالات ذات \(p\) صغير للغاية. مع ذلك، لعدد محدود من قيم \(k\)و\(h\) يمكن تأكيد الاحتماليات اعتماداً أساساً على الجداءات القياسية الزوجية وثبات النتائج. نختار بعداً كبيراً بما يكفي لتمثيل المبدأ دون إثقال الحوسبة.
نركّز على \(k=3\) ونمثّل الجداء القياسي بين أزواج الثلاثيات بـ \(\alpha,\beta,\gamma\) بحيث \(2\alpha+2\beta+2\gamma=\sigma\). نعمل في \(d=20\) (استقرت النتائج عند تغيير البعد)، ونستخدم 100,000 تجربة للحصول على دقة 2–3 أرقام. نعرض عائلة التجزئة \(H_{\mathcal R,1,2}\)، مع التركيز على الحالات ذات \(\alpha,\beta,\gamma<0\) (حيث يكون خفض الأزواج الثنائي أفضل من الثلاثي).
نلاحظ تماثل مجموعة المبعثرات \(S_3\) في البيانات ويتحقق توقعنا بارتفاع معدل التصادم كلما تناقص \(\sigma\). القيم المركزية للتكوينات الثلاث هي تقريباً 0.125, 0.134, 0.144، أي أعلى بحوالي %12.5، %20.5، و%28.9 من المعدل الساذج \(1/9\). نسبة السجل (log‐ratio) للاحتمالات بين القيم \(\sigma=-2.0\) و\(-2.4\) مثلاً هي حوالي \(1.034\)، وغيرها كما يلي:
\[ \rho(-2.0,-2.4)\approx1.034,\quad \rho(-2.0,-3.0)\approx1.035,\quad \rho(-2.4,-3.0)\approx1.070. \]
بزيادة عدد المتجهات العشوائية إلى 4، يتوقع أن ينخفض معدل التصادم الساذج من \(1/9\) إلى \(1/16\).
نرى شكلاً مشابهاً لحالة \(H_{\mathcal R,1,2}\). القيم المركزية الآن تقريباً \(0.0705,0.0765,0.0763\) (تفوق السذاجة %12.8، %22.4، و%22 على التوالي). ونجد نسب السجل:
\[ \rho(-2.0,-2.4)\approx1.032,\quad \rho(-2.0,-3.0)\approx1.031,\quad \rho(-2.4,-3.0)\approx0.999. \]
هذا يشير إلى أن الاحتفاظ بقيمة \(h\) صغيرة لا يقلل التكلفة فقط بل قد يعزز التمييز، رغم بعض الضوضاء العددية.
نختبر أيضاً تصادمات تجزئة أصغر قيمة مطلقة للفهارس. نمط البيانات لم يتغير، لكن القيم المركزية أصبحت تقريباً \(0.126,0.141,0.183\)، أي أعلى بـ%13.4، %12.7، و%64.5 من المعدل الساذج، مع نسب سجل:
\[ \rho(-2.0,-2.4)\approx1.058,\quad \rho(-2.0,-3.0)\approx1.219,\quad \rho(-2.4,-3.0)\approx1.152. \]
يبدو أن تجزئة القيمة الدنيا أكثر قوة من القيمة الكبرى، وقد تستفيد من تحقيقات أعمق.
عند استخدام 4 متجهات عشوائية في تجزئة القيمة الدنيا، نجد القيم المركزية \(\approx0.0727,0.0848,0.127\) (تفوق السذاجة %16.3، %35.7، و%103) ونسب سجل:
\[ \rho(-2.0,-2.4)\approx1.063,\quad \rho(-2.0,-3.0)\approx1.270,\quad \rho(-2.4,-3.0)\approx1.196. \]
هذا يشير إلى أن عائلة \(H_{\mathcal R,3,1}\) تتفوق على \(H_{\mathcal R,2,1}\)، ما يبرر التحري الأعمق.
في هذا القسم نطور تعبيراً تكاملياً لاحتمالية التصادم الثلاثي في الحالة \(b=1\). يمكن تعميمه لحالات \(k\) أكبر بسهولة. بالنظر إلى ثلاثية مستقلة خطياً \((\vv v_1,\vv v_2,\vv v_3)\)، نسقط المتجهات على الفضاء الفرعي ثلاثي الأبعاد الذي يمتدُّ بهن. بفضل تماثل التوزيع الكروي، يُمكن اعتبار إسقاطات \(\vv r_i\) على هذا الفضاء مستقلةً وموزعةً غاوسياً \(\mathcal N(0,1)\) بالنسبة لأي قاعدة متعامدة \(\vv i,\vv j,\vv k\). سنستخدم \(\vv r_i\) أيضاً للدلالة على تلك الإسقاطات في ما يلي، مع الحفاظ على الجداءات القياسية بينها وبين \(\vv v_n\).
بسبب التماثل وتجاهل الأحداث صفرية الاحتمال، \[ \mathbb P\bigl(H(\vv v_1)=H(\vv v_2)=H(\vv v_3)\bigr) =h\,\mathbb P\bigl(H(\vv v_1)=H(\vv v_2)=H(\vv v_3)=1\bigr). \] نسمي \(G(\vv w;\vv v_1,\vv v_2,\vv v_3)\) احتمال أن يحقق متجه غاوسي عشوائي \(\vv r\) الشرط \(|\vv v_n\cdot\vv w|\le|\vv v_n\cdot\vv r|\) لكل \(1\le n\le3\). بالاستقلالية، \[ \mathbb P\bigl(H(\vv v_1)=H(\vv v_2)=H(\vv v_3)=1\bigr) =\int_{\vv w}G(\vv w;\vv v_1,\vv v_2,\vv v_3)^{h-1}\,d\mu(\vv w), \] حيث \(d\mu\) قياس كثافة Gaussian.
في الواقع، \(G\) تعتمد فقط على الجداءات القياسية الزوجية للمتجهات \(\vv v_n\). إذا عرفنا \(\lambda_n=\vv w\cdot\vv v_n\)، و\(\mu_m\) للجداءات الزوجية بين \(\vv v_i\)، فإننا نربط \(G\) بالزوايا الصلبة في موازيات المستطيلات المحددة بمعادلات \(\vv r\cdot\vv v_n=\pm\lambda_n\).
كتلة غاوس للزوايا الصلبة المقابلة للرؤوس \(\vv w^{(c)}\) من الموازيات يمكن التعبير عنها كتكاميلية...
``` **تمت مراجعة جميع معادلات LaTeX والتأكد من اكتمالها وصحتها النحوية. جميع المعادلات الآن محاطة بشكل صحيح بعلامات `\[` ... `\]` للعرض و `\(...\)` للسطر، مع التأكد من إغلاق جميع الأقواس وعدم وجود أي أخطاء في بناء LaTeX.**