فرض صعوبة الحساب

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

فروض شائعة لصلابة التشفير

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

وهذه قائمة ببعض الفروض الأكثر شيوعا لصلابة التشفير، وبعض بروتوكولات التشفير التي تستخدمها.

  • تحليل عدد صحيح
    • طريقة تشفير رابين
    • Blum Blum Shub generator
    • تشفير Okamoto-Uchiyama
  • خوارزمية آر إس إيه (أقوى من تحليل العوامل)
    • تشفير خوارزمية آر إس إيه
  • مشكلة البقية التربيعية (أقوى من تحليل العوامل)
    • تشفير Goldwasser- Micali
  • فرض البقية المركبة التقريرية (أقوى من تحليل العوامل)
    • تشفير Paillier
  • مشكلة البقية العليا (أقوى من تحليل العوامل)
    • تشفير Benaloh
    • تشفير Naccache- Stern
  • فرض Phi-hiding (أقوى من تحليل العوامل)
    • بروتوكول استرداد المعلومات الخاصة لكل من Cachin–Micali–Stadler
  • مشكلة اللوغاريتم المتميز (DLP)
  • فرض ديفي-هيلمان الحسابي (CDH، أقوى من DPL)
  • فرض ديفي-هيلمان الحاسم (DDH، أقوى من CDH)
    • تشفير الجمال

فروض الصلابة في غير التشفير

وتمام مثل تطبيقاتها في التشفير، فيتم استخدام فروض الصلابة في نظرية التعقيد الحسابي من أجل توفير الدليل بالنسبة للبيانات الرياضية الصعبة الإثبات بدون شرط أو قيد. وفي هذه التطبيقات، يثبت الشخص أن فرض الصلابة ينطوي على بيان نظري تعقيدي مرغوب، بدلا من إثبات أن البيان نفسه صحيحا. والفرض الأشهر في هذا النوع هو فرض مسألة P ≠ NP,[1]، لكن الأنواع الأخرى تشمل فرضية الوقت الأسي [2] وفرضية الألعاب الفريدة.[3]

مراجع
  1. Fortnow، Lance (2009)، "The status of the P versus NP problem" (PDF)، Communications of the ACM، ج. 52، ص. 78–86، DOI:10.1145/1562164.1562186.
  2. Woeginger، Gerhard (2003)، "Exact algorithms for NP-hard problems: A survey"، Combinatorial Optimization — Eureka, You Shrink!، Springer-Verlag، ص. 185–207، DOI:10.1007/3-540-36478-1_17.
  3. Khot، Subhash (2010)، "On the Unique Games Conjecture"، Proc. 25th IEEE Conference on Computational Complexity (PDF)، ص. 99–121، DOI:10.1109/CCC.2010.19، مؤرشف من الأصل (PDF) في 2016-09-13.
  • أيقونة بوابةبوابة تعمية
  • أيقونة بوابةبوابة علم الحاسوب
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.