💻 computer science

Information-Theoretic Distributed Point Functions with Shorter Keys

تقدم هذه الورقة دالة نقطة موزعة ذات معلومات نظرية (ITDPF) جديدة، آمنة تماماً وذات خصوصية واحدة (1-private) فوق المجموعة $\mathbb{Z}_p$ ، والتي تحقق مفاتيح سرية أقصر تقاربيّاً من المخططات الحالية عبر الاستفادة من تحويل الحصص بناءً على تقنيات استرجاع المعلومات الخاصة الحديثة.

المؤلفون الأصليون: Hang Deng, Liang Feng Zhang

نُشر 2026-04-28

📖 3 دقيقة قراءة☕ قراءة في استراحة قهوة

CC BY 4.0

المؤلفون الأصليون: Hang Deng, Liang Feng Zhang

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

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

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

الطريقة القديمة مقابل الطريقة الجديدة

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

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

كيف فعلوا ذلك: "الوصفة السرية"

لم يخترع المؤلفان تعويذة سحرية جديدة من الصفر؛ بل استخدما وصفة ذكية (تسمى إطار عمل LKZ) تحول نوعاً من أدوات مشاركة الأسرار إلى نوع آخر.

المكون الأساسي (PIR): "الصلصة السرية" التي استخدموها هي أداة متطورة تسمى استرجاع المعلومات الخاص (PIR). فكر في PIR كوسيلة تتيح لك سؤال أمين مكتبة عن كتاب معين دون أن يعرف أمين المكتبة أي كتاب سألت عنه. لقد جعل الاختراق الأخير الذي حققه غاسيمي، كوبارتي، وسودان عملية "السؤال" هذه فعالة للغاية.
التحويل (الخدعة السحرية): اكتشف المؤلفان كيفية ترجمة آلية "السؤال" الخاصة بـ PIR الجديد إلى آلية "تقسيم المفاتيح" المطلوبة لـ DPF.
- تشبيه: تخيل أن PIR القديم كان يشبه سؤال أمين المكتبة عن كتاب باستخدام نموذج معقد مكون من 10 صفحات. أما PIR الجديد فيستخدم رمزاً صغيراً من كلمتين فقط. وجد المؤلفون طريقة لتحويل هذا الرمز الصغير المكون من كلمتين إلى مفاتيح سرية لخريطة الكنز، مما يضمن بقاء المفاتيح صغيرة.

النتيجة: مفتاح صغير وآمن تماماً

تزعم الورقة البحثية أنها بنت نظاماً يتميز بـ:

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

العقبة (القيود)

المؤلفون صريحون بشأن المقايضات:

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

الملخص

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

إليك ملخص تقني مفصل للورقة البحثية بعنوان "الدوال النقطية الموزعة ذات المعلومات النظرية بمفاتيح أقصر" (Information-Theoretic Distributed Point Functions with Shorter Keys) من تأليف هانغ دينج وليانغ فينغ تشانغ.

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

تتناول الورقة بناء الدوال النقطية الموزعة ذات المعلومات النظرية (ITDPF).

التعريف: تسمح $(t, n)$ -ITDPF لـ دالة نقطية $f_{\alpha, \beta}(x)$ (التي تُخرج $\beta$ عند المدخل $\alpha$ و$0 $في أي مكان آخر) بالانقسام إلى$ n $من المفاتيح السرية. أي مجموعة فرعية مكونة من$ \le t $من الخوادم لا يمكنها تعلم أي شيء مطلقاً عن الدالة (أمن مثالي)، بينما يؤدي مجموع تقييمات جميع الخوادم الـ$ n$ إلى إعادة بناء قيمة الدالة.
التحدي: المقياس الأساسي للكفاءة في DPFs هو حجم المفتاح (الحجم الأقصى للمفاتيح السرية). تعاني الـ ITDPFs الآمنة تماماً الموجودة لمجموعة المخرجات $G = \mathbb{Z}_p$ $G = Z_{p}$ (حيث $p$ $p$ هو أي عدد أولي) من أحجام مفاتيح دون المستوى الأمثل.
- حققت الأعمال السابقة (مثل Boyle et al. و Li et al.) أحجام مفاتيح تتضمن أسساً تعتمد على دوال مثل $\nu_r(N) = (\log N)^{1/r}(\log \log N)^{1-1/r}$ .
- الهدف هو تقليل حجم المفتاح التقاربي مع الحفاظ على الأمن المثالي ودعم أي عدد أولي $p$ .

2. المنهجية

يقترح المؤلفون بناءً جديداً يعتمد على إطار عمل LKZ (Li, Kopparty, and Zhang) مدمجاً مع تقنيات استرجاع المعلومات الخاصة (PIR) الحديثة.

أ. إطار عمل LKZ

يقوم إطار العمل بتحويل مخطط مشاركة الأسرار (SSS) إلى ITDPF عبر تحويل الحصص (Share Conversion).

تحويل الحصة: يتطلب تحويل الحصص من مخطط مشاركة أسرار عتبة $(t, n)$ -SSS ( $L_1$ ) إلى حصص من مخطط additive SSS ( $L_2$ ) بحيث يكشف مجموع الحصص المحولة عن علاقة محددة بالسر الأصلي.
التمثيل الثنائي (Bilinear Representation): يتم تمثيل الدالة النقطية كدالة ثنائية (bilinear function) للحصص المحولة.
الرؤية الجوهرية: يتناسب حجم مفتاح الـ ITDPF الناتج مع التعقيد الاتصالي لمخطط PIR المستخدم لتوليد تحويل الحصة.

ب. الاستفادة من PIR القائم على المشتقات من GKS

الابتكار التقني الجوهري هو استخدام مخطط 1-private $n_r$ -server PIR الأحدث من GKS (Ghasemi, Kopparty, and Sudan, STOC 2025).

آلية GKS: على عكس مخططات PIR السابقة التي تستعلم فقط عن تقييمات متعدد الحدود، تستعلم GKS عن كل من التقييمات ومشتقات هاسي (Hasse derivatives) لمتعدد الحدود.
الأساس الرياضي:
- يستخدم عائلات $S$ -matching ومتعددات حدود $S$ -decoding فوق الحقول المنتهية.
- يقدم خاصية الاستيفاء الصفري مع التعدد (0-interpolation property with multiplicity). من خلال طلب المشتقات، يمكن للمخطط استيفاء الحد الثابت لمتعدد حدود متفرق باستخدام خوادم أقل أو بارامترات أصغر.
- تحديداً، تحقق GKS تعقيداً اتصالياً قدره $2^{O(\nu_{r+1}(N))}$ لـ $n_r$ من الخوادم، حيث تعتمد $n_r$ على عدد العوامل الأولية للمقياس.

ج. خطوات البناء المقترحة

الإعداد (Setup):
- اختيار مقياس $M = m \cdot p$ (حاصل ضرب أعداد أولية متمايزة).
- بناء عائلة $S_M$ -matching ومتعدد حدود $S_M$ -decoding مع تعدد 2 (بفضل استعلامات المشتقات).
تحويل الحصة (Conv):
- يمتلك الخادم حصة $c_\ell$ مشتقة من متجه عشوائي $w$ والمؤشر المستهدف $\alpha$ .
- بالنظر إلى مدخل $x$ ، يحسب الخادم "متعدد حدود جوهري" $D_x(Z)$ مقيداً بخط ضربي.
- باستخدام قاعدة السلسلة (chain rule)، يحسب الخادم مشتقة هاسي من الدرجة الأولى لـ $D_x(Z)$ عند نقاط محددة $b_\ell$ .
- يخرج الخادم حصة محولة تتضمن التقييم $D_x(b_\ell)$ وحد الحد المشتق، موزوناً بمعاملات الاستيفاء $a_{\ell, k}$ .
توليد DPF:
- ينشئ المولد $2n_r$ من المفاتيح. يتكون كل مفتاح من زوج: حصة جمعية لقيمة المخرج وحصة من الـ SSS القائم على PIR.
- تقوم خوارزمية التقييم بحساب الضرب الداخلي لمكونات المفتاح لاستعادة الحصة الجمعية لـ $f_{\alpha, \beta}(x)$ .

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

تحويل حصة مبتكر: اشتق المؤلفون دالة تحويل حصة جديدة مباشرة من PIR القائم على مشتقات GKS. هذا هو أول تطبيق لـ PIR القائم على المشتقات لبناء ITDPFs.
حجم مفتاح محسّن: قاموا ببناء $(1, 2n_r)$ $(1, 2 n_{r})$ -ITDPF مثالي الأمان مع مجموعة مخرجات $\mathbb{Z}_p$ $Z_{p}$ .
- حجم المفتاح: $O(2^{c_2(r) \cdot \nu_{r+1}(N)} \cdot \log p)$ .
- التحسين: هذا أصغر تقاربياً من أفضل الـ ITDPFs الآمنة تماماً السابقة (على سبيل المثال، $2^{O(\nu_r(N))}$ الخاصة بـ Li et al.)، مما يقلل الأس من $\nu_r(N)$ إلى $\nu_{r+1}(N)$ .
الأمن المثالي: يحافظ البناء على الأمن المثالي (الأمن المعلوماتي ضد الخصوم غير المقيدين حسابياً)، على عكس بعض البدائل الإحصائية التي تضحي بالأمن مقابل الكفاءة.
العمومية: يعمل المخطط مع أي عدد أولي $p$ كمقياس لمجموعة المخرجات، وهو تعميم هام للعديد من البناءات السابقة.

4. النتائج

الحدود النظرية: تثبت الورقة أن المخطط المقترح يلبي متطلبات الصحة والأمن المثالي لإطار عمل LKZ.
المقارنة (الجدول I):
- مقارنة بـ Thm. 10 of [10] (Li et al.)، الذي يمتلك حجم مفتاح $O(2^{c_1(r) \cdot \nu_r(N)}$ )، يحقق المخطط الجديد $O(2^{c_2(r) \cdot \nu_{r+1}(N)})$ . وبما أن $\nu_{r+1}(N) < \nu_r(N)$ ، فإن مفاتيح المخطط الجديد أقصر تقاربياً.
- مقارنة بـ Thm. 1 of [2] (Boyle et al.)، المخطط الجديد ليس أسوأ بل يوفر توسعاً تقاربياً أفضل للقيم الكبيرة لـ $N$ .
البارامترات: عدد الخوادم المطلوب هو $2n_r$ ، حيث يتم تعريف $n_r$ بواسطة عدد العوامل الأولية في بناء PIR (مثلاً $n_1=2, n_2=3, \dots$ ).

5. الأهمية

الكفاءة في MPC و PIR: تعتبر DPFs لبنات أساسية للحوسبة متعددة الأطراف الآمنة (MPC) واسترجاع المعلومات الخاصة (PIR). إن تقليل حجم المفتاح يترجم مباشرة إلى انخفاض في تكاليف الاتصال ومتطلبات التخزين في هذه البروتوكولات.
الربط بين PIR و DPFs: يظهر هذا العمل تآزراً قوياً بين التطورات الأخيرة في PIR (تحديداً النهج القائم على المشتقات) وبناء DPFs. ويشير إلى أن التحسينات في التعقيد الاتصالي لـ PIR يمكن ترجمتها مباشرة إلى DPFs أكثر كفاءة.
الاتجاهات المستقبلية:
- يقتصر البناء الحالي على DPFs ذات 1-private (الأمن ضد خادم واحد متواطئ) لأن PIR الخاص بـ GKS هو 1-private. يعد التوسع إلى $t$ -private DPFs حيث $t > 1$ دون حدوث انفجار أسي في عدد الخوادم تحدياً مفتوحاً.
- تحديد التوسع من مجموعة المخرجات $\mathbb{Z}_p$ إلى مجموعات أبيلية (Abelian groups) arbitrary كعمل مستقبلي.

باختصار، تقدم هذه الورقة طفرة في كفاءة الـ ITDPFs ذات المعلومات النظرية المثالية من خلال الاستفادة من تقنيات PIR الحديثة القائمة على المشتقات، محققة أقصر المفاتيح السرية المعروفة لمجموعات المخرجات ذات الرتب الأولية.