تابع یک‌طرفه

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در علوم رایانه، تابع یک‌طرفه به تابعی گفته می‌شود که برای هر ورودی، خروجی تابع به راحتی قابل محاسبه است، امّا به‌دست آوردنِ پیش‌تصویرِ خروجیِ متناظر با یک ورودیِ تصادفی، دشوار می‌باشد. منظور از راحتی و دشواری محاسبه، آسانی یا سختی محاسبه از لحاظ پیچیدگی محاسبه است. محاسبه در زمانِ چندجمله‌ایِ قطعی را آسان و عدم توانایی محاسبه در زمان چندجمله‌ای قطعی را سخت می‌گوییم. توجّه داشته باشید که برای یک‌طرفه بودن تابع، نیازی به یک‌به‌یک بودن آن نیست.

وجود توابع یک‌طرفه در علوم رایانه، هنوز به عنوان یک مسئلۀ حل نشدۀ پژوهشی مطرح می‌باشد. در واقع وجود چنین توابعی نشانگر نابرابری کلاس‌های P و NP است که به تبع آن مهم‌ترین مسئلۀ حل‌نشدۀ علوم رایانۀ نظری ثابت می‌شود. عکس گزارۀ گفته شده درست نیست، بدین معنی که نابرابری کلاس‌های P و NP، وجود توابع یک‌طرفه را به طور مستقیم نتیجه نمی‌دهد.

در موارد کاربردی منظور از آسانی و سختی معمولاً به دستگاه محاسبۀ مورد نظر برمی‌گردد. توابع یک‌طرفه، ابزارهای بنیادی در رمزنگاری، احراز هویّت، اصالت‌سنجی و دیگر کاربردهای امنیّت داده می‌باشند. گرچه مسئلۀ وجود توابع یک‌طرفه هنوز مسئله‌ای باز است، امّا نامزدهای متعدّدی برای این توابع جهت استفاده در مخابرات و سامانه‌های تجارت الکترونیک در طول دهه‌های گذشته درنظر گرفته شده است.

تعریف نظری[ویرایش]

تابع یک‌طرفه است هرگاه f توسّط یک الگوریتم چندجمله‌ای قابل محاسبه باشد، برای هر الگوریتم تصادفی که در زمان چندجمله‌ای از طول ورودی اجرا می‌شود و برای هر چندجمله‌ای و برای مقادیر بزرگ داشته باشیم:

به‌طوری که انتخاب به‌طور یکنواخت روی است. توجّه داشته باشید که طبق تعریف، به‌دست آوردن پیش‌تصویر یک عنصر باید در حالت میانگین سخت باشد و لزومی ندارد که در بدترین حالت هم سخت باشد.

مفاهیم مرتبط[ویرایش]

جایگشت یک‌طرفه تابع یک‌طرفه‌ای است که خود تابع یک جایگشت است. به‌طور دقیق‌تر، تابع یک‌طرفه‌ای را که یک‌به‌یک و پوشا باشد، یک جایگشت یک‌طرفه می‌نامند. جایگشت‌های یک‌طرفه ابزارهای بنیادی مهمّی در رمزنگاری هستند. اینکه وجود جایگشت یک‌طرفه، وجود تابع یک‌طرفه را نتیجه می‌دهد، هنوز به عنوان مسئله‌ای حل نشده باقی‌مانده است. تابع چکیده‌ساز مقاوم در برابر برخورد تابع یک‌طرفه‌ای است که مقاوم در برابر برخورد نیز می‌باشد. بدین معنی که هیچ الگوریتم تصادفی در زمان چندجمله‌ای نمی‌تواند مقادیر متمایز و را با احتمال غیر ناچیز پیدا کند به‌طوری‌که باشد.

لگاریتم و توان گسسته[ویرایش]

تابع که عدد اوّل و عدد صحیح بین صفر و را می‌گیرد و باقی‌ماندۀ را بر برمی‌گرداند، توان گسسته نامیده می‌شود. توان گسسته در زمان قابل محاسبه است به‌طوری‌که تعداد بیت‌های می‌باشد. محاسبۀ معکوس این تابع نیازمند محاسبۀ لگاریتم گسستۀ به پیمانۀ است. به طور خلاصه مسئلۀ لگاریتم گسسته به این صورت است که به ازای عدد اوّل و عدد صحیح که ، هدف پیدا کردن عدد است به‌طوری که باشد. برای این مسئله، هیچ الگوریتمی وجود ندارد که در زمان چندجمله‌ای اجرا شود. سیستم رمز الگمال بر مبنای لگاریتم گسسته طرّاحی شده است.

توابع چکیده‌ساز امن[ویرایش]

تعدادی تابع چکیده‌ساز رمزنگاری مانند SHA-256 وجود دارند که در زمان کمی قابل محاسبه می‌باشند. تعدادی از نسخه‌های ساده از تحلیل‌های امنیّتی با موفقیّت عبور نکردند، امّا نسخه‌های قوی‌تر همچنان راه‌حل‌های عملی برای محاسبۀ یک‌طرفه می‌باشند.

خم‌های بیضوی[ویرایش]

خم‌های بیضوی مجموعه اعداد صحیحی هستند که در معادلۀ صدق می‌کنند. تعریف جمع برای نقاط دوبعدی رو خم‌ها و ضرب اسکالر برای آنها به صورت دنباله‌ای از عمل جمع، منجر به معادلۀ برای نقاط می‌شود که با داشتن و محاسبۀ آسان است، امّا در صورتی که و معلوم باشند محاسبۀ از لحاظ محاسباتی دشوار است.

نامزدهای دیگر[ویرایش]

نامزدهای دیگری برای توابع یک‌طرفه وجود دارند که مبتنی بر سختی کدگشایی کدهای خطّی تصادفی، مسئلۀ مجموع زیرمجموعه‌ها و مسائل دیگری می‌باشند.

تابع یک‌طرفۀ جهانی[ویرایش]

تابع صریح وجود دارد که اگر تابع یک‌طرفه وجود داشته باشد، نیز یک‌طرفه خواهد بود. به عبارت دیگر، در صورتی که هر تابع یک‌طرفه باشد، نیز یک‌طرفه خواهد بود. چون این تابع، اوّلین تابعِ ترکیبیاتیِ یک‌طرفه‌یِ کاملی است که ارائه شده است، به عنوان تابع یک‌طرفۀ جهانی شناخته می‌شود. در نتیجه، مسئلۀ پیدا کردن تابع یک‌طرفه، به مسئلۀ اثبات یک‌طرفه بودن تابع تحویل می‌شود.

منابع[ویرایش]