💻 computer science

Lower Bounds on Black-Box Constructions of Pseudorandom Functions

تثبت هذه الورقة أنه لا يمكن لأي بناء "الصندوق الأسود الكامل" لدالة عشوائية كاذبة (PRF) من مولد عشوائي كاذب (PRG) أن يحقق أقل من $o(n/\log n)$ من الاستدعاءات غير التكيفية للمولد العشوائي الكاذب، حتى بالنسبة للدوال العشوائية الكاذبة الضعيفة ذات المخرجات المكونة من بت واحد، مما يوفر حدوداً دنيا قوية على كفاءة مثل هذه البناءات ويترك إمكانية وجود بناء يعتمد على استدعاء واحد كتحدٍ رئيسي مفتوح.

المؤلفون الأصليون: Bar Alon, Itai Dinur, Muthuramakrishnan Venkitasubramaniam

نُشر 2026-08-17

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

CC BY 4.0

المؤلفون الأصليون: Bar Alon, Itai Dinur, Muthuramakrishnan Venkitasubramaniam

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

معضلة صانع الأقفال الرقمي

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

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

لعقود من الزمن، كان الوصفة القياسية (المعروفة باسم بناء GGM) هي استخدام آلة مد البذرة مراراً وتكراراً، في هيكل يشبه الشجرة، حوالي $\omega(\log n)$ مرة (حيث $n$ هو حجم البذرة). إنها تعمل بشكل رائع، لكنها تبدو معقدة بعض الشيء. هل هناك طريق مختصر؟ هل يمكننا بناء باب خزنة مثالي باستخدام آلة مد البذرة مرة واحدة فقط؟ أو ربما بضع مرات فقط؟ يغوص هذا البحث بعمق في هذا السؤال، حيث يعمل كالمحقق الذي يحاول إثبات أنه مهما كنت بارعاً، فلا يمكنك ببساطة بناء باب خزنة آمن بعدد قليل جداً من عمليات مد البذرة.

الاكتشاف الكبير للورقة: مشكلة "القليل جداً"

تتناول هذه الورقة، التي كتبها بار ألون، وإيتاي دينور، وموثوراماكريشنان فينكيتاسوبيرياميان، السؤال الجوهري: ما هو الحد الأدنى المطلق لعدد المرات التي يجب أن نستدعي فيها مولداً عشوائياً زائفا (PRG) لبناء دالة عشوائية زائفة (PRF)؟

يثبت المؤلفون أنه بالنسبة لنوع محدد ومعقول جداً من البناء، فإن الإجابة هي "أكثر بكثير مما قد تأمل". وتحديداً، يظهرون أنه لا يمكنك بناء PRF آمنة باستخدام طريقة "الصندوق الأسود الكامل" (fully black-box) إذا استدعيت الـ PRG عدداً ضئيلاً من المرات—وتحديداً، أقل من $n / \log n$ مرة تقريباً (حيث $n$ هو طول مدخل الـ PRG).

لفهم برهانهم، تخيل لعبة "كشف المزيف":

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

النتيجة الرئيسية:
تثبت الورقة أنه بالنسبة للبناءات غير التكيفية (حيث يقرر الباني جميع أسئلة الـ PRG قبل رؤية أي إجابات)، فمن المستحيل بناء PRF بعدد استدعاءات أقل من $o(n / \log n)$ . وينطبق هذا حتى لو كانت الـ PRF تخرج بتًا واحداً فقط (0 أو 1) وحتى لو كان الخصم مقيداً بطرح أسئلة بسيطة وعشوائية.

نتيجة "المخرجات الطويلة":
نظر المؤلفون أيضاً في دوال الـ PRF التي تنتج سلاسل طويلة من البيانات (وليس مجرد بت واحد). وأثبتوا أنه حتى لو كان مسموحاً للباني بأن يكون "تكيُّفياً" (يطرح الأسئلة واحداً تلو الآخر ويستخدم الإجابات لتقرير السؤال التالي)، فلا يزال هناك حد صارم. إذا قام الـ PRG بمد المدخل بمقدار صغير، فأنت بحاجة إلى $out / \log n$ استدعاء على الأقل. وإذا قام الـ PRG بمد المدخل بمقدار كبير، فأنت بحاجة إلى $out / r$ استدعاء على الأقل.

ماذا يعني هذا بالنسبة لحلم "الاستدعاء الواحد"

لفترة طويلة، تساءل علماء التشفير عما إذا كان بناء "استدعاء واحد" ممكناً—أي بناء PRF مثالية عن طريق مد البذرة مرة واحدة فقط.

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

تحذير "مقيد الاستعلامات"

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

الخلاصة

هذه الورقة لا تقترح مجرد حد؛ بل تقدم برهاناً رياضياً على أن "الطريق المختصر" لبناء الـ PRF هو طريق مسدود. إذا كنت تريد بناء PRF آمنة عبر "الصندوق الأسود"، فلا يمكنك تخطي الخطوات. يجب عليك دفع الثمن باستدعاء الـ PRG لعدد كافٍ من المرات لضمان أن "الاعتلاج" (الإنتروبيا - أي العشوائية وعدم القدرة على التنبؤ) مرتفع بما يكفي لخداع أي مخترق. إن بناء GGM الشهير، الذي يستخدم حوالي $\omega(\log n)$ من الاستدعاءات، يتبين أنه شبه مثالي. إن حلم بناء حصن بطلقة واحدة (أو لبنة واحدة) مستحيل رياضياً في هذا السياق.

ملخص تقني: الحدود الدنيا للإنشاءات الصندوقية السوداء للدوال شبه العشوائية

بيان المشكلة

تتناول الورقة سؤالاً جوهرياً مفتوحاً في علم التشفير: ما هو الحد الأدنى لعدد الاستدعاءات لمولد شبه عشوائي (PRG) اللازم لإنشاء دالة شبه عشوائية (PRF) عبر إنشاء صندوقي أسود كامل؟

لقد أرسى العمل الرائد لـ Goldreich وGoldwasser وMicali (GGM) أنه يمكن بناء PRF باستخدام PRG عبر نهج قائم على الشجرة. وعند دمجه مع تقنية توسيع المجال لـ Levin، يتطلب هذا الإنشاء $\omega(\log n)$ من الاستدعاءات لـ PRG، حيث $n$ هو طول مدخلات الـ PRG. وبينما أثبت العمل الأخير لـ Beimel وMalkin وMazor مثالية GGM لفئة محددة من "إنشاءات الأشجار"، فإن الحالة العامة لا تزال غير محلولة. وتحديداً، لا يزال من غير المعروف ما إذا كان يمكن بناء PRF باستدعاءات أقل من $\omega(\log n)$ ، أو حتى باستدعاء واحد، باستخدام تقنيات الصندوق الأسود العامة.

يستقصي هذا العمل هذا السؤال ضمن إطار الإنشاءات الصارية السوداء بالكامل (fully black-box constructions)، حيث يكون كل من الإنشاء والاختزال (reduction) صندوقيين أسودين. ويركز المؤلفون تحديداً على فئة من الاختزالات تسمى الاختزالات المقيدة بالاستعلام (query-bounded reductions)، حيث يكون عدد التفاعلات التي يقوم بها الاختزال مع الخصم (adversary) محدوداً بمتعدد حدود مستقل عن تعقيد استعلام الخصم (بشرجع أن يكون الخصم ناجحاً بشكل كافٍ).

المنهجية

يستخدم المؤلفون نموذج الاختزال الفوقي (meta-reduction paradigm) لتحديد حدودهم الدنيا. تتضمن هذه التقنية إنشاء خصم "حقيقي" غير فعال يمكنه محاكاة خصم "مثالي" (الذي يكسر الـ PRF) دون الوصول المباشر إلى الـ PRG الأساسي، مما يؤدي إلى كسر أمن الـ PRG باستخدام عدد استعلامات أقل مما هو مسموح به.

المكونات التقنية الرئيسية:

الاختزالات المقيدة بالاستعلام: يعرّف المؤلفون الاختزال بأنه مقيد بالاستعلام إذا كان عدد المرات التي يستعلم فيها للخصم المميز (distinguishing adversary) محدوداً بمتعدد حدود $d(n)$ ، بغض النظر عن عدد الاستعلامات التي يجريها الخصم لـ oracle الخاص به. تلتقط هذه الفئة معظم الاختزالات المعروفة في الأدبيات، بما في ذلك GGM وإنشاءات Goldreich-Levin.
الخصوم المثاليون مقابل الحقيقيون:
- الخصم المثالي ( $A_{ideal}$ ): خصم غير فعال لديه وصول أسي (exponential access) إلى oracle الـ PRG. يحاول كسر الـ PRF من خلال إيجاد مفتاح متسق مع كسر كبير من أزواج المدخلات-المخرجات.
- الخصم الحقيقي ( $A_{real}$ ): خصم غير فعال ليس لديه وصول إلى الـ PRG. بدلاً من ذلك، يتلقى أزواج (الاستعلام-الجواب) الناتجة عن تفاعل الاختزال مع الـ PRG. يحاول محاكاة $A_{ideal}$ عبر تقدير احتمال أن يكون المفتاح متسقاً مع المخرجات المرصودة.
دوال الدرجة (Score Functions) والاستقلالية:
- التحدي الجوهري هو أن مخرجات الـ PRF على مدخلات مختلفة قد تكون مترابطة إذا كانت تشترك في بذور (seeds) الـ PRG.
- يقدم المؤلفون إجراءً لتحديد "البذور المتكررة" (البذور المستخدمة من قبل مدخلات عديدة) واستبدال مخرجاتها بقيم ثابتة. هذا يقلل من عدد استدعاءات الـ PRG النشطة.
- بالنسبة للمدخلات المتبقية، يستخدم المؤلفون ادعاءً توافقياً (Claim 3/6) لإظهار أنه إما أن مجموعة كبيرة من المدخلات تستخدم بذور PRG منفصلة متبادلاً (مما يسمح بحجج الاستقلالية عبر متباينة Hoeffding)، أو أن عدد هذه المفاتيح ضئيل جداً.
- للتعامل مع المسافة الإحصائية بين الخصمين المثالي والحقيقي، يستخدم المؤلفون عتبة عشوائية (randomized threshold) (تُسحب عشوائياً من $[0.8, 1]$ ) بدلاً من عتبة ثابتة. يعمل هذا على تنعيم حدود القرار، مما يضمن أن توزيع مخرجات الخصم الحقيقي قريب إحصائياً من توزيع الخصم المثالي، بشرط أن يكون عدد المدخلات $m$ كبيراً بما يكفي بالنسبة لعدد استعلامات الاختزال $d$ .
حجج الإنتروبيا للمخرجات الطويلة: بالنسبة للنتيجة الثانية (Theorem 2)، يستخدم المؤلفون حجة قائمة على الإنتروبيا. يقومون بإنشاء PRG محدد يطبق العشوائية فقط على بادئة (prefix) صغيرة من البذرة. هذا يحد من إنتروبيا مخرجات الـ PRF لتكون أقل بكثير من مخرجات دالة عشوائية حقيقية، مما يسمح للمميز بكسر الإنشاء إذا كان عدد الاستدعاءات منخفضاً جداً.

المساهمات والنتائج الرئيسية

1. الحد الأدنى للاستدعاءات غير التكيفية (Theorem 1)

تثبت الورقة أنه لا يوجد إنشاء صندوقي أسود كامل لـ PRF من PRG باستخدام استدعاءات غير تكيفية (non-adaptive) واختزالات مقيدة بالاستعلام إذا كان عدد الاستدعاءات $c$ يحقق:
$c = o\left(\frac{n}{\log n}\right) \quad \text{و} \quad c = o\left(\frac{in}{\log in}\right)$
حيث $n$ هو طول مدخلات الـ PRG و $in$ هو طول مدخلات الـ PRF.

النطاق: تسري هذه النتيجة حتى بالنسبة لـ الـ PRFs الضعيفة (حيث يكون الخصم مقيداً باستعلامات i.i.d. منتظمة) ولـ PRFs ذات مخرج مكون من بت واحد (one-bit output).
الآثار: هذا ينفي إمكانية بناء PRF باستدعاء ثابت لـ PRG (على سبيل المثال، استدعاء واحد) لـ PRFs ذات أطوال مدخلات $in = \omega(\log n)$ ، مما يحل حالة محددة من المشكلة المفتوحة للاختزالات المقيدة بالاستعلام.

2. الحد الأدنى للمخرات الطويلة (Theorem 2)

تحدد الورقة حداً أدنى لـ PRFs ذات مخرجات طويلة ($out$) ينطبق حتى على الإنشاءات التكيفية ولا يتطلب أن يكون الاختزال مقيداً بالاستعلام.

النتيجة: لا يوجد إنشاء صندوقي أسود كامل لـ PRF بمخرج طوله $out$ من PRG بامتداد (stretch) قدره $r$ باستخدام أقل من $\frac{out}{\max(r, \omega(\log n))}$ من الاستدعاءات.
المقارنة مع GGM: يستخدم إنشاء GGM (مع خدعة Levin) $\omega(\log n)$ من الاستدعاءات لـ PRG بامتداد $n$ -bit لإنتاج مخرج بطول $n$ -bit. ومن خلال دمج هذا مع PRG بامتداد 1-bit (يتطلب $O(n/\log n)$ استدعاء)، يصبح إجمالي الاستدعاءات لـ PRG بامتداد 1-bit هو $\omega(n)$ . يوضح Theorem 2 حداً أدنى قدره $\Omega(n / \omega(\log n))$ ، مما يبين أن GGM مثالي حتى عامل $\omega(\log n)$ .

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

تدعي الورقة أنها حققت تقدماً كبيراً في السؤال طويل الأمد حول مثالية إنشاءات الـ PRF من الـ PRG.

مثالية GGM: بينما كانت النتائج السابقة محدودة بـ "إنشاءات الأشجار"، فإن هذا العمل يوفر حدوداً دنيا لإنشاءات الصندوق الأسود العامة تحت افتراضات محددة ولكن طبيعية (الاختزالات المقيدة بالاستعلام).
حل حالة الاستدعاء الواحد: يصرح المؤلفون صراحة بأن نتيجتهم تحل مسألة ما إذا كان يمكن بناء PRF باستدعاء واحد لـ PRG لفئة الاختزالات المقيدة بالاستعلام. لقد أثبتوا أن مثل هذا الإنشاء مستحيل لـ PRFs ذات أطوال مدخلات $in = \omega(\log n)$ .
المتانة: نتائج الاستحالة تسري حتى بالنسبة للـ PRFs الضعيفة، وفي حالة المخرجات الطويلة، حتى للإنشاءات التكيفية.
القيود: يقر المؤلفون بتواضع بأن نتيجتهم الرئيسية (Theorem 1) تعتمد على افتراض "التقيد بالاستعلام". ويشيرون إلى أنه لا يزال من المسائل المفتوحة ما إذا كان يمكن توسيع هذه الحدود الدنيا لتشمل جميع اختزالات الصندوق الأسود، حيث يعتمد برهانهم على كون عدد تفاعلات الاختزال مستقلاً عن تعقيد استعلام الخصم.

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