دالة وحيدة الاتجاه

في علم التعمية الحديثة، الدالة وحيدة الاتجاه (بالإنجليزية: one way function) هي دالة رياضية من السهل حساب قيمتها لأي مدخل في وقت متعدد الحدود (Polynomial Time)، لكن من الصعب جدًا (عمليًا) معرفة المدخل إذا عُرف الناتج فقط. يعتمد الأمان في كثير من خوارزميات التعمية على وجود مثل هذه الدوال. وجود هذه المسائل وحيدة الاتجاه يرتبط بمسألة شهيرة في علم الحاسوب، وهي: هل جميع المسائل التي يمكن التحقق من حلها بسرعة يمكن أيضًا حلها بسرعة؟ إذا كانت الإجابة نعم (أي إذا كان NP = P)، فلن توجد دوال وحيدة الاتجاه. أما إذا ثبت وجود دالة وحيدة الاتجاه، فهذا يعني بالضرورة أن NP لا تساوي P.^[1]^[2]^[3]

مقدمة

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

عالم الخوارزميات (Algorithmica): حيث NP = P، وتصبح جميع المسائل التي يمكن التحقق منها قابلة للحل بسهولة.
عالم الحدس (Heuristica): مسائل NP الكاملة صعبة فقط في أسوأ الحالات، بينما يسهل حل معظم الحالات العملية.
بيسيلاند (Pessiland): توجد مسائل NP الكاملة الصعبة حتى في الحالة المتوسطة، لكن لا وجود لدوال وحيدة الاتجاه.
مينيكربت (Minicrypt): توجد دوال وحيدة الاتجاه، لكن أنظمة التشفير بالمفتاح العام غير ممكنة.
كريبتومانيا (Cryptomania): توجد دوال وحيدة الاتجاه وأنظمة تشفير بمفتاح عام، مما يتيح الاتصال الآمن.

تشير معظم الأدلة النظرية الحالية إلى أن العالم الخامس (Cryptomania) هو الأقرب للواقع، إلا أن إثبات وجود الدوال وحيدة الاتجاه أو عدمه ما يزال من أعقد مسائل علم الحاسوب، ولا توجد أدلة قاطعة ترجح أيًا من هذه العوالم بشكل نهائي.^[4]

التعريف

الدالة $f:\{0,1\}^{*}\to \{0,1\}^{*}$ تُسمى دالة وحيدة الاتجاه إذا كان من الممكن حساب $f$ بواسطة خوارزمية زمنها كثير الحدود، ولكن أي خوارزمية عشوائية بزمن كثير الحدود تحاول حساب شبه معكوس لـ $f$ تحقق نجاحًا باحتمال ضئيل. (الرمز $*$ هنا يعني أي عدد من التكرارات، انظر نجمة كلين).

أي أنه، لكل خوارزمية عشوائية $F$ ، ولكل عدد صحيح موجب $c$ ولكل $n$ كبير بما فيه الكفاية حيث $n=\mathrm {length} (x)$ ،

$\Pr \left[f(F(f(x)))=f(x)\right]<n^{-c}$

حيث أن الاحتمال يؤخذ على اختيار $x$ من التوزيع المنتظم على $\{0,1\}^{n}$ وعلى عشوائية $F$ .^[5]

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

ليس من الكافي أن تكون الدالة "فاقدة للمعلومات" (أي ليست واحد لواحد) حتى تُعتبر دالة وحيدة الاتجاه. على سبيل المثال، الدالة التي تعطي سلسلة من الأصفار بطول $n$ لأي مُدخل بطول $n$ ليست دالة وحيدة الاتجاه، لأن من السهل إيجاد مُدخل يعيد نفس المخرج. بشكل أدق: لمثل هذه الدالة التي تخرج فقط سلسلة من الأصفار، يمكن لخوارزمية $F$ أن تعيد أي سلسلة بطول $n$ عند إدخال $f(x)$ ، وسوف تجد بالفعل سابقة صحيحة لهذا الناتج، حتى وإن لم يكن هو نفسه المدخل الأصلي الذي أنتج سلسلة الأصفار.^[5]

دوال مرشحة لتكون وحيدة الاتجاه

فيما يلي قائمة بدوال لا يُعرف اهي وحيدة الاتجاه، وبشكل عام فانه قد حصلت بحوث كثيرة ولا يوجد تقدم نحو حل لاي منها:

الضرب والتفكيك

الدالة f تحصل على عددين أوليين p,q بالعد الثنائي والمُخرج حاصل الضرب أي: $f(p,q)=p\cdot q$ بينما يمكن ان نحسب هذه الدالة بوقت $O(n^{2})$ في حين أن n هو طول المُدخلات، الدالة العكسية والتي هي ايجاد عوامل عدد N هي مسألة لم تُحل بعد حيث أن أفضل الخوارزميات لحلها عدد الخطوات فيها: $O(2^{(\log {N})^{\frac {1}{3}}(\log {\log {N}})^{\frac {2}{3}}})$ , وهو شبه حدودي متعلق ب- $\log {N}$

دالة رابين

دالة رابين ببساطة هي دالة التربيع النمطية، أي كالتالي: $f(x)=x^{2}\ {\bmod {\ }}N$ حيث أنَّ $N=pq$ وكلا من p و- q عددين اوليين. يمكن البرهنة بأن ايجاد الجذر التربيعي النمطي مكافئ لتفكيك العدد N الذي كما اسلفنا مسألة تفكيك الاعداد هي مسألة صعبة.^{[بحاجة لمصدر]}

مراجع

↑ Leonid Levin (2003). "The Tale of One-Way Functions". ACM. arXiv:cs.CR/0012023. {{استشهاد بدورية محكمة}}: الاستشهاد بدورية محكمة يطلب |دورية محكمة= (مساعدة)
↑ draft available from author's site). Cambridge University Press. (ردمك 0-521-79172-3). (see also wisdom.weizmann.ac.il) نسخة محفوظة 09 أغسطس 2016 على موقع واي باك مشين.
↑ Russell، A. (1995). "Necessary and Sufficient Conditions for Collision-Free Hashing". Journal of Cryptology. ج. 8 ع. 2: 87–99. DOI:10.1007/BF00190757.
↑ Impagliazzo، R. (1995). "A personal view of average-case complexity". IEEE Comput. Soc. Press: 134–147. DOI:10.1109/SCT.1995.514853. ISBN:978-0-8186-7052-7. مؤرشف من الأصل في 2025-06-17. {{استشهاد بدورية محكمة}}: الاستشهاد بدورية محكمة يطلب |دورية محكمة= (مساعدة)
1 2 Goldreich، Oded (2001). Foundations of Cryptography. Cambridge: Cambridge University Press. ج. vol. 1, ch. 2.1–2.3. ISBN:978-0-511-04687-2. {{استشهاد بكتاب}}: |المجلد= يحوي نصًّا زائدًا (مساعدة)

[1] Leonid Levin (2003). "The Tale of One-Way Functions". ACM. arXiv:cs.CR/0012023. {{استشهاد بدورية محكمة}}: الاستشهاد بدورية محكمة يطلب |دورية محكمة= (مساعدة)

[2] raft available from author's site). Cambridge University Press. (ردمك 0-521-79172-3). (see also wisdom.weizmann.ac.il) نسخة محفوظة 09 أغسطس 2016 على موقع واي باك مشين.

[3] Russell، A. (1995). "Necessary and Sufficient Conditions for Collision-Free Hashing". Journal of Cryptology. ج. 8 ع. 2: 87–99. DOI:10.1007/BF00190757.

[4] Impagliazzo، R. (1995). "A personal view of average-case complexity". IEEE Comput. Soc. Press: 134–147. DOI:10.1109/SCT.1995.514853. ISBN:978-0-8186-7052-7. مؤرشف من الأصل في 2025-06-17. {{استشهاد بدورية محكمة}}: الاستشهاد بدورية محكمة يطلب |دورية محكمة= (مساعدة)

[:0-5] 1 2 Goldreich، Oded (2001). Foundations of Cryptography. Cambridge: Cambridge University Press. ج. vol. 1, ch. 2.1–2.3. ISBN:978-0-511-04687-2. {{استشهاد بكتاب}}: |المجلد= يحوي نصًّا زائدًا (مساعدة)

[1]

[2]

[3]

[4]

[5]