💻 computer science

Efficient Fuzzy Private Set Intersection from Secret-shared OPRF

تقترح هذه الورقة بروتوكولات تقاطع المجموعات الخاصة الضبابية عالية الكفاءة لمقاييس مسافة $L_p$ تستفيد من دوال التشفير العشوائية القابلة للبرمجة والمنسية ذات الحصص السرية وتقنية البادئة لتحقيق تعقيد خطي والتفوق بشكل كبير على البناءات الحالية في كل من وقت التشغيل وتكلفة الاتصال.

المؤلفون الأصليون: Xinpeng Yang, Meng Hao, Chenkai Weng, Robert H. Deng, Yonggang Wen, Tianwei Zhang

نُشر 2026-04-17

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

CC BY 4.0

المؤلفون الأصليون: Xinpeng Yang, Meng Hao, Chenkai Weng, Robert H. Deng, Yonggang Wen, Tianwei Zhang

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

إليك شرح لورقة البحث "Efficient Fuzzy Private Set Intersection from Secret-shared OPRF" (تقاطع المجموعات الخاصة الضبابي الفعال من خلال OPRF القائم على الأسرار المشتركة)، مترجم إلى لغة بسيطة باستخدام تشبيهات إبداعية.

الصورة الكبيرة: مشكلة "التوفيق الضبابي"

تخيل أنك وصديقك تحاولان إيجاد أرضية مشتركة، لكن لا يمكنكما إظهار قوائمكما لبعضكما البعض.

السيناريو: لديك قائمة بأغانيك المفضلة (المجموعة A). ولدى صديقك قائمة بأغانيه المفضلة (المجموعة B).
المشكلة القياسية (المطابقة التامة): تريد معرفة الأغاني المتطابقة تماماً. هذا سهل؛ فأنت فقط تتحقق مما إذا كانت "الأغنية X" في قائمتك هي نفسها "الأغنية X" في قائمته.
المشكلة "الضبابية": الآن، تخيل أن قوائمكما ليست مجرد أغانٍ، بل هي بصمات أصابع أو مسحات للوجه.
- بصمة إصبعك قد تكون مشوشة قليلاً اليوم.
- مسحة وجه صديقك قد تكون التُقطت في إضاءة مختلفة.
- هما ليسا متطابقين تماماً، لكنهما "قريبان بما يكفي" ليعبرا عن نفس الشخص.
- الهدف: تريدان العثور على هذه المطابقات "القريبة بما يكفي" دون الكشف عن بصمات الأصابع أو الوجوه الفعلية لبعضكما البعض.

التحدي: القيام بذلك بشكل آمن يشبه عادةً محاولة حل لغز ضخم حيث تكلف كل قطعة منه ثروة لتحريكها. الطرق السابقة كانت بطيئة، ومكلفة، وتتطلب "دروعاً رياضية" ثقيلة (تشفير معقد) مما جعلها غير عملية للاستخدام في العالم الحقيقي.

حل المؤلفين: مجموعة أدوات جديدة خفيفة الوزن

قام الباحثون (Yang, Hao, et al.) ببناء نظام جديد سريع، رخيص، وآمن. لقد استبدلوا "الدروع الرياضية الثقيلة" بمجموعة من الحيل الذكية وخفيفة الوزن.

إليكم كيف فعلوا ذلك، مقسماً إلى ثلاث أفك Aber ideas رئيسية:

1. "المصافحة السرية" (so-OPPRF)

التشبيه: تخيل أنك وصديقك تريدان التحقق مما إذا كنتما تعرفان كلمة مرور سرية، لكن لا تريدان قول كلمة المرور بصوت عالٍ، ولا تريدان معرفة كلمة مرور الآخر أيضاً.

الطريقة القديمة: يقوم كل منكما بكتابة كلمات المرور على ورقة، ثم يضعها في خزنة فولاذية ثقيلة (تشفير مكلف) ويرسلها بالبريد إلى طرف ثالث للتحقق منها. هذا يستغرق وقتاً طويلاً.
الطريقة الجديدة (so-OPPRF): أنت وصديقك تستخدمان "دفتر ملاحظات سحري".
- تكتب أنت قائمة "المطابقات المحتملة" في الدفتر.
- يسأل صديقك: "هل 'X' موجود في دفتر ملاحظاتك؟"
- يعطيك الدفتر كلاً منكما سراً منقسماً. تحصل أنت على نصف الإجابة، وهو يحصل على النصف الآخر.
- السحر: لا يعرف أي منكما الإجابة الكاملة بمفرده. أنت فقط تعرف الإجابة عندما تدمجان نصفيكما. إذا كانت الإجابة "نعم، هناك تطابق"، فسيحصل كلاهما على إشارة محددة. وإذا كانت "لا"، فستحصلان على ضوضاء عشوائية.
- لماذا هي رائعة: لأنها تستخدم رياضيات بسيطة (مثل جمع الأرقام) بدلاً من التشفير المعقد، مما يجعلها سريعة للغاية.

2. "الفلتر ذو الخطوتين" (من الخشن إلى الناعم)

التشبيه: تخيل أنك تبحث عن كلب مفقود في مدينة ضخمة. لن تتحقق من كل منزل واحداً تلو الآخر؛ فهذا سيستغرق سنوات.

الخطوة 1: فحص الحي (الرسم الخرائطي الخشن - Coarse Mapping):
- تقسم المدينة إلى أحياء. إذا كان الكلب في "الحي أ"، فأنت تتحقق فقط من المنازل في "الحي أ".
- في الورقة البحثية، يحولون كل بصمة إلى "معرف حي". إذا كانت بصمتا الإصبع قريبتين، فسيحصلان على نفس المعرف.
- المخاطر: أحياناً، قد يعيش كلبان مختلفان في نفس الحي (إيجابية كاذبة).
الخطوة 2: فحص عتبة الباب (التصفية الدقيقة - Refined Filtering):
- الآن، تتحقق فقط من المنازل المحددة في ذلك الحي. تنظر بدقة لترى ما إذا كان الكلب هو حقاً الذي تبحث عنه.
- في الورقة البحثية، يستخدمون "المصافحة السرية" (من الخطوة 1) للقيام بهذا الفحص النهائي. إذا كانت بصمات الأصابع قريبة حقاً، فإن المصافحة تؤكد ذلك. أما إذا كانا مجرد "جيران في الحي" ولكن ليس تطابقاً، فإن المصافحة تفشل.

3. خدعة "الرمز البريدي" (تحسين البادئة - Prefix Optimization)

التشبيه: تخيل أنك تبحث عن منزل برقم شارع يتراوح بين 100 و 200.

الطريقة القديمة: تتحقق من كل رقم: 100، 101، 102... وصولاً إلى 200. هذا يتطلب 100 عملية فحص!
الطريقة الجديدة (البادئة): تدرك أنك لست بحاجة للتحقق من كل رقم.
- بدلاً من التحقق من 100 رقم، تتحقق من بضع "كتل" (مثل "10x"، "11x"، "12x").
- هذا يحول المهمة التي تستغرق 100 خطوة إلى مهمة تستغرق 7 أو 8 خطوات فقط.
- لماذا يهم هذا: عندما تكون "المسافة" المسموح بها كبيرة (على سبيل المثال، بصمة إصبع ضبابية جداً)، تجعل هذه الخدعة النظام أسرع بشكل أسي.

النتائج: لماذا يجب أن نهتم؟

اختبر الباحثون نظامهم الجديد مقابل أفضل الطرق الحالية (والتي تشبه استخدام محرك بخاري لتشغيل سيارة سباق).

السرعة: نظامهم أسرع بـ 12 إلى 145 مرة.
- التشبيه: إذا كان النظام القديم يستغرق 10 دقائق للعثور على تطابق، فإن النظام الجديد يقوم بذلك في 4 ثوانٍ.
استهلاك البيانات: يستخدم نظامهم بيانات أقل بـ 3 إلى 8 مرات للإرسال عبر الإنترنت.
- التشبيه: بدلاً من إرسال شاحنة محملة بالطوب، يرسلون ظرفاً واحداً.
القابلية للتوسع: يعمل بشكل رائع حتى عندما يكون لديك ملايين العناصر أو بيانات عالية الأبعاد (مثل مسحات الوجه ثلاثية الأبعاد المعقدة).

ملخص في جملة واحدة

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

لماذا يهم هذا بالنسبة لك؟

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

إليك ملخص تقني مفصل لورقة البحث بعنوان "Efficient Fuzzy Private Set Intersection from Secret-shared OPRF".

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

تسمح عملية تقاطع المجموعات الخاص (Private Set Intersection - PSI) لطرفين (المرسل الذي يمتلك المجموعة $Q$ والمستقبل الذي يمتلك المجموعة $W$ ) بحساب التقاطع $Q \cap W$ دون الكشف عن العناصر غير المتقاطعة. وتوسع تقنية تقاطع المجموعات الضبابي (Fuzzy PSI - FPSI) هذا المفهوم ليشمل السيناريوهات التي لا يكون فيها التطابق التام كافيًا (مثل المصادقة البيومترية)، مما يسمح للمستقبل بمعرفة العناصر $q \in Q$ إذا وجد عنصر $w \in W$ بحيث يكون $dist(q, w) \le \delta$ وفقًا لمقياس مسافة (عادةً ما يكون $L_p$ حيث $p \in [1, \infty]$ ).

القيود الحالية:

التعقيد العالي: تعاني بروتوكولات FPSI الحالية لمقاييس $L_p$ العامة غالبًا من تعقيد أسي في بُعد العنصر $d$ أو تعقيد فوق خطي في عتبة المسافة $\delta$ .
عدم الكفاءة: تعتمد البروتوكولات الحديثة ذات التعقيد الخطي (مثل Gao et al. [14] و Dang et al. [16]) بشكل كبير على التشفير المتماثل الجمعي (Additively Homomorphic Encryption - AHE) (مثل ElGamal و Paillier). هذه العمليات القائمة على المفتاح العام مكلفة حاسوبيًا، مما يؤدي إلى أداء عملي ضعيف مقارنة بنهج المفتاح المتماثل.
قابلية التوسع: تجعل البيانات عالية الأبعاد وعتبات المسافة الكبيرة ( $\delta$ ) الحلول الحالية بطيئة للغاية ومستهلكة للاتصالات بشكل مفرط.

٢. المنهجية

يقترح المؤلفون إطار عمل جديد لـ FPSI يحقق تعقيدًا خطيًا في أحجام المجموعات ( $m, n$ )، والبُعد ( $d$ )، والعتبة ( $\delta$ )، وذلك باستخدام عمليات المفتاح المتماثل خفيفة الوزن بشكل أساسي. تتضمن المنهجية الأساسية ثلاث مكونات رئيسية:

أ. اللبنة الجديدة: Shared-Output OPPRF (so-OPPRF)

تقدم الورقة دالة التشفير شبه العشوائية القابلة للبرمجة مع مخرجات مشتركة سريًا (so-OPPRF).

الوظيفة: على عكس الـ OPPRF القياسي حيث يتعلم المستقبل المخرج، تقوم so-OPPRF بإخراج حصص سرية (secret shares) لقيمة الـ PRF لكلا الطرفين. لا يمكن لأي طرف معرفة القيمة الكاملة بمفرده.
البناء: تجمع بين مخزن قيم-مفاتيح غامض (Oblivious Key-Value Store - OKVS) وبين so-OPRF.
- يقوم المرسل ببرمجة الـ PRF على نقاط محددة باستخدام ترميز OKVS.
- يقوم المستقبل بالاستعلام عن المدخلات ويتلقى حصصًا سرية للنتيجة.
- يتجنب هذا تسريب معلومات التطابق الجزئي التي تحدث في الـ OPPRF القياسي، والتي كانت تتطلب سابقًا تشفير AHE مكلفًا لإخفائها.

ب. التعيين الضبابي المجزأ (Modular Fuzzy Mapping)

صمم المؤلفون بروتوكولاً مجزأً لمرحلة "التعيين الخشن" (تخصيص معرفات للعناصر ضمن مسافة $\delta$ ):

التعيين المحلي: يولد كلا الطرفين معرفات محلية بناءً على فترات حجمها $2\delta$ . ولمنع تسرب المعلومات المتعلقة بتداخل الفترات، يستخدمون so-OPPRF لاسترجاع حصص سرية لقيم عشوائية مرتبطة بهذه الفترات.
التعيين العالمي: لدمج التعيينات المحلية في معرف (ID) عالمي دون الكشف عن القيم الأساسية، قدموا so-OPRF (Secret-Shared Input OPRF). يمتلك كلا الطرفين حصصًا سرية من المفتاح والمدخل. يتعلم المستقبل المعرف النهائي، بينما يتعلم المرسل معرفاته الخاصة، مما يضمن أن العناصر ضمن مسافة $\delta$ تحصل على معرفات متطابقة دون تسريب القيم الوسيطة.

ج. التصفية المنقحة (Refined Filtering)

بعد التعيين الخشن، يجب استبعاد الإيجابيات الكاذبة (العناصر التي لها نفس المعرف ولكن مسافتها $> \delta$ ).

يستخدم الطرفان so-OPPRF مرة أخرى لحساب الحصص السرية للمسافة (أو صفر لـ $L_\infty$ ).
يستخدمون اختبار المساواة الخاص (PEQT) أو اختبار الفترة الخاص للتحقق مما إذا كانت المسافة المشتركة تقع ضمن العتبة.
أخيرًا، يسمح بروتوكول النقل الغامض (Oblivious Transfer - OT) للمستقبل باسترجاع عناصر المرسل المطابقة.

د. تحسين البادئة (Prefix Optimization)

بالنسبة لعتبات المسافة الكبيرة $\delta$ ، يتم تحسين الاعتماد الخطي على $\delta$ ليصبح لوغاريتميًا ( $O(\log \delta)$ ) باستخدام تمثيل البادئة (prefix representation).

بدلاً من برمجة الفترة بأكملها $[q-\delta, q+\delta]$ (بحجم $2\delta+1$ )، يقوم المرسل ببرمجة $O(\log \delta)$ فقط من البادئات التي تغطي الفترة.
يقلل هذا بشكل كبير من تكاليف الاتصال والحوسبة لعتبات $\delta$ الكبيرة.

٣. المساهمات الرئيسية

so-OPPRF: لبنة تشفيرية مبتكرة تتيح التقييم الغامض لدوال PRF القابلة للبرمجة مع مخرجات مشتركة سرًا، مما يعمل كحجر أساس لعمليات المطابقة الضبابية الفعالة.
بروتوكولات FPSI فعالة: أول بروتوكولات FPSI لمسافات $L_p$ العامة ( $p \in [1, \infty]$ ) التي تحقق تعقيدًا خطيًا في $m, n, d,$ و $\delta$ باستخدام أدوات المفتاح المتماثل (PRF, OT, OKVS) بدلاً من AHE.
تحسين البادئة: تكييف تقنيات البادئة لتقليل التعقيد من $O(\delta)$ إلى $O(\log \delta)$ للعتبات الكبيرة، مما يحافظ على الكفاءة دون عمليات المفتاح العام الثقيلة.
التصميم المجزأ: فصل واضح بين مرحلتي التعيين الضبابي والتصفية، مما يبسط تحليل البروتوكول وتنفيذه.

٤. النتائج التجريبية

قام المؤلفون بتنفيذ البروتوكولات بلغة ++C ومقارنتها بالأعمال الحديثة: Gao et al. (ASIACRYPT'24) و Dang et al. (CCS'25).

مكاسب الأداء:
- وقت التشغيل: حقق تسريعًا يتراوح بين 12 $\times$ إلى 145 $\times$ مقارنة بـ Gao et al. و 9 $\times$ إلى 80 $\times$ مقارنة بـ Dang et al.
- الاتصالات: قلل تكاليف الاتصال بنسبة 3 $\times$ إلى 8 $\times$ (مقابل Gao) و 5 $\times$ إلى 19 $\times$ (مقابل Dang).
قابلية التوسع: تتسع فجوة الأداء مع زيادة أحجام المجموعات والأبعاد. على سبيل المثال، عند $m=n=2^{16}$ و $d=8$ و $\delta=32$ ، يكون البروتوكول المقترح أسرع بـ 145 $\times$ من Gao et al.
تحسين البادئة: بالنسبة لـ $\delta$ الكبيرة (مثل $\delta=1024$ )، قللت نسخة تحسين البادئة الاتصالات بنسبة 11 $\times$ ووقت التشغيل بنسبة ~50% مقارنة بالنسخة غير المزودة بالبادئة، مع استمرار تفوقها على المنافسين.

٥. الأهمية

الجدوى العملية: من خلال استبدال التشفير المتماثل (Homomorphic Encryption) المكلف بعمليات المفتاح المتماثل، يجعل هذا العمل من FPSI أمرًا ممكنًا عمليًا للتطبيقات الواقعية مثل المصادقة البيومترية (التعرف على بصمة الإصبع/الوجه) و مطابقة الجينوم، حيث تعد البيانات عالية الأبعاد وتحمل الضوضاء أمرًا بالغ الأهمية.
التقدم النظري: يحل هذا العمل السؤال المفتوح حول ما إذا كان من الممكن تحقيق FPSI فعال ملموسًا بتعقيد خطي دون استخدام AHE، مما يوفر نموذجًا جديدًا للحوسبة متعددة الأطراف الآمنة في سيناريوهات المطابقة الضبابية.
التأثير المستقبلي: من المرجح أن تكون الأدوات المقدمة so-OPPRF و si-OPRF لبنات بناء مفيدة لبروتوكولات الخصوصية الأخرى التي تتطلب تقييمات مشتركة سرًا.

القيود والعمل المستقبلي:
يعتمد البروتوكول الحالي على افتراض الإسقاط المنفصل (أن العناصر متباعدة بما يكفي في بُعد واحد على الأقل). يهدف العمل المستقبلي إلى تخفيف هذه الافتراضات وتحقيق أمن خبيث (malicious security) دون فقدان كبير في الكفاءة.