Billion-Scale Nearest-Neighbor Search under Fully Homomorphic Encryption on a Single GPU, Balancing Leakage and Cost
تقدم هذه الورقة نظاماً مُسرَّعاً بواسطة وحدة معالجة الرسومات للبحث عن أقرب الجيران بمقياس المليارات تحت التشفير المتماثل كلياً، والذي يحقق زمن استجابة عملياً من خلال الجمع بين تقليل الرتب والتوجيه الهرمي، مع قياس وتخفيف التسرب الهندسي المرتبط بذلك عبر الحشو المبذر بالبذور.
البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل
تخيل أن لديك مكتبة تحتوي على مليارات الصور، وتريد العثور على الصورة الأكثر تشابهاً مع صورة في جيبك. عادةً، يقوم الكمبيوتر بمسح كل صورة للعثور على المطابقة، ولكن ماذا لو لم تتمكن من إظهار صورتك للكمبيوتر لأنها خاصة؟ ماذا لو كانت المكتبة مملوكة لشخص غريب لا تثق به؟ هذا هو المشكل الذي سعى الباحثون لحله. لقد أرادوا طريقة تمكن الكمبيوتر من البحث في قاعدة بيانات ضخمة وسرية دون أن يرى أبداً السؤال الفعلي الذي يتم طرحه. وللقيام بذلك، يستخدمون طريقة تسمى التشفير المتماثل الكلي، وهي تشبه وضع سؤالك داخل صندوق شفاف مغلق. يمكن للكمبيوتر إجراء عمليات حسابية على الصندوق دون فتحه، ليعيد نتيجة لا تزال مغلقة. وفقط أنت، بامتلاكك للمفتاح، يمكنك فتح الصندوق النهائي لرؤية الإجابة. لسنوات، كانت هذه الفكرة بطيئة جداً بحيث لا يمكن الاستفادة منها في المجموعات الضخمة من البيانات، لأن الرياضيات المطلوبة لإبقاء الصندوق مغلقاً كانت ثقيلة للغاية.
لقد بنى فريق من الباحثين الآن نظاماً يجعل هذا ممكناً لمليار عنصر، يعمل على بطاقة رسوميات واحدة. لقد تمكنوا من العثور على الصور الأكثر تشابهاً في قاعدة بيانات تضم 1.39 مليار مدخل دون أن يرى الخادم الاستعلام. يعمل النظام باستخدام خدعتين رئيسيتين لتسريع العملية. أولاً، يقوم بتبسيط الصور؛ فبدلاً من مقارنة كل تفصيل صغير في الصورة، يقوم النظام بتقليل وصف كل صورة إلى نسخة أقصر وأبسط قبل بدء البحث، مما يجعل العمليات الحسابية أخف بكثير. ثانياً، لا ينظر النظام إلى كل صورة؛ بل يستخدم تسلسلاً هرمياً، يشبه الخريطة التي تشير أولاً إلى حي عام، ثم إلى شارع محدد، وأخيراً إلى بضعة منازل. يتحقق الكمبيوتر فقط من الصور في تلك المناطق المختارة، متجاوزاً البقية. هذا يسمح للنظام بالعثور على الإجابة الصحيحة بسرعة، رغم أن البيانات مغلقة داخل صندوق.
تظهر النتائج أن هذا النهج يعمل بشكل جيد للغاية. ففي مجموعة بيانات تضم 1.39 مليار صورة، وجد النظام المطابقة الصحيحة ضمن أفضل عشر نتائج في 90 بالمائة من الحالات. وعندما سمح الباحثون بالصور المتطابقة تقريباً -بما أن الإنترنت مليء بنسخ مختلفة قليلاً من نفس الصورة- قفزت نسبة النجاح إلى 95 بالمائة. استغرقت العملية بأكملها حوالي ست ثوانٍ لكل بحث على بطاقة رسوميات واحدة. هذه سرعة "قابلة للنشر"، مما يعني أنها سريعة بما يكفي للاستخدام في العالم الحقيقي بمجرد تجهيز قاعدة البيانات مسبقاً. كما اختبر الباحثون نظامهم على مجموعة أخرى من مليار عنصر من المتجهات ذات الـ 96 بُعداً، وحققوا نسبة نجاح 90 بالمائة في غضون 2.3 ثانية فقط. تثبت هذه الأرقام أن البحث في مليارات العناصر المشفرة على جهاز واحد لم يعد مجرد حلم نظري.
ومع ذلك، كان الباحثون حذرين في قياس ما يدفعه هذا السر من ثمن فيما يتعلق بالخصوصية. فبينما لا يرى الخادم السؤال أو الإجابة، فإنه يرى مجموعات البيانات التي يطلب الكمبيوتر الاطلاع عليها. ويمكن لهذا النمط من الوصول أن يكشف أدلة حول قاعدة البيانات نفسها. فمن خلال مراقبة المجموعات التي تُطلب معاً، يمكن للمراقب إعادة بناء حوالي 72 بالمائة من الخريطة التي توضح كيفية تنظيم البيانات. كما يمكنهم تخمين أن بحثين مختلفين يبحثان عن أشياء متشابهة إذا طلبا نفس المجموعات. ولإصلاح ذلك، جرب الباحثون طريقة حيث يطلب الكمبيوتر مجموعات إضافية من البيانات الوهمية جنباً إلى جنب مع المجموعات الحقيقية لإخفاء النمط الحقيقي. وإذا كانت المجموعات الوهمية تتغير في كل مرة، يمكن لمهاجم ذكي أن يعرف الحقيقة من خلال مقارنة عمليات البحث المتعددة. ولكن إذا كانت المجموعات الوهمية ثابتة ودائمة، فلا يمكن للمهاجم تجريدها. هذا "الحشو الموجه" (seeded padding) يقلل من تسرب المعلومات بنحو 35 ضعفاً، حيث تنخفض نسبة استعادة خريطة قاعدة البيانات من 72 بالمائة إلى 2 بالمائة فقط.
استكشف الفريق أيضاً طرقاً أخرى لجعل البحث أسرع، مثل تقنية "تكميم المنتج" (product quantization)، التي تقسم البيانات إلى أكواد صغيرة. ووجدوا أنه تحت التشفير، لم تعمل هذه الطريقة بشكل جيد؛ فإما أنها فشلت في التفوق على البحث المشفر القياسي أو أنها سربت الكثير من المعلومات حول بنية البيانات. لذا قرروا عدم استخدامها، والتمسك بدلاً من ذلك بالطريقة الأبسط المتمثلة في تقليل حجم أوصاف البيانات واستخدام الخريطة الهرمية. يسلط هذا الاختيار الضوء على نتيجة رئيسية: أحياناً يكون النهج المباشر أفضل من النهج المعقد عندما تكون الخصوصية هي الأولوية.
يعمل النظام من خلال قيام المستخدم بإرسال سؤال مشفر إلى الخادم. يقوم الخادم، الذي يحتفظ بقاعدة البيانات المشفرة، بإجراء العمليات الحسابية على البيانات المغلقة. يتحقق أولاً من بضعة آلاف من الفئات الواسعة، ثم يضيق النطاق إلى بضعة آلاف من المجموعات الأكثر تحديداً، وأخيراً يقوم بتقييم الصور الفعلية في تلك المجموعات. في كل خطوة، يعيد الخادم درجات (scores) مشفرة. يقوم المستخدم بفك تشفير الدرجات، ويقرر المجموعات التي يجب النظر فيها تالياً، ثم يرسل طلباً جديداً. لا يرى الخادم أبداً قرار المستخدم أو الإجابة النهائية. تستمر هذه العملية المتبادلة حتى يتم العثور على أفضل عشر مطابقات. قام الباحثون بقياس الوقت المستغرق لتحميل البيانات وإجراء التقييم، مستثنين الوقت الذي يستغرقه المستخدم لفك تشفير النتيجة النهائية أو الوقت الذي تستغرقه البيانات للانتقال عبر الشبكة. ووجدوا أن الوقت يهيمن عليه تحميل البيانات المشفرة في ذاكرة الكمبيوتر، وليس العمليات الحسابية نفسها.
في تحليلهم لمخاطر الخصوصية، أظهر الباحثون أن التسرب هو خاصية تتعلق بكيفية توجيه البحث، وليس بالبيانات المحددة التي يتم البحث عنها. وسواء كانت قاعدة البيانات تحتوي على وجوه أو صور عامة، فإن نمط الوصول يكشف نفس القدر من المعلومات الهيكلية. وقد أثبتوا أنه بدون حماية، يمكن للمراقب استعادة تجميع البيانات بشكل شبه كامل. ومع استخدام "الحشو ذو المجموعات الثابتة"، انخفضت هذه الاستعادة بشكل كبير، رغم أنها لم تختفِ تماماً. والمقايضة واضحة: لإخفاء نمط الوصول، يجب على النظام جلب المزيد من البيانات مما هو ضروري فعلياً، مما يزيد من الوقت المستغرق لإكمال البحث. وقد أظهر الباحثون أن هذه التكلفة يمكن إدارتها، لكنها تتطلب توازناً بين مقدار الخصوصية المطلوبة وسرعة عمل النظام.
يمثل هذا العمل خطوة كبيرة للأمام في جعل البحث الخاص عملياً على نطاق واسع. فهو يثبت أنه يمكنك البحث في مليار عنصر دون الكشف عن نيتك، بشرط أن تكون مستعداً لقبول بضع ثوانٍ من التأخير وتكلفة خصوصية مدارة بعناًية. لا يعتمد النظام على السحر أو النظريات غير المثبتة؛ بل يستخدم رياضيات راسخة وهندسة ذكية لحل مشكلة حقيقية. لقد قدم الباحثون دليلاً كاملاً حول كيفية بناء وتشغيل هذا النظام، بما في ذلك الإعدادات الدقيقة للسرعة والدقة. كما أظهروا أين تكمو الحدود، لا سيما فيما يتعلق بالمعلومات التي تتسرب من خلال نمط البحث. ومن خلال كونهم شفافين بشأن ما هو مخفي وما هو مكشوف، فإنهم يقدمون مساراً واقعياً للبحث الآمن عن البيانات في عصر أصبحت فيه الخصوصية ذات قيمة متزايدة.
غارق في أبحاث مجالك؟
تصلك نشرة يومية بأحدث الأبحاث المطابقة لكلماتك البحثية المفتاحية — مع ملخصات تقنية، بلغتك.