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

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

نقاش ودلائل على وجود دوال ذات اتجاه واحد

وجود دالة ذات اتجاه واحد قد لا يكون مفاجئة فان بعض الخصائص الطبيعية للوقت هو اننا لا نستطيع العودة بالوقت الى الوراء وبهذا فان الوقت هو مصطلح يقوي وجود هذه العناصر في الرياضيات . مثال اخر هي عملية الضرب , في حين انه يسهل ضرب عددين ولكن من الصعب معرفة العوامل اذا معطى الحاصل, هذه الامثلة لا تقطع بوجود هذا المصطلح انما جل ما نعرفه انها قد تكون موجودة وقد لا تكون فلنفرض اننا اخترعنا الة زمنية تعبر في الزمن الى الوراء فان هذا لا يعني نهاية وجود دوال ذات اتجاه واحد ولكن هذه "الدالة" ليست كذلك , وهذا الامر ينطبق ايضا على دالة الضرب , وما يفاجئ اكثر انه في حال نجح شخص ما ببرهنة $NP \neq P$ فهذا ايضا لا يعني وجود هذه الدوال , في كل الاحوال هي دوال ذات رونق خاص تمكننا من فعل امور لطالما حلم الانسان بفعلها مثل اللعب بدون الغش واثبات الهوية وكثير من الامور من هذا الضرب ...

التعريف

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

1. f نستطيع ان نحسبها بواسطة آلة تورنج حتمية بوقت حدودي (polynomial deterministic Turing machine)
2. لكل خوارزمية عشوائية متعددة الحدود A يوجد دالة متعددة الحدود (.)p :

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

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

المزيد

• Oded Goldreich (2001). Foundations of Cryptography: Volume 1, Basic Tools. Cambridge University Press. فصول من الكتاب في موقع الكاتب
• Jonathan Katz and Yehuda Lindell (2007). Introduction to Modern Cryptography.