Computational hardness assumption

خب لینک اول Computational hardness assumption داره چی میگه.
میگه در علم رمزنگاری مدرن دنبال این هستن که الگوریتم هایی ایجاد کنن که بشه امنیت اونا رو به روشی بقدر کافی قابل اطمینان ثابت کرد (طبیعتا با متدهای منطقی/ریاضی). چون میدونیم که در دنیای علم و منطق، تکیه بر حدس و تصور و احساسات اعتباری نداره و باید تاجاییکه شدنی هست به اثبات و روشنی و اطمینان رسید، که بالاترین حد این اثبات معمولا اثبات با ریاضیات است. اما حتی در این شکل هم سطوح اثبات با هم فرق میکنن. بعضی اثبات ها کامل و مطلق هستن، ولی خیلی دیگر اثبات های کامل و مطلق ندارن و مثلا بر یکسری فرض هایی بنا شدن که عموما تصور میشه و احتمال زیادی داده میشه که درست هستن و تجربه و شواهد بر این امر صحه میگذارند اما بهرحال اثبات منطقی/ریاضی براشون وجود نداره.

در بعضی موارد، الگوریتم ها دارای امنیت اثبات شدنی از نوع نظریهء اطلاعات هستن که قوی ترین نوع امنیته که مشروط و موکول روی فرضهای ثابت نشده و یا محدودیت های دنیای واقعی نیست؛ بطور مثال الگوریتم one-time pad. ولی در خیلی موارد هم طراحی چنین الگوریتم هایی و اثبات امنیت اونا در عمل ممکن نیست؛ در این موارد متخصصان به امنیت از نوع توان پردازشی عقب نشینی میکنن که سطح محدودتر و پایین تری از اثبات و امنیت رو داراست. در این سطح، امنیت بر اساس محدودیت توان پردازشی در دسترس بشر فرض میشه. یعنی میگن این الگوریتم ها با در نظر گرفتن اینکه در واقعیت توان پردازشی در دسترس انسان محدودیت های خاص فعلی و آیندهء نزدیک یا دور رو داره، امن هستن و کسی عملا قادر به شکست اونا نیست چون مثلا نیاز به زمان و/یا انرژی بسیار بسیار زیادی هست که در نتیجه انجامش عملا غیرممکنه یا اهمیتی نداره. طبیعتا برای تعریف و اثبات این نوع از امنیت، بر میزان سختی انجام یک عملیات خاص، تکیه میشه (اینکه چقدر نیاز به منابع پردازشی/زمان/انرژی داشته باشه). اما چون خود اثبات «حداقل میزان سختی انجام یک عملیات خاص» کار دشواریه و در خیلی موارد کسی نتونسته تاحالا این کار رو بکنه، بنابراین خیلی از این عملیات تنها فرض میشن که فلان قدر یا بقدر کافی سخت هستن، چون تاحالا کسی نتونسته راه ساده تری برای انجام اونا پیدا کنه. و به این هست که میگن Computational hardness assumption، یعنی «فرض دشواری پردازشی». نکته: بنده اهل برگردان های فارسی نیستم و اونا رو در خیلی موارد چندان مناسب و مفید نمی بینم و ترجیح میدم از همون عبارت های انگلیسی خودشون استفاده کنم، و اینطور ترجمه ها رو صرفا برای درک مطلب میذارم که شاید ترجمه های چندان دقیق و درستی هم نباشن.
بطور مثال میدونیم که اگر کسی بتونه الگوریتمی از نوع Polynomial time برای فاکتورگیری از اعداد صحیح بزرگ پیدا کنه، الگوریتم رمزنگاری RSA قطعا بطور کامل شکسته میشه، ولی خب کسی تاحالا نتونسته چنین روش کارایی برای فاکتورگیری اعداد صحیح بزرگ پیدا کنه، با وجود اینکه خیلی افراد خیلی ریاضیدان ها در تاریخ برای این کار تلاش کردن؛ و بنابراین فرض رو بر این میذاریم که فاکتورگیری از اعداد صحیح بزرگ ماهیتا عملیات ناکارایی هست (به نسبت بزرگی عدد بصورت تصاعدی به پردازش نیاز داره). کسی نمیدونه آیا واقعا هیچ روش کارایی برای فاکتورگیری اعداد وجود داره یا نه که بشریت روزی بتونه بهش دست پیدا کنه، ممکنه وجود داشته باشه و ممکنه وجود نداشته باشه، کسی نتونسته چیزی رو در این مورد ثابت کنه، ولی هرکس تلاش کرده چنین روشی/الگوریتمی پیدا کنه موفق نشده، و بنابراین میشه گفت چنین الگوریتمی احتمالش زیاده اصولا از نظر ریاضی ممکن نیست یا حداقل دست یافتن بهش خیلی دشواره و چندان محتمل نیست به زودی محقق بشه (البته بحث رایانه های کوانتمی و الگوریتم Shor که برای فاکتورگیری اعداد بزرگ قابل استفاده است جداست و ما فعلا کاری با اون نداریم چون فیلد جداگانه ایه و هنوز هم رایانه های کوانتمی در مقیاس بزرگ تحقق پیدا نکردن و بنظر نمیرسه چندان هم به این امر نزدیک باشیم یا اصلا هیچوقت بالاخره شدنی بشه).

بسیاری فرضهای دشواری پردازشی وجود دارند. گرچه هیچکدام از این فرضها ثابت نشده اند، اما بعضی از آنها از بعضی دیگر قوی تر هستند (قابل اطمینان تر بنظر می آیند – شواهد بیشتر و محکمتری تجربهء بیشتری آنها را پشتیبانی میکند). طبیعی است که متخصصان ترجیح میدهند و تلاش میکنند الگوریتم هایی که طراحی میکنند بر اساس تعداد کمتری از فرضهای ثابت نشده استوار باشند و فرضهای استفاده شده هم از نوع هرچه قوی تر باشند.

1 دیدگاه در “Computational hardness assumption

  1. به نام خداوند مهرگستر خیلی مهربان
    “الذين آمنوا يقاتلون في سبيل الله و الذين كفروا يقاتلون في سبيل الطاغوت فقاتلوا أولياء الشيطان إن كيد الشيطان كان ضعيفا ”
    “آنانکه باورکردند کُشندگانند در راهیِ خداوند هم آنانکه روگردانیدند کُشندگانند در راه سرکشان باز کشندگانید دوستانِ سرکش گسترُ اگر فریبیست سرکش گسترُ بود خیلی سستی”
    من دانشی فراوانُ آنجا دوست دارم که بهره به آیین خداوند برساند نه بهره به دشمنان خداوند همانند توانایی جنگی آتش اندازانِ اتمی که دستِ ناباوران به خداوند باشد را دوست ندارم،دانش کلید گذاری رمزی اگر به سود باورمندان باشد خیلی خوب است نه تنها در نرم افزار در درون مردم یک کشور همانند این که توی مردم باورمند کشوری رخدادی پیش بیاید هم افشای آن به سود دشمنان می شود مردم خودباز هم کم باور به خداوند همیشه دودل بازیگر آن را در شبکه های بیگانه پخش می کنند،پناه بر خداوند از دودلان

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

*

شما می‌توانید از این دستورات HTML استفاده کنید: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>