💻 computer science

Towards Scalable Fuzzy PSI via Efficient Fuzzy Matching

تقدم هذه الورقة بروتوكولات تقاطع المجموعات الخاصة (PSI) الضبابية القابلة للتوسع لمسافات $L_p$ العامة في كل من الإعدادات منخفضة وعالية الأبعاد، وذلك عبر الاستفاء من تقنيات المطابقة الضبابية القائمة على OPRF وOT وتقنية إطار التجزئة ثنائي الطبقات المبتكرة، محققةً تحسينات كبيرة في السرعة وتكاليف الاتصال مقارنة بالأعمال السابقة ذات الحالة الراهنة.

المؤلفون الأصليون: Meng Hao, Xinpeng Yang, Hanxiao Chen, Tianwei Zhang, Haiyang Xue, Guomin Yang, Hongwei Li, Robert H. Deng

نُشر 2026-08-13

📖 6 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Meng Hao, Xinpeng Yang, Hanxiao Chen, Tianwei Zhang, Haiyang Xue, Guomin Yang, Hongwei Li, Robert H. Deng

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل أنك في حفلة صاخبة ومزدحمة حيث يرتدي الجميع بطاقات تعريفية، لكن البطاقات مشوهة قليلاً. تريد العثور على أصدقائك، لكن لا يمكنك قراءة الكتابة الدقيقة على بطاقاتهم بسبب التشويه. يحدث هذا في العالم الحقيقي طوال الوقت: قد يقرأ ماسح بصمات أصابعك بصمتك بشكل مختلف قليلاً عن المرة السابقة، أو قد يضع تطبيق نظام تحديد المواقع العالمي (GPS) سيارتك بعيداً ببضعة أقدام عن موقعها الفعلي. هذه هي مشكلة المطابقة "الضبابية" (fuzzy matching)—البحث عن أشياء متشابهة تقريباً، وليست متطابقة تماماً.

الآن، تخيل أنك تريد العثور على هؤلاء الأصدقاء دون أن يعرف أي شخص آخر في الحفلة من تبحث عنه، ودون أن تكشف عن بطاقة تعريفك الخاصة لهم. هذا هو عالم "تقاطع المجموعات الضبابي الخاص" (Private Set Intersection - PSI): خدعة سحرية تشفيرية حيث يمكن لشخصين مقارنة قوائم العناصر الخاصة بهما والعثي على المطابقات، لكنهما لا يتعلمان أي شيء عن العناصر التي لم تتطابق. لسنوات، حاول العلماء بناء نسخة من هذه الخدعة السحرية تعمل مع البيانات "الضبابية" (مثل البطاقات المشوهة أو بصمات الأصابع المختلفة قليلاً) دون أن تستغرق وقتاً طويلاً في الحوسبة أو تتطلب حاسوباً خارقاً لإرسال النتائج.

هذه الورقة البحثية بعنوان "نحو تقاطع مجموعات ضبابي قابل للتوسع عبر مطابقة ضبابية فعالة"، هي بمثابة فريق من المهندسين الذين اخترعوا للتو طريقة جديدة وسريعة جداً للقيام بعملية المطابقة الضبابية هذه. يجادل المؤلفون، وهم مجموعة من الباحثين من جامعات في سنغافورة والصين، بأن الطرق القديمة كانت بطيئة وخرقاء للغاية، مثل محاولة العثور على إبرة في كومة قش من خلال فحص كل قطعة قش واحدة تلو الأخرى. إنهم يقترحون نظاماً جديداً يستخدم طرقاً مختصرة ذكية وأدوات تشفيرية "خفيفة الوزن" لجعل هذه العملية أسرع وأرخص بكثير، خاصة عند التعامل مع مجموعات ضخمة من البيانات.

الطريقة القديمة: النقل الثقيل والبطيء

لفهم سبب أهمية هذا الاختراع الجديد، دعونا ننظر إلى الطرق القديمة. في السابق، للاعتمد على أدوات تشفيرية معقدة وثقيلة جداً للبحث عن المطابقات الضبابية بشكل آمن. فكر في هذه الأدوات كخزائن حديدية ضخمة ومصفحة؛ فهي آمنة، لكنها أيضاً ثقيلة جداً للحمل. إذا كنت تريد مقارنة قائمتين تحتوي كل منهما على 10,000 عنصر، فإن الطرق القديمة ستتطلب قدرة حوسبية ونقلاً للبيانات لدرجة أن الأمر سيبدو وكأنك تحاول تحريك جبل باستخدام ملعقة.

حاولت بعض الطرق الأحدث استخدام أدوات أخف، لكنها واجهت مشكلة مختلفة: فقد أصبحت أبطأ فأبطأ كلما زادت درجة "الضبابية" (الفرق المسموح به بين العناصر). كان الأمر يشبه سيارة تغرز في الطين كلما زاد عمق الطين. إذا أردت السماح بتشويه أكبر في بطاقة الاسم، فإن النظام سيتوقف عن العمل. ويشير مؤلفو هذه الورقة إلى أن هذه الأساليب الموجودة ببساطة ليست قابلة للتوسع بما يكفي للاستخدام في العالم الحقيقي، خاصة عندما يكون لديك مجموعات بيانات كبيرة أو تحتاج إلى السماح باختلافات أكبر.

الخدعة الجديدة: أداتان خفيفتان

حل المؤلفون يتمثل في استبدال الخزائن الحديدية الثقيلة بأداتين أخف وأكثر كفاءة: الدوال شبه العشوائية المتجاهلة (Oblivious Pseudorandom Functions - OPRF) والنقل المتجاهل (Oblivious Transfer - OT).

تخيل OPRF كصندوق قفل سحري وغير قابل للكسر. يضع أحد الأشخاص رمزاً سرياً بالداخل، ويمكن للشخص الآخر التحقق مما إذا كان المفتاح الذي يمتلكه يفتح الصندوق، لكن لا يتعلم أي منهما الرمز السري للآخر. لقد ابتكر المؤلفون طريقة جديدة لاستخدام هذه الصناديق وهي أسرع بكiele من السابق. بدلاً من التحقق من كل تركيبة ممكنة لـ "المطابقات الوشيكة" (وهو رقم ضخم جداً)، تستخدم طريقتهم الجديدة خدعة "عكس الأدوار". الأمر يشبه جعل شخصين يتبادلان الوظائف في منتصف اللعبة لضغط قائمة طويلة من الاحتمالات في فحص واحد سريع. هذا يقلل الوقت المطلوب من نمو أسي (يصبح ضخماً بسرعة كبيرة) إلى نمو أكثر بطئاً بكثير.

الأداة الثانية، OT، هي مثل "قائمة الطعام السرية" في مطعم. يريد الزبون (المستلم) طلب طبق معين دون إخبار النادل (المرسل) بما اختاره، ويعطيه النادل الطبق دون معرفة ما طلبه. يستخدم المؤلفون نسخة مخصصة من هذا للتحقق مما إذا كانت نقطتان قريبتين بما يكفي. وهذا مفيد بشكل خاص للبيانات القصيرة والبسيطة، مثل التحقق مما إذا كان عددان قريبين من بعضهما.

مرشح الطبقة المزدوجة: بحث ذكي

للبيانات ذات الأبعاد المنخفضة والصغيرة (مثل إحداثيات 2D أو مواقع 3D)، يقدم المؤلفون إطار عمل جديداً عبقرياً يسم يسمونه نظام "التجزئة ثنائي الطبقة" (dual-layer hashing).

تخيل أنك تبحث عن كتاب معين في مكتبة تضم ملايين الكتب. الطريقة القديمة هي التجول في كل الممرات وفحص كل كتاب. طريقة المؤلفين الجديدة تشبه وجود أمين مكتبة يقوم أولاً بفرز الكتب في صناديق كبيرة (التجزئة المكانية - spatial hashing) ثم يستخدم آلة فرز ذكية وسريعة جداً (Cuckoo hashing) لتضييق النطاق إلى مجرد بضعة صناديق.

إليك الجزء السحري: في الأنظمة القديمة، كان على المستلم التحقق من كل صندوق محتمل يمكن أن يكون عنصرهم فيه، مما يعني فحص ملايين الصناديق حتى لو كان لدى المرسل بضعة كتب فقط. أدرك المؤلفون أن معظم تلك الصناديق فارغة! لذا، بنوا نظاماً يضع فيه المرسل كتبه فقط في الصناديق التي يشغلها بالفعل. بعد ذلك، يتحقق المستلم فقط من تلك الصناديق المحددة. يطلقون على هذا "تقليل نطاق المدخلات"، وهو مجرد طريقة منمقة للقول: "دعونا ننظر فقط حيث توجد الأشياء بالفعل".

وللتأكد من أن هذا الاختصار لا يؤدي بالخطأ إلى إظهار الكتب الخاطئة (النتائج الإيجابية الكاذبة)، أضافوا "فحص اتساق" نهائي. إنه مثل حارس أمن يتحقق من أن الكتاب الذي وجدته موجود بالفعل في الصندوق الصحيح قبل السماح لك بأخذه.

النتائج: تسريع الحفلة

لم يكتفِ المؤلفون ببناء هذا نظرياً؛ بل بنوه واختبروه. لقد قارنوا بروتوكولهم الجديد بأفضل الأساليب الحالية (من باحثين مثل van Baarsen و Pu، و Piske et al.) باستخدام بيانات محاكاة على خادم قوي.

كانت النتائج دراماتيكية. بالنسبة للبيانات منخفضة الأبعاد (مثل 2 إلى 8 أبعاد)، كان بروتوكولهم الجديد أسرع بما يصل إلى 145 مرة في وقت التشغيل وقلل كمية البيانات المرسلة عبر الشبكة بمقدار 20 مرة مقارنة بأفضل طريقة سابقة. أما بالنسبة للبيانات عالية الأبعاد (مثل 16 إلى 64 بُعداً)، فقد شهدوا تسارعاً يصل إلى 36 مرة وانخفاضاً في الاتصالات يصل إلى 54 مرة.

كما أظهروا أن نظامهم يتعامل مع عتبات "الضبابية" الأكبر بشكل أفضل بكثير. بينما كانت الأساليب القديمة تتباطأ بشكل حاد كلما سمحت باختلافات أكبر، ظل نظامهم سريعاً وفعالاً.

ما لم يفعلوه (ولماذا يهم ذلك)

من المهم ملاحظة ما لا تدعيه هذه الورقة. المؤلفون حذرون في قول إن حلهم عالي الأبعاد يعتمد على افتراض محدد: وهو أن نقاط البيانات "منفصلة عالمياً" (globally disjoint). في تشبيه الحفلة الخاص بنا، يعني هذا افتراض أنه لا يوجد صديقان يقفان بالقرب من بعضهما البعض لدرجة تجعل بطاقات أسمائهما المشوهة تتداخل بطريقة مربكة. وبينما يعد هذا افتراضاً قوماً وقد لا يناسب كل سيناريو في العالم الحقيقي، إلا أنه يسمح لهم بتحقيق السرعة الهائلة التي حققوها. لقد صرحوا بوضوح أنه بدون هذا الافتراض، تصبح المشكلة أصعب بكثير، وهم لا يدعون أنهم حلوا هذه النسخة الأصعب بعد.

علاوة على ذلك، لم يقترحوا هذه الأفكار فحسب؛ بل أثبتوها رياضياً ودعموها بتجارب واسعة النطاق. لم يقولوا فقط "إنه أسرع"؛ بل قاموا بقياس ذلك، موضحين بالضبط عدد الثواني والميجابايت التي تم توفيرها.

الخلاصة

باختصار، تمثل هذه الورقة خطوة كبيرة للأمام في جعل المطابقة الضبابية التي تحافظ على الخصوصية عملية وممكنة. من خلال استبدال الأدوات التشفيرية الثقيلة والبطيئة بأدوات أخف وأذكى، واستخدام نظام ترشيح ذكي ثنائي الطبقة، بنى المؤلفون بروتوكولاً أسرع بكมาก وأكثر كفاءة من أي شيء متاح حالياً. وبينما يعمل بشكل أفضل تحت ظروف معينة (مثل افتراض "الانفصال العالمي" للأبعاد العالية)، فإن النتائج تشير إلى أننا أقرب بكثير إلى القدرة على مطابقة البيانات الضبابية بأمان—مثل بصمات الأصابع، أو المواقع، أو المسحات البيومترية—دون التضحية بالسرعة أو الخصوصية. إنها تذكير بأن أفضل طريقة لحل مشكلة ضخمة ليست دائماً ببناء آلة أكبر، بل ببناء آلة أذكى.

ملخص تقني: نحو تقاطع مجموعات ضبابي (Fuzzy PSI) قابل للتوسع عبر مطابقة ضبابية فعالة

بيان المشكلة
يتيح تقاطع المجموعات الضبابي الخاص (fuzzy PSI) للمرسل الذي يمتلك مجموعة من النقاط ذات $d$ من الأبعاد $Q$ والمستقبل الذي يمتلك مجموعة $W$ حساب التقاطع بشكل خاص حيث تحقق النقاط عتبة مسافة $\delta$ (أي $\text{dist}(\mathbf{q}, \mathbf{w}) \le \delta$ ) تحت مقياس معين (على سبيل المثال $L_p$ لـ $p \in [1, \infty]$ ).

تواجه الحلول الحالية تحديات كبيرة في التوسع:

الأدوات التشفيرية الثقيلة: تعتمد العديد من البروتوكولات على التشفير المتماثل (AHE) أو الدوائر المشوشة (GCs) المكلفة، مما يؤدي إلى أعباء إضافية ملموسة.
التعقيد المقاربي الضعيف: البروتوكولات خفيفة الوزن الحديثة (مثل van Baarsen و Pu [46]) غالبًا ما تتضمن تعقيدات تتدرج كـ $O((\log \delta)^d)$ أو $O(\delta)$ بالنسبة لعتبة المسافة $\delta$ والبعد $d$ . وهذا يخلق اختناقات شديدة للقيم الكبيرة من $\delta$ أو البيانات عالية الأبعاد.
الأعباء التربيعية: تؤدي المقارنة الزوجية إلى تعقيد $O(mn)$، وهو أمر غير عملي للمجموعات الكبيرة.

يطرح المؤلفون السؤال التالي: هل يمكننا بناء بروتوكولات fuzzy PSI قابلة للتوسع مع ضمانات كفاءة ملموسة ومقاربة (asymptotic) لكل من مسافات $L_p$ العامة عبر المجموعات منخفضة وعالية الأبعاد؟

المنهجية

يقترح البحث مجموعة من البروتوكولات المبنية على ابتكارين تقنيين أساسيين: المطابقة الضبابية ذات الكفاءة المقاربية (Asymptotically Efficient Fuzzy Matching) وإطار عمل التجزئة ثنائي الطبقة (Dual-Layer Hashing Framework).

2.1 المطابقة الضبابية ذات الكفاءة المقاربية
صمم المؤلفون بروتوكولين لمطابقة نقطة واحدة ضبابياً لتقييم $\text{dist}(\mathbf{q}, \mathbf{w}) \le \delta$ بشكل آمن:

بروتوكول OPRF معكوس الأدوار:
- الآلية: يحسن هذا البروتوكول النهج القائم على OPRF (الذي استخدم محاولات البادئة لتقليل برمجة المرسل ولكن زاد من حسابات المستقبل إلى $O((\log \delta)^{d/2}$ ). يقدم المؤلفون آلية OPRF معكوسة الأدوار ذات خطوتين.
- العملية:
  1. يقوم المرسل ببرمجة خريطة OPRF تربط بادئات الفترات بقيم عشوائية.
  2. يقوم المستقبل بتقييم هذه القيم للحصول على مجموعة من القيم.
  3. الابتكار: تُعكس الأدوار في استدعاء OPRF ثانٍ. يقوم المستقبل ببرمجة OPRF جديد يربط مخرجات الجولة الأولى بقيمة واحدة، بينما يقوم المرسل بالتقييم.
- النتيجة: هذا يضغط تقييمات المستقبل من $O(\log \delta)$ إلى قيمة واحدة لكل بُعد، مما يقلل العبء الحسابي من $O((\log \delta)^d)$ إلى $O(d \log \delta)$ .
بروتوكول OT المخصص:
- الآلية: مصمم للمدخلات ذات أطوال البت القصيرة ( $\ell$ )، ويستفيد هذا البروتوكول من النقل المستحي (Oblivious Transfer - OT) لحساب البت الأكثر أهمية (MSB) وعمليات AND مباشرة.
- النتيجة: يحقق عبئاً قدره $O(d \ell)$ . وعند دمجه مع تقليل النطاق (انظر أدناه)، فإنه يوفر أداءً ملموساً متفوقاً من خلال إزالة الاعتماد على معلمة الأمان الإحصائي $\lambda$ المتأصلة في إنشاءات OPRF.

2.2 أطر عمل Fuzzy PSI

للمجموعات منخفضة الأبعاد
يقترح المؤلفون إطار عمل التجزئة ثنائي الطبقة الذي يجمع بين التجزئة المكانية (Spatial Hashing) وتجزئة كوكو (Cuckoo Hashing):

التجزئة المكانية: تقسم الفضاء ذو $d$ من الأبعاد إلى خلايا شبكية بطول ضلع $2\delta$ .
التحسين ثنائي الطبقة:
- بدلاً من أن يتحقق المستقبل من جميع الخلايا المجاورة $2^d$ لكل نقطة (مما يؤدي إلى $O(2^d n)$ من استدعاءات المطابقة الضبابية)، يلاحظ المؤلفون أن الخلايا التي تحتوي على نقاط المرسل هي فقط ذات الصلة.
- تجزئة كوكو: يقوم المرسل بخرائط نقاطه إلى جدول. ويقوم المستقبل بخرائط خلايا جيرانه المحتملة إلى نفس الجدول.
- الاختزال: يقلل هذا من عدد استدعاءات المطابقة الضبابية المطلوبة من $O(2^d n)$ إلى $O(m)$ .
تقليل النطاق وفحص الاتساق: لاستخدام المطابقة القائمة على OT الأكثر كفاءة، يتم تقليل نطاق المدخلات إلى الجوار المحلي لنقطة المرسل (مكعب فائق بطول ضلع $6\delta$ ). ولمنع النتائج الإيجابية الكاذبة الناتجة عن هذا النطاق الصغير (حيث قد تقع القيم العشوائية بالصدفة ضمن $\delta$ )، يتحقق فحص إضافي للاتساق مما يؤكد أن نقطة المرسل ونقطة المستقبل تقعان في نفس خلية الشبكة تماماً.

للمجموعات عالية الأبعاد
لتجنب التضخم الأسي $2^d$ ، يبني المؤلفون بروتوكولات قائمة على افتراض التباعد العالمي (الصور الإسقاطية للكرات لا تتداخل في أي بُعد).

الآلية: يقومون بتجميع (compile) المطابقة الضبابية القائمة على OPRF إلى PSI متعدد النقاط.
التصفية: يقوم البروتوكول أولاً بإنشاء معرفات فريدة بناءً على مسافة $L_\infty$ . وبما أن $L_\infty$ يحد من $L_p$ ، فإن هذه المعرفات تعمل كمرشح أولي. فقط الأزواج ذات المعرفات المتطابقة تخضع لفحوصات مسافة $L_p$ صارمة.
التعقيد: يحقق هذا عبئاً زمنياً خطياً في أحجام المجموعات ( $m, n$ )، والبعد ( $d$ )، ولوغاريتمياً في العتبة ( $\log \delta$ )، أي $O((m+n)d \log \delta)$ .

المساهمات الرئيسية
مطابقة ضبابية ذات كفاءة مقاربية:
- بروتوكول OPRF معكوس الأدوار يحقق عبئاً قدره $O(d \log \delta)$ ، مما يحسن من $O((\log \delta)^d)$ في الأعمال السابقة.
- بروتوكول قائم على OT بعبء قدره $O(d \ell)$ ، مناسب للمدخلات القصيرة.
إطار عمل جديد منخفض الأبعاد:
- إطار عمل تجزئة ثنائي الطبقة (مكانية + كوكو) يقلل استدعاءات المطابقة الضبابية من $O(2^d n)$ إلى $O(m)$ .
- تحسين تقليل مساحة المدخلات مع فحص الاتساق لتمكين المطابقة الفعالة القائمة على OT دون نتائج إيجابية كاذبة.
بروتوكولات محسنة عالية الأبعاد:
- بروتوكولات للمجموعات عالية الأبعاد تحت افتراض "التباعد العالمي"، محققة تعقيداً خطياً في $d$ و $O(\log \delta)$ في العتبة.
تقييمات واسعة النطاق:
- اختبارات قياسية شاملة عبر مقاييس $L_\infty, L_1,$ و $L_2$ للأبعاد $d \in [2, 64]$ والعتبات $\delta \in [16, 1024]$ .
النتائج التجريبية

قام المؤلفون بتنفيذ بروتوكولاتهم ومقارنتها مع الأعمال الحديثة: van Baarsen و Pu [46] (القائم على OPRF) و Piske et al. [38] (القائم على OPRF و OT).

الأداء منخفض الأبعاد ( $d \in [2, 8]$ ):
- التسريع: أسرع بمقدار يصل إلى 145 $\times$ في وقت التشغيل مقارنة بـ [46] و 25 $\times$ أسرع من [38].
- الاتصال: تقليل في تكلفة الاتصال يصل إلى 20 $\times$ مقارنة بـ [46] و 17 $\times$ مقارنة بـ [38].
- القابلية للتوسع: على عكس [46]، الذي ينمو وقت تشغيله مع $(\log \delta)^{d/2}$ ، يظل أداء البروتوكول المقترح ثابتاً تقريباً مع زيادة $\delta$ .
الأداء عالي الأبعاد ( $d \in [16, 64]$ ):
- التسريع: أسرع بمقدار يصل إلى 36 $\times$ في وقت التشغيل مقارنة بـ [46].
- الاتصال: تقليل في تكلفة الاتصال يصل إلى 54 $\times$ مقارنة بـ [46].
- تظهر الميزة بشكل واضح عند قيم عتبة المسافة الكبيرة ( $\delta$ )، حيث تعاني البروتوكولات السابقة من توسع خطي أو فوق الخطي.

الأهمية والادعاءات

يدعي البحث تقديم تقدم في مجال fuzzy PSI من الناحيتين الملموسة والمقاربية:

التحسين المقاربي: يحل مشكلات $O((\log \delta)^d)$ و $O(\delta)$ في البروتوكولات خفيفة الوزن السابقة، موفراً $O(d \log \delta)$ وتبعية خطية في أحجام المجموعات.
الكفاءة الملموسة: من خلال الجمع بين OPRF معكوس الأدوار، و OT، وإطار عمل التجزئة ثنائي الطبقة الجديد، يحقق البروتوكول تسريعات عملية هائلة وتقليلاً في تكلفة الاتصال، مما يجعل fuzzy PSI قابلاً للتطبيق لعتبات أكبر وأبعاد أعلى مما كان ممكناً من قبل.
العمومية: يدعم الحل مسافات $L_p$ العامة ( $p \in [1, \infty]$ ) لكل من الإعدادات منخفضة وعالية الأبعاد، بينما كانت العديد من الأعمال السابقة محدودة بمقاييس معينة (مثل $L_\infty$ فقط) أو تتطلب افتراضات تشفيرية ثقيلة.

يؤكد المؤلفون أنه بينما تعتمد بروتوكولات الأبعاد العالية على افتراض "التباعد العالمي" القوي، فإن البروتوكولات منخفضة الأبعاد تعمل تحت افتراضات أضعف وأكثر واقعية (مركز/كرة فريدة لكل خلية شبكية) بما يتوافق مع الأعمال الفعالة السابقة.