💻 computer science

Weak Zero-Knowledge and One-Way Functions

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

المؤلفون الأصليون: Rohit Chatterjee, Yunqi Li, Prashant Nalini Vasudevan

نُشر 2026-02-19

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

CC BY 4.0

المؤلفون الأصليون: Rohit Chatterjee, Yunqi Li, Prashant Nalini Vasudevan

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

إليك شرح لورقة "الصفرية المعرفة الضعيفة والدوال أحادية الاتجاه" باستخدام لغة بسيطة وتشبيهات إبداعية.

الصورة الكبيرة: "خدعة السحر" و"القفل غير القابل للكسر"

تخيل التشفير كأنه لعبة ضخمة من خدع السحر والأقفال غير القابلة للكسر.

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

السؤال الكبير: هل وجود هذه "الخدع السحرية" (المعرفة الصفرية) يثبت أن "الأقفال غير القابلة للكسر" (الدوال أحادية الاتجاه) يجب أن تكون موجودة؟

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

هذه الورقة تسأل: ماذا لو كانت الخدع السحرية "ضعيفة"؟ ماذا لو كانت تحتوي على أخطاء ملحوظة؟ هل لا نزال نحصل على أقفال غير قابلة للكسر؟

اكتشاف الورقة: حتى الخدع السحرية "السيئة" تبني أقفالاً قوية

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

إليك كيف فصّلوا ذلك:

1. قاعدة "مجموع الأخطاء"

تخيل أن الأخطاء في خدعة سحرية تشبه الثقوب في دلو.

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

تثبت الورقة أنه طالما أن إجمالي حجم كل هذه الثقوب مجتمعة أقل من حجم الدلو، فلا يزال بإمكانك بناء قفل غير قابل للكسر.

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

2. "المحقق المتكرر" (كيف فعلوا ذلك)

لإثبات ذلك، استخدم المؤلفون استراتيجية ذكية تتضمن "محققاً" و"محاكياً".

المحاكي (The Simulator): في المعرفة الصفرية، يوجد برنامج كمبيوتر يمكنه تزييف الخدعة السحرية دون معرفة السر. إنه مثل المزور الذي يمكنه صنع لوحة مزيفة تبدو تماماً مثل الأصلية.
المعكس (The Inverter): هذا هو المخترق الذي يحاول كسر "القفل غير القابل للكسر".
الخدعة: خلق المؤلفون سيناريو حيث إذا استطاع المخترق كسر القفل بسهولة، فبإمكانه استخدام هذه القدرة لحل الخدعة السحرية.
- إذا استطاع المخترق كسر القفل، يمكنه العمل كـ "محقق خارق" يستطيع التمييز بين خدعة سحرية حقيقية وواحدة مزيفة.
- لكن إذا كانت الخدعة السحرية لمسألة "صعبة" (مسألة يُفترض أنها مستحيلة الحل)، فلا ينبغي أن يوجد محقق خارق.
- التناقض: بما أن المحقق الخارق لا يمكن أن يوجد (لأن المسألة صعبة)، فإن المخترق لا يمكنه كسر القفل. وبالتالي، القفل غير قابل للكسر!

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

3. تشبيه "الرحلة الذهاب والإياب"

تنظر الورقة أيضاً إلى الخدع السحرية التي تستغرق عدة خطوات (جولات).

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

وجد المؤلفون أنه بالنسبة لهذه الخدع متعددة الخطوات، تتغير قاعدة "حجم الثقب" قليلاً بناءً على عدد الخطوات.

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

لماذا يهم هذا؟

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

الخلاية

فكر في هذه الورقة كأنها مفتش سلامة لعالم التشفير.

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

إنها تطمئننا بأن بروتوكولاتنا التشفيرية "المعيبة" و"الضعيفة" قادرة على حماية عالمنا الرقمي.

إليك ملخص تقني مفصل للورقة البحثية بعنوان "Weak Zero-Knowledge and One-Way Functions" (المعرفة الصفرية الضعيفة والدوال أحادية الاتجاه) من إعداد روهيت تشاترجي، يونقي لي، وبرشانت ناليني فاسوديفان.

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

تبحث الورقة في التداعيات التشفيرية لبروتوكولات المعرفة الصفرية الضعيفة (Weak ZK). تتطلب بروتوكولات المعرفة الصفرية القياسية عادةً أن تكون أخطاء الإكمال ( $\epsilon_c$ )، والمتانة ( $\epsilon_s$ )، والمعرفة الصفرية ( $\epsilon_z$ ) دوالاً مهملة (negligible) بالنسبة لمعلم الأمن. ومع ذلك، فإن العديد من بروتوكولات المعرفة الصفرية الطبيعية والمفيدة (مثل التلوين الثلاثي لـ 3-Coloring أو عدم تماثل الرسم البياني Graph Non-Isomorphism) تمتلك بطبيعتها معدلات خطأ غير مهملة (ثابتة أو ملحوظة).

السؤال المركزي هو: هل وجود مثل هذه البروتوكولات "الضعيفة" للمعرفة الصفرية للغات الصعبة في الحالة الأسوأ (worst-case) في فئة NP يستلزم وجود دوال أحادية الاتجاه (One-Way Functions - OWFs)؟

أرست الأعمال السابقة (مثل Chakraborty et al., CRYPTO 2025) هذا الاستلزام فقط تحت شروط مقيدة، وتحديداً اشتراط $\epsilon_c + \sqrt{\epsilon_s} + \epsilon_z < 1$ . يهدف المؤلفون إلى تحديد العتبة الدقيقة لمعدلات الخطأ التي لا تزال تضمن وجود الدوال أحادية الاتجاه، لتغطية أكثر إعدادات المعلمات عمومية وغير بديهية.

2. المنهجية

يستخدم المؤلفون نهجاً اختزالياً (reductionist approach)، حيث يقومون ببناء دوال أحادية الاتجاه بمدخلات مساعدة (ai-OWFs) من وجود بروتوكولات المعرفة الصفرية الضعيفة. إذا وجدت هذه الدوال (ai-OWFs)، يمكن اشتقاق الدوال أحادية الاتجاه القياسية (standard OWFs) تحت افتراض أن NP صعبة في الحالة الأسوأ (تحديداً $NP \not\subseteq ioP/poly$ ).

تتضمن المنهجية الجوهرية ما يلي:

تعريف الدوال المرشحة الصعبة: بناء دالة $f_x$ بناءً على محاكي المعرفة الصفرية (simulator). مدخل الدالة $f_x$ هو عشوائية المحاكي $\rho$ ، ومخرجها هو المسار (transcript) أو جزء من المسار الذي ولّده المحاكي.
اختزال "المعكوس إلى المميّز" (Inverter-to-Distinguisher Reduction): بافتراض وجود معكوس فعال $A$ $A$ للدالة $f_x$ $f_{x}$ ، يبني المؤلفون مميزاً (أو استراتيجية مُثبِت $\tilde{P}$ $\tilde{P}$ ) يمكنه تقرير عضوية اللغة $L$ $L$ .
- إذا كان $x \in L$ ، فإن المعكوس يسمح ببناء مُثبِت يقنع المتحقق (verifier) باحتمالية عالية (قريبة من 1).
- إذا كان $x \notin L$ ، تضمن المتانة (soundness) أن المتحقق يقبل باحتمالية منخفضة ( $\le \epsilon_s$ ).
تحليل الخطأ: التحدي التقني الرئيسي هو تحليل الخطأ المتراكم. يقوم المؤلفون بتنقيح بناء الدالة المرشحة واستراتيجية المعكوس لتقليل العقوبة الناتجة عن خطأ المعرفة الصفرية $\epsilon_z$ $ϵ_{z}$ .
- حالة المعرفة الصفرية غير التفاعلية (NIZK): يقومون بتعديل مخرج الدالة ليشمل بت التحقق $a = V(x, r, \pi)$ . يسمح هذا للمعكوس بالانحصار في إيجاد سوابق الصور (pre-images) التي تتوافق مع البراهن الصحيحة، مما يتجنب عقوبة مزدوجة لـ $\epsilon_z$ .
- حالة العملات العامة التفاعلية (Public-Coin Interactive Case): يستخدمون بناءً تكرارياً (recursive construction). بالنسبة لبروتوكول مكون من $k$ جولة، يعرّفون سلسلة من الدوال $f_{k}, f_{k-1}, \dots, f_1$ . يُستخدم المعكوس للدالة $f_i$ لبناء استراتيجية مُثبِت للجولة $i$ تزيد من احتمالية نجاح الجولات اللاحقة. يسمح هذا النهج التكراري بضبط أوجه قياس الخطأ بشكل أدق.

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

تقدم الورقة ثلاث نظريات رئيسية تحسن بشكل كبير من الحدود السابقة:

أ. المعرفة الصفرية غير التفاعلية (NIZK)

النتيجة: إذا كانت جميع لغات NP تمتلك براهن/حجج NIZK بأخطاء تحقق $\epsilon_c + \epsilon_s + \epsilon_z < 1$ ، فإن الدوال أحادية الاتجاه موجودة (بافتراض $NP \not\subseteq ioP/poly$ ).
التحسين: هذا يغطي جميع القيم غير البديهية الممكنة للأخطاء. العمل السابق تطلب $\epsilon_c + \sqrt{\epsilon_s} + \epsilon_z < 1$ .
الدلالة: إذا وجدت NIZKs بخطأ $\epsilon_c$ مهمل، فيمكن تضخيمها لتصبح ذات أخطاء مهملة لجميع المعلمات إذا كان مجموع الأخطاء أقل من 1.

ب. المعرفة الصفرية متعددة الجولات بالعملات العامة (عام)

النتيجة: إذا كانت جميع لغات NP تمتلك براهن/حجج ZK بالعملات العامة مكونة من $t$ رسائل تحقق $\epsilon_c + \epsilon_s + (t-1)\cdot\epsilon_z < 1$ ، فإن الدوال أحادية الاتجاه موجودة.
التحسين: تم تقليل معامل $\epsilon_z$ من $t$ (الحد البديهي) إلى $t-1$ .

ج. المعرفة الصفرية بالعملات العامة ذات الجولات الثابتة

النتيجة: إذا كانت جميع لغات NP تمتلك براهن/حجج ZK بالعملات العامة مكونة من $k$ جولة (حيث $k$ ثابت) تحقق $\epsilon_c + \epsilon_s + k \cdot \epsilon_z < 1$ ، فإن الدوال أحادية الاتجاه التي تعمل في حالات لانهائية (ioOWFs) موجودة.
التحسين: يحقق هذا المعامل الخطي الأمثل $k$ لـ $\epsilon_z$ .
القصور: النتيجة تؤدي إلى ioOWFs بدلاً من OWFs القياسية لأن البناء التكراري يتطلب نجاح جميع المعكوسات في السلسلة في آن واحد على نفس أطوال المدخلات.

4. التفاصيل التقنية للتحسينات

تحسين NIZK: يلاحظ المؤلفون أن بناء Ostrovsky-Wigderson (OW93) يتسبب في عقوبة قدرها $2\epsilon_z$ . من خلال تعريف الدالة المرشحة كـ $f_x(\rho) = (r, V(x, r, \pi))$ بدلاً من مجرد $r$ ، يتم إجبار المعكوس على إيجاد عشوائية $\rho$ تنتج برهاناً صحيحاً. هذا يعالج التحقق ضمنياً، مما يقلل عقوبة المعرفة الصدرية إلى $\epsilon_z$ واحدة، وبالتالي تحقيق الحد $\epsilon_s + \epsilon_z < 1$ .
الاستراتيجية التكرارية للبروتوكولات التفاعلية: بالنسبة لبروتوكولات $k$ -round، يعرّف المؤلفون دالة $f_{i,x}$ تخرج المسار حتى الجولة $i$ وتقديراً لاحتمالية نجاح الجولات المتبقية. يُستخدم المعكوس للدالة $f_{i,x}$ لاختيار رسالة المُثبِت في الجولة $i$ التي تعظم احتمالية النجاح المقدرة للجولات اللاحقة. هذا التحسين "الجشع" (greedy) في كل خطوة يسمح بحصر إجمالي الخطأ في $k \cdot \epsilon_z$ بدلاً من $(2k-1)\epsilon_z$ أو أكثر.

5. ملخص النتائج

نوع البروتوكول	شرط الخطأ لوجود OWF	البدائية الناتجة	الافتراض
NIZK	$\epsilon_c + \epsilon_s + \epsilon_z < 1$	Standard OWF	$NP \not\subseteq ioP/poly$
العملات العامة ( $t$ رسائل)	$\epsilon_c + \epsilon_s + (t-1)\epsilon_z < 1$	Standard OWF	$NP \not\subseteq ioP/poly$
العملات العامة ( $k$ جولات)	$\epsilon_c + \epsilon_s + k \cdot \epsilon_z < 1$	Infinitely-Often OWF	$NP \not\subseteq P/poly$

ملاحظة: الشرط $\epsilon_c + \epsilon_s + \epsilon_z \ge 1$ يعتبر تافهاً/بلا معنى لـ NIZK لأنه يعني أن البروتوكول لا يوفر أي أمن.

6. الأهمية

اكتمال التوصيف: تكمل هذه الورقة عملياً توصيف الـ NIZK الضعيفة. فهي تظهر أن أي معرفة صفرية غير تفاعلية ضعيفة (حيث يكون مجموع الأخطاء أقل من 1) هي كافية لاستلزام وجود الدوال أحادية الاتجاه، بشرط أن تكون NP صعبة في الحالة الأسوأ. هذا يغلق الفجوة التي تركتها الأعمال السابقة التي تطلبت حدوداً مثل الجذر التربيعي أو غيرها من الشروط المقيدة.
دقة الحدود: توفر النتائج لبروتوكولات العملات العامة حدوداً أكثر دقة بكثير لتراكم خطأ المعرفة الصفرية. تقليل المعامل من $(2k-1)\epsilon_z$ إلى $k\epsilon_z$ للبروتوكولات ذات الجولات الثابتة يعد تحسيناً نظرياً جوهرياً.
أسس التشفير: يعزز هذا العمل الارتباط العميق بين صعوبة المسائل في الحالة الأسوأ (NP) ووجود البدائيات التشفيرية الأساسية (OWFs). فهو يثبت أن حتى بروتوكولات المعرفة الصفرية "غير المثالية"، الشائعة في الممارسة العملية، قوية بما يكفي لرفع مستوى التشفير القياسي.
الاتجاهات المستقبلية: تحدد الورقة مسائل مفتوحة، مثل توسيع هذه النتائج لتشمل بروتوكولات العملات الخاصة (private-coin) وتحسين نتيجة الجولات الثابتة لإنتاج OWFs قياسية (وليس فقط infinitely-often OWFs).

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