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

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

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

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

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

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

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

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

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

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

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

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