نقدم ونحلل عائلة من دوال التجزئة والتصفية التي من المرجح أن تولّد تصادمات لمجموعات صغيرة قابلة للتخفيض من المتجهات. قد توفر هذه الدوال تحسينات عملية لعمليات غربلة الشبكات للمتجهات القصيرة. بشكل خاص، في إطار التقارب الأحادي، تظهر العائلة سلوكاً تقاربياً مختلفاً بشكل ملحوظ عن دوال التجزئة والتصفية الحالية.
كما نعرض عائلة من دوال التجزئة والتصفية التي تزيد من احتمال تصادم المجموعات الصغيرة القابلة للتخفيض من المتجهات. قد توفّر هذه الدوال تحسينات عملية لعمليات غربلة الشبكات للمتجهات القصيرة. بشكل خاص، في إطار تقارب معيّن، تظهر هذه العائلة سلوكاً تقاربياً مختلفاً بشكل جوهري عن الدوال المستخدمة حالياً.
تعتمد خوارزميات ما بعد الكم مثل 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\)-طريق في دوال التجزئة أو عبر عائلات من ناجيات التصفية متعددة الأطراف. نقترح تعميماً لتجزئة الزاوية من (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{h}{a}^{-(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 متجهات عشوائية في تصفية القيمة الدنيا، نجد القيم المركزية تقريباً \(0.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\) هو قياس الكثافة الغاوسية.
في الواقع، \(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)}\) من موازيات المستطيلات يمكن التعبير عنها كتكاميلية...