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

في علم التعمية الحديثة(modern cryptography) دالة وحيدة الاتجاه(one way function) هي دالة التي يمكن حسابها بوقت حدودي أو يمكن حسابها بسرعة عالية اما ان نعكسها فهي عملية صعبة اي بوقت معقول لا يمكن عكسها ووجود هذه الدوال مرتبط بالمسألة الشهيرة NP=P حيث انه إذا NP=P حينها لا يوجد اي دالة ذات اتجاه واحد وإذا ما برهن انه يوجد دالة كهذه فهذا يعني : NP≠P .[1][2][3]

مقدمة

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

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

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

التعريف

دالة *{0,1}→*{0, 1}:f هي دالة قوية ذات اتجاه واحد إذا:

f نستطيع ان نحسبها بواسطة آلة تورنغ حتمية بوقت حدودي (polynomial deterministic Turing machine)
لكل خوارزمية عشوائية متعددة الحدود A يوجد دالة ضئيلة $\varepsilon (n)$ بحيث :

Pr[A(f(x))\in \ f^{-1}(f(x))]<\varepsilon (n)

حيث أن فضاء الاحتمالات على $x\in _{R}\{0,1\}^{n}$ وكذلك على عشوائية الخوارزمية A .

دوال وحيدة الاتجاه ضعيفة هي دوال التي تحقق الشروط السابقة ولكن $\varepsilon (n)$ هي دالة ليست ضئيلة .

التعريف لا يحتم على الدالة ان تكون غير قابلة للقلب انما فقط جزء بسيط جدا منها يمكن قلبه بسهولة ! ولهذا دلالات كبيرة، إذ انه لا حاجة لان نفترض ان المهاجم هو ذو قوة حسابية غير محدودة انما فقط ذو قوة حسابية "معقولة" اي ان المهاجم لديه قدرة حسابية حدودية تمكنه من بلوغ جزء قليل من مقلوب الدالة ما لا يتيح له المقدرة على حساب مقلوب مُدخل معطى معين هو يريد ايجاده . فرضية ان المهاجم هو ذو قوة حسابية غير محدودة ينبع منها ان الدوال غير حصينة وبالتالي لا يمكن ان تكون ذي منفعة عملية، وبما ان هذه الفرضية غير صحيحة البتة لذا فالدالة تُعتبر حصينة .

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

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

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

الدالة 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. الوسيط |CitationClass= تم تجاهله (مساعدة); Cite journal requires |journal= (مساعدة)
draft availablefrom 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. الوسيط |CitationClass= تم تجاهله (مساعدة)

بوابة تعمية
بوابة رياضيات
بوابة علم الحاسوب

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Leonid Levin (2003). "The Tale of One-Way Functions". ACM. arXiv:cs.CR/0012023. الوسيط |CitationClass= تم تجاهله (مساعدة); Cite journal requires |journal= (مساعدة)

[2] raft availablefrom 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. الوسيط |CitationClass= تم تجاهله (مساعدة)